对满足换基规定的单纯形法的改进

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

·202· 北京科技大学学报 1997年第2期 mi/(叨=Σ， s.t.AX=B (3) HX+A(U+-U-)-V+EW=-C V≥0，X≥0，U+≥0，U-≥0，w≥0 其中： - X0=[x…,]为AK=B,X≥0的I个基本可行解. 令问题(3)的初始基本可行解为U+0=U-0=0=0,w=, 2+c小=l X0,则VTX=0.从此出发，用单纯形方法，保持VTX=0的条件下进行基变换，如果经有 限步迭代，得到问题(3)的最优解X·,V,U+·,U·,W*=0(且VTX·=0),便得到了问 题(2)的K-T点：X,V,U·=U+·-U·,从而得到二次规划问题(1)的最优解X*. 以上便是满足换基规定的单纯形方法， 关于这个方法的收敛性，文献[1]在定理102.3中证明了以下任意一个条件满足时，均可 得到问题(1)的最优解：(I)H为正定矩阵；(2)C=0;(3)存在y∈E+n使C=[HA]y,否则，可 能出现迭代不下去的情况， 2补充算法设计 根据K-T条件的必要性，当问题(I)存在最优解X·时，问题(3)存在X·,U+·,U-·, V·,W=0的最优基本可行解且满足VTX=0,如果问题(3)仅有这1个解，根据单纯形 法的基本定理（文献[1]定理612），无须保持这一换基规定，用单纯形法即可经有限步迭代 得到这个解.但由于问题(3)共有3n+2m个变量，方程组却只有n+m个，更多的是有不止1 个最优基本可行解.因此，当用满足换基规定的单纯形法求解问题(3)出现迭代不下去的情况 时，不妨暂时放弃TX=0这一约束，改用单纯形法继续送代，首先得到问题(3)的】个最优基 本可行解；然后，在最优基本可行解集中进行基变换，直到得到满足V·TX=O的最优解. 为了算法描述方便，将首次得到问题(3)的最优基本可行解时的单纯形表见表1.不失一 般性，将基变量排在了前m列，且在y,,(=1,,m)中至少有一对变量x,y,满足x,y,+0. 表中a是常数；c,b,都是大于等于0的 表1单纯形表 常数，右下角显示目标值∫=0； m=m+n,n=2+3n,y,(i=1,,n) -f b 代表的是X,U+,U,V,W的各分量.表 0 a1m1 Q1元 0b1 中前行是问题(3)中的线性约束方程经 过k次迭代的结果，最后一行是目标函数 0 后前l d 0 经过k次迭代的结果， 本算法是当目标值∫*0，但用满足 0 0Cmt1… C开 0 换基规定的单纯形法却无法实现基变换时采用

北 京 科 技 大 学 学 报 年 第 期 ‘ 哟 一 粤 ‘ 二 刀万 十 一 一 一 二 一 七 ， 全 ， 全 ， 一 全 ， 丫 之 归尹护 十 一 口儿 ，刀 。叉艺 其 中 一 卜 卜 ， “ 二 、 ’ “ ， 飞 ， “ · “ 【 ” 〔冷 一 们 为 一 ， 之 的 个基 本可 行解 · 令 问题 的初 始 基 本 可行解 为 “ 一 “ 砂 ， 衅 二 ，粤”才 ‘ 者 “ ， 则 叮 “ 从此 出发 ， 用单纯 形方 法 ， 保持 的条件 下进行基变 换 如果 经有 限步迭 代 ， 得 到 问题 的最 优解 ’ ， ’ ， ’ ， 一 ’ ， 附 ’ 且 ’ ， 便得 到 了 问 题 的 一 兀点 中 ， ’ ， ’ ’ 一 一 ’ ， 从而得 到二 次规划 问题 的最优解 字 以 上便 是 满足 换基规定 的单纯形 方 法 关 于这个方法 的收敛性 ， 文 献 〕在 定理 中证 明了 以 下任 意 一个条件满足 时 ， 均 可 得 到 问题 的最 优解 为正定矩 阵 存街 ‘ 戈 ， 。 使 一 〔 矛〕， 否 则 ， 可 能 出现迭代 不 下 去 的情 况 补充算法设计 根据 一 条件 的必要 性 ， 当问题 存在最优解 ’ 时 ， 问题 存在 ’ ， ‘ ， 一 ’ ， ， 一 。 的最 优基 本可 行 解 且 满 足 一 如果 问题 仅有 这 个解 ， 根 据单纯 形 法 的基 本 定 理 文 献 定理 ， 无 须保持 这 一换 基 规定 ， 用 单纯 形 法 即可 经有 限步迭 代 得 到 这个解 但 由于 问题 共有 个变量 ， 方 程组 却只 有 个 ， 更多 的是 有不 止 个最优基 本可 行解 因此 ， 当用 满 足换基规定 的单纯形 法求解 问题 出现迭代不下 去 的情 况 时 ， 不妨 暂 时放弃 尸 这 一 约束 ， 改 用单纯形 法 继续迭 代 ， 首先得 到 问题 的 个最优基 本可行解 然 后 ， 在 最 优基 本 可行解 集 中进 行基 变换 ， 直到得到 满足 ， ， 的最优解 为 了算 法 描 述 方便 ， 将首 次得到 问题 的最 优基 本 可 行解 时 的单纯形 表 见 表 不 失 一 般性 ， 将基 变量 排在 了前不 列 ， 且 在 乃 ， 。 卜 一 不 中至 少有一 对变量 今 满足‘ · 羊 表 中 弓是 常数 可 ， 《 都 是 大 于 等 于 “ 的 常 数 ， 右 下 角 显 示 目 标 值厂 一 蔽 一 ， 万一 ， ， ， 一 ， · ， 万 止 代 表 的 是 ， 十 ， 一 ， ， 的 各 分 量 表 表 单纯形表 二 少二 ， ，厂 耐 中前不行 是 问题 中 的 线性 约束 方 程 经 过 次迭 代 的结 果 ， 最 后 一行是 目标 函 数 经过 次迭 代的结果 一 本 算法 是 当 目标值厂， ， 但 用 满足 一 换基规定 的单纯形 法 却无法 实现基 变换 时采用 石 不 口 万 月 月 命

Vol.19 No.2 刘萍等：对满足换基规定的单纯形法的改进 ·203· 具体算法如下： 步骤1：放弃换基规定，改用单纯形法继续迭代，首先得到问题(3)的一个最优基本可行 解（即表1）. 步骤2：建立X,V在基变量表.该表用于记录X,V中进人基变量的分量. 步骤3：建立待人基变量集合Y=yI至少存在一个a,>0}. 步骤4：依次考察Y中待人基变量，计算b,/a,=min(亿，Ia,,得到相应的行数r,r值 是待人基变量主元行数， 4>0 关于人基变量的选择按以下条件： (1)y,入基后，目标值仍保持为0.即若c>0,需y取值为0才能入基. (2)查在基变量表，y,入基后不会出现循环. (3)y入基后，将取消在基变量表中的一对xy,+0,同时又不带来新的一对. (4)若Y中无满足条件(3)的y,选择对在基变量表无影响的y,入基. 以上4条中，条件(1)，(2)是人基变量y,必须满足的.在此基础上，优先选择满足条件(3) 或(4)的y,入基.如Y中无满足条件(1)，(2)的人基变量，输出问题(I)有无界解，停；否则转步 骤5. 步骤5：y,人基.判断TX-0是否成立，若是，输出最优解X·,停；若否，记录新变量入基 带来的X,V在基变量表的变化.转步骤3. 3收敛性讨论 如果问题(1)存在有界最优解，将会通过步骤1得到表1.由于V「X·+0得到的仅是问 题(3)的最优基本可行解，而不是与问题(I)对应的最优基本可行解.但因问题(1)存在最优 解，步骤3所形成的待人基的非基变量集合Y不空，这保证了进人步骤4后r的存在性.r值确 定后，新变量人基可能出现的情况是：(I)取消了一对x,卡0；(2)在取消了一对的同时又带来 另一对x”,卡0；(3)对在基变量表没有影响，只是得到了另一个最优基本可行解.由于最优基 本可行解个数有限，本算法设计的进基原则又可保证在基变量表不出现循环，因此必经有限 步得到满足VTX·=0的最优基本可行解. 另一方面，如果问题(1)为无界解，根据K-T条件，问题(3)不会存在满足VTX*=0, W=0的最优解.这时可能有两种情况：问题(3)不存在W=0的最优解，进人步骤1后，由 单纯形法即可使迭代终止；问题(3)存在W-0的最优解，但不满足V·TX·=0,这时在步骤4 使迭代终止 4实例计算 为了检验补充算法对各种可能情况的处理能力和收敛性，我们在计算机上进行了相应的 数值试验，看到了本算法如何有效地避免循环，逐一地解决X,V向量中多组分量同时在基的 问题.但限于篇幅，这里只能给出最简单的试验题目

刘 萍等 对满 足换基规定 的单纯形法 的 改进 具 体算法 如 下 步 骤 放 弃 换 基 规定 ， 改 用 单纯 形 法 继 续 迭 代 ， 首 先 得 到 问题 的 一 个 最 优 基 本 可 行 解 即表 步 骤 建 立 ， 在 基 变量 表 该表 用于 记 录， 中进人 基 变量 的分量 步 骤 建 立 待人 基 变 量 集 合 一 妙 ， 至 少存在 一个 · 步 骤 依 次考 察 中待人基 变 量 ， 计算叹 ’ 伍 口 ， 得 到相 应 的行 数 ， 值 口 ， 一 、 一 ， 一叭 ‘ “ ， 是 待 人基变 量 主元行 数 关 于人 基变量 的选 择按 以 下 条件 芯人基 后 ， 目标值仍保 持为 · 即若叮 ， 需 乃取值 为 才 能人 基 · 查 在 基 变 量 表 ， 耳人 基 后 不 会 出现循环 · 乃人基后 ， 将 取 消在基 变量 表 中的一 对气 ‘ 羊 ， 同时又 不带来新 的一 对 若 中无 满足条件 的艺 ， 选择对在基 变量 表无影 响 的 沁人基 · 以 上 条 中 ， 条件 ， 是 人 基 变量 艺必 须 满 足 的 · 在 此基础 上 ， 优先 选 择满 足条件 或 的 乃人 基 · 如 中无 满足 条件 ， 的人 基 变量 ， 输 出 问题 有 无界 解 ， 停 否 则转 步 骤 步 骤 艺人基 · 判 断 尸 一 是 否 成 立 ， 若是 ， 输 出最 优解 ’ ， 停 若否 ， 记 录新 变 量人 基 带来 的 ， 在基变量 表 的变化 转步骤 收敛性讨论 如果 问题 存 在 有 界 最 优解 ， 将 会通 过 步 骤 得 到 表 由于 广 ， 羊 。 得 到 的仅是 问 题 的最 优基 本可 行 解 ， 而 不 是 与 问题 对应 的 最 优基 本 可 行 解 但 因 问题 存 在 最 优 解 ， 步 骤 所 形 成 的待人基 的非基 变 量集合 不 空 这 保证 了进人 步 骤 后 的存 在性 值确 定 后 ， 新 变量 人基 可 能 出现 的情 况是 取 消 了一 对 ‘ 羊 以 在取 消 了一 对的 同时又 带来 另 一 对人 ， 羊 对 在 基 变 量 表 没 有 影 响 ， 只 是 得 到 了另 一 个最 优基 本 可 行 解 由于 最 优基 本可 行 解 个 数有 限 ， 本算 法 设 计 的进基 原则 又 可 保 证在 基 变 量 表 不 出现 循 环 ， 因此 必 经有 限 步得 到 满足 ， 二 的最优基本 可行解 另 一 方 面 ， 如 果 问题 为 无 界 解 ， 根 据 一 条件 ， 问题 不 会存 在 满足 ’ 二 ， 附 ， 二 的最 优解 这 时 可 能有 两种情 况 问题 不存 在 ， 的最 优解 ， 进人 步骤 后 ， 由 单纯形 法 即可 使迭 代终止 问题 存在 矛一。 的最 优解 ， 但 不满足 工 一 。 ， 这 时在 步骤 使迭代 终止 实例计算 为 了检 验 补充算 法 对各 种 可 能情 况 的处理 能力 和 收敛性 ， 我们 在计算机上 进 行 了相 应 的 数值 试 验 看 到 了本 算 法 如 何 有 效 地 避 免循 环 ， 逐 一地 解 决 ， 向量 中多 组 分 量 同时在基 的 问题 但 限于 篇 幅 ， 这 里 只 能 给 出最 简单 的试验题 目

·204· 北京科技大学学报 1997年第2期 考虑文献[3]中例题： mine(X)=-2x+(x) s.t2x+35+x=6 2x+5+x=4 (4) x≥0(i=1,…,4) 对应问题(3)的形式： 2000 0 0000 0000 ,P= 6 0 L0000 故心，，U+0=U-0=0=0为问题(4)的初始可行解.初始单纯形表见表2.从表2开始， 用满足换基规定的单纯形法，经3步迭代，目标值从3降为1，尚有2个检验数为负，其中，检 验数次负的为一1，应变量v,人基，但x也已在基中，为了满足换基规定，迭代只能到此中止， 表2初始单纯形表 5。V354i4G453wyw4-∫b, ✉C H -E A -AT E y -200 1 1-6-4 6 4 0000 1-3 Wolfe算法遇到了迭代不下去的困难.按照本文补充算法，则： 进入步骤1，放弃换基规定，让y,人基，便得到了问题(3)的一个最优基本可行解： X=[2/3014138/3]T,V=[001130], U+*=[1/30],U-*=[00],w=0. 进入步骤2，建立在基变量表：{比，xx"}. 进入步骤3，建立待入基变量表y={"""www}. 进入步骤4，由此时单纯形表知，，"，同时为基变量，x主元位于第5行；y,主元位于第2 行.对Y中待人基变量计算r值：第1个非基变量x的，值正好是基变量x主元位于的行数， 因此5入基，得到以下结果 X-[2/314/9010/9],V-[001/30], U**=[1130]',U-·=[00],W*=0. 满足V·TX·=0,,从而X·是问题(4)的最优解，迭代结束. 5结论 使用改进了满足换基规定的单纯形算法，可解决原算法可能出现的迭代不下去的问题， 以确保人工变量W消失为0. (下转217页)

北 京 科 技 大 学 学 报 年 第 期 考 虑 文 献 〕中例题 飞 一 ，‘ 一 卜 … ，︸一 幻 一 一 凡 ，甲 · ， 凡 戈 凡 戈 七 ， … ， ‘咬乙 ‘ ‘峨乙 ， 尸刀 一 气 ︵ ，‘，︸， “︶、 对应 问题 的形 式 二 「二子 厂 ， 」 故妙 ， 妒 ， 。 二 一 ” 砂 为 问题 的初 始 可 行解 初始 单纯形 表 见表 从表 开始 ， 用满 足换基规定 的单纯 形 法 ， 经 步迭 代 ， 目标值从 降为 ， 尚有 个检验数为 负 其 中 ， 检 验 数次 负的 为 一 ， 应 变量 人基 ， 但 戈也 已 在基 中 · 为 了满足换基抓定 ， 迭 代只 能到 此 中止 ， 表 初始单纯形表 处 为 为 ， ， ， ， 。 丁 。 言 。 丁 。 歹 。 · ， 、‘ ， ‘ 一 。 一 月 一 一 一 一 算 法 遇 到 了迭代不 下 去 的 困难 按 照 本 文 补充算 法 ， 则 进人 步骤 ， 放弃换基规定 ， 让 。 人基 ， 便得 到 了 问题 的一 个 最 优基 本 可 行解 ， ， ， ’ ， 一 ’ 」 ， 体 进人 步 骤 ， 建 立 在基 变 量 表 ， 戈 ， 凡 ， 咋 进 人 步骤 ， 建 立 待人 基 变量 表 一 凡 ， 、 ， ， ， ， ， 、 进 人 步 骤 ， 由此 时单 纯 形 表 知 ， 戈 ， 同 时 为基 变 量 ， 戈主 元 位 于 第 行 主元 位 于 第 行 · 对 中待 人 基 变量 计算 值 二第 个 非基 变量 的 值 正 好是 基 变量 凡主元位 于 的行数 ， 因此 毛 人基 ， 得 到 以 下 结果 一 ， 一 一 ， 十 ‘ ， 一 ’ ， 附 满 足 ’ 下 ’ 二 ， ， 从而 · 是 问题 的最 优解 ， 迭 代 结束 结 论 使 用 改 进 了满 足 换 基 规 定 的单纯 形 算法 ， 可 解 决 原算法 可 能 出现 的迭 代 不 下 去 的 问题 ， 以 确保 人 工 变 量 附消 失 为 下 转 页

Vol.19 No.2 宋波等：Fe液中Bi蒸气溶解平衡及第三组元的影响 ·217· Dissolution Equilibrium of Bismuth Vapor in Liquid Iron and the Interaction Effect of Third Element Song Bo Zhao Baodong Han Oiyong Liu Yong Applied Science School.UST Beijing,Beijing 100083.China ABSTRACT The dissolution equilibrium of Bi vapor in liquid iron and the interaction effect of third element were conducted in a sealed Mo reaction chamber by vapor pres- sure method.The relationship between the standard solution Gibbs free energy of Bi in liquid iron and temperature obtained can be expressed.The interaction coefficients of third elements on Bismuth in liquid iron at 1 873 K can be deduced. KEY WORDS bismuth,liquid iron,thermodynamic parameters,impurity 米米米米米米米米米米米米米米米采米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米米 (上接204页) 参考文献 1魏权龄，王日类，徐兵.数学规划引论.北京：北京航空航天大学出版社，1991.290 2 Wolfe P.Econometrica,1959,27(3):382 3陈开明.非线性规划.上海：复且大学出版社，1991.269 Modification to Wolfe's Simplex Method Liu Ping Ling Xiaodong?) 1)Information Engineering School.UST Beijing,Beijing 100083.China 2)CITIC Research Intemational ABSTRACT To guarantee the convergence of the algorithm,the short form of Wolfe's method requires the coefficients of the objective function and constraint equations to satisfy some specific conditions.The above conditions of the convergence theorem can be eliminated by the improved method. KEY WORDS quadratic programming,simplex method,numerical implementation

宋波等 液 中 蒸气溶解 平衡及第三组元 的影 响 · 七 勘 助 ， ， ， 正 陇 任 面 面 ， ， ， 上 接 页 参 考 文 献 魏权龄 ， 王 日爽 ， 徐兵 数学规划 引论 北京 北京航空航 天大学 出版社 ， ， ， 陈开 明 非线性规划 上海 复旦大学 出版社 ， ， “ ， ， 加 ’ ， 刀 掩 代 ， ， 】 ，