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