0I:10.13374/.j.1ssm1001053x.1997.02.018 第19卷第2期 北京科技大学学报 Vol.19 No.2 1997年4月 Journal of University of Science and Technology Beijing Apr.1997 对满足换基规定的单纯形法的改进 刘萍)凌晓东) 1)北京科技大学信息工程学院，北京1000832)中信公司国际研究所，北京100083 摘要针对满足换基规定的单纯形法可能出现的选代不下去的问题，构造了使迭代得以继续的 补充算法.这个补充算法的基本思想是暂时放弃换基规定，首先进人与所解问题对应的线性规划 的最优基本可行解集中；然后，在这个集合中进行基变换，直到得到二次规划问题的最优解.经证 明，改进后的算法取消了原算法收敛性定理所需的3个条件，使得它可求解任何一个凸二次规划 问题，计算实例证明，补充算法有较好的结果， 关键词二次规划，单纯形法，数值实现，换基规定 中图分类号0221.2 满足换基规定的单纯形法（相当于Wofe方法冈的短形式）是一种求解二次规划的常用 算法，为保持换基规定，某些二次规划问题的求解将出现迭代不下去的情况，而尽管该问题存 在最优解.为此，本文中设计了一段使迭代得以继续的算法，以确保修改后的算法可以成功地 求解任何一个凸二次规划问题，而不至于中途停止. 1满足换基规定的单纯形法概述 考虑二次规划问题： min Q(X)CTX+1 /2XHX (1) s.tAX=B,X≥0 其中X= e- ba A的秩为m,m≤n,H为半正定矩阵. 在此假定下，X·成为问题()的最优解的充分必要条件是存在m维向量U·,n维向量 V,并使X·,U·,V*满足K-T条件： AX=B C+HX+A-V=0 (2) X=0,V≥0，X≥0 将(2)式中的U表示为U=U+-U-(其中U+≥0，U-≥0)，去掉非线性方程中的 TX=O,并引人人工变量W=[w,,wT,可得到线性规划的标准形式(3)： 1996-10-02收稿 第一作者女41岁副教授硕士第 卷 第 期 年 月 北 京 科 技 大 学 学 报 。 对满足换基规定 的单纯形法 的改进 刘 萍 凌晓 东 “ 北京 科技 大学信息工 程学 院 ， 北京 中信公 司 国 际研究所 ， 北京 摘要 针 对满足 换基规定 的单纯形 法 可 能 出现 的迭 代不 下去 的 问题 ， 构造 了使迭代得 以 继续 的 补充算 法 这个补充算法 的基 本思想 是 暂时 放弃换基规定 ， 首先进人 与所解 问题 对应的 线性规划 的最优基本 可 行解 集 中 然后 ， 在这 个集 合 中进行基变换 ， 直到得 到二 次规划 问题 的最 优解 经 证 明 ， 改进后 的算法取 消 了原算法 收敛性定理 所需 的 个条件 ， 使得 它 可 求解 任何一 个 凸 二 次规划 问题 计算实例证 明 ， 补充算法有 较好的结果 关键词 二次规划 ， 单纯形 法 ， 数值 实现 ， 换基规定 中图分类号 满 足换基规定 的单纯形法 【 ’】 相 当于 方法 的短形 式 是 一种求解二 次规划 的常用 算 法 为保持换基规定 ， 某 些 二 次规划 问题 的求解 将 出现迭 代不下 去 的情 况 ， 而 尽 管 该 问题存 在最优解 为此 ， 本 文 中设计 了 一段 使迭代得 以 继 续 的算法 ， 以 确保修改 后 的算法 可 以 成 功地 求解 任何 一个凸二 次规划 问题 ， 而 不 至 于 中途停止 满足换基规定 的单纯形法概述 考 虑 二 次规划 问题 刀 己 丫刀无才 ， 之 其 中 一 」 ， 一 一 · 一 · 。 呱 一 溯 “… … 一 出 … 亨力 ， 一 一 的秩 为 ， ‘ ， 为半正 定矩 阵 在 此 假 定 下 ， 成 为 问题 的最 优解 的充 分 必 要 条件是 存 在 维 向量 ’ ， 。 维 向量 ， ， 并使 ， ， ’ ， 巾 满足 一 条件 刀 ‘ 丫 一 砰 ， 全 ， 之 将 式 中的 表示 为 二 一 一 其 中 七 ， 一 全 ， 去掉非 线性 方 程 中的 砰 一 ， 并 引 人 人 工 变 量 附 二 卜 ， 一 ， 月 ， 可 得 到 线 性 规 划 的 标 准 形 式 一 一 收稿 第一 作者 女 岁 副教授 硕 士 DOI ：10．13374／j ．issn1001－053x．1997．02．018