韩伯棠管理运筹学第三单纯形法灵敏分析与对偶PPT课件

1、1单纯形表的灵敏度分析 一、目标函数中变量系数Ck 灵敏度分析 1在最终的单纯形表里，xk 是非基变量。 在这种情况下，由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与 Ck 没有任何关系，所以当Ck 变成Ck+Ck 时，在最终单纯形表中其系数的增广矩阵不变，又因为xk 是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Z K也不变，只是Ck 变成了Ck+Ck 。这时K=CK Zk 就变成了Ck+Ck Zk=K+Ck 。要使得原来的最优解仍为最优解，只要 K+Ck 0即可，也就是Ck的增量CK-K 即可。第1页/共59页2在最终的单纯形表中，XK是基变量。 当CK变成Ck+

2、Ck时，同上一样，可知在最终的单纯形表中的约束方程的增广矩阵不变，但是基变量在目标函数中的系数CB变了，则Zj (j=1,2,n)一般也变了，不妨设CB=(CB1,CB2, CK, ,CBm) , 当CB 变成 (CB1,CB2,（ CK+Ck) , ,CBm) , 则：kjkkjkjkjkjjjjkjkkjkmjBmkjKjBjBmjBmkjkKjBjBTmjkjjjBmkKBBjTmjkjjjBmKBBjacaccacczcacacacacacacacaccacacaaaaccccczaaaacccczjjjj2211221121212121 )z(z.z . .)(. ),.,.,)()

3、,.,(,.,(:),.,.,)(,.,.,(这样检验数变成了第2页/共59页 这也就是说，要使最优解不变，对于除了akk 外的所有的大于零的akj,Ck的增量Ck 都要小于等于 j / akj , 对于所有小于零的akj ，Ck都要大于等于j / akj 。我们用数学式表示使得最优解不变，C 的变化范围为：. 0, 1, 0,kj ; 0a,a, 0a ; 0a,a, 0a , , 0 :, 0,kkjkjkjkjkjkjkkkkkKKkkkkkkkjjkjjkjkjkkjkjjaxaczcczccccacackj故知知是基变量因为时而当这里当这里当也就是时只要当要使最优解不变0min0ma

4、xkjkjjkkjkjjaacaa第3页/共59页 目标函数： max Z=50X1+100X2， 约束条件： X1+X2300， 2X1+X2400， X2250, X10, X20. 此题在第五章里，已得到最终单纯形表为：迭代次数基变量CB x1 x2 s1 s2 s3 b 50 100 0 0 0 2 x1 S2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50250 zj j=cj-zj 50 100 50 0 50 0 0 -50 0 -50Z=27500第4页/共59页 先对非基变量先对非基变量s1的目标函数的系数的目标函数的系数C

5、3进行灵敏进行灵敏度分析。这里度分析。这里3=-50，所以当，所以当C3 的增量的增量C3-(-50)即即C350时，最优解不变，也就是说时，最优解不变，也就是说S1的目标的目标函数的系数函数的系数C3=C3+C30+50=50时，最优解不时，最优解不变。变。 再对基变量再对基变量x1的目标函数的系数的目标函数的系数C1进行灵敏度进行灵敏度分析。分析。 也可以按以下方法来计算出使最优解不变的C1的变化范围。 .1000,50505050:,5050,50)150max(max0max:,5050min0min,50150, 0, 0,111111115511111331513111514131

6、211的最优解不变即有的目标函数也就是时这样可知当同样有有可知外有知道除了中在cccccxCaaaaaaaaaaaaaajjjjjj第5页/共59页在最终的单纯形表中，用在最终的单纯形表中，用C1代替原来的代替原来的C1=50计算得表如计算得表如下：下： 从30，得到-C10，即C10，并且从50， 得到C1-1000，C1100。 从上两式可知：当0C1100 时最优解不变，如果采取了不属于这范围的C1，必存在某个检验数j0，我们可以继续用单纯形表进行迭代，以求出新的最优解。迭代次数基变量CB x1 x2 s1 s2 s3 b C1 100 0 0 0 2 x1 S2 x2 C1 0 100

7、 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50250 zj j=cj-zj C1 100 C1 0 -C1+100 0 0 - C1 0 C1- 100 第6页/共59页 用最终单纯形表对Cj 进行灵敏度分析，求得使最优解保持不变的C1, C3变化范围与我们在第三章里用计算机求解所得的结果是一样，其实管理运筹学软件就是按这种方法进行编程，对Cj 进行灵敏度分析的。 二、约束方程右边常数灵敏度分析 我们在第三章对线性规划问题的计算机求解中，也曾经对约束方程右边常数bj 进行了灵敏度分析，根据计算机输出的表格，可知道，约束方程右边常数在什么范围内变化时，其对偶价格不变

8、，那么在用单纯形表对bj 进行灵敏度分析时，首先应从单纯形表中找到有关对偶价格的信息。 在第三章里我们给了对偶价格这样的定义：变量或人工变量)的Zj 有关。下面我们仍以第二章例1为例在其最终单纯形表上找出其约束条件的对偶价格。变量(或剩余第7页/共59页 此题的最终单纯形表如下，这是一个求目标函数最大值的问题。 从上表可以发现设备台时数的约束方程中的松弛变量S1 的zj 值50正好等于计算机解中设备台数的对偶价格，原料A约束方程中的松弛变量S2 的Zj 值0正好等于计算机解中的原料A的对偶价格。同样原料B的约束方程中的松弛变量S3 的Zj 值50正好等于计算机解中的原料B的对偶价格。松弛变量的

9、Zj 值是否等于对应的约束条件的对偶价格呢?回答是肯定的。迭代次数基变量CB x1 x2 s1 s2 s3 b 50 100 0 0 0 2 x1 S2 x2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 50250 zj j=cj-zj 50 100 50 0 50 0 0 -50 0 -5027500第8页/共59页 下面我们来看一看对于非基变量的松弛变量的Zj 值是否也正确地给出了与其对应的约束条件的对偶价格? 第9页/共59页 第10页/共59页 对于含有大于等于号的约束条件，为了化成标准型就添上了剩余变量。这时这个约束条件的对偶价格就和这个剩

10、余变量的Zj 有关了。只不过当约束条件右边的常量增加一个单位时，约束条件更严格了。这将给满足约束条件带来些困难。就使最优目标函数值特别“恶化”而不是改进，故这时，约束条件的对偶价格应取Zj 值的相反数-Zj。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的Zj 值。 下面我们给出一个由最终单纯形表对于不同约束类型的对偶价格的取值表：约束类型约束类型 对偶价格的取值对偶价格的取值 等于这个约束条件对应的松弛变量的等于这个约束条件对应的松弛变量的Zj值值 等于与这个约束条件对应的剩余变量的等于与这个约束条件对应的剩余变

11、量的Zj值的相反数值的相反数-Zj= 等于与这个约束条件对应的人工变量的等于与这个约束条件对应的人工变量的Zj 值值第11页/共59页F 从对偶价格的定义，可以知道当对偶价格为正时，它将改进目标函数值。对于求目标函数最大值的线性规划来说改进就是增加其目标函数值，而对求目标函数最小值的线性规划来说改进却是减少其目标函数值。F 当对偶价格为负时，它将“恶化”目标函数值，对求目标函数最大值的线性规划来说恶化就是减少其目标函数值，而对求目标函数最小值的线性规划来说“恶化”却是增加其目标函数值。F 在第三章我们已提及过影子价格，对于求目标函数最大值的线性规划中对偶价格等于影子价格，而对求目标函数最小值的

12、线性规划中影子价格为对偶价格的相反数。 下面我们就来求出bj 的变化范围，在这个范围内变化其对偶价格不变。第12页/共59页$ 一般地，由于bj 的变化，资源投入起了变化，最优解是变化的。从这时也可以看出：所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量(最优基)不变，且所得的最优解仍然是可行的bj 的变化范围。 下面我们来看一下当某个bk 变成bk =bk+bk时在原来的最终单纯形表中的基不变的条件下，最终单纯形表会有什么变化。第13页/共59页 单纯形表的迭代实际上是约束方程的增广矩阵的行的初等变换，bk的变化不会影响系数矩阵的迭代，所以在最终单纯形表的系数矩阵不变，又已

13、知最终单纯形表中的基不变，可知CB不变，这样Zj=CBpTj 也不变，检验数j=Cj-Zj 也不变，唯一带来变化的只是最终单纯形表中的b列，那么bk变化前后的b列到底有什么关系呢? 原来的约束方程组不妨用矩阵表示为Ax=b，通过一些单纯形表的迭代变成以B为基的最终单纯形表，实际上也就是在原来的约束方程组左乘B-1。即B-1AX=B-1b，在初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里正好就变成了B-1，这里可知： 其实迭代过程也是用矩阵初等变换求B的逆阵B-1的过程。1001121011B第14页/共59页 这样在最终单纯形表里系数矩阵就是B-1A，基变量(记为xB)的解就为B

14、-1b记在单纯形表的b列中。当bk变成bk+bk时，也就是原来初始单纯形表中的b向量变成了b向量，这里 这样在最终单纯形表中基变量XB 的解就变成了 x B=B-1(b+ b)=B-1b+B-1b。要使XB 为可行解，只要B-1b+B-1b 0即可，在此不等式中求出的bk 的变化范围，就是使得第k个约束条件的对偶价格不变的bk 的变化范围。bbbbbbbbbbbbbbbkkmkkmk则令,0.0b, 0.0.,.11第15页/共59页 mkkkkkkkkmkkkKdbdbdbdbbBdddD. ,. 321121则第16页/共59页 在上述的不等式中求出满足所有不等式的bk 的范围，也就确定了

15、bk 的变化范围，bk在此范围内变化使得其对应的约束条件的对偶价格不变。即bk的变化范围是：m)1,2,.,(j . 0. 0. , 0,. . :221121211jkkBjmkkBmkkBkkBBmkkkkkkBmBBBBBdbxdbxdbxdbxxdbdbdbxxxbBxxx即要求每个分量即要使为新的最优解0min0max ikikBikikikBiddxbddx第17页/共59页B-1的第K列在最终单纯形表中如何确定? 我们知道初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里就变成了B-1，B-1的第k列是由初始单纯形表里的系数矩阵中的单位矩阵中的单位列向量ek ，通过迭代

16、在最终单纯形表中就变成了B-1 的第k列。如果第K个的约束方程中有松弛变量，那么这个松弛变量在最终单纯形表上的系数列正好就是B-1的第K列，因为这个松弛变量在初始单纯表上的系数列正好就是单位向量ek 。如果第K个约束方程有剩余变量，那么B-1的第K列正好等于这个剩余变量在最终单纯形表上的系数列的相反数，因为这个剩余变量在初始单纯形表上的系数列正好是单位向量ek 的负向量，如果第K个约束方程只有人工变量，那么B-1第K列正好是这个人工变量在最终单纯形表上的系数列，因为这个人工变量在初始单纯形表上的系数列正好是单位向量ek 。第18页/共59页 对b1分析，因为第一个方程中含有松弛变量S1，故松弛

17、变量在最终单纯形表中的系数列 (1, -2，0) T 就是B-1 的第一列。d11=10, d21=-20=-50/1=-50，而min -XB i/di1 dI 1 0，则继续进行迭代以求出新的最优解。 下面仍以第二章例1为例来加以说明。第20页/共59页例例 该厂除了生产该厂除了生产、产品外，现试制成一个新产品产品外，现试制成一个新产品，已知生产产品已知生产产品，每件需要设备，每件需要设备2台时，并消耗台时，并消耗A原料原料0.5公公斤，斤，B原料原料1.5公斤，获利公斤，获利150元，问该厂是否应生产该产品元，问该厂是否应生产该产品和生产多少和生产多少? 解：这是一个增加一个新的变量的问

18、题。可以把它认为是一个改变变 量x3在初始表上的系数列的问题，从(0，0，0)T 变成(2，0.5，1.5)T 。这样在原来的最终表上添上新的一列变量，X3 的一列，把它放在S3 之后的第6列上，显然X3 是非基变量，迭代次数基变量CB x1 x2 s1 s2 s3 x3 b 50 100 0 0 0 150 x1 S2 x2 50 0 100 1 0 1 0 -1 0.5 0 0 -2 1 1 -2 0 1 0 0 1 1.5 50 50250 zj j=cj-zj 50 100 50 0 50 175 0 0 -50 0 -50 -25275005 .125 .05 .15 .021001

19、12101 :)5 .1 , 5 .0 , 2(61pB变为在最终表上第21页/共59页 这时Z6=500.5+1001.5=175, 6=C6 Z6=150-175=-25。如上表所示，这时新变量的检验数6 小于零，可知原最优解就是新问题的最优解，即该厂还应该生产I产品50件， 产品250件，不生产产品可得最大利润27500元。第22页/共59页 :,35125160 ,125105 . 0)100, 0 ,50(Z ,105 . 0125 . 1100112101 :66661613把这些结果填入下表在最终表上的系数列首先求出解zcpBpBxj第23页/共59页 显然，由于6 0，可知这不

20、是最优解，要进行迭代，选取X3为入基变量，X1为出基变量。迭代次数基变量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 160 2 x1 S2 x2 50 0 100 1 0 1 0 -1 0.5 0 0 -2 1 1 0 0 1 0 0 1 1 50 5025050/0.5250/1 zj j=cj-zj 50 100 50 0 50 125 0 0 -50 0 -50 3527500第24页/共59页 可知此规划的最优解x1=0，x2=0，s1=0，s2=0，s3=50，x3=200，此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，

21、生产产品200件，可获最大利润32000元。迭代次数基变量CB x1 x2 s1 s2 s3 x3 b比值 50 100 0 0 0 160 2 x3 S2 x2 160 0 100 2 0 2 0 -2 1 0 0 -2 1 0 -2 1 -2 0 3 0 100 5015050/1150/3 zj j=cj-zj 120 100 120 0 -20 160 -70 0 -120 0 20 031000X3S3X21600100 2 0 -2 2 0 1 0 0 -2 1 1 0 -2 1 4 -3 0 0200500 zj j=cj-zj120 100 80 20 0 160 -70 0

22、-80 -20 0 032000第25页/共59页 2在初始表上的变量Xk的系数列pK改变为pK ，经过迭代后，在最终表上Xk是基变量，在这种情况下原最优解的可行性和最优解都可能遭到破坏，问题变得十分复杂。一般不去修改原最终表，而是重新计算。 在学了灵敏度分析之后，我们来看一看如何从“管理运筹学”软件的计算输出上去识别线性规划问题有惟一解呢，还是具有无穷多组解?从单纯形法上我们知道有无穷多组解的识别方法为是否存在一个非基变量的检验数为零，如果存在，则此线性规划有无穷多组解，如不存在，则此线性规划只有惟一解。第26页/共59页 1如果在最终表上检验数为零的非基变量是松弛变量或剩余变量Sk。显然在

23、计算机输出中没有专门松弛变量与剩余变量栏，但是我们仍然从输出中找到它们的信息。首先由于是非基变量，可知在最优解中其值都为零，也就是在计算机输出的约束条件栏里，某一个约束条件的松弛或剩余变量的值为零，又因为这个非基变量的检验数为零，所以这个约束条件的对偶价格为零。反过来说，如果在计算机输出的约束条件栏里有一个约束条件的松弛或剩余变量为零，且其对偶价格也为零，那么我们就可知道有一个非基变量的松弛变量或剩余变量的检验数为零，这个线性规划有无穷多组解。第27页/共59页 2如果在最终单纯形表上，检验数为零的非基变量是一般决策变量XK。在对非基变量XK的目标系数CK的灵敏度分析中知道CKK，对任何非基变

24、量Xi 在计算机输出的相差值一栏中就记录了i 的值，它表示只有目标函数系数Ci 的增量改进了i 的值，Xi 才有可能成为基变量而取正值。因为K=0，所以很容易从计算机输出中识别出Xk ，也就是说只要在计算机输出中存在一个取值为零的决策变量并且其相差值也为零，我们就可以确认这个变量就是最终表上检验数为零的非基变量，可知此线性规划有无穷多组解。如果在计算机输出解的信息中不存在上述这两种情况，我们可以断定此线性规划只有惟一最优解。第28页/共59页 每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，称其中的任一个为原问题，另一个为对偶问题。在这一节中将揭示原问题与对偶问题的关系，如何将原

25、问题转化为其对偶问题，如何从原问题的求解的结果中去找到其对偶问题的答案，并介绍对偶问题的经济解释以及对偶单纯形法。先来看一个例题。 例4 某工厂在计划期内安排、两种产品，已知生产单位产品所需设备A、B、C台时如表所示：资源限量设备A11300台时设备B21400台时设备C01250台时F 该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少产品和产品，才能使工厂获利最多?6.2 线性规划的对偶问题第29页/共59页 此例题与第二章例1有相同之处，只是不过把原料A、B改成了设备B、设备C，做这些改动是为了使读者更容易理解。 这个问题的数学模型与第二章的例1是一

26、样的，求解的结果也是一样的。 设X1为产品的计划产量，X2为产品的计划产量，则有：目标函数：max Z =50X1+100X2 约束条件：X1+X2300, 2X1+X2400, X2250, X1, X20.第30页/共59页 现在从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢? 设y1，y2，y3分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润，也就是由于出租可以获得的利润。建立模型要从两方面来考虑：第31页/共59页 思路：把生产单位产品所需各设备的台时总租金不应当低于原利润50元，即

27、y1+2y250，否则就不出租还是用于生产产品以获利50元；同样把生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即y1+y2+y3100，否则这些设备台时就不出租，还是用于生产产品以获利100元。租金租金资源限量资源限量设备设备A,y111300台时台时设备设备B,y221400台时台时设备设备C,y301250台时台时怎么做？怎么做？一、作为出租者来说:第32页/共59页 这样从两个不同的角度来考虑同一个工厂的最大利润(最小租金)的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题。下面来研究这两个问题在数学模型上的关系。 &

28、amp;他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，& 即min 300y1+400y2+250y3，& 这样得到了该问题的数学模型：二、对于租用者来说:一样的吗？一样的吗？第33页/共59页 1求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。

29、 第34页/共59页 3原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i 个约束条件的右边常数项就等于对偶问题的目标函数中的第 i个变量的系数。 4对偶问题的约束条件的系数矩阵A是原问题约束条件的系数矩阵的转置ATnm2n1nm12111Ta.aa.a.aaA 则 ,a.aa.a.aaA mnm2m11n1211设第35页/共59页 在例4中，对于原问题其约束条件为： X101211对应的对偶问题的约束条件为： Y111021第36页/共59页则其对偶问题： min f=bT y AT yCT, y0, 其中 y=(y1, y2, ym)T 用矩阵的形式来表示，

30、则原问题变为：max Z=CX AXb X0其中A为mn矩阵，该问题有m个约束条件n个变量，X=(X1,X2,Xn)T, b=(b1, b2, bm)T, C=(C1,C2,Cn)。第37页/共59页 以上问题的原问题已在第五章里用单纯形以上问题的原问题已在第五章里用单纯形求出，现在我们用单纯形法求出其对偶问题的求出，现在我们用单纯形法求出其对偶问题的解。解。 加上剩余变量加上剩余变量S1, S2和人工变量和人工变量a1 ，把此问题化成标准型如下：，把此问题化成标准型如下： max (-f )=-300y1- 400y2 -250y3 Ma1 y1+2y2-S1+a1=50， y1+y2+y3

31、 S2= 100， y1，y2，y3，S1，S3，a10 把上述数据填人单纯形表计算。把上述数据填人单纯形表计算。第38页/共59页迭代迭代次数次数基变基变量量CB Y1 Y2 Y3 S1 S2 a1 b-300 -400 -250 0 0 -M 1 a1 Y3-M-250 1 2 0 -1 0 1 1 1 1 0 -1 0 50 10050/2100/1 Zj j=Cj-Zj-M-250 -2M-250 -250 M 250 -MM-50 2M-150 0 -M -250 0-50M-25000 2Y2Y3-400-250 1 0 -1/2 0 1/2 1/2 0 1 1/2 -1 -1/2

32、 25 7525/(1/2)75/(1/2) Zj j=Cj-Zj -325 -400 -250 75 250 -75 25 0 0 -75 -250 M+75 -28750 3 Y1 Y3 -300 -250 1 2 0 -1 0 1 0 -1 1 1 -1 -1 5050 Zj Cj-Zj -300 -350 -250 50 250 -50 0 -50 0 -50 -250 M+50 -27500结果如下：第39页/共59页 得到最优解得到最优解y1=50，y2=0，y3=50，S1=0，S2=0，a1=0， - f 的最大值为的最大值为 -27500，即目标函数，即目标函数f 的最小值的

33、最小值为为f =27500元。元。 从上面可知每台时的租金如下：从上面可知每台时的租金如下：A设备为设备为50元，元，B设备为设备为0元，元，C设备为设备为50元。这样把工厂的元。这样把工厂的所有设备出租可共得租金所有设备出租可共得租金27500元。这对出租者元。这对出租者来说这钱不比自己生产所得的利润少，对租用者来说这钱不比自己生产所得的利润少，对租用者来说这租金是出租者愿意出租设备的最小费用，来说这租金是出租者愿意出租设备的最小费用，因为这是目标函数的最小值。因为这是目标函数的最小值。 结 论第40页/共59页 通过与原问题的最优解比较，发现对偶问题的最优解即最通过与原问题的最优解比较，发

34、现对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通，也能讲得通，。 以后不必解此对偶问题，就可以从原问题的最终单以后不必解此对偶问题，就可以从原问题的最终单纯形表上得到其对偶问题的最优解。纯形表上得到其对偶问题的最优解。第41页/共59页 对偶问题的解为对偶问题的解为: 目标函数最优值为：目标函数最优值为：27500 变量变量 最优解最优解 相差值相差值 Y1 50 0 Y2 0 50 Y3 50 0 约束约束 松弛剩余变量松弛剩余变量 对偶价格对偶价格 1 0 -50 2 0 -250 在对偶问题的解中，如上表

35、可找到产品在对偶问题的解中，如上表可找到产品I的对偶价格为的对偶价格为 -50元，即当元，即当 每件产品每件产品的利润（租金）增加的利润（租金）增加1元，则求最大值的元，则求最大值的总租金应减少总租金应减少50元（即求最小值的总租金增加元（即求最小值的总租金增加50元），也就是原元），也就是原问题的总利润将要提高问题的总利润将要提高50元，也就是说工厂最优生产计划为生产元，也就是说工厂最优生产计划为生产50件件I产品。同样从对偶问题的解中可找到产品产品。同样从对偶问题的解中可找到产品的对偶价格为的对偶价格为 -250元，也就是说当每件元，也就是说当每件 产品的利润增加产品的利润增加1元，则最低

36、总租金元，则最低总租金即原问题的总利润将要提高即原问题的总利润将要提高250元，这条信息也就是告诉我们工元，这条信息也就是告诉我们工厂最优生产计划为生产厂最优生产计划为生产250件件产品。产品。另外，从对偶问题的最另外，从对偶问题的最低总租金低总租金27500元可得元可得到原问题工厂的最大利到原问题工厂的最大利润为润为27500元。元。第42页/共59页说明 对于两个有对偶关系的线性规划的问题只要求得了其中一个最优解，就可以从这个对于两个有对偶关系的线性规划的问题只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道了其中一个最优值也就找到了其对偶问题的对偶价格而求

37、得其对偶问题的最优解，知道了其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。问题的最优值，因为这两个最优值相等。 故在求解一个线性规划问题时，可以把其对偶问题一起来加以考虑，找一个比较容故在求解一个线性规划问题时，可以把其对偶问题一起来加以考虑，找一个比较容易求解的来求解，求出了一个最优解同时也就求出了另一个问题的最优解。易求解的来求解，求出了一个最优解同时也就求出了另一个问题的最优解。 上述的例题要求租金的合理定价不如求解工厂的最大利润，因为求最大利润比较容上述的例题要求租金的合理定价不如求解工厂的最大利润，因为求最大利润比较容易，不需要加上人工变量，而求出了最大利润的问题

38、。易，不需要加上人工变量，而求出了最大利润的问题。 下面来看看如何从原问题结果中写出对偶规划问题的最优解：下面来看看如何从原问题结果中写出对偶规划问题的最优解：第43页/共59页第44页/共59页第45页/共59页 一、两个问题都有可行解，从而都有最优解。 二、一个问题为无界解，另一个问题必有无可行解。 三、两个问题都无可行解。 有关证明看相关的书。想想相互对偶的两个线性规划问题解的关系是怎样的？有三种情形啊！第46页/共59页 前面讲了如何写出求最大值(最小值)的线性规划问题的对偶问题， 但要求该最大值(最小值)线性规划问题的约束条件都取小于等于号(大于等 于号)。下面来阐述如何写出任一个线

39、性规划的问题的对偶问题。第47页/共59页将下面的线性规划化为对偶问题：将下面的线性规划化为对偶问题： Max Z=3X1+4X2+6X3 S.t. 2X1+3X2+6X3440 6X1-4X2-X3100 5X1-3X2+X3=200 X1,X2,X30. 为了写出它的对偶问题，不妨把为了写出它的对偶问题，不妨把 它的约束条件都它的约束条件都变换成取小于等于号的不等式。第一个约束条件不用变换成取小于等于号的不等式。第一个约束条件不用变，而第二个约束，两边都乘以变，而第二个约束，两边都乘以-1， 得得 -6X1+4X2+X3-100。 对于第三个约束条件，可以用小于等于和大于对于第三个约束条件

40、，可以用小于等于和大于等于两个约束条件来替代它。等于两个约束条件来替代它。 即有即有 5X1-3X2+X3200 和和 5X1-3X2+X3200 再把第一个两边乘以再把第一个两边乘以 -1得：得：-5X1+3X2-X3-200. 通过这些变换，得到了一个和原线性规划等价的线通过这些变换，得到了一个和原线性规划等价的线性规划问题：性规划问题：?第48页/共59页 Max Z=3X1+4X2+6X3 S.t. 2X1+3X2+6X3440 -6X1+4X2+X3-100 5X1-3X2+X3200 -5X1+3X2-X3-200. X1,X2,X30. 这个求最大值的线性规划问题的约束条件都取这

41、个求最大值的线性规划问题的约束条件都取小于等于号，小于等于号， 其对偶问题为：其对偶问题为： .,y 0,y 66y 43343y 35562y s.t. 200200100440yfmin 33213333213321332133213321yyyyyyyyyyyyyyyyyyyy 记为条件于原问题的第三个约束这两个决策变量都来源为了表示量一样都是不同的决策变和这里的书上有错啊！第49页/共59页 因为在该对偶问题中因为在该对偶问题中y3和和y3的系数只相差一的系数只相差一个符号，可以把上面的对偶问题化为个符号，可以把上面的对偶问题化为:., 0, ,yy 0,y 6)(6y 4)(343y

42、 3)(562y s.t. )(200100440yfmin 33333333213321332133213321可正可负但尽管令yyyyyyyyyyyyyyyyyyy .y, 0,y , 66y 4343y 3562y s.t. 200100440yfmin : 321321321321321没有限制问题化为这样原规划的对偶规划yyyyyyyyy改正过来！第50页/共59页下面我们用一个例子来说明如何写出一个任意线性规划问题的对偶问题。化为对偶问题的重要做法！对照原线性规划问题，可以知道当原线性规划问题的第i个约束条件取等号时，则其对偶问题的i个决策变量没有非负限制。反过来如果当原线性规划问

43、题中的第i个决策变量Xi没有非负限制时，用类似的方法知道其对偶问题中第i个约束条件取等号。第51页/共59页 .y , 0,y 43y , 9332y 352y s.t. 24060180ymax Z :, 13221321321321没有限制得其对偶规划为然后按上面规则yyyyyyyy作业 . , 0, x . , 0, x24035x 24035x 6032x- ,6032x 18032 x 18032 xs.t. 493xfmin 3213212121321321321321321没有限制没有限制经变换得xxxxxxxxxxxxxxxx如果为如果为5x1+3x20,？第52页/共59页3对偶单纯形法 对偶单纯形法和单纯形法一样都是求解原线性规划问题