我的运筹学课件wang-对偶理论与灵敏度分析

1、 线性规划的对偶模型线性规划的对偶模型 对偶性质对偶性质 对偶问题的经济解释影子价格对偶问题的经济解释影子价格 对偶单纯形法对偶单纯形法 灵敏度分析灵敏度分析 对偶理论是线性规划的重要内容之一。随着线性规划问题研究对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。规划问题。 前者是由矩阵，右端向量和价值向量定义的，称之为原前者是由矩阵，右端向量和价值向量定义的，称之为原问题；问题； 后者也是由相同的数据集合，和构成的，称之为原问题后者也是由相同的数据集合，和构成的，

2、称之为原问题的对偶问题。的对偶问题。 一对原问题和对偶问题是紧密关联的，它们不但有相同的数据一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。有着重要的经济意义，是研究经济学的重要概念和工具之一

3、。 设某工厂生产两种产品甲和乙，生产中需设某工厂生产两种产品甲和乙，生产中需4种设备种设备按按A，B，C，D顺序加工顺序加工，每件产品加工所需的机时数、每件产品的利润，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表值及每种设备的可利用机时数列于下表 ：产品数据表产品数据表 设备设备产品产品ABCD产品利润产品利润（元件）（元件） 甲甲 21402乙乙 22043设备可利用设备可利用机时数（时）机时数（时） 1281612问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？获得最大利润？1. 解

4、：设甲、乙型产品各生产解：设甲、乙型产品各生产x1及及x2件，则数学模型为：件，则数学模型为： 0,124164821222.32max2121212121xxxxxxxxtsxxz反过来问：若反过来问：若工厂决策者工厂决策者决定决定不再自己生产甲、乙产品，而不再自己生产甲、乙产品，而是把各种设备的有限机时数是把各种设备的有限机时数租让给租让给其他工厂使用，这时工厂其他工厂使用，这时工厂的决策者应该的决策者应该如何确定各种设备的租价如何确定各种设备的租价，才是最佳决策？，才是最佳决策？在市场竞争的时代，厂长的最佳决策显然应符合两条：在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原

5、则不吃亏原则。把设备租出去所获得的租金不应低于利用这把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润些设备自行生产所获得的利润。由此原则，便构成了新规划的不。由此原则，便构成了新规划的不等式约束条件。等式约束条件。 （2）竞争性原则竞争性原则。即在上述不吃亏原则下，尽量降低机时总收。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。费，以便争取更多用户。设设A、B、C、D设备的机时价分别为设备的机时价分别为y1、y2、y3、y4，则新的线性，则新的线性规划数学模型为：规划数学模型为： 0,340222042.1216812min4321432143214321yyyy

6、yyyyyyyytsyyyy把同种问题的两种提法所获得的数学模型用表把同种问题的两种提法所获得的数学模型用表2表示，将会发表示，将会发现一个有趣的现象。现一个有趣的现象。原问题与对偶问题对比表原问题与对偶问题对比表A（y1） B（y2）C（y3） D（y4） 甲（甲（x1） 21402乙（乙（x2） 220431281612 min max z 对偶性是线性规划问题的最重要的内容之一。每一个线性规划（对偶性是线性规划问题的最重要的内容之一。每一个线性规划（ LP ）必然有与之相伴而生的另一个线性规划问题，即任何一个求必然有与之相伴而生的另一个线性规划问题，即任何一个求 maxZ 的的LP都都有

7、一个求有一个求 minZ 的的LP。其中的一个问题叫。其中的一个问题叫“原问题原问题”，记为，记为“P”，另一个，另一个称为称为“对偶问题对偶问题”，记为，记为“D”。2. 0,124164821222.32max2121212121xxxxxxxxtsxxz 0,340222042.1216812min4321432143214321yyyyyyyyyyyytsyyyy原问题原问题-P对偶问题对偶问题-D23x1x2原问题原问题12y122128y212816y3401612y40412对偶问题对偶问题23（1）对称形式）对称形式特点：目标函数求极大值时，所有约束条件为特点：目标函数求极大值

8、时，所有约束条件为号，变号，变量非负量非负;目标函数求极小值时，所有约束条件为目标函数求极小值时，所有约束条件为号，变量非号，变量非负负.0XbAXCXmaxZ ：PTT : minA YCY0TDWY b原问题原问题对偶问题对偶问题目标函数目标函数maxmin约束条件约束条件变量数量变量数量约束条件个数约束条件个数约束条件个数约束条件个数变量数量变量数量例例2.1 写出线性规划问题的对偶问题写出线性规划问题的对偶问题 0,5643 7 32 532432max321321321321321xxxxxxxxxxxxxxxZ解：首先将原问题变形为对称形式解：首先将原问题变形为对称形式 0,5 6

9、4 3 7 32532432max32132132132321xxxxxxxxxxxxxxxZ 注意：注意：以后不强调等以后不强调等式右段项式右段项 b b00，原因在对，原因在对偶单纯型表中只保证偶单纯型表中只保证 而不保证而不保证 ，故，故 b b可以是负数。可以是负数。0 j 01 bB 0,4675343232 532min 321321321321321yyyyyyyyyyyyyyyW对对偶偶问问题题：(2) 非对称型对偶问题非对称型对偶问题若给出的线性规划不是对称形式，可以先化成对称形式若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。再写对偶问题。也可直接也可直接按教

10、材表按教材表2-2中的对应关系中的对应关系写出非对写出非对称形式的对偶问题称形式的对偶问题。原问题原问题（或对偶问题）（或对偶问题）对偶问题对偶问题（或原问题）（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束= =b b约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数C C目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项例例2.2 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题. 0,5643732532432max32

11、1321321321321xxxxxxxxxxxxxxxZ解：原问题的对偶问题为解：原问题的对偶问题为123123123123123m in2352323435764,Wyyyyyyyyyyyyyyy 无约束无约束例例2.3 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题. 无无约约束束4321432142143214321, 0, 06 43 247 23 523 4 532maxxxxxxxxxxxxxxxxxxxxZ解：原问题的对偶问题为解：原问题的对偶问题为 无无约约束束32132131321321321,0,01 72 54 3332 2234 645minyyyyyy

12、yyyyyyyyyyyW例例2.4无约束、，4321432143243214321321321321321321 , 002473254334324323min20,5643732532422min. 1xxxxxxxxxxxxxxxxxxxZ. xxxxxxxxxxxxxxxZ 无约束无约束答案：答案：32132132132131321321321321321321y0,y0,y44y4y4y 37y3y3y 23yy 2y32y y 253max. 2 0.yy0,y46y7y5y24yy 3y2y 3y2y 532max. 1yyyWyyyW性质性质1 1 对称性定理对称性定理：对偶问题

13、的对偶是原问题：对偶问题的对偶是原问题minZ=-CXs.t.-AX -bX0minW=Ybs.t.AYCY0maxZ=CXs.t.AX bX0对偶的定义对偶的定义对偶的定义对偶的定义maxW=-Ybs.t.-AY-CY 0性质性质2 2 弱对偶原理弱对偶原理( (弱对偶性弱对偶性) )：设设 和和 分别是问题分别是问题(P)(P)和和(D)(D)的可行解，则必有的可行解，则必有0X0Y njmiiijjbyxcbYCX1100即即：推论推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其

14、原问题目的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。标函数值的上界。推论推论2: 在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若其中一个问题可行）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解（但目标函数无界，则另一个问题无可行解（如果原问题没有上界，如果原问题没有上界，即即maxZ+，则对偶问题不可行。如果对偶问题没有下界，即，则对偶问题不可行。如果对偶问题没有下界，即minW-，则原问题不可行，则原问题不可行 ）；）；反之不成立反之不成立(即无可行解的原因即无可行解的原因有二）有二）。这也是对偶问题的无界性。这也是对偶问题的无界性。 0,0

15、24 2max21212121xxxxxxxxZ无界无界（原）（原） 0,012 24min21212121yyyyyyyyW无可无可行解行解（对）（对）关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可行解无可行解无可行解无可行解问题无界问题无界对偶问题对偶问题原问题原问题例例2.5推论推论3 3：在一对对偶问题（在一对对偶问题（P）和（）和（D）中，若一个可行（如）中，若一个可行（如P），而另一个不可行（如），而另一个不可行（如D），则该可行的问题目标函数），则该可行的问题目标函数值无界。值无界。 02023220322 432max41432143214321xxxxxxx

16、xxxxxxZ试估计它们目标函数的界，并验证弱对偶性原理。试估计它们目标函数的界，并验证弱对偶性原理。（P）例例2.6解：解： 0,04233322 212 2020min212121212121yyyyyyyyyyyyW（D） 由观察可知：由观察可知： =（1.1.1.1），）， =（1.1），分别），分别是（是（P）和（）和（D）的可行解。）的可行解。Z=10 ，W=40，故有，故有 ，弱对偶定理成立。由推论，弱对偶定理成立。由推论可知，可知，W 的的最小值不能小于最小值不能小于10，Z 的最大值不能超过的最大值不能超过40。_XCbY_X_Y性质性质3 最优性定理最优性定理：如果如果 是

17、原问题的可行解，是原问题的可行解， 是其对偶是其对偶问题的可行解，并且问题的可行解，并且:0X0Ywz:00即即BYCX 则则 是原问题的最优解，是原问题的最优解， 是其对偶问题的最优解。是其对偶问题的最优解。0X0Y 例如例如:在一对对偶问题（在一对对偶问题（P）和（）和（D）中，可找到）中，可找到 X*=（0.0.4.4），）， Y*=（1.2，0.2）,且且Z=W=28 ，则则X*，Y*分别是分别是 P和和D 的最优解。的最优解。性质性质4 强对偶性强对偶性：若原问题及其对偶问题均具有可行解，则两若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。者均具有

18、最优解，且它们最优解的目标函数值相等。-1BY=CB（还可推出另一结论：若（还可推出另一结论：若（LP）与（）与（DP）都有可行解，则两者都）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。）有最优解，若一个问题无最优解，则另一问题也无最优解。）推论推论 若原问题有一个对应于基的最优解，那么此时的单纯若原问题有一个对应于基的最优解，那么此时的单纯形乘子是对偶问题的一个最优解。形乘子是对偶问题的一个最优解。根据这个推论我们根据这个推论我们可以在原问题的最优单纯形表中直接找可以在原问题的最优单纯形表中直接找到对偶问题的最优解到对偶问题的最优解，即松弛变量检验数的相反数，即松

19、弛变量检验数的相反数 。 -1BY=C B对偶问题可改写为原问题的检验数对应对偶问题的一个基本解。原问题的检验数对应对偶问题的一个基本解。证明：设是原问题的一个可行基，证明：设是原问题的一个可行基，且且则原问题可以写为则原问题可以写为BBNNBNSBNSmaxZ=C X+C XBX+NX+X =bX ,X,X01212SSBNSSminW=YbY(B,N)-(Y ,Y )=(C ,C )Y,Y ,Y01212SBSNSSminW =YbYB-Y=CYN-Y=CY,Y,Y0其中其中 分别为原问题决策变量中基变量和非基变量所对应的对偶约束分别为原问题决策变量中基变量和非基变量所对应的对偶约束的剩余

20、变量。的剩余变量。 对偶问题也可等价表示为：对偶问题也可等价表示为：12SSY ,YA=(B,N)对原问题可行基，对原问题可行基，可得可行解可得可行解对应于的检验数分别为对应于的检验数分别为。不难验证，不难验证，为对偶问题的一个基本解。为对偶问题的一个基本解。-1BX =B bBNSX ,X ,X-1-1NBB0,C -C B N,-C B12-1-1BSSNBY=C B ,Y =0,Y =-(C -C B N)例例 利用单纯形表求原问题的最优解，并由最优单纯利用单纯形表求原问题的最优解，并由最优单纯形表推出对偶问题的最优解。形表推出对偶问题的最优解。解：原问题线性规划模型为：解：原问题线性规

21、划模型为：引入松弛变量，引入松弛变量，化标准形得化标准形得: :12123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,j=1.51212121212maxZ=32x +30 x3x +4x365x +4x409x +8x76x0,x0345x ,x ,x32282 1 0 -2/3 0 1/34/3X132 0 0 1/3 1 -2/33/4X404/2 1 0 0 2 -14X1324/3 0 0 1 3 -24X308/4/5 1 4/5 0 1/5 08X13212/8/5 0 8/5 1 -3/5 012

22、X3040/5 5 4 0 1 040X4036/3 3 4 1 0 036X30 0 0 -7/6 0 -19/6Z 0 1 3/4 0 -1/48X230 0 0 0 7/2 -11/2278Z 0 1 0 -9/4 5/45X230 0 22/5 0 -32/5 0256Z4/4/5 0 4/5 0 -9/5 14X50 32 30 0 0 00Z76/9 9 8 0 0 176X50 X1 X2 X3 X4 X5bXBCB 32 30 0 0 0 C32282由最优表可知，原问题最优解由最优表可知，原问题最优解同时不难得到同时不难得到原问题的最优基原问题的最优基由强对偶定理的推论可得此

23、时的单纯形乘子由强对偶定理的推论可得此时的单纯形乘子 为对偶问题的最优解为对偶问题的最优解, ,即松弛变量检验数即松弛变量检验数的相反数。的相反数。 4, 12034B=(P P,P 121B03331044C3230000CBXBbX1X2X3X4X603230X4X1X23/44/38001/31-2/310-2/301/3013/40-1/4Z00-7/60-19/6*43X =(,8,0,0)34322822maxZ=282312123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,

24、j=1.5*-1B719Y =C B(,0,)66性质性质5 互补松弛性互补松弛性：设设X0和和Y0分别是分别是P问题问题 和和 D问题问题 的可行的可行解，则它们分别是最优解的充要条件是：解，则它们分别是最优解的充要条件是： 000ss0XYXY其中：其中：Xs、Ys为松弛变量（为松弛变量（松驰变量松驰变量*对偶变量对偶变量=0）性质性质5的应用：的应用：该性质给出了已知一个问题最优解求另一个问题最优该性质给出了已知一个问题最优解求另一个问题最优解的方法解的方法，即已知，即已知Y求求X或已知或已知X求求Y 00ssXYXY互补松弛条件互补松弛条件由于松弛变量都非负，要使求和式等于零，则必定每

25、一分量为由于松弛变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：零，因而有下列关系：若若Y0，则，则Xs必为必为0；若；若X0，则，则Ys必为必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。方程组的解即为最优解。例例2.7已知线性规划已知线性规划 3 , 2 , 1, 0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是X=(6,2,0)T,求其对偶问题的最优解求其对偶问题的最优解Y。解：写出原问题的对偶问题，即解：写出原问题的对偶问题，即 0,1

26、422321610min2121212121yyyyyyyyyyw1212312412512345min1016232241,0wyy yyy yy y yy yyyyyy 标准化标准化设对偶问题最优解为设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，由互补松弛性定理可知，X和和 Y满足：满足：00 ssXYXY即：即：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy因为因为X1=60，X2=20，所以，所以对偶问题的第一、二个约束的对偶问题的第一、二个约束的松弛变量等于零松弛变量等于零，即，即y30，y40，带入方程中：，带入方程中： 422322121y

27、yyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：从而对偶问题的最优解为：Y=(1,1)，最优值，最优值w=26。例例2.8 已知线性规划已知线性规划 无约束无约束321321321321, 0, 06422minxxxxxxxxxxxxz的对偶问题的最优解为的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。，求原问题的最优解。解解: 对偶问题是对偶问题是 021264max2121212121yyyyyyyyyyw无约，无约，标准化标准化 121231241252341max462120,0，5wyyyyy yy y yy +y yyyyy无约束无约束设

28、对偶问题最优解为设对偶问题最优解为X(x1，x2 ，x3)T ,由互补松弛性定理由互补松弛性定理可知，可知，X和和 Y满足：满足：0),)(,(0),)(,(5421321543 TTxxyyxxxyyy将将Y =(0,-2)带入由方程可知，带入由方程可知，y3y50，y41。 y2=-20 x50又又y4=10 x20将将x2，x5分别带入原问题约束方程中，得：分别带入原问题约束方程中，得： 643131xxxx解方程组得：解方程组得：x1=-5,x3=-1, 所以原问题的最优解为所以原问题的最优解为X=(-5,0,-1)，最优值，最优值z=-12原问题与对偶问题解的对应关系小结原问题与对偶

29、问题解的对应关系小结对应关系对应关系原问题原问题最优解最优解无界解无界解无可行解无可行解对偶问题对偶问题最优解最优解(Y,Y)(N,N)无界解无界解(Y,Y)无可行解无可行解(Y,Y)无法判断无法判断1. 影子价格的数学分析：影子价格的数学分析：0D0minmaxYCYAXbAXPbYW CX Z定义：在一对定义：在一对 P 和和 D 中，若中，若 P 的某个约束条件的右端项常的某个约束条件的右端项常数数bi （第第i种资源的拥有量种资源的拥有量）增加一个单位时，所引起目标）增加一个单位时，所引起目标函数最优值函数最优值z* 的改变量称为的改变量称为第第 i 种资源的影子价格种资源的影子价格，

30、其值等，其值等于于D问题中对偶变量问题中对偶变量yi*。由强对偶定理可知，如果原问题有最优解，那么对偶由强对偶定理可知，如果原问题有最优解，那么对偶问题也有最优解，而且它们的目标函数值相等，即有：问题也有最优解，而且它们的目标函数值相等，即有：其中是线性规划原问题约束条件的右端其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。数据向量，它代表各种资源的拥有量。为对偶问题最优解，它为对偶问题最优解，它代表在资源最优代表在资源最优利用条件下对各种单位资源的估价利用条件下对各种单位资源的估价，这种估计不是资源的市场，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创

31、造利润、产价格，而是根据资源在生产中所作出的贡献（如创造利润、产值等）而作出估价。值等）而作出估价。*X*Y*1122mmZ=CX =Y b=y by by b12mb=(b ,b ,b )T*12mY =(y ,y ,y )2. 影子价格的经济意义影子价格的经济意义1）影子价格是一种边际价格）影子价格是一种边际价格在其它条件不变的情况下，单位资源数量的变化所引在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量起的目标函数最优值的变化。即对偶变量yi 就是第就是第 i 种资源种资源的影子价格。即：的影子价格。即： )2 , 1(*miybZii 2）影子价格是一

32、种机会成本）影子价格是一种机会成本在市场经济的条件下，当某种资源的市场价格低于影子在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。时，才处于平衡状态。影子价格的大小客观地反映了各种不同资源在系统内

33、的影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度稀缺程度。如果第。如果第i i种资源供大于求，即在达到最优解时，种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量，由互补松弛定理，该种资源没有用完，或松弛变量，由互补松弛定理，在对偶最优解中，第在对偶最优解中，第ii种资源的影子价格。反之种资源的影子价格。反之如果第如果第ii种资源的影子价格种资源的影子价格 ，那么由互补松弛定理，那么由互补松弛定理，原问题的第原问题的第i i个约束为严格等式，即，这表明第个约束为严格等式，即，这表明第ii种资种资源已经用完，成为稀缺资源。源已经用完，成为稀缺资源。 *Yiu0*iy0iu0

34、*iy03）影子价格在资源利用中的应用）影子价格在资源利用中的应用4）影子价格对单纯形表计算的解释）影子价格对单纯形表计算的解释单纯形表中的检验数单纯形表中的检验数 miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j种产品的价格种产品的价格; ; 表示生产该种产品所消耗表示生产该种产品所消耗的各项资源的影子价格的总和的各项资源的影子价格的总和, ,即产品的即产品的隐含成本隐含成本。 miiijya1当产值大于隐含成本时，即当产值大于隐含成本时，即 ，表明生产该项产品有，表明生产该项产品有利，可在计划中安排；否则利，可在计划中安排；否则 ，用这些资源生产别的，用这些资源

35、生产别的产品更有利，不在生产中安排该产品。产品更有利，不在生产中安排该产品。0 j 0 j 12123124125jmaxZ=32x +30 x3x +4x +x =365x +4x +x =409x +8x +x =76x0,j=1.5设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/ /吨）吨） 32 32 30 30 例例4*X=(,8)3T2maxZ=2823719*Y =(,0,)66对偶最优解对偶最优解其中为设备其中为设备A A的影子价格，的影子价

36、格，在资源最优利用的条件下，设备在资源最优利用的条件下，设备A A每增加每增加一个单位台时，可以使总利润增加元。一个单位台时，可以使总利润增加元。若设备可供台时数，则若设备可供台时数，则*17y =67623*X=(,8)34T5maxZ=2836 对偶单纯形法是求解线性规划的另一个基本方法。它是对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。 找出一个对偶问题的可行基，找出一个对偶问题的可行

37、基，保持对偶问题为可行解保持对偶问题为可行解的的条件下，条件下，(即必须保持所有的检验数非正，同时取消原问题必即必须保持所有的检验数非正，同时取消原问题必须可行的要求，即须可行的要求，即取消常数列的非负限制取消常数列的非负限制)，判，判断断XB是否可行是否可行（XB=b为非负），有最优解。否则，通过变换基解，直到找为非负），有最优解。否则，通过变换基解，直到找到原问题基可行解（即到原问题基可行解（即XB为非负），这时原问题与对偶问题为非负），这时原问题与对偶问题同时达到可行解。同时达到可行解。找出一个找出一个DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP为可行解情况下转移到为

38、可行解情况下转移到LP的另一个基本解的另一个基本解最优解最优解是是否否循循环环结束结束例例2.9 用对偶单纯形法求解：用对偶单纯形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）将模型转化为求最大化问题，约束方程化为等式求将模型转化为求最大化问题，约束方程化为等式求出一组基本解，因为对偶问题可行（求出一组基本解，因为对偶问题可行（求max问题）。问题）。 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZcj-9-12-15000bcBxBx1

39、x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14j-9-12-150000icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x29/14100-5/141/1423/7(-3/-9,-45/

40、-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原问题的最优解为：原问题的最优解为：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 由定理由定理4，其对偶问题的最优解为：，其对偶问题的最优解为：Y*= （1/3 , 3 , 7/3），），W*= 72 对偶单纯形法应注意的问题：对偶单纯形法应注意的问题： 用对偶单纯形法

41、求解线性规划是一种求解方法，而不是去求对偶用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解问题的最优解 初始表中一定要满足对偶问题可行，也就是说检验数满足最优判初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则别准则 最小比值中最小比值中 的绝对值是使得比值非负，在极小化问题的绝对值是使得比值非负，在极小化问题 j j00，分母分母a aij ij0 0 这时必须取绝对值。在极大化问题中，这时必须取绝对值。在极大化问题中， j j00，分母，分母a aij ij00， 总满足非负，这时绝对值符号不起作用，可以去掉。如总满足非负，这时绝对值符号不起作用，可以去掉。

42、如在本例中将目标函数写成在本例中将目标函数写成ijja 这里这里 j j 0 0在求在求 k k时就可以不带绝对值符号。时就可以不带绝对值符号。32134maxxxxz ijja 对偶单纯形法与普通单纯形法的对偶单纯形法与普通单纯形法的换基顺序不一样换基顺序不一样，普通单纯形法，普通单纯形法是先确定进基变量后确定出基变量，是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变对偶单纯形法是先确定出基变量后确定进基变量量后确定进基变量； 普通单纯形法的最小比值是普通单纯形法的最小比值是 其目的是保证下一其目的是保证下一个原问题的基本解可行，个原问题的基本解可行，对偶单纯形法的最小比值对偶单纯

43、形法的最小比值是是 0minikikiiaab其目的是保证下一个对偶问题的基本解可行其目的是保证下一个对偶问题的基本解可行 0minljljjjaa 对偶单纯形法在确定出基变量时，若不遵循对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的规则，任选一个小于零的b bii对应的基变量出基，不影响计算结果，对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。只是迭代次数可能不一样。 0|min iilbbb-1BX =B b 一个标准形式的线性规划问题可由约束矩阵，右端项向一个标准形式的线性规划问题可由约束矩阵，右端项向量量b b，和价值向量完全确定，假如一个线性规划问题对于给，

44、和价值向量完全确定，假如一个线性规划问题对于给定的数据集合，定的数据集合，b b，有最优解，则最优解。最，有最优解，则最优解。最优目标函数值，其中为最优基。优目标函数值，其中为最优基。 但是线性规划问题所对应的数据集合，但是线性规划问题所对应的数据集合，b b，常常是通，常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此这些数据完全可能发生变化。因此有必要来分析一下当这些数有必要来分析一下当这

45、些数据发生波动时，对目前的最优解，最优值或者最优基会产生什据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。么影响，这就是所谓的灵敏度分析。 -1BZ=C B b灵敏度分析主要讨论如下二类问题：灵敏度分析主要讨论如下二类问题：线性规划的数据集合在什么范围内波动将不影响最优解或最优线性规划的数据集合在什么范围内波动将不影响最优解或最优基？基？ 若最优解发生变化，应如何用最简单的方法找到新的最优解。若最优解发生变化，应如何用最简单的方法找到新的最优解。为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形为讨论方便，以下列出标准型线性规划问题最优单纯形表的一

46、般形式，式，其中其中B B为线性规划问题的最优基为线性规划问题的最优基：CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn) CB2 XB2 : : CBm XBm Z CBB-1b C-CBB-1A 11mjjijijBjica xcC B P 1jjP =BP1bBb线性规划问题的标准形式线性规划问题的标准形式11max.1,2,0,1,2,LLnjjjnijjijjZc xa xbs timxjnm ax.0ZC XA Xbs tX令：令：例例1-11-1：某企业利用三种资源生产两种产品的最优计划问题归：某企业利用三种资源生

47、产两种产品的最优计划问题归结为下列线性规划结为下列线性规划 0,45 802903 45 max2121212121xxxxxxxxxxZ问题：问题：（1 1）确定）确定x x2 2的系数的系数c c2 2的变的变化范围，使原最优解保持最化范围，使原最优解保持最优；优；（2 2）若）若c c2 2=6=6，求新的最优，求新的最优计划。计划。 1212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 优 表最 优

48、 表如下：如下：4 = c25 05 = 52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12j000c2 - 55 - 2c2最优解最优解X*=（35，10，25，0，0）保持不变。保持不变。（1）（2）Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2用单纯形法求解得。用单纯

49、形法求解得。x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=405/2原料（公斤）原料（公斤）产品（万件）产品（万件）供应量供应量A B C DA B C D甲甲乙乙3 2 10 43 2 10 40 0 2 1/20 0 2 1/218183 3利润（万元利润（万元/ /万件）万件）9 8 50 199 8 50 19问应该怎样组织生产，才能使总利润最大，问应该怎样组织生产，才能使总利润最大，若产品或的利润产若产品或的利润产生波动，波动范围多大时，原最优解保持不变生波动，波动范围多大时，原最优解保持不变？解解：设生产，四种产品设生产，四种产品各万件，则此问题

50、的各万件，则此问题的线性规划模型为：线性规划模型为：1234x ,x ,x ,x123412341342jmaxZ=9x +8x +50 x +19x3x +2x +10 x +4x182x +x3x0,j=1,2,3,4标准化，引入松弛变量标准化，引入松弛变量x x5 5,x,x6 6， 利用单纯形表求解：利用单纯形表求解：-4 -2/3 0 0 -13/3 -10/388Z2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/321X4X319500 2 0 2 -3 -1084Z261 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/

51、2X1X39509 8 0 13/2 0 -2575Z1-3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2X5X30509 8 50 19 0 00Z9/53/23 2 10 4 1 0 0 0 2 1/2 0 1183X5X600X1 X2 X3 X4 X5 X6BXBCB9 8 50 19 0 0C即最优生产方案是生产产品即最优生产方案是生产产品1 1万件，产品万件，产品2 2万件，万件，不生产不生产, ,两种产品。可得最大利润为两种产品。可得最大利润为8888万元。万元。 *X =(0,0,1,2) ,maxZ=88TC 9 8 50 19 0 0CBXBBX1 X2

52、 X3 X4 X5 X 61950X4X321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 -4 -2/3 0 0 -13/3 -10/3最优表：最优表：(1)1)若产品的利润，有改变量。因为为非基变量，若产品的利润，有改变量。因为为非基变量，推得推得 44或（万元）时或（万元）时原最优解不变，最优利润值（万元）也原最优解不变，最优利润值（万元）也不变。不变。1c91c1x-1BZ =C B b=881c13*X =(0,0,1,2)T( () )若产品的利润若产品的利润 ，有改变量。因为为基变量，有改变量。因为为基变量，推得推得3c503c3x

53、35c22 原最优解不变，原最优解不变，最优利润值最优利润值（万元）（万元）347.5c52-1B332Z =C B b=(19,50+ c )=88+ c1 1c即当即当时时XB= B1b例例2 2：对于上例中的线性规划作下列分析：对于上例中的线性规划作下列分析：（1 1）b b3 3在什么范围内变化，原最优基不变？在什么范围内变化，原最优基不变？（2 2）若）若b b3 3=55=55，求出新的最优解。，求出新的最优解。 0,45 802903 45Z max2121212121xxxxxxxxxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14

54、 x2 10 010-12000-1-321-01105-21最优基：最优基：B=I=（P3，P1，P2）B1=最优解：最优解：X*=（35，10，25，0，0）（1）XB=B1b= 2 1- 01 1 05- 2 190803b80802333bb250 - 5b90803b=0 B1解得解得40b350，即当，即当b340，50 时，最优基时，最优基B 不变不变z*=5（80b3）+4（80+2b3） =80+3b3333b280b805b-250*2*1*3xxx=（2）当当 b3= 55 时时 80802333250-5bbb 30 25 25=x2 x1x50-11/5-3/500j

55、0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j -101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045Cj最优解：最优解：X*=（30，20，0，0，5）1212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 优 表最 优 表如下：如下：三、增加一个变量三、增加一个变量 的分析的分析jx例例3 3

56、：（续例：（续例1 1）设企业研制了一种新产品，）设企业研制了一种新产品，对三种资源的消耗系数列向量以对三种资源的消耗系数列向量以P6表示表示P6= = 。问它。问它的价值系数的价值系数c c6 6符合什么条件才必须安排它的符合什么条件才必须安排它的生产？设生产？设c c6 6=3=3，新的最优生产计划是什么？，新的最优生产计划是什么？3/ 211/ 2 6=c6CBB1P6 =c6（0，5，4） = c65/202/116P21-01105-212/112/302/11=B1P6 =Cj540003CBXBbx1x2x3x4x5x60 x3250012-515x1351001-11/24x2

57、 10 010-120j 000-1-31/23x6250012-515x145/210-1/203/204 x2 10 010-120j00-1/2-2-1/201212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 优 表最 优 表如下：如下：四、四、 增加新的约束条件的分析（直接添加到最终单纯形表中）增加新的约束条件的分析（直接添加到最终单纯形表中）例例4: 4: 假设在例假设在例1 1中，还要考虑一个

58、新的资源约束：中，还要考虑一个新的资源约束： 4x4x1 1+2x+2x2 2150150121212121212max543902804215045,0 zxxxxxx x xxxxx12123124125122516346max54394028045,00215 zxxxxx xx x x x x x x xxx xxxx标准化标准化cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351001-104 x2 10 010-1200 x6150420001000-1-30Cj540000CBXBbx1x2x3x4x5x60 x3250012-505x1351

59、001-104x210010-1200 x6 150 420001j 000-1-300 x3250012-505x1351001-104x210010-1200 x6 -10 000-201j000-3-300 x3150010-515x1301000-11/24x21501002-1/20 x4 5 00010-1/2j0000-3-1/21212312412512m a x5439 028 04 5,0 Zxxxxx xx x x x xxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12j000-1-3最 优 表最 优 表如下：如下：1. c1. cj j和和b bi i同时变化的情况同时变化的情况五、五、 其它变化情况的分析其它变化情况的分析例例5: 5: 在例在例1 1中，假定中，假定c c2 2由由4 4上升为上升为6 6，b b3 3增加到增加到5555，试问最优，试问最优解将会发生什么变化？解将会发生什么变化？1212121212max5439028045,0 zxxxxxx x xx x21-01105-21B1= B