运筹学课件ch02

1、二 线性规划与目标规划n第第1 1章章 线性规划与单纯形法线性规划与单纯形法n第2章 对偶理论与灵敏度分析n第3章 运输问题n第4章 目标规划第2章 对偶理论和灵敏度分析n第1节 单纯形法的矩阵描述 n第2节 改进单纯形法n第3节 对偶问题的提出n第4节 线性规划的对偶理论n第5节 对偶问题的经济解释影子价格n第6节 对偶单纯形法n第7节 灵敏度分析n第8节* 参数线性规划第第2章线性规划的对偶理论与灵敏度分析章线性规划的对偶理论与灵敏度分析1、掌握对偶理论及其性质、掌握对偶理论及其性质2、掌握对偶单纯形法、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容、熟悉灵敏度分析的概念和内容4、掌握限制

2、常数与价值系数、约束条件系数的变化对、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法、了解参数线性规划的解法第1节 单纯形法的矩阵描述 设线性规划问题可以用如下矩阵形式表示： 目标函数 max z=CX 约束条件 AXb 非负条件 X0第1节 单纯形法的矩阵描述 将该线性规划问题的约束条件加入松弛变量后，得到标准型： max z=CX+0Xs AX+IXs=b X，X s0其中I 是mm

3、单位矩阵。 第1节 单纯形法的矩阵描述 若以Xs为基变量，并标记成XB，可将系数矩阵（A，I）分为（B，N）两块。B是基变量的系数矩阵，N是非基变量的系数矩阵。并同时将决策变量也分为两部分： 相应地可将目标函数系数C分为两部分：CB和CN，分别对应于基变量XB和非基变量XN，并且记作 C=（CB, CN）NBXXX第1节 单纯形法的矩阵描述 若经过迭代运算后，可表示为：相应有;XXXXXXSNNSBB2111非基变量：变量可包含原基变量和松弛基变量非基变量基变量松弛变量：其中系数矩阵2121SSSXXX;SNN;NBA第1节 单纯形法的矩阵描述线性规划问题可表示为：)(X,)(bXSXNBXN

4、X)(XCXCXCXCXNSNBNSSNNBBNNB230X22BX12CzmaxB21BB212211非负条件约束条件目标函数第1节 单纯形法的矩阵描述将（2-2）式移项及整理后得到：SBSNBNBsNBSNBX)IBCC(X)NBCC(bBCz;XSBXNBbBX;XSXNbBX111121111212112121目标函数：第1节 单纯形法的矩阵描述令非基变量=0，由上式得到：bB;bBX)(1B11Cz0目标函数的值基可行解第1节 单纯形法的矩阵描述（1）非基变量的系数表示为：1B1Bj11C-C-C21c1BAB)n,j(z)NBCC(jBN与检验数也可表示为：对应已用的检验数符号第1

5、节 单纯形法的矩阵描述 （2）规则表示为： RHS值 表示选用0的分量 换入变量的系数向量ijiijiji)PB()bB()PB()PB()bB(min111110第1节 单纯形法的矩阵描述（3）单纯形表与矩阵表示的关系)(bBCbBXXXzBCNBCCBNBBNNBBBN7201101111111121 第1节 单纯形法的矩阵描述单纯形表中的数据基变量 非基变量等式右边系数矩阵检验数011BBXBbBCBCNBCCbBBNBRHSXXBBBNsN111111111小结1）掌握矩阵的运算；2）理解基矩阵的作用；3）了解矩阵运算与单纯表的关系。第2节 改进单纯形法求解线性规划问题的关键是计算B-

6、1 ，以下介绍一种比较简便的计算B-1的方法。第2节 改进单纯形法设mn系数矩阵为A，求其逆矩阵时，可先从第1列开始。mmmmmmaaaaaaaaaA212222111211第2节 改进单纯形法以a11为主元素, 进行变换)(a/aa/aa/aaaPmm111111121111112111主元素第2节 改进单纯形法然后构造构造含有（1）列，而其他列都是单位列的矩阵1/1/00/11111121111aaaaaEm第2节 改进单纯形法可得到)(mm)(m)(m)()(m)(aaaaaaAE;PE11212122111121110010011121122211211121aaaaaaaa第2节 改

7、进单纯形法)(a122而后以第2列的 为主元素，进行变换)(a/aa/a/aP)()(m)()()()(2112212122122112212第2节 改进单纯形法1001001122121221221122)()(m)()()(a/aa/a/aE然后构造构造含有（2）列，而其他列都是单位列的矩阵可得到)(mm)(m)(m)(m)()(aaaaaaAEE222212322321312001001第2节 改进单纯形法重复以上的步骤，直到获得112111AAEEEm可见EnE2E1=A-1。用这方法可以求得单纯形法的基矩阵B的逆矩阵B-1 第2节 改进单纯形法以例1为例进行计算。1241648200

8、032524132154321xxxxxxxxxxxxzmax第2节 改进单纯形法第1步：确定初始基，初始基变量;确定换入，换出变量（1）确定初始基和初始基变量： （2）计算非基变量的检验数，确定换入变量。54354300111xxxX;P,P,PBB换入变量对应注意：212100103240204110001000100032000 x ,x,),(,)P,PN(NBCCBNN第2节 改进单纯形法(3) 确定换出变量5341201628021021010 x,minPBPBbBminii对应表示选择0的元素第2节 改进单纯形法（4）基变换计算将新的基 单位矩阵。计算：243P,P,P4101

9、21141021402112/E/P；构造主元素4101211111410121110111/BEB第2节 改进单纯形法（5）计算非基变量的系数矩阵（6）计算RHS410214114141012111411111/NBN316212168410121111/bB第2节 改进单纯形法第1步计算结束后的结果),(),(C,CC;x ,xX;x ,x ,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基第2节 改进单纯形法计算非基变量的检验数，确定换入变量换入变量对应注意：515111114321000414100010210130002111x ,x/,/)

10、,(,)P,PN(NBCCBNN第2节 改进单纯形法确定换出变量120341612011111111x,minPBPBbBminii对应第2节 改进单纯形法由此得到新的基 410021421014100010210110001400110001400104104111212212412/BEBEPP,P,PB2主元素第2节 改进单纯形法计算RHS382121684100214210112/bB第2节 改进单纯形法第2步计算结束后的结果),(),(C,CC;x ,xX;x ,x ,xX;P,P,PBNBTNTB003022222532412412价值系数非基变量基变量基第2节 改进单纯形法第3步

11、：计算非基变量（x3, x5）的检验数换入变量正检验数对应注意：535322124121000014100314210130200222x ,x/,/),(,)P,PN(NBCCBNN第2节 改进单纯形法确定换出变量4441328212051251212x/,/minPBPBbBminii对应第2节 改进单纯形法新的基主元素的系数向量是换入变量4/122/11004/1002142/101;,51252513PBxPPPB第2节 改进单纯形法计算B的逆矩阵18100210041181214133/E/构造08121121204104100214210118100210041112313/BEB

12、第2节 改进单纯形法计算非基变量的检验数已无正检验数注意：8123010001081211212041030200433313333/,/),(,P,PNNBCCBNN第2节 改进单纯形法得到最优解：244128/12/1162/1284/1013251*bBxxxX1424430213,bBCzB*目标函数的最优值为：第3节 对偶问题的提出v什么是对偶？对同一事物（或问题），从不同的角度（或立场）提出相对的两种不同的表述。v例如：在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。周长一定，面积最大的矩形是正方形。面积一定，周长最短的矩形是正方形。v这种表述有利于加深对事物的认识和

13、理解。v线性规划问题也有对偶关系。第3节 对偶问题的提出v对第1章例1从对偶的角度进行表述。假设该工厂的决策者决定不生产产品、，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品，可获利2元，那么生产每件产品的设备台时和原材料出租或出让的所有收入应不低于生产一件产品的利润，这就有 y1+4y22第3节 对偶问题的提出v对第1章例1从对偶的角度进行表述。同理将生产每件产品的设备台时和原材料出租或出让的所有收

14、入应不低于生产一件产品的利润，这就有 2y1+4y33把工厂所有设备台时和资源都出租或出让，其收入为 w = 8y1+16y2+12y3从工厂的决策者来看当然w愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题：第3节 对偶问题的提出 称这个线性规划问题为例1线性规划问题(这里称为原问题)的对偶问题。这就是从另一角度提出的线性规划问题。min w=8y1+16y2+12y3 y1+4y2 2 2y1 +4y33 yi0，i=1,2,3 (2-8)第3节

15、对偶问题的提出进一步来讨论它们之间的关系。从第1节得到检验数的表达式是 CNCBBN-1与CBB-1由第1章已知：当检验数 CNCBBN-10 (2-9) CBB-10 (2-10) 时，表示线性规划问题已得到最优解。这也是最优解的判断条件。 第3节 对偶问题的提出现在讨论这两个条件。v(1) 由于(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘子，用符号Y= CBB-1表示。由(2-10)式，得到Y0v(2) 对应基变量XB的检验数是0，CBCBB-1B=0。包括基变量在内的所有检验数可用C CBB-1A0表示。 从此可得CCBB-1A=CYA0，移项后，得到YACv(3)

16、Y由(2-10)式，得到 Y= CBB-1 (2-11) 将(2-11)式两边右乘b，得到 Yb= CBB-1b (2-12) Yb= CBB-1b=z，因Y的上界为无限大，所以只存在最小值。第3节 对偶问题的提出现在讨论这两个条件。v(4) 从这里可以得到另一个线性规划问题 min w=Yb YAC Y0 称它为原线性规划问题max z=CXAXb，X0的对偶规划问题 。第3节 对偶问题的提出对偶规划问题oy,y,yyyyyy,y,yYY,Yyyymin,YminT3213121321321342240324020411216812168约束条件：目标函数：第4节 线性规划的对偶理论4.1

17、原问题与对偶问题的关系4.2 对偶问题的基本性质1对称形式下对偶问题的一般形式对称形式下对偶问题的一般形式 定义：满足下列条件的线性规划问题称为具有对称形式定义：满足下列条件的线性规划问题称为具有对称形式：(1)其变量均为非负约束；其变量均为非负约束；(2)其约束条件当目标函数求极其约束条件当目标函数求极大时取大时取“”号，当目标函数求极小时取号，当目标函数求极小时取“”号；号；(3)右端项右端项b可取负值。可取负值。 ), 1(0max:221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczLPjmnmnmmnnnnnn ), 1(0m

18、in:221122222112112211112211miycyayayacyayayacyayayaybybybwDPinmmnnnmmmmmm ), 1(0max:221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczLPjmnmnmmnnnnnn4.1 原问题与对偶问题的关系v对称型原问题与对偶问题的关系minmaxzmaxzmin21212222212111211121mnmmnmmmnnnijcccbaaaybaaaybaaayxxxyx对偶关系原关系4.1 原问题与对偶问题的关系v例2 根据表2-3写出原问题与对偶问题的表达式

19、 x y x1x2by1111y2222y3888c444.1 原问题与对偶问题的关系v下列形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP)032240124164821216832321312121212132121y,y,yyyyyx ,xxxxxyyyminxxzmax2、非对称形式的原对偶问题关系、非对称形式的原对偶问题关系 并非所有的LP问题都有对称形式，故讨论一般情况下LP问题如何写出其对偶问题例例 写出下述线性规划的对偶问题写出下述线性规划的对偶问题无约束321321321321321004163253234maxxxxxxxxxxxxxxxxz解：先化为对称形式，解

20、：先化为对称形式， 4 4 1 6632 5532 334max33213321332133213321xxxxxxxxxxxxxxxxxxxxz0 , , ,3 653 654 31 32 442min332133213321332133213321yyyyyyyyyyyyyyyyyyyyyyyyw , 33322yyyyy令令 ,将上边将上边3,4两个约束条件合并两个约束条件合并,得得 无约束321321321321321003654313242minyyyyyyyyyyyyyyyw4.1 原问题与对偶问题的关系v非对称形式的变换关系原问题的约束条件中含有等式约束条件时，按以下步骤处理。设

21、等式约束条件的线性规划问题为 n ,j ,xm,i,bxaxczmaxjnjijijnjjj21021114.1 原问题与对偶问题的关系v非对称形式的变换关系第一步：先将等式约束条件分解为两个不等式约束条件njjijnjjijnjjijjnjijijnjjjm,ibxam,jbxam,jbxan ,j ,xm,i,bxaxczmax11111142212113221210214.1 原问题与对偶问题的关系v非对称形式的变换关系第二步：按对称形式变换关系可写出它的对偶问题o设yi是对应(2-13)式的对偶变量，yi是对应(2-14)式的对偶变量，i=1,2,，mm,i,y,yn,j ,cyaya

22、ybybmin iimijmi iijiijmimi iiii2102111114.1 原问题与对偶问题的关系02111 ii iiimij iiijmi iiiy,y,yyyn ,j,cyyayybmin令将上述规划问题的各式整理后得到m,.iyn ,j,cyaybminimijiijmiii212111，为无约束4.1 原问题与对偶问题的关系综合上述，线性规划的原问题与对偶问题的关系可表示为：RHSRHS0000mn00nminzmax约束条件的目标函数变量系数目标函数变量的系数约束条件量变无约束个个件条束约件条束约个无约束个量变目标函数目标函数对偶问题原问题m4.1 原问题与对偶问题的关

23、系例3 试求下述线性规划原问题的对偶问题 无约束43213432243114321432100362422153532x,x ,x,xyxxxyxxxyxxxxxxxxzmin4.1 原问题与对偶问题的关系由表2-4中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题，无约束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax4.2 对偶问题的基本性质v(1) 对称性：对偶问题的对偶是原问题 ;v(2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb;v(3) 无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题

24、)无可行解; v(4) 可行解是最优解时的性质 ;v(5) 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等;v(6) 互补松弛性 ;v(7) 原问题检验数与对偶问题解的关系。 4.2 对偶问题的基本性质v(1) 对称性： 对偶问题的对偶是原问题。 证明：设原问题是max z=CX; AXb； X0根据对偶问题的对称变换关系，可以找到它的对偶问题是min w=Yb; YAC； Y0若将上式两边取负号，又因min w=max(-w)可得到max(w)=Yb; YA C； Y0根据对称变换关系，得到上式的对偶问题是min( w)= CX； AX b; X0又因 min(w)=m

25、ax w，可得Max w=max z=CX； AXb; X0这就是原问题。4.2 对偶问题的基本性质bYXCYX存在是对偶问题的可行解则是原问题的可行解，若v(2)弱对偶性0Xb;AXCX;zmax设原问题是bXAX即以满足约束条件是原问题的可行解，所因,左乘上式，得到将是对偶问题的可行解，若YY0;min:YCYAYb原问题的对偶问题是CAYY所以满足是对偶问题的可行解，因.,XCXAYX得到右乘上式将.证毕于是得到bYXAYXCbYXAY4.2 对偶问题的基本性质是不可能成立。,XCbYv(3) 无界性 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。0,1120,242mi

26、nmax:2121212121212121yyyyyyxxxxxxyyxxzDPLP例v从两图对比可明显看到原问题无界，其对偶问题无可行解y1y20,1120,242minmax:2121212121212121yyyyyyxxxxxxyyxxzDPLP例4.2 对偶问题的基本性质v(4) 可行解是最优解时的性质 设 是原问题的可行解， 是对偶问题的可行解， 当 时， 是最优解。XbYXCY,XY证毕。所以是最优解存在，的所有可行解同理可证明，对原问题最优解最小的可行解，因而是可见是使目标函数取值所以因都存在所有可行解可知，对偶问题的，根据性质证：若.,.,;2XCbYXCXbYbYbYXCX

27、CbYYbYXC4.2 对偶问题的基本性质, 0,1ABCCBXB必存在对应的基矩阵是原问题的最优解，它证：设v(5) 对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。是对偶问题的最优解。得可见由性质得YXCbBCbYB, 4,11BCYB令.,可行解是原问题的对偶问题的所以又YCAY 0,YX得是原问题最优解由4.2 对偶问题的基本性质为最优解。当且仅当，和那么题的可行解，分别为原问题和对偶问若Y,X;XYXYY,XSS00v(6) 互补松弛性0,0,minSSSSYYXXCYYAbXAXYbCXzmax对偶问题原问题题的标准关系是证：设原问题和对偶问将原问题目标函数中

28、的系数向量C用C=YA-YS代替后，得到 z=(YA YS)X=YAX YSX (2-15)将对偶问题的目标函数中系数列向量b，用b=AX+XS代替后，得到 w=Y(AX+XS)=YAX+YXS (2-16)XYXYYbYAXCXSS1621524）式可知，有），（由（），则有根据性质（偶问题的最优解，又若分别是原问题和对是最优解。），可知由性质（则若YXXCXAYbY0XY0,XYSS,4,;0, 0XYXYSS4.2 对偶问题的基本性质v(7) 原问题检验数与对偶问题解的关系 设原问题是max z=CX; AX+XS=b; X,XS0 它的对偶问题是min w=Yb; YA YS=C; Y

29、,YS0 则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系见表2-5。YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。 YYYBCNBCCXXXSSBBNSNB21110v(7) 原问题检验数与对偶问题解的关系 证: 设B是原问题的一个可行基，于是A=(B,N)；原问题可 改写为max z=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS0相应地对偶问题可表示为 min w=Yb YB YS1=CB (2-17) YN YS2=CN (2-18)Y，YS1,YS20这里YS=(YS1，YS2)。当求得原问题的一个解：XB=B-1b,

30、其相应的检验数为 CN CBB-1N 与 CBB-1现分析这些检验数与对偶问题的解之间的关系：令Y=CBB-1,将它代入(2-17)式，得YB-YS1=CBB-1B-YS1=CB-YS1=CB,得YS1=0. 将Y=CBB-1代入(2-18)式得,YN-YS2=CBB-1N-YS2=CN,得YS2=CN CBB-1N证毕。 YYYBCNBCCXXXSSBBNSNB211104.2 对偶问题的基本性质v例4 已知线性规划问题max z=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。4.2 对偶问题的基本性质v上述问题的对偶问题为m

31、in w=2y1+y2-y1-2y21y1+ y21y1- y20y1，y20由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但无最优解。4.2 对偶问题的基本性质v例5 已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解 。4.2 对偶问题的基本性质v例5 已知线性规划问题 解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22

32、 3y1+y23 y1，y204.2 对偶问题的基本性质v例5 已知线性规划问题 将y1* =4/5,y2* =3/5的值代入约束条件，得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得 x2*=x3*=x4*=0。因y1，y20；原问题的两个约束条件应取等式，故有 x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；w*=5第5节 对偶问题的经济解释影子价格v在单纯形法的每步迭代中，目标函数取值z=CBB-1b，和检验数CN CBB-1N中都有乘子Y=CBB-1，那么Y的经济意义是什么?设B是m

33、ax z=CXAXb，X0的最优基，由(2-12)式可知 z*=CBB-1b=Y*b 对z求偏导数，得 *B*YBCbz1由上式可知，变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。第5节 对偶问题的经济解释影子价格v第1章中例1的影价格及其经济解释。 由表1-5可知cj23000 CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。 第5节 对偶问题的经济解释影子价格v第1章中例1的影价格及其经济解释。 这说明是其他条件

34、不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。 从图2-1可看到，设备增加一台时，代表该约束条件的直线由移至，相应的最优解由(4，2)变为(4，2.5)，目标函数z=24+32.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由移至，相应的最优解 从 ( 4 ， 2 ) 变 为 ( 4 . 2 5 ， 1 . 8 7 5 ) ， 目 标 函 数 z = 4.25+31.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由移至，

35、这时的最优解不变。第5节 对偶问题的经济解释影子价格v第1章中例1的影价格及其经济解释。 第5节 对偶问题的经济解释影子价格vyi*的值代表对第i种资源的估价影子价格。 这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应

36、把已有资源卖掉。可见影子价格对市场有调节作用。第6节 对偶单纯形法v前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。v通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。v根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cjCBB-1Pj0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。 第6节 对偶单纯形法v设

37、原问题为 max z=CX AX=b X0又设B是一个基。不失一般性，令B=(P1，P2，Pm)，它对应的变量为 XB=(x1，x2，,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是 (1) 对应基变量x1，x2，,xm的检验数是i=ci zi=ci CBB-1Pj=0，i=1,2,m (2) 对应非基变量xm+1，xn的检验数是j=cj zj=cj CBB-1Pj0，j=m+1,n第6节 对偶单纯形法v每次迭代是将基变量中的负分量xl取出，去替换非基变量中的

38、xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。第6节 对偶单纯形法v对偶单纯形法的计算步骤如下： (1) 根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。 (2) 确定换出变量。按min(B-1b)i(B-1b)i0(B-1b)l 对应的基变量xi为换出变量 (3) 确定换入变量。在单纯形表中检查xl 所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算

39、。若存在lj0 (j=1,2,，n), 计算 lkkkljljjjjazcaazc0min第6节 对偶单纯形法v对偶单纯形法的计算步骤如下： 按规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。 (4) 以lk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。 重复步骤(1)(4)。第6节 对偶单纯形法v例6 用对偶单纯形法求解min w=2x1+3x2+4x3x1+2x2+x332x1x2+3x34x1，x2，x30 解：解：先将此问题化成下列形式，以便得到对偶问题的初始可行基 max z= 2x1 3x2 4x3 x1 2x2 x3+x4 = 32x1

40、+x2 3x3 +x5= 4xj0，j=1,2,5第6节 对偶单纯形法v例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-zj -2 -3 -4 0 0 从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。 第6节 对偶单纯形法v换出变量的确定：v换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数lj(j=1,2,，n)。若所有lj0，则无可行解，停止 计算。按上述对偶单纯形法计

41、算步骤(2)，即按min(B-1b)i(B-1b)i0(B-1b)l对应的基变量xi为换出变量。计算min( 3, 4)= 4故x5为换出变量。 12234,22min故x1为换入变量。换入、换出变量的所在列、行的交叉处“2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。第6节 对偶单纯形法cj -2 -3 -4 0 0 CB XB b x1 x2 x3 x4 x5 0 -2 x4 x1 -1 2 0 1 -5/2 -1/2 1/2 3/2 1 0 -1/2 -1/2 cj-zj 0 -4 -1 0 1 由表 2-7 看出，对偶问题仍是可行解，而 b 列中仍有负分量。 故重复上述迭代步骤，

42、得表 2-8。 第6节 对偶单纯形法表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)第6节 对偶单纯形法从以上求解过程可以看到对偶单纯形法有以下优点：l (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。l (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单

43、纯形法求解。l (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第7节 灵敏度分析v以前讨论线性规划问题时，假定ij，bi, cj都是常数。但实际上这些系数往往是估计值和预测值。v如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。v因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内

44、变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。第7节 灵敏度分析v显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。设问题设问题0maxXbAXCXz相应的最优单纯形表为相应的最优单纯形表为Cjc1c2cnCBXBbx1x2xncB1cB2cBmxB1xB2xBmB-1bB-1A

45、=B-1(P1,P2,Pn)cj-zjC-CB B-1A7.1 资源数量变化的分析资源数量变化是指资源中某系数br发生变化即即b变成变成b=b+b，此时需修改表中第三列，此时需修改表中第三列即基变量的取值由即基变量的取值由XB=B-1b变为变为XB=B-1(b+ b) 目标函数值由目标函数值由Z= CB B-1b变为变为Z= CB B-1(b +b) 此时若此时若b0，则因为，则因为j没有改变，最优解仍是最优解，没有改变，最优解仍是最优解，否则，单纯形表对应的是新问题的一个正则解，此时需否则，单纯形表对应的是新问题的一个正则解，此时需用对偶单纯形法继续迭代。用对偶单纯形法继续迭代。 7.1 资

46、源数量变化的分析mrirrrrmrrirrrrraaabbabababBbBbBbBbBbbB111111110000)(新的最优解的值可允许变化范围用以下方法确定。7.1 资源数量变化的分析在最终表中求得的经过变化后的 b 列的所有元素， 要求bi+airbr0，i=1,2,m。由此可得 airbr-bi，i=1,2，m 当air0 时，br-bi/air； 当air0 时，br-bi/air；于是得到 新的最优解的值可允许变化范围用以下方法确定。0min0maxiririiriririiaabbaab7.1 资源数量变化的分析例如求第1章例1中第二个约束条件b2的变化范围。解：可以利用第1

47、章例1的最终计算表中的数据：cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 4 1 0 1 1/4 0 0 x5 4 0 0 -2 1/2 1 3 x2 2 0 1 1/2 -1/8 0 -z -14 0 0 -3/2 -1/8 0 7.1 资源数量变化的分析可计算b2：0008/12/14/12440008/12/112/1204/102440022211bbbBbB由上式，可得b24/0.25=16，b24/0.5=8，b22/0.125=16。所以b2的变化范围是8，16；显然原b2 =16，加它的变化范围后，b2的变化范围是8，32。7.1 资源数量变

48、化的分析2800040125. 05 . 015 . 02025. 001bB例7 从表1-5得知第1章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品，。求这时该厂生产产品，的最优方案。 解：先计算B-1b,将结果反映到最终表1-5中，得表2-10。cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4+0 4-8 2+2 1 0 0 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj 0 0 -1.5 -0.125 0 7.1 资源数量变化的分析由于表2-10中b列有负数，故用对

49、偶单纯形法求新的最优解。计算结果见表2-11。cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x3 x2 4 2 3 1 0 0 0 0 1 0 1 0 0.25 -0.25 0 0 -0.5 0.25 cj-zj 0 0 0 -0.5 -0.75 即该厂最优生产方案应改为生产4件产品，生产3件产品，获利z*=42+33=17(元)从表2.11 看出x3=2，即设备还有2小时未被利用。7.2 标函数中价值系数cj的变化分析v可以分别就cj是对应的非基变量和基变量两种情况来讨论。 (1) 若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是 j=

50、cjCBB-1Pj 或 当cj变化cj后，要保证最终表中这个检验数仍小于或等于零，即j=cjCBB-1Pj0 那么cj+cjYPj，即cj的值必须小于或等于YPjcj，才可以满足原最优解条件。这就可以确定cj的范围了。 miiijjjyac17.2 标函数中价值系数cj的变化分析v可以分别就cj是对应的非基变量和基变量两种情况来讨论。 (2) 若cr是基变量xr的系数。因crCB，当cr变化cr时，就引起CB的变化，这时 (CB+CB)B-1A=CBB-1A+(0，cr，0)B-1A =CBB-1A+cr(r1,r2,，rn) 可见，当cr变化cr后，最终表中的检验数是 j=cjCBB-1Ac

51、r rj，j=1,2,，n 若要求原最优解不变，即必须满足j0。于是得到 a7.2 标函数中价值系数cj的变化分析njacaacarjjrrjrjjrrj, 2 , 1;, 0;, 0当当cr可变化的范围是 0min0maxrjrjjjrrjrjjjaacaa7.2 标函数中价值系数cj的变化分析例8 试以第1章例1的最终表表1-5为例。 设基变量x2的系数c2变化c2，在原最优解不变条件下，确定c2的变化范围。解：解： 这时表1-5最终计算表便成为表2-12所示。 7.2 标函数中价值系数cj的变化分析若保持原最优解，从表2-12的检验数行可见应有由此可得c23 和c21。c2的变化范围为

52、3c21即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。0818025 . 122cc和7.3 技术系数ij的变化v例9 分析在原计划中是否应该安排一种新产品。以第1章例1为例。设该厂除了生产产品，外，现有一种新产品III。已知生产产品III，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。问该厂是否应生产该产品和生产多少? 解：解：分析该问题的步骤是： (1) 设生产产品II为x3台，其技术系数向量P3=(2,6,3)T，然后计算最终表中对应x3的检验数3=c3CB-13=5(1.5,0.125,0)(2,6,3)T=1.250 说明安排生产产品III是

53、有利的。7.3 技术系数ij的变化(2) 计算产品在最终表中对应 x3的列向量 25. 025 . 13620125. 05 . 015 . 02025. 0031PB 并将(1)，(2)中的计算结果填入最终计算表 1-5，得表 2-13(a)。 cj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x5 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 0 1 0 2 0.5 0.25 0.5 0.125 0 1 0 1.5 2 0.25 cj-zj 0 0 -1.5 -0.125 0 1.25 由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验

54、数，说明目标函数值还可以改善。7.3 技术系数ij的变化(3) 将x3作为换入变量，x5作为换出变量，进行迭代，求出最优解。计算结果见表2-13(b)，这时得最优解：x1=1,x2=1.5，x3=2。总的利润为16.5元。比原计划增加了2.5元。cj 2 3 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x5 2 0 3 x1 x3 x2 1 2 1.5 1 0 0 0 0 1 1.5 -1 0.75 -0.125 0.25 0.1875 -0.75 0.5 -0.125 0 1 0 cj-zj 0 0 -0.25 -0.4375 -0.625 0 7.3 技术系数ij的变化v

55、例10 分析原计划生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品的工艺结构有了改进，这时有关它的技术系数向量变为P1=(2,5,2)T，每件利润为4元，试分析对原最优计划有什么影响? 解：解：把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。375. 05 . 025. 12520125. 05 . 015 . 02025. 0011PB同时计算出x1的检验数为c1CBB-1P1=4(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1 的列向量位置，得表2-14。7.3 技术系数ij的变化c

56、j 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 0 3 x1 x5 x2 4 4 2 1.25 0.5 0.375 0 0 1 0 -2 0.5 0.25 0.5 0.125 0 1 0 cj-zj 0.375 0 -1.5 -0.125 0 可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15 7.3 技术系数ij的变化v表2-15表明原问题和对偶问题的解都是可行解。所以表中的结果已是最优解。即应当生产产品，3.2单位；生产产品，0.8单位。可获利15.2元。v注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。7.3 技术系数ij的变

57、化例11 假设例10的产品的技术系数向量变为P1=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案? 解：解： 方法与例10相同，以x1代替x1，并计算列向量375. 15 . 325. 12540125. 05 . 015 . 02025. 0011PBx1的检验数为c1CBB-1P1=4（1.5,0.125,0)(4,5,2)T =2.625。将这些数字填入最终表1-15的x1列的位置，得到表2-16。7.3 技术系数ij的变化将表2-16的x1变换为基变量，替换x1，得表2-17。 7.3 技术系数ij的变化cj 2 3 0 0 0 CB XB b x1 x2 x3

58、x4 x5 4 0 3 x1 x5 x2 3.2 15.2 -2.4 1 0 0 0 0 1 0 -2 0.5 0.2 1.2 0.4 0 1 0 cj-zj 0 0 -1.5 0.4 0 从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行，用方程表示时为0 x1+x2+0.5x3 0.4x4+0 x5= 2.4引入人工变量x6后，便为 x2 0.5x3+0.4x4+x6=2.4将x6作为基变量代替x2，填入表2-17，得到表2-18。7.3 技术系数ij的变化v这时可按单纯形法求解。vx4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。v在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。v此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品，0.667单位；产品，2.667单位，可得最大利润10.67元。 7.3 技术系数ij的变化第8节* 参数线性规划v灵敏度分析主要讨论在最优基不变情况下，确定系数aij，bi，cj的变化范围。v参数线性规划研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值