Pim+k p P,+ B P 即P能被P1…,P1,Pk,P1…Pm线性表示,故是基可行解 2、证X在非退化情形是改进的基可行解。由(7)可得 f(X)=f-n0≤f=f(x") 而当X为非退化的基可行解时,由(12)知>0。于是f(x)<f=f(X)。即目标 函数严格下降 以上X到X的更换基变量的过程,可以完全通过矩阵的初等交换,即 Guass消去法 来实现。其实质就是把进基变量xm+所对应的列向量变为单位向量(它的非0分量1位于 离基变量所在的行)。沿用Guas消元的术语,元素Bm称为主元(在单纯形表上常用* 号来标识),P称为主元列。上述变换亦称转轴变换,或(l,m+k)旋转变换。以上过程 完全可以在单纯形表中进行,其中目标函数行可看作是第m+1个约束方程,同样参加消元 变换 这样,对改进解X。用定理1和2加以考察。若仍不满足,则继续重复上述换基过程。 如此迭代下去,便得一基可行解序列。其目标函数值在非退化情形,依次严格下降,因而序 列中不可能有重复的项。由于基可行解是有限的,故迭代至有限步必满足定理1或2。 这个迭代过程可以用粗略的框图表示如下: 基可行解 是否所有,≤0? 最优解 否→k 是否有Bk>0? 无解 是,取O Br>01 BI 以Bk为主元实行换基消元
68 1 1 m k mm k 1 l m k m lm k lm k lm k P P P P + + + + + + = − + + + − 即 Pl 能被 1 1 1 , , , , , , P P P P P l m k l m − + + 线性表示，故 1 X 是基可行解。 2、证 1 X 在非退化情形是改进的基可行解。由（7）可得 1 ( ) ( ) m k f X f f f X = − = + 而当 X 为非退化的基可行解时，由（12）知 0 。于是 1 f X f f X ( ) ( ) = 。即目标 函数严格下降。 以上 X 到 1 X 的更换基变量的过程，可以完全通过矩阵的初等交换，即 Guass 消去法 来实现。其实质就是把进基变量 m k x + 所对应的列向量变为单位向量（它的非 0 分量 1 位于 离基变量 所在的行）。沿用 Guass 消元的术语，元素 lm k + 称为主元（在单纯形表上常用* 号来标识）， Pm k + 称为主元列。上述变换亦称转轴变换，或 ( , ) l m k + 旋转变换。以上过程 完全可以在单纯形表中进行，其中目标函数行可看作是第 m+1 个约束方程，同样参加消元 变换。 这样，对改进解 1 X 。用定理 1 和 2 加以考察。若仍不满足，则继续重复上述换基过程。 如此迭代下去，便得一基可行解序列。其目标函数值在非退化情形，依次严格下降，因而序 列中不可能有重复的项。由于基可行解是有限的,故迭代至有限步必满足定理 1 或 2。 这个迭代过程可以用粗略的框图表示如下： 无解 否 最优解 是 是，取 min{ | 0} l i ik i lk ik = = 否 → k 0 基可行解 是否所有 0? j 是否有 0? ik 以 lk 为主元实行换基消元
例1 5x1+3x2+x3 200 x1+x2+x4 +5x 此即第一章例1的标准形式。 列表迭代如下 3 100 0 X4 00 (检验数中,若有两个以上大于0,以往的迭代一般取其中最大的) X4 163 0 55 f 0 x 2 0 f 0 0 175 表3已是最优表,故最优解和最优值分别为 (25,250,0,20)2,f(X)=-1 此与用图解法得到的结果相同 §3初始基可行解的求法
69 例 1 1 2 3 1 2 4 1 2 5 1 2 5 3 200 50 3 5 220 0, 1, ,5 min 4 3 i x x x x x x x x x x i f x x + + = + + = + + = = = − − 此即第一章例 1 的标准形式。 列表迭代如下： 1 x 2 x 3 x 4 x 5 x 3 x 4 x 5 x 5 * 3 1 0 0 1 1 0 1 0 3 5 0 0 1 200 50 220 f 4 3 0 0 0 0 （检验数中，若有两个以上大于 0，以往的迭代一般取其中最大的） 1 x 2 x 3 x 4 x 5 x x1 4 x 5 x 1 5 3 5 1 0 0 0 5 2 * 5 1 1 0 0 5 16 5 3 − 0 1 40 100 f 0 5 3 5 4 − 0 0 −160 1 x 2 x 3 x 4 x 5 x x1 x2 5 x 1 0 2 1 2 3 − 0 0 1 2 1 − 2 5 0 0 0 1 −8 1 25 20 f 0 0 2 1 − 2 3 − 0 -175 表 3 已是最优表，故最优解和最优值分别为 T x (25,25,0,0,20) * = , ( ) 175 * f X = − 此与用图解法得到的结果相同。 §3 初始基可行解的求法 10 25
回过头来,研究初始基可行解的求法,在这里我们给出两种处理方法。它们都是通过引 入所谓人工变量的办法来实现的。 (一)大M法 设问题是标准的: AX= 6 X≥0 (14) mIn f=CX 为了获得一个初始基可行解。引入人工变量y…y令y=(y1…,yn)。考察另一个 线性规划问题 AX +y=b X≥0,y≥0 (15) min z=CX+ME1 其中M>0是一个充分大的数,E=(1,1,…,1) 定理2 是问题(15)的最优解。若y°=0,则X是问题(14)的最优解。若 y≠0,则问题(14)无可行解。反之,若X是问题(14)的最优解,则是问题(15) 的最优解 证明设x是(14)的任一可行(X(15)的一个可行解。于是当y=0时, 因是(15)的最优解,而是(15)的可行解。故 CX°=CX0+MY0≤CX+MEO=CX 所以X是(14)的最优解 X 若y≠0设(14)有一可行解X,则。是(15)的一个可行解。于是 CX+MEy≤CX 因y≠0,故当M充分大时,上式不可能成立。所以这时(14)没有可行解。 反之,若X是(14)的最优解。设是(15)的任一可行解,则 、若y=0,则Ⅹ是(14)的一个可行解。于是CX≤CX=CX+MEy
70 回过头来，研究初始基可行解的求法，在这里我们给出两种处理方法。它们都是通过引 入所谓人工变量的办法来实现的。 （一） 大 M 法 设问题是标准的： 0 min AX b X f CX = = (14) 为了获得一个初始基可行解。引入人工变量 1 , , m y y 令 1 ( , , )T m y y y = 。考察另一个 线性规划问题 0, 0 min AX y b X y z CX MEy + = = + (15) 其中 M 0 是一个充分大的数，E=(1,1, ,1)。 定理 2 设 X y 是问题（15）的最优解。若 y =0,则 X 是问题（14）的最优解。若 y 0，则问题（14）无可行解。反之，若 X 是问题（14）的最优解，则 0 X 是问题（15） 的最优解。 证明 设 x 是（14）的任一可行解，则 0 X 是（15）的一个可行解。于是当 y =0 时， 因 X y 是（15）的最优解，而 0 X 是（15）的可行解。故 CX0=CX0+MEY0≤CX+ME0=CX 所以 X 是（14）的最优解。 若 y 0,设（14）有一可行解 X，则 0 X 是（15）的一个可行解。于是 CX MEy CX + 因 y 0,故当 M 充分大时，上式不可能成立。所以这时（14）没有可行解。 反之，若 X 是（14）的最优解。设 X y 是（15）的任一可行解，则 1、若 y=0，则 X 是(14）的一个可行解。于是 CX CX CX MEy = +
2、若y≠0,由于M0可以充分大,所以必有CX≤CX+MEy 因此 是(15)的最优解 0 推论若问题(15)无最优解,则问题(14)亦无最优解。 上述定理说明,为了获得(14)的最优解,可直接去求解(15)。而(15)的初始基可 行解是明显的。此法的缺点是,其中M较难确定,给上机计算带来麻烦。但手算时不必具 体给出,只要把它作为一个足够大的正参数来处理就行了。 例2 x1+2x2+3 x1+x2+5x3 +2x,+x3+ ≥0,j=1, 2 3x3+x 添加的人工变量不必非要m个,其实根据问题具体情况,只要在初始表中能凑成一个 单位矩阵I就可以了。此例只须增加二个人工变量y1y2即可。具体迭代过程如下: x 2 01 -1-M 0 00 f3M+23M+48M+40 35M+10 55 001M00101515 7 3 y 4 2 M+27M+16 8M+4 f 0 00 3M-6 6 7 0 473705 7 7 6 16 90 f 7
71 2、若 y 0，由于 M>0 可以充分大，所以必有 CX CX MEy + 因此 0 0 X 是（15）的最优解。 推论 若问题（15）无最优解，则问题（14）亦无最优解。 上述定理说明，为了获得（14）的最优解，可直接去求解（15）。而（15）的初始基可 行解是明显的。此法的缺点是，其中 M 较难确定，给上机计算带来麻烦。但手算时不必具 体给出，只要把它作为一个足够大的正参数来处理就行了。 例 2 1 2 3 1 2 3 1 2 3 4 1 2 3 4 2 3 15 2 5 20 2 10 0, 1, ,4 min 2 3 j x x x x x x x x x x x j f x x x x + + = + + = + + + = = = − − − + 添加的人工变量不必非要 m 个，其实根据问题具体情况，只要在初始表中能凑成一个 单位矩阵 I 就可以了。此例只须增加二个人工变量 1 2 y y, 即可。具体迭代过程如下： 1 x 2 x 3 x 4 x 1 y 2 y x4 1 2 1 1 0 0 1 2 3 0 1 0 2 1 5 0 0 1 10 15 20 f 1 3 3 -1 -M -M 0 x4 y1 y2 1 2 1 1 0 0 1 2 3 0 1 0 2 1 5 * 0 0 1 10 15 20 f 3M+2 3M+4 8M+4 0 0 0 35M+10 4 x 1 y 3 x 5 3 5 9 0 1 0 5 1 − 5 1 − * 5 7 0 0 1 5 1 − 5 2 5 1 1 0 0 5 1 6 3 4 f 5 − M + 2 5 7M +16 0 0 0 5 8 + 4 − M 3M-6 4 x 2 x 3 x * 7 6 0 0 1 7 9 − 7 4 7 1 − 1 0 0 7 5 7 3 − 7 3 0 1 0 7 1 − 35 10 7 15 7 15 7 25 f 7 6 0 0 0 ) 7 16 − (M + 7 4 − M + 7 90 −
7 2 001 0 15 至此,最优解和最优值分别是 555 X=22000=15 (二)二阶段法 构造一个辅助问题 b X≥0,y≥0 mn=∑y 问题(14)和(16)的解之间有如下关系 定理4若(16)的最优基可行解为 0),则x是(14)的一个可行解。若(16 的最优基可行解为 且Y°≠0,则(14)没有可行解。 证明前一结论显然成立,下面只证后者。用反证法。设X为(14)的一个可行解, 则0是(16的一个可行解。它使目标函数z取0值但此时(16)的最优值z=∑y> 产生矛盾。故(14)不可能有可行解。 定理4的一个前提是(16)有最优解。这是不成问题的。显然,(16)有一个现成的基 可行解X=b,=1…m,X=0,又因目标函数值z=∑≥0。它在可行解集合上显然有 下界0。故必有最优解(单纯形迭代只有两种结果:一是有最优解。一是可行解无下界)。 (16)的初始单纯形表具如下形式 y 0
72 1 x 2 x 3 x 1 0 0 6 7 2 3 − 3 2 0 1 0 6 1 2 1 3 1 − 0 0 1 2 1 − 2 1 0 2 5 2 5 2 5 f 0 0 0 -1 − M −1 − M -15 至此，最优解和最优值分别是 ,0,0,0) 2 5 , 2 5 , 2 5 ( * X = T , 15 * f = − （二）二阶段法 构造一个辅助问题： 1 0, 0 min m i i AX y b X y z y = + = = (16) 问题（14）和（16）的解之间有如下关系 定理 4 若（16）的最优基可行解为 0 X ，则 X 是（14）的一个可行解。若（16） 的最优基可行解为 X Y ，且 Y 0 ，则（14）没有可行解。 证明 前一结论显然成立，下面只证后者。用反证法。设 X 为（14）的一个可行解， 则 0 X 是（16）的一个可行解。它使目标函数 z 取 0 值。但此时（16）的最优值 z= 1 m i i y = = >0。 产生矛盾。故（14）不可能有可行解。 定理 4 的一个前提是（16）有最优解。这是不成问题的。显然，（16）有一个现成的基 可行解 , 1, , Y b i m i i = = ，X=0，又因目标函数值 z 1 m i i y = = 0。它在可行解集合上显然有 下界 0。故必有最优解（单纯形迭代只有两种结果：一是有最优解。一是可行解无下界）。 （16）的初始单纯形表具如下形式： 1 y … m y 1 x … n x 1 y m y 1 11 a … n a1 … … … 1 am1 … amn 1 b mb z 0 … 0 = m i i a 1 1 … = m i ain 1 = m i i b 1