参考案例成果1

1、1第六章 线性规划马昱春清华大学计算机系 22回顾标准形式Augmented form 一般形式General form)21(j 0 )21(i )( Z (min)max 11lxmbxaxcjnjijijnjjjLL=n variables，nlbi non-negative单纯型法(Simplex Method)顶点若S=XAXb,X0有解，则必可在的某个顶点上取得最大值。X是S的顶点的充要条件是X的非0元对应的A的列向量线性无关100040010004001021000122A=m=4Bx1 x2 x3 x4 x5 x6Bx=bx=B-1bx3=12; x4=8; x5=16; x6

2、=12CB=c1,c2cm为基变量对应的目标系数向量4找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环核心是：变量迭代100040010004001021000122A=b12816120.2500010010004-0.501001-0.500102P= P062163X1=(0,0,12,8,16,12)，Z1=0X2=(0,3,6,2,16,0), Z2=9Z= ?初等变换 B-1PjB-1Aj变量的变换 变量非负 目标函数增大5当 时， 为换入变量确定换出变量100040010004001021000122A=1281612Ax6=0, 成为非基变量，

3、与 x2交换变量的变换P0( 1 2 m )T再设 Pj(1j 2j mj )T，P06目标函数有所改善Z ( cjCBPj ),又因为PjB-1Aj，于是CBPjCBB-1Aj 同时 Z(X1)CBP0CBB-1b为了讨论方便，令 zjCBPjCBB-1Aj，jcjzj，称为检验数100040010004001021000122A=b1281612A初等变换 B-10.2500010010004-0.501001-0.500102P=P P062163目标函数： Z=CBP0= CBB-1bCB=c1,c2cm为基变量对应的目标系数向量PjB-1Aj，于是CBPjCBB-1Aj7收敛性讨论：

4、jcjzj， Z j,若存在j0,目标函数可改善 = (k/kj) 于是Aj进入，Ak退出，由原顶点X转到新顶点X若Pj= (1j 2j mj )T 0目标函数无上界，此线性规划问题无最优解若所有j0,目标函数已经达到最大，X是问题的解求极小问题则若所有j0,目标函数已经达到最大，X是问题的解Z ( cjCBPj ),8定理设X( 1 2 m 0 0 ) 是线性规划问题 maxZCX，AXb，X0的一个解.A1，A2，Am是X的正元对应的基 如果j0，j1，2， ，n+m，则X是最大值点 其中jcjCBB-1Aj。证设S是线性规划问题的允许解域，任给YS，Z(Y)CY根据假设j0，即jcjzj

5、 0 cjzj，j1，2， ,nm写成矩阵形式就是 C(CBB-1A1， CBB-1A2 , , CBB-1Aj )C CBB-1A 于是CY CBB-1AY， CY CBB-1b而B-1bP0，CBP0CX从而CYCX，即X是最大值点 Z ( cjCBPj ),9找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代结束其步骤总结如下：10问题是：max zc1x1+c2x2+cn+mxn+m，约束条件： x1, x2 , , xn+m0。B-1( b A1 A2 An+m )( P0 P1 P2 Pn+m ) j =cjCBPj1

6、1 1 c1c2cn+mCB123 XBZ=CBP01111 we can increase x1 to enlarge Z.（0，3，6，2，16，0）cj 2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4-Z-9 2 0 0 0 0 -3/46/2216/412 (1) 计算 z0及cjzj如果cjzj0，则不可能使目标函数有所改善,问题的最优解是xb1 P0(1)， xb2 P0(2) ， , xbm P0(m) ，xj0

7、，jb1 , b2 , , bm , 1 j n+m 目标函数值即为 z0 ( 2 ) 如若不然，进入的基Pj的选取应满足 cjzj0, 然而当n很大时，增加了很多计算量，所以也 可以选第一个cj zj0确定了进入基Pj后,计算 以确定退出的基Pk ( 3 )表中第k行第 j 列元素akj(0)取作主元素，对第 j 列进行消元 把所得的结果写入表，返回( 1 )这样周而复始，直至达到最优 B-1( b A1 A2 An+m )( P0 P1 P2 Pn+m ) j =cjCBPj1 1 1 c1c2cn+mCBXBZ=CBP013（四）、单纯形表P0保持非负14例 题：cj 2 3 0 0 0

8、 0cBxBP0 P1 P2 P3 P4 P5 P60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z0 15cj 2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z0 2 3 0 0 0 012/28/212/4cj 2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P6000 x3x4x5 Z3x23010001/42620100-

9、1/2100100-1/21640001016cj 2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/4Z9 2 0 0 0 0 -3/46/2216/4cj 2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P60203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/44412Z13 0 0 0 -2 0 1/4退化17cj

10、2 3 0 0 0 0cBxBP0 P1 P2 P3 P4 P5 P60203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 0Z14 0 0 -1/2 -1 0 0 0 0 0 -2 0 1/413Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 P1 P2 P3 P4 P5 P6P0 xBcB 2 3 0 0 0 0cjX1=4,x2=2得到最优解Zmax=1418cj 2 3 0 0 0 0cB

11、xBP0 P1 P2 P3 P4 P5 P60203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0Z14 0 0 0 -3/2 -1/8 0 0 0 0 -2 0 1/413Z4412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 P1 P2 P3 P4 P5 P6P0 xBcB 2 3 0 0 0 0cjX1=4,x2=2得到最优解Zmax=1419X1=4,x2=2得到最优解Z=2*

12、4+3*2=142*4+2*2=124+2*2=84*4=164*2=81220cj 3 6 2 0 0cBxBP0 P1 P2 P3 P4 P500 x4x521 3 4 1 1 0 1 3 2 0 1 Z0 3 6 2 0 01/32/421cj 3 6 2 0 0cBxBP0 P1 P2 P3 P4 P500 x4x521 3 4 1 1 0 1 3 2 0 1 Z0 3 6 2 0 01/32/4cj 3 6 2 0 0cBxBP0 P1 P2 P3 P4 P506x4x2 Z 1 0 -2 0 -212/51/3 1/3 1 2/3 0 1/32/3 5/3 0 -5/3 1 -4/

13、3 222cj 3 6 2 0 0cBxBP0P1 P2 P3 P4 P536x1x2 Z 0 0 -1 -3/5 -6/5cj 3 6 2 0 0cBxBP0 P1 P2 P3 P4 P506x4x22/31/3 5/3 0 -5/3 1 -4/3 1/3 1 2/3 0 1/3 Z2 1 0 -2 0 -212/5故最优解为x1=2/5,x2=1/5,目标函数z=12/5 1/5 0 1 1 -1/5 3/5 2/5 1 0 -1 3/5 -4/5 12/523cj 1 0 0 0 2 -1cBxBP0 P1 P2 P3 P4 P5 P602-1x4x5x645/75/76/7-12/7

14、1/14 5/14 1 0 0 1/7 -3/14 -1/14 0 1 0-3/7 1/7 -2/7 0 0 1Z4/7 2/7 4/7 -1/7 0 0 0-10/390624cj 1 0 0 0 2 -1cBxBP0 P1 P2 P3 P4 P5 P6020 x4x5x2 Z 2 0 1 0 0 0由于c1z10，但P1(3/2 ,1/2,3)T,所有元素都为负数，故问题无界解 cj 1 0 0 0 2 -1cBxBP0 P1 P2 P3 P4 P5 P602-1x4x5x645/75/76/7-12/7 1/14 5/14 1 0 0 1/7 -3/14 -1/14 0 1 0-3/7

15、1/7 -2/7 0 0 1Z4/7 2/7 4/7 -1/7 0 0 0-10/39066 -3 1 -2 0 0 72 -1/2 0 -1/2 0 1 06 -3/2 0 1/2 1 0 -1/2Z ( cjCBPj ),25进入基的选择若j0，则Aj进入基阵可使目标函数增大选择最大的j?当问题规模十分大时,计算量可观,而且有退化现象不能保证迭代次数少?26例cj 3 2 0 0cBxBP0 P1 P2 P3 P400 x3x445 2 1 1 0 5 1 0 1Z0 3 2 0 012(1)27cj 3 2 0 0cBxBP0 P1 P2 P3 P400 x3x445 2 1 1 0 5

16、 1 0 1Z0 3 2 0 012cj 3 2 0 0cBxBP0 P1 P2 P3 P403x3x1 Z 0 7/5 0 -3/5510/3(2)1 1 1/5 0 1/52 0 3/5 1 -2/5328cj 3 2 0 0cBxBP0 P1 P2 P3 P403x3x121 0 3/5 1 -2/5 1 1/5 0 1/5Z3 0 7/5 0 -3/5510/3cj 3 2 0 0cBxBP0 P1 P2 P3 P423x2x1 Z 1-5(3)10/3 0 1 5/3 -2/31/3 1 0 -1/3 1/323/3 0 0 -7/3 1/329cj 3 2 0 0cBxBP0 P1

17、 P2 P3 P423x2x110/31/3 0 1 5/3 -2/3 1 0 -1/3 1/3Z23/3 0 0 -7/3 1/31-5cj 3 2 0 0cBxBP0 P1 P2 P3 P420 x2x4Z 8 -1 0 -2 0X1=0,x2=4,maxZ = 8(4)1 3 0 -1 14 2 1 1 030选较小的j进入(1)cj 3 2 0 0cBxBP0 P1 P2 P3 P400 x3x445 2 1 1 0 5 1 0 1Z0 3 2 0 054cj 3 2 0 0cBxBP0 P1 P2 P3 P420 x2x4Z 8 -1 0 -2 0X1=0,x2=4,maxZ = 8

18、1 3 0 -1 14 2 1 1 0Blands ruleBlands rule Robert G. Bland, now a professor of operations research atCornell University. An algorithmic refinement of the simplex methodChoose the lowest-numbered (i.e., leftmost) nonbasic columntwith a positive cost. s_rule 32改善的单纯形法单纯形法在进行列消元时相当于左乘以某一基矩阵B的逆所以计算B是关键若求

19、得B1, 便可计算PjB1Aj，jCjZjCjCBB1Aj因而计算j时CB B1是公共部分，可以先计算因为CBB1Aj (CBB1) Aj CB( B1Aj )，故在原有的单纯形表格中要增加一列CBB1, B1存于A中的m阶单位矩阵的单元中 100040010004001021000122A=b1281612A初等变换 B-10.2500010010004-0.501001-0.500102P=P P062163B-1( b A1 A2 An+m )( P0 P1 P2 Pn+m ) 331953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法。其基本步

20、骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。对于线性规划问题改善的单纯形法计算步骤如下：( a )计算B1，B1b，( b )计算CBB1, CBB1b，( c )计算jCjCBB1Aj，j1 , 2 , ,n+m.若所有j0，计算结束由P0所确定的Z(X)便是所求的目标函数最大值否则令cjzjmax cl zlcl zl0或遵循bland法则.( d ) PjB1Aj，计算相应的，确定主元素及退出基，设为Pk，以Aj取代Ak，返回( a

21、 )34cj -1 -1 4 0 0 0cBxBCBB-1P0 P1 P2 P3 P4 P5 P6000 x4x5x6000924 1 1 2 1 0 0 1 1 -1 0 1 0 -1 1 1 0 0 1Z 4-1/29/24jCjCBB1AjB-1( b A1 A2 An+m )( P0 P1 P2 Pn+m ) j =cjCBB-1Aj1 1 1 c1c2cn+mCBXBZ=CBP0CBB-135cj -1 -1 4 0 0 0bA1 A2 A3 A4 A5 A6924 1 1 2 1 0 0 1 1 -1 0 1 0 -1 1 1 0 0 1cj -1 -1 4 0 0 0cBxBCB

22、B-1P0 P1 P2 P3 P4 P5 P6004x4x5x3 0 1 0 -2 0 0 1 1 1 0 0 1Z 3 -1/3-400416430-1jCjCBB1Ajx6出，x3入PjB1Aj36cj -1 -1 4 0 0 0cBxBCBB-1P0 x1 x2 x3 x4 x5 x6-104x1x5x3 1 1/3 0 -2/3 0 0 1 10 1/3 0 1/3Z 0 -4 0 -1 0 -2 1021/3613/3cj -1 -1 4 0 0 0bA1 A2 A3 A4 A5 A69241 1 2 1 0 0 1 1 -1 0 1 0-1 1 1 0 0 1CBB-1 Z 0 1

23、 0 -2 0 0 1 1 1 0 0 1x4x5x3004 P1 P2 P3 P4 P5 P6P0 xBcB -1 -1 4 0 0 0cj3 -1/3-400416430-1jCjCBB1Aj1737（一）、模型情况 变 量：xj0 xj0 xj无约束 结1、组成 约束条件： = b 目标函数： max min 果2 、变量 xj0 令 xj= -xj ， xj0 xj0 不处理 xj 无约束 令xj = xj xj, xj0 , xj0 唯一最优无穷最优无界解无可行解单纯形法的进一步讨论385单纯形法的进一步讨论不同标准型的判别准则:maxmin最优解换入变量换出变量j 0j 0若存在非

24、基变量对应的j =0，则存在无穷多个最优解讨论405.1人工变量标准化后找不到单位阵，采用人造基给方程加入人工变量由于所添加的剩余变量的技术系数为1，不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量称为剩余变量413、约束 条件：加入松弛变量加入人工变量先减去 再加上例：424、目标函数：max , min 设规划模型约束条件为 ，需加入人工变量 ，而得到一个mm的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。 若当 ，而还有人

25、工变量（非零）时，则表示原问题无可行解。43 加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。 即假定人工变量在目标函数中的系数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。.大M法：44cj-31100MMcBxBbP1P2P3P4P5P6P70 x4111-21100011Mx63-4120-1103/2Mx71-20100011Z-3+6M1-M1-3M0M00cBxBbP1P2P3P4P5P6P70 x4103-20100-1Mx610

26、100-11-211x31-2010001Z-11-M00M03M-145cj-31100MMcBxBbP1P2P3P4P5P6P70 x4123001-22-541x210100-11-21x31-2010001Z2-10001M-1M+1cBxBbP1P2P3P4P5P6P7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3Z-20001/31/3M-1/3M-2/3最优解为（4 1 9 0 0 0 0），Z = 246 用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。 第一阶段： 在原线性规

27、划问题中加入人工变量，构造如下模型：.两阶段法：47对上述模型求解（单纯形法），若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。 第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。例：第一阶段48cj0000011cBxBbP1P2P3P4P5P6P70 x4111-211000111x63-4120-1103/21x71-20100011Z46-1-301000 x4103-20100-11x610100-11-210 x31-2010001Z10-1001030 x4123001-22-50 x210100-11-20 x31-2010000Z0000001149cj-31100cBxBbP1P2P3P4P50 x4123001-241x210100-11x31-20100