运筹学-单纯形矩阵描述与改进单纯形法课件.pptx

1、1第1节 单纯形法的矩阵描述 设线性规划问题可以用如下矩阵形式表示：目标函数 max z=CX 约束条件 AXb 非负条件 X02 将该线性规划问题的约束条件加入松弛变量后，得到标准型：max z=CX+0Xs AX+IXs=b X，X s0其中I 是mm单位矩阵。3 若以Xs为基变量，并标记成XB，可将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分：相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作 C=（CB,CN）NBXXX4线性规划问题可表示为：)23(0,X)22(BX)12(

2、CzmaxBBBNNNNBXbNXXCX非负条件约束条件目标函数将（2-2）式移项及整理后得到：NBNBNBNBXNBCCbBCzNXBbBXNXbBX)(;1111目标函数：5令非基变量=0，由上式得到：bB;bBX)(1B11Cz0目标函数的值基可行解6（1）非基变量的系数表示为：)|(C-C),2,1(c)(1Bj1NBBnjzNBCCjBN所有检验数可表示为：对应已用的检验数符号7（2）单纯形表与矩阵表示的关系)72(0101111bBCbBXXzNBCCNBIBNBBNbBCXNBCCzbBNXBXBNBNNB1111-)(-;目标函数：8单纯形表中的数据基变量 非基变量等式右边系数

3、矩阵检验数0I1BBXBbBCNBCCbBNBRHSXBBNN1111 9单纯形表中的数据基变量 非基变量松弛变量松弛变量 等式右边系数矩阵检验数01IBBXBbBCBCNBCCbBBNBRHSXXBBBNsN11111110（3）规则表示为：RHS值 表示选用0的分量 换入变量的系数向量ljlijijiPBbBPBPBbB)()(0)()()(min1111111小结1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。12求解线性规划问题的关键是计算B-1，以下介绍一种比较简便的计算B-1的方法。设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。mmmmmmaaaaa

4、aaaaA21222211121113以a11为主元素,进行变换)1(/11111121111112111aaaaaaaaPmm主元素14然后构造构造含有（1）列，而其他列都是单位列的矩阵1/1/00/11111121111aaaaaEm15可得到)(mm)(m)(m)()(m)(aaaaaaAE;PE11212122111121110010011121122211211121aaaaaaaa16)(a122而后以第2列的 为主元素，进行变换)(a/aa/a/aP)()(m)()()()(2112212122122112212171001001122121221221122)()(m)()()

5、(a/aa/a/aE然后构造构造含有（2）列，而其他列都是单位列的矩阵可得到)(mm)(m)(m)(m)()(aaaaaaAEE22221232232131200100118重复以上的步骤，直到获得IAEEEm11112可见EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-1 19第2节 改进单纯形法以例1为例进行计算。1241648200032524132154321xxxxxxxxxxxxzmax20第2节 改进单纯形法第第1步步：确定初始基，初始基变量;确定换入、换出变量（1）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入变量。54354300111xxx

6、X;P,P,PBB换入变量对应注意：212100103240204110001000100032000 x,x,),(,)P,PN(NBCCBNN21第2节 改进单纯形法(3)确定换出变量5341201628021021010 x,minPBPBbBminii对应表示选择0的元素22第2节 改进单纯形法（4）基变换计算将新的基 单位矩阵。计算：243P,P,P410121141021402112/E/P；构造主元素4/1012/111114/1012/1110111BEB23（5）计算非基变量的系数矩阵（6）计算RHS410214114141012111411111/NBN3162121684

7、10121111/bB24第2节 改进单纯形法第1步计算结束后的结果),(),(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基25第2节 改进单纯形法第第2步：步：计算非基变量的检验数，确定换入变量换入变量对应注意：515111114321000414100010210130002111x,x/,/),(,)P,PN(NBCCBNN26第2节 改进单纯形法确定换出变量3203,416,12min0min11111111xPBPBbBii对应27由此得到新的基 4/1002142/1014/1000102/101100014

8、001100014001041041,1121221112412BEBEPBPPPB2主元素28计算RHS382121684100214210112/bB29第2步计算结束后的结果),(),(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB003022222532412412价值系数非基变量基变量基30第3步：计算非基变量（x3,x5）的检验数换入变量正检验数对应注意：535322124121000014100314210130200222x,x/,/),(,)P,PN(NBCCBNN31确定换出变量4441328212051251212x/,/minPBPBbBminii对应32新

9、的基主元素的系数向量是换入变量4/122/11004/1002142/101;,51252513PBxPPPB基变换：33计算B的逆矩阵18/1002/1004/118/12/14/133E构造08121121204104100214210118100210041112313/BEB34计算非基变量的检验数已无正检验数注意：8/1,2/301000108/12/112/1204/10)3,0,2(0,0,433313333PPNNBCCBNN35得到最优解：244128/12/1162/1284/1013251*bBxxxX1424430213,bBCzB*目标函数的最优值为：36改进单纯形法

10、步骤改进单纯形法步骤1.求线性规划的标准形式，确定-1000000,BBCCXXNBNB及其逆矩阵和初始基，。，。确定，从而计算，）求（。规则求出换出变量，根据，计算可得）从（。，确定换入变量，从而求出）求（11111111111110k10010010000010,321 2.NBNBlkBNNCCXXbBNBBExbBPBNBxNBCCNB3.重复第2步（下标加1），直至求出最优解。37第6节 对偶单纯形法v在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解基解。v通过逐步迭代，当在检验数行得到对偶问题的解也是基可当在检验数行得到对偶问题的解也是基

11、可行解时，已得到最优解。即原问题与对偶问题都是最优解。行解时，已得到最优解。即原问题与对偶问题都是最优解。v根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到最优解。38cj-2-3-4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5-3-4-1-2-2 1-1-3 1 0 0 1 cj-zj-2-3-4 0 0 从该表看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。39对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：(1)把线性规划转化

12、为“近似标准形式近似标准形式”，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量换出变量。按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量 (3)确定换入变量换入变量。在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有所有lj0，则无可行解，则无可行解，停止 计算。若存在lj0 (j=1,2,，n),计算 lkkkljljjjjazcaazc0min40按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问

13、题解仍为可行解。(4)以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)(4)。41v例6 用对偶单纯形法求解min w=2x1+3x2+4x3x1+2x2+x332x1x2+3x34x1，x2，x30 解：解：先将此问题化成下列形式，以便得到对偶问题的初始基可行解max z=2x1 3x2 4x3 x1 2x2 x3+x4 =32x1+x2 3x3 +x5=4xj0，j=1,2,542v例6的初始单纯形表，见表2-6。cj-2-3-4 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5-3-4-1-2-2 1-1-3 1 0 0 1 cj-z

14、j-2-3-4 0 0 从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。43v换出变量的确定：v换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有若所有lj0，则无可行解，则无可行解，停止 计算。按上述对偶单纯形法计算步骤(2)，即按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算min(3,4)=4故x5为换出变量。12234,22min故x1为换入变量。换入、换出变量的所在列、行的交叉处“2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。44由表

15、2-7 看出，对偶问题仍是可行解，而 b 列中仍有负分量。故重复上述迭代步骤，得表 2-8。45表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)46对偶单纯形法有以下优点：对偶单纯形法有以下优点：l(1)初始解可以是非可行解初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量不需要加入人工变量，因此可以简化计算。l(2)当变量多于约束条件变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计

16、算工作量，因此对变量较少，而对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。l(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。l对偶单纯形法的主要局限性主要局限性：对大多数线性规划问题，很难找到一个初始基。3.3.对偶理论对偶理论 slide 58slide 58：例题：例题作业作业3 3：1.1.课本课本P74.P74.2.3 2.3 (2)(2)、(3)(3)2、写出下列线性规划问题的对偶问题。321422minxxxz无约束321321321321,0

17、,534332243xxxxxxxxxxxx 3、试用对偶单纯形法求解下列线性规划问题。21minxxz0,3742212121xxxxxx 作业作业4 4：4.4.课本课本P76.P76.2.9(1)-(5)2.9(1)-(5)49第8节*参数线性规划v灵敏度分析主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。v参数线性规划研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值。即把某一参数作为参变量，而目标函数在某区间内是这个参变量的线性函数，含这个参变量的约束条件是线性等式或不等式。v因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题。其步骤是：50第8节*

18、参数线性规划v(1)对含有某参变量t的参数线性规划问题。先令t=0，用单纯形法求出最优解；v(2)用灵敏度分析法，将参变量t直接反映到最终表中；v(3)当参变量t连续变大或变小时，观察b列和检验数行各数字的变化。若在b列首先出现某负值时，则以它对应的变量为换出变量；于是用对偶单纯形法迭代一步。若在检验数行首先出现某正值时，则将它对应的变量为换入变量；用单纯形法迭代一步；v(4)在经迭代一步后得到的新表上，令参变量t继续变大或变小，重复步骤(3)，直到b列不能再出现负值，检验数行不能再出现正值为止。51参数参数c c的变化的变化0,18231224)5()23()(max21212121xxxx

19、xxxtxttzv例12 试分析以下参数线性规划问题。当参数t0时的最优解变化。解：解：将此模型化为标准型0,18231224)(0)5()23()(max54321521423154321xxxxxxxxxxxxxxxxtxttz52cj 3 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 3 x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 0 1/3 1/2 1/3-1/3 0 1/3 cj-zj 0 0 0-3/2-1 令令t=0，用单纯形法求解的结果，见表，用单纯形法求解的结果，见表2-20。将c的变化直接反映到最终表2-20中，得表2-21。cj

20、3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5-t 3+2t x3 x2 x1 2 6 2 0 0 1 0 1 0 1 0 0 1/3 1/2 1/3-1/3 0 1/3 cj-zj 0 0 0-(3/2)+(7/6)t-1-(2/3)t 计算t的变化范围53当 t 值变化，在40，即0t9/7时，为最优解(2,6,2,0,0)T；当 t 值增大，t(3/2)/(7/6)=9/7时，在检验数行首先出现40；表示还可以继续改进。t=9/7为第一临界点。当t9/7时，40，这时x4作为换入变量。用单纯形法迭代一步，得表2-22。cj 3+2t 5-t 0 0 0

21、 CB XB b x1 x2 x3 x4 x5 0 5-t 3+2t x4 x2 x1 6 3 4 0 0 1 0 1 0 3-3/2 1 1 0 0-1 1/2 0 cj-zj 0 0(9/2)-(7/2)t 0-(5/2)+(1/2)t 54当t继续增大t(5/2)/(1/2)=5时，在检验数行首先出现50，在50，即9/7t5时，得最优解(4,3,0,6,0)T。t=5为第二临界点。当t5时，50，这时x5作为换入变量，用单纯形法迭代一步，得表2-23。cj 3+2t 5-t 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 3+2t x4 x5 x1 12 6 4 0

22、0 1 2 2 0 0-3 1 1 0 0 0 1 0 cj-zj 0 5-t-3-2t 0 0 t继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。55参数参数b b的变化分析的变化分析0,6263max21212121xxtxxtxxxxz例13 分析以下线性规划问题，当t0时，其最优解的变化范围。解解 将上述模型化为标准型 0,626)(03max43214213214321xxxxtxxxtxxxxxxxz56然后计算 03/13/13/13/21tttbB 令令t=0，用单纯形法迭代两次，求解的结果，见表，用单纯形法迭代两次，求解的结果，见表2-24

23、。将此计算结果反映到最终表将此计算结果反映到最终表2-24，得表，得表2-25。cj 1 3 0 0 CB XB b x1 x2 x3 x4 1 3 x1 x2 2-t 4 1 0 0 1 2/3 1/3-1/3 1/3 cj-zj 0 0-5/3-2/3 57参数参数b b的变化分析的变化分析在表2-25中进行分析，当t增大至t2时，则b0；即0t2时，最优解为(2t,4,0,0)T。当t2时，则b10；故将x1作为换出变量，用对偶单纯形法迭代一步，得表2-26 cj 1 3 0 0 CB XB b x1 x2 x3 x4 0 3 x1 x2-6+3t 6-t-3 1 0 1-2 1 1 0 cj-zj-2 0-3 0 从表2-26可见，当t6时，问题无可行解时，问题无可行解；当2t6时，问题的最优解为(0，6t，0，6+3t)T。作业作业3 3：1.1.课本课本P74.P74.2.3 2.3 (2)(2)、(3)(3)2、写出下列线性规划问题的对偶问题。321422minxxxz无约束321321321321,0,534332243xxxxxxxxxxxx 3、试用对偶单纯形法求解下列线性规划问题。21minxxz0,3742212121xxxxxx 作业作业4 4：4.4.课本课本P76.P76.2.9(1)-(5)2.9(1)-(5)