线性互补问题的一种混合整数线性规划解法
- 格式：pdf
- 大小：122.61 KB
- 文档页数：3
引理 １ （ Ｌ ） ＭＩＰ 必存 在最 优解 。
证明： 对于（ ＩＰ ， Ｙ ＝ ＝ ｉ ，， ，） Ｍ Ｌ ）ａ＝ ０（ ＝１２ … ｎ 定义的点 （ ｚａ 是可行 的； ，，） 由于问题（ ＩＰ 的 ＭＬ ） 可行域是紧的， 因此 ，Ｍ Ｌ ） （ ＩＰ 的最优解存在 （ 且满足 ａ ≥ ０ 。 ） 定理 １ （ ＩＰ 的最优解 ａ ０ Ｌ Ｐ 口Ｍ） ＭＬ ） ＞ 铮 Ｃ （ ， 有解 ， 并且 ＝ ／ ａ 是一个解。
ｓｔ ．． ≥ ０， ｘ ＋ 口 ≥ ０ ， Ｍ
当且仅当（ Ｐ 达到最优 目标值 ０时， 的 Ｘ Ｎ） 对应 就是（ Ｃ ） Ｌ Ｐ 的一个解 。本文给出了 Ｌ Ｐ ｑＭ） ｊ Ｃ （ ， 问题的
一
个直接求解方法： 混合整数线性规划解法。该方法的优点在于把线性互补问题转化为相应的混合整
维普资讯
２０ ０ ７年 ｌ ２月
陕 西
理
工 学 院 学
报
Ｄｅ ． ｏ ７ ｃ２ ｏ Ｖｏ． ３ Ｎｏ ４ １２ ．
第２ ３卷第 ４期
Ｊ ｕｎ ｌｏ ｈ ａ ｘ ｉｅｓｔ ｆＴ ｃ ｎ ｌｇ ｏ ｒ ａ ｆＳ ａ ｎ ｉＵｎｖ ｒｉ ｏ ｅｈ ｏｏ ｙ ｙ
方法 。把 线性 互补 问题 转 化为 一个 混合整数 线性 规 划 ， 然后 采 用数 学软 件进 行 求解 ； 值 实验 数
结果表 明 ， 给 出的方 法能 够 准确快 速地 求得 原 问题 的 最优解 。 所
［ 关 键 词］ 线性互补问题 ； 混合整数线性规划 ； 数 学软件 ［ 中图分类号］ ０ ２ ２１ ［ 文献标识码］ Ａ 线性互补问题…（ 简记为 Ｌ Ｐ ｑ Ｍ） Ｌ Ｐ 是一类非常重要 的优化 问题 ， Ｃ（ ， 或 Ｃ ） 它在工程 、 经济与交通 平衡等领域有着广泛的应用 ， 其一般形式是 ： 求 ∈ 使下式 Ｒ，
（Ｉ） Ｌ ０ Ｙ ｙ 口 ｚ Ｍ Ｐｌ ０ ≤ ≤ ＋ｑ ， ＬＪ Ｍ ｅ —ｚ≤ ≤
０≤ ａ≤ １， ｚ∈ ｛ １ ０，｝ ，
其中： ＝（ ，， １ 。 Ｒ ， Ｒ ， ∈ 我们称（ ＩＰ 为（ Ｃ ） Ｐ １１ …，） ∈ Ｙ∈ ｚ Ｒ ， Ｍ Ｌ ） Ｌ Ｐ 问题的伴随混合整数线性规划。
维普资讯
第 ４期
雍龙 泉 ， 邓方安 ， 赵景服
线性互补 问题 的一种混合整 数线性规划解法
证明 ： 设 ａ ０ 则 Ｘ’＝，／ 满 足 ： ’＞ ， ｊ’ａ ０≤口 ’ ’ ≤１一 。 ０≤ａ （ 和 ’ Ｍｘ’＋ｑ ’ 由于 ｇ ∈｛ ， ）≤ 。， ｉ ０
（ Ｍｘ ＋ｑ ：０， ） ≥ ０ Ｍｘ＋口≥ ０ ，
成立 ； 其中Ｍ ∈ “ ， ∈ Ｒ ｑ Ｒ 。对上述 Ｌ Ｐ ｑ Ｍ） Ｃ （ ， 的研究 主要集 中在理论与算法两个方面 ， 前者主要研究 其解的存在性 、 唯一性 、 稳定性及灵敏度分析 ， 后者主要建立其有效的求解方法和相应 的收敛性分析， 求 解 Ｌ Ｐ ｑＭ） Ｃ （ ， 问题常用的算法是内点算法¨ 和非内点算法 ； 其基本思想是构造非线性优化问题： （ Ｐ Ｎ ） ａ ｎ Ｔ Ｍｘ＋口 ｒｉ ｘ （ ），
ａ＝ ｍｉ ｛ ｌａ ， ｝ ｎ ａ ，２１ ， Ｙ ＝ａ ， ｘ
其 中 ：ｌ ｉ｛／ 。 。 ０｝ ａ ＝ｍｎ １ （ ａ ＝ｍｎ １ｘ： ＞ ， ２ ｉ｛／ Ｍｘ＋ｑ （ ）： Ｍｘ＋ ） ０｝则 （ ，，） 问题 （ Ｌ ） 口 ＞ ． ｊ ｚａ 是 ， ＭＩＰ 的可 行 解 ， 同 ａ ０矛盾 。因此 ， Ｌ Ｐ ｑ ） 这 ’＝ 若 Ｃ （ ， 有解 ， 则必 有 ａ ０成立 。 ’＞
作者简介 ： 雍龙泉 （９０ ）男 ， 西洋 县人 ， 西理 工学 院讲 师 ， 士 。 １８一 ， 陕 陕 硕 主要研 究 方 向 为优化 算 法及 其应 用。邓方 安 （９３ ）男 ， １６一 ， 陕西 宁强人 ， 陕西理工学院教授 ， 士 ， 博 主要研究方 向为优化算法 、 糙集理论及其在优化 中的应用。 粗
１ ， 以 ， 于 ｉ ，， ， ， ｝所 对 ＝１２ … ｎ 或者 有 ｉ ０ 或 者 有 （ ’＝ ， Ｍｘ’＋ｑ ： 因此 ， ＝ ， ａ 是 Ｌ Ｐ ｑ Ｍ） ） ０． Ｘ ｊ ／ ’ Ｃ （ ， 的
一
个解 。
反过 来 ， 设 ａ ０． 果 Ｌ Ｐ ｑ Ｍ） 假 ‘＝ 如 Ｃ （ ， 有解 Ｘ， 么不会 同 时有 Ｘ＝ 那 ０和 Ｍｘ＋ｑ＝ 否则 ， 意味 着 ０， 这 ｑ＝ 对 于 ｉ ， ， ， 令 ０． ＝１２ … ｎ， ｒ， 若 （ １ Ｍｘ＋ｑ ＞０ ， ） ‘ 【 若 （ ０， Ｍｘ＋ｑ ＝０ ， ）
数线性规划， 然后通过求解混合整数线性规划得到原问题的最优解； 由于该方法对线性互补问题中矩阵
未做限制 ， 因此 比文献 ［ ］ ５ 中所给出的方法给更一般 ， 更实用。
１ 混合整数线性规划解法
定义 １ 【 ６ 对给定的线性互补问题 ， 考虑如下混合整数线性规划
ｍ ａｘ
，ห้องสมุดไป่ตู้
口
，
［ 文章 编号 ］６３— ９４ ２０ ）４— ００— ３ １７ ２４ （０７ ０ ０ ８ ０
线 性 互 补 问题 的一 种 混 合 整 数 线 性 规 划 解 法
雍龙泉 ， 邓 方安 ， 赵 景 服
（陕西理工学 院 数学 系 ， 陕西 汉 中 ７３ ０ ） ２０ １
［ 摘
要 ］ 经典 算法 一般 采 用迭代过 程 求解线 性互补 问题 ， 究 了线性 互补 问题 的直接 求解 研
收稿 日期 ：０ ６—１ ２ ２０ ２— Ｏ 基金项 目： 国家 自然科学基金 资助项 目（ ０ ７０ ２ ； ７４ ２ ７ ） 陕西省 中青 年科技 人才培 养计划 项 目（ ４ Ｋ ９ ； ０ Ｊ ２９） 陕西理 工学院科 研基金资助项 目（ Ｌ Ｑ ０ １ ；Ｌ Ｑ ０ ２ ） Ｓ Ｇ Ｄ ５７ Ｓ Ｇ Ｄ ６７ 。
证明： 对于（ ＩＰ ， Ｙ ＝ ＝ ｉ ，， ，） Ｍ Ｌ ）ａ＝ ０（ ＝１２ … ｎ 定义的点 （ ｚａ 是可行 的； ，，） 由于问题（ ＩＰ 的 ＭＬ ） 可行域是紧的， 因此 ，Ｍ Ｌ ） （ ＩＰ 的最优解存在 （ 且满足 ａ ≥ ０ 。 ） 定理 １ （ ＩＰ 的最优解 ａ ０ Ｌ Ｐ 口Ｍ） ＭＬ ） ＞ 铮 Ｃ （ ， 有解 ， 并且 ＝ ／ ａ 是一个解。
ｓｔ ．． ≥ ０， ｘ ＋ 口 ≥ ０ ， Ｍ
当且仅当（ Ｐ 达到最优 目标值 ０时， 的 Ｘ Ｎ） 对应 就是（ Ｃ ） Ｌ Ｐ 的一个解 。本文给出了 Ｌ Ｐ ｑＭ） ｊ Ｃ （ ， 问题的
一
个直接求解方法： 混合整数线性规划解法。该方法的优点在于把线性互补问题转化为相应的混合整
维普资讯
２０ ０ ７年 ｌ ２月
陕 西
理
工 学 院 学
报
Ｄｅ ． ｏ ７ ｃ２ ｏ Ｖｏ． ３ Ｎｏ ４ １２ ．
第２ ３卷第 ４期
Ｊ ｕｎ ｌｏ ｈ ａ ｘ ｉｅｓｔ ｆＴ ｃ ｎ ｌｇ ｏ ｒ ａ ｆＳ ａ ｎ ｉＵｎｖ ｒｉ ｏ ｅｈ ｏｏ ｙ ｙ
方法 。把 线性 互补 问题 转 化为 一个 混合整数 线性 规 划 ， 然后 采 用数 学软 件进 行 求解 ； 值 实验 数
结果表 明 ， 给 出的方 法能 够 准确快 速地 求得 原 问题 的 最优解 。 所
［ 关 键 词］ 线性互补问题 ； 混合整数线性规划 ； 数 学软件 ［ 中图分类号］ ０ ２ ２１ ［ 文献标识码］ Ａ 线性互补问题…（ 简记为 Ｌ Ｐ ｑ Ｍ） Ｌ Ｐ 是一类非常重要 的优化 问题 ， Ｃ（ ， 或 Ｃ ） 它在工程 、 经济与交通 平衡等领域有着广泛的应用 ， 其一般形式是 ： 求 ∈ 使下式 Ｒ，
（Ｉ） Ｌ ０ Ｙ ｙ 口 ｚ Ｍ Ｐｌ ０ ≤ ≤ ＋ｑ ， ＬＪ Ｍ ｅ —ｚ≤ ≤
０≤ ａ≤ １， ｚ∈ ｛ １ ０，｝ ，
其中： ＝（ ，， １ 。 Ｒ ， Ｒ ， ∈ 我们称（ ＩＰ 为（ Ｃ ） Ｐ １１ …，） ∈ Ｙ∈ ｚ Ｒ ， Ｍ Ｌ ） Ｌ Ｐ 问题的伴随混合整数线性规划。
维普资讯
第 ４期
雍龙 泉 ， 邓方安 ， 赵景服
线性互补 问题 的一种混合整 数线性规划解法
证明 ： 设 ａ ０ 则 Ｘ’＝，／ 满 足 ： ’＞ ， ｊ’ａ ０≤口 ’ ’ ≤１一 。 ０≤ａ （ 和 ’ Ｍｘ’＋ｑ ’ 由于 ｇ ∈｛ ， ）≤ 。， ｉ ０
（ Ｍｘ ＋ｑ ：０， ） ≥ ０ Ｍｘ＋口≥ ０ ，
成立 ； 其中Ｍ ∈ “ ， ∈ Ｒ ｑ Ｒ 。对上述 Ｌ Ｐ ｑ Ｍ） Ｃ （ ， 的研究 主要集 中在理论与算法两个方面 ， 前者主要研究 其解的存在性 、 唯一性 、 稳定性及灵敏度分析 ， 后者主要建立其有效的求解方法和相应 的收敛性分析， 求 解 Ｌ Ｐ ｑＭ） Ｃ （ ， 问题常用的算法是内点算法¨ 和非内点算法 ； 其基本思想是构造非线性优化问题： （ Ｐ Ｎ ） ａ ｎ Ｔ Ｍｘ＋口 ｒｉ ｘ （ ），
ａ＝ ｍｉ ｛ ｌａ ， ｝ ｎ ａ ，２１ ， Ｙ ＝ａ ， ｘ
其 中 ：ｌ ｉ｛／ 。 。 ０｝ ａ ＝ｍｎ １ （ ａ ＝ｍｎ １ｘ： ＞ ， ２ ｉ｛／ Ｍｘ＋ｑ （ ）： Ｍｘ＋ ） ０｝则 （ ，，） 问题 （ Ｌ ） 口 ＞ ． ｊ ｚａ 是 ， ＭＩＰ 的可 行 解 ， 同 ａ ０矛盾 。因此 ， Ｌ Ｐ ｑ ） 这 ’＝ 若 Ｃ （ ， 有解 ， 则必 有 ａ ０成立 。 ’＞
作者简介 ： 雍龙泉 （９０ ）男 ， 西洋 县人 ， 西理 工学 院讲 师 ， 士 。 １８一 ， 陕 陕 硕 主要研 究 方 向 为优化 算 法及 其应 用。邓方 安 （９３ ）男 ， １６一 ， 陕西 宁强人 ， 陕西理工学院教授 ， 士 ， 博 主要研究方 向为优化算法 、 糙集理论及其在优化 中的应用。 粗
１ ， 以 ， 于 ｉ ，， ， ， ｝所 对 ＝１２ … ｎ 或者 有 ｉ ０ 或 者 有 （ ’＝ ， Ｍｘ’＋ｑ ： 因此 ， ＝ ， ａ 是 Ｌ Ｐ ｑ Ｍ） ） ０． Ｘ ｊ ／ ’ Ｃ （ ， 的
一
个解 。
反过 来 ， 设 ａ ０． 果 Ｌ Ｐ ｑ Ｍ） 假 ‘＝ 如 Ｃ （ ， 有解 Ｘ， 么不会 同 时有 Ｘ＝ 那 ０和 Ｍｘ＋ｑ＝ 否则 ， 意味 着 ０， 这 ｑ＝ 对 于 ｉ ， ， ， 令 ０． ＝１２ … ｎ， ｒ， 若 （ １ Ｍｘ＋ｑ ＞０ ， ） ‘ 【 若 （ ０， Ｍｘ＋ｑ ＝０ ， ）
数线性规划， 然后通过求解混合整数线性规划得到原问题的最优解； 由于该方法对线性互补问题中矩阵
未做限制 ， 因此 比文献 ［ ］ ５ 中所给出的方法给更一般 ， 更实用。
１ 混合整数线性规划解法
定义 １ 【 ６ 对给定的线性互补问题 ， 考虑如下混合整数线性规划
ｍ ａｘ
，ห้องสมุดไป่ตู้
口
，
［ 文章 编号 ］６３— ９４ ２０ ）４— ００— ３ １７ ２４ （０７ ０ ０ ８ ０
线 性 互 补 问题 的一 种 混 合 整 数 线 性 规 划 解 法
雍龙泉 ， 邓 方安 ， 赵 景 服
（陕西理工学 院 数学 系 ， 陕西 汉 中 ７３ ０ ） ２０ １
［ 摘
要 ］ 经典 算法 一般 采 用迭代过 程 求解线 性互补 问题 ， 究 了线性 互补 问题 的直接 求解 研
收稿 日期 ：０ ６—１ ２ ２０ ２— Ｏ 基金项 目： 国家 自然科学基金 资助项 目（ ０ ７０ ２ ； ７４ ２ ７ ） 陕西省 中青 年科技 人才培 养计划 项 目（ ４ Ｋ ９ ； ０ Ｊ ２９） 陕西理 工学院科 研基金资助项 目（ Ｌ Ｑ ０ １ ；Ｌ Ｑ ０ ２ ） Ｓ Ｇ Ｄ ５７ Ｓ Ｇ Ｄ ６７ 。
