9=（91,92》…,9m）, A=(ai)是秩为m的m×n矩阵， a,B为常数。 我们知道，若qTX+B>0,则(1)~(3)的任意局部极小也是全部局极小(3)。 1 Charnes-一Cooper算法 令S={X引AX=b,X≥0}，设S非空有界。 先作变量替换： Y=ym+1X,yn+1≥0 (4) 考虑下述线性规划： min (prY+ay+1) (5) s.t.AY-by+1=0 (6) qY+Byn+1=Y,y≠0 (7) Y≥0，ym+1≥0 (8) Y是实数。 上述线性规划具有性质，对每个可行解（少.…），一定有>0。 事实上，若此性质不成立，即有ym+1=0,则由(6)、(8)，AY=0,Y≥0， 又由(7)， qTY=Y≠0， 所以 Y≠0 这样，对于(1)~(3)的可行解X及任意的1≥0， X+AY 也是(1)~(3)的可行解。这与S的边界性矛盾。所以，ym+1>0。 若qX+B>0,用单纯形法解(5)~(8)，由(5)~(8)的最优解可得(1)~ (3)的最优解。这就是： 定理1。如果(i),对(1)~(3)的某个最优解X°，gTX°+B及y都为正， (ii),(y◆T,y+1)T是(5)~(8)的最优解。 则 片，是1)~3)的最优解是（证明见3）。 2(1)~(3)与(5)~(8)的等价性 下面我们证明，定理1的逆定理亦成立。 定理2。计X◆是(1)~(3)的最优解，qTX+B>0,>0,令 qx+B,Yyx ·151·二 ， ， ， … … ， ， ， ‘ ， 是秩为， 的， 。 矩 阵 ， ， 刀为常数 。 我们知道 ， 若 『 刀 ， 则 的任 意 局 部极小也是全 部局 极小〔 〕 。 一 算法 令 二 ， ， 设 非空有界 。 先作变量替换 二 。 ， ， 。 夕 考虑下 述线 性规划 。 ， 刁 一 夕 。 ， 了 十 刀 。 ， 夕， ，铸 ， 。 护是 实数 。 、 、 ，， ，’ ，、 。 一 ， ‘ 一 ， 一 、 一 工止戏任扰 划县月 往城 河 毋，、 田 仃麟 飞 ， ， ， 一正 月 。 、 了 了 事实上 ， 若此性质不成立 ， 邵有为 。 二 ， 则 由 的 、 ， 二 分， 奋分 又由 ， 俨 夕护 ， 析以 价 这样 ， 对于 的可 行解 及 任意的 之 ， 十 几 也是 的可行解 。 这与 的边界 性矛盾 。 所 以 ， ， ， ， 。 若 夕 ， 用单纯 形法解 ， 由 的最优 解 可 得 的最优解 。 这就是 定理 。 如果 ， 对 的某个最优解 。 ， 丁 。 刀及夕都为正 ， ， ， 份 十 是 的最优解 。 则 牛 是 一 的最优解是 证 明则 〕 食 与 一 的等价性 下 面我们证明 ， 定理 的逆定理亦成 立 。 定理 。 计 是 的最优解 ， 了 刀 。 ， ， 。 ， 令 夕舍 十 夕 刀 今 二 育