《韩伯棠管理运筹学(第三版)-第六章-单纯形法的灵敏度分析与对偶ppt课件.ppt》由会员分享，可在线阅读，更多相关《韩伯棠管理运筹学(第三版)-第六章-单纯形法的灵敏度分析与对偶ppt课件.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 单纯形法的灵敏度分析与对偶 6.1、单纯形表的灵敏度分析 6.2、线性规划的对偶问题 6.3、对偶单纯形法 1单纯形表的灵敏度分析 一、目标函数中变量系数ck 灵敏度分析 1在最终的单纯形表里，xk 是非基变量。 在这种情况下，由于约束方程系数增广矩阵（方程AX=b 系数矩阵为A，它的增广矩阵为(A b) ）在迭代中只是其本身的行的初等变换与 ck 没有任何关系，所以当ck 变成ck + ck 时，在最终单纯形表中其系数的增广矩阵不变，又因为xk 是非基变量，所以基变量的目标函数的系数不变，即cB不变，可知z K也不变，只是ck 变成了ck + ck 。这时K= ckzk 就变成了ck
2、+ck zk=k+ck 。要使得原来的最优解仍为最优解，只要 K+ck 0即可，也就是Ck的增量ck-K 即可。迭代迭代次数次数基基变变量量cB x1 x2 s1 s2 s3 b比值比值 bi/ai2 50 100 0 0 0 0 s1 s2 s3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 300 400 250 zj j=cj-zj 0 0 0 0 0z=0 50 100 0 0 0 xk 是非基变量ck 是系数2在最终的单纯形表中，xk是基变量。 当ck 变成ck + ck时，同上一样，可知在最终的单纯形表中的约束方程的增广矩阵不变，但是基变量在目标函数中的系
3、数cB变了，则zj (j=1,2,n)一般也变了，不妨设cB=(cB1,cB2, cK, ,cBm) , 当cB 变成 (cB1,cB2,（ cK+ck) , ,cBm) , 则：kjkkjkjkjkjjjjkjkkjkmjBmkjKjBjBmjBmkjkKjBjBTmjkjjjBmkKBBjTmjkjjjBmKBBjacaccacczcacacacacacacacaccacacaaaaccccczaaaaccccz- -)z(-z.z . .)(. ),.,.,)(),.,(,.,(:),.,.,)(,.,.,(jjjj2211221121212121这样检验数变成了 这也就是说，要使最优解
4、不变，对于除了akk 外的所有的大于零的akj,ck的增量ck 都要小于等于 j / akj , 对于所有小于零的akj ，ck都要大于等于j / akj 。我们用数学式表示使得最优解不变，c 的变化范围为：. 0, 1, 0,kj ; 0a,a, 0a ; 0a,a, 0a , , 0 :, 0,kkjkjkjkjkjkjkkkkkKKkkkkkkkjjkjjkjkjkkjkjjaxaczcczccccacackj故知知是基变量因为时而当这里当这里当也就是时只要当要使最优解不变0min0maxkjkjjkkjkjjaacaack 目标函数： max z=50 x1+100 x2， 约束条件：
5、 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 先对非基变量先对非基变量s1的目标函数的系数的目标函数的系数c3进行灵敏度分进行灵敏度分析。这里析。这里3=-50，所以当，所以当c3 的增量的增量c3-(-50)即即c350时，时，最优
6、解不变，也就是说最优解不变，也就是说s1的目标函数的系数的目标函数的系数c3=c3+c30+50=50时，最优解不变。时，最优解不变。 再对基变量再对基变量x1的目标函数的系数的目标函数的系数c1进行灵敏度分析。进行灵敏度分析。 也可以按以下方法来计算出使最优解不变的c1的变化范围。 .1000,50505050:,5050,50)150max(max0max:,5050min0min,50150, 0, 0,111111115511111331513111514131211的最优解不变即有的目标函数也就是时这样可知当同样有有可知外有知道除了中在cccccxcaaaaaaaaaaaaaajjj
7、jjj在最终的单纯形表中，用在最终的单纯形表中，用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 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+10
8、0 0 0 - c1 0 c1- 100 用最终单纯形表对cj 进行灵敏度分析，求得使最优解保持不变的c1, c3变化范围与我们在第三章里用计算机求解所得的结果是一样，其实管理运筹学软件就是按这种方法进行编程，对cj 进行灵敏度分析的。 二、约束方程右边常数灵敏度分析 我们在第三章对线性规划问题的计算机求解中，也曾经对约束方程右边常数bj 进行了灵敏度分析，根据计算机输出的表格，可知道，约束方程右边常数在什么范围内变化时，其对偶价格不变，那么在用单纯形表对bj 进行灵敏度分析时，首先应从单纯形表中找到有关对偶价格的信息。 在第三章里我们给了对偶价格这样的定义：变量或人工变量)的zj 有关。下面
9、我们仍以第二章例1为例在其最终单纯形表上找出其约束条件的对偶价格。 此题的最终单纯形表如下，这是一个求目标函数最大值的问题此题的最终单纯形表如下，这是一个求目标函数最大值的问题。 从上表可以发现设备台时数的约束方程中的松弛变量s1 的zj 值50正好等于计算机解中设备台数的对偶价格，原料A约束方程中的松弛变量s2 的zj 值0正好等于计算机解中的原料A的对偶价格。同样原料B的约束方程中的松弛变量s3 的zj 值50正好等于计算机解中的原料B的对偶价格。迭代次数基变量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
10、 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松弛变量的zj 值是否等于对应的约束条件的对偶价格呢?回答是肯定的。 下面我们来看一看对于非基变量的松弛变量的下面我们来看一看对于非基变量的松弛变量的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 5025
11、0 zj j=cj-zj 50 100 50 0 50 0 0 -50 0 -5027500 对于含有大于等于号的约束条件，为了化成标准型就添上了剩余变量。这时这个约束条件的对偶价格就和这个剩余变量的Zj 有关了。只不过当约束条件右边的常量增加一个单位时，约束条件更严格了。这将给满足约束条件带来些困难。就使最优目标函数值特别“恶化”而不是改进，故这时，约束条件的对偶价格应取Zj 值的相反数-Zj。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的Zj 值。 下面我们给出一个由最终单纯形表对于不同约束类型的对偶价格的取
12、值表：约束类型约束类型 对偶价格的取值对偶价格的取值 等于这个约束条件对应的松弛变量的等于这个约束条件对应的松弛变量的Zj值值 等于与这个约束条件对应的剩余变量的等于与这个约束条件对应的剩余变量的Zj值的相反数值的相反数-Zj= 等于与这个约束条件对应的人工变量的等于与这个约束条件对应的人工变量的Zj 值值F 从对偶价格的定义，可以知道当对偶价格为正时，它将改进目标函数值。对于求目标函数最大值的线性规划来说改进就是增加其目标函数值，而对求目标函数最小值的线性规划来说改进却是减少其目标函数值。F 当对偶价格为负时，它将“恶化”目标函数值，对求目标函数最大值的线性规划来说恶化就是减少其目标函数值，
13、而对求目标函数最小值的线性规划来说“恶化”却是增加其目标函数值。F 在第三章我们已提及过影子价格，对于求目标函数最大值的线性规划中对偶价格等于影子价格，而对求目标函数最小值的线性规划中影子价格为对偶价格的相反数。 下面我们就来求出bj 的变化范围，在这个范围内变化其对偶价格不变。$ 一般地，由于bj 的变化，资源投入起了变化，最优解是变化的。从这时也可以看出：所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量(最优基)不变，且所得的最优解仍然是可行的bj 的变化范围。 下面我们来看一下当某个bk 变成bk =bk+bk时在原来的最终单纯形表中的基不变的条件下，最终单纯形表会有什
14、么变化。 单纯形表的迭代实际上是约束方程的增广矩阵的行的初等变换，bk的变化不会影响系数矩阵的迭代，所以在最终单纯形表的系数矩阵不变，又已知最终单纯形表中的基不变，可知CB不变，这样Zj=CBpTj 也不变，检验数j=Cj-Zj 也不变，唯一带来变化的只是最终单纯形表中的b列，那么bk变化前后的b列到底有什么关系呢? 原来的约束方程组不妨用矩阵表示为Ax=b，通过一些单纯形表的迭代变成以B为基的最终单纯形表，实际上也就是在原来的约束方程组左乘B-1。即B-1AX=B-1b，在初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里正好就变成了B-1，这里可知： 其实迭代过程也是用矩阵初等变
15、换求B的逆阵B-1的过程。1001121011B 这样在最终单纯形表里系数矩阵就是这样在最终单纯形表里系数矩阵就是B-1A，基变，基变量量(记为记为xB)的解就为的解就为B-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 的变化范围。bbbbb
16、bbbbbbbbbbkkmkkmk则令,0.0b, 0.0.,.11 mkkkkkkkkmkkkKdbdbdbdbbBdddD. ,. 321121则 在上述的不等式中求出满足所有不等式的bk 的范围，也就确定了bk 的变化范围，bk在此范围内变化使得其对应的约束条件的对偶价格不变。即bk的变化范围是：m)1,2,.,(j . 0. 0. , 0,. . :221121211jkkBjmkkBmkkBkkBBmkkkkkkBmBBBBBdbxdbxdbxdbxxdbdbdbxxxbBxxx即要求每个分量即要使为新的最优解0min0max ikikBikikikBiddxbddxB-1的第K列在
17、最终单纯形表中如何确定? 我们知道初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里就变成了B-1，B-1的第k列是由初始单纯形表里的系数矩阵中的单位矩阵中的单位列向量ek ，通过迭代在最终单纯形表中就变成了B-1 的第k列。如果第K个的约束方程中有松弛变量，那么这个松弛变量在最终单纯形表上的系数列正好就是B-1的第K列，因为这个松弛变量在初始单纯表上的系数列正好就是单位向量ek 。如果第K个约束方程有剩余变量，那么B-1的第K列正好等于这个剩余变量在最终单纯形表上的系数列的相反数，因为这个剩余变量在初始单纯形表上的系数列正好是单位向量ek 的负向量，如果第K个约束方程只有人工变量，
18、那么B-1第K列正好是这个人工变量在最终单纯形表上的系数列，因为这个人工变量在初始单纯形表上的系数列正好是单位向量ek 。 对b1分析，因为第一个方程中含有松弛变量S1，故松弛变量在最终单纯形表中的系数列 (1, -2，0) T 就是B-1 的第一列。d11=10, d21=-20=-50/1=-50，而min -XB i/di1 dI 1 0，则继续进行迭代以求出新的最优解。 下面仍以第二章例1为例来加以说明。例例 该厂除了生产该厂除了生产、产品外，现试制成一个新产品产品外，现试制成一个新产品，已知，已知生产产品生产产品，每件需要设备，每件需要设备2台时，并消耗台时，并消耗A原料原料0.5公
19、斤，公斤，B原料原料1.5公斤，获利公斤，获利150元，问该厂是否应生产该产品和生产多少元，问该厂是否应生产该产品和生产多少? 解：这是一个增加一个新的变量的问题。可以把它认为是一个改变变 量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
20、50250 zj j=cj-zj 50 100 50 0 50 175 0 0 -50 0 -50 -25275005 .125 .05 .15 .02100112101 :)5 .1 , 5 .0 , 2(61pB变为在最终表上 这时Z6=500.5+1001.5=175, 6=C6 Z6=150-175=-25。如上表所示，这时新变量的检验数6 小于零，可知原最优解就是新问题的最优解，即该厂还应该生产I产品50件， 产品250件，不生产产品可得最大利润27500元。 :,35125160 ,125105 . 0)100, 0 ,50(Z ,105 . 0125 . 1100112101 :
21、66661613把这些结果填入下表在最终表上的系数列首先求出解zcpBpBxj 显然，由于6 0，可知这不是最优解，要进行迭代，选取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 可知此规划的最优解x1=0，x2=0，s1=0，s2=0，s3=50，x3
22、=200，此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品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
23、0200500 zj j=cj-zj120 100 80 20 0 160 -70 0 -80 -20 0 032000 2在初始表上的变量Xk的系数列pK改变为pK ，经过迭代后，在最终表上Xk是基变量，在这种情况下原最优解的可行性和最优解都可能遭到破坏，问题变得十分复杂。一般不去修改原最终表，而是重新计算。 在学了灵敏度分析之后，我们来看一看如何从“管理运筹学”软件的计算输出上去识别线性规划问题有惟一解呢，还是具有无穷多组解?从单纯形法上我们知道有无穷多组解的识别方法为是否存在一个非基变量的检验数为零，如果存在，则此线性规划有无穷多组解，如不存在，则此线性规划只有惟一解。 1如果在最终表上
24、检验数为零的非基变量是松弛变量或剩余变量Sk。显然在计算机输出中没有专门松弛变量与剩余变量栏，但是我们仍然从输出中找到它们的信息。首先由于是非基变量，可知在最优解中其值都为零，也就是在计算机输出的约束条件栏里，某一个约束条件的松弛或剩余变量的值为零，又因为这个非基变量的检验数为零，所以这个约束条件的对偶价格为零。反过来说，如果在计算机输出的约束条件栏里有一个约束条件的松弛或剩余变量为零，且其对偶价格也为零，那么我们就可知道有一个非基变量的松弛变量或剩余变量的检验数为零，这个线性规划有无穷多组解。 2如果在最终单纯形表上，检验数为零的非基变量是一般决策变量XK。在对非基变量XK的目标系数CK的灵
25、敏度分析中知道CKK，对任何非基变量Xi 在计算机输出的相差值一栏中就记录了i 的值，它表示只有目标函数系数Ci 的增量改进了i 的值，Xi 才有可能成为基变量而取正值。因为K=0，所以很容易从计算机输出中识别出Xk ，也就是说只要在计算机输出中存在一个取值为零的决策变量并且其相差值也为零，我们就可以确认这个变量就是最终表上检验数为零的非基变量，可知此线性规划有无穷多组解。如果在计算机输出解的信息中不存在上述这两种情况，我们可以断定此线性规划只有惟一最优解。 每一个线性规划问题，都存在每一个与它密切相关的线性规每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，称其中的任一个为原问题
26、，另一个为对偶问题。在这划的问题，称其中的任一个为原问题，另一个为对偶问题。在这一节中将揭示原问题与对偶问题的关系，如何将原问题转化为其一节中将揭示原问题与对偶问题的关系，如何将原问题转化为其对偶问题，如何从原问题的求解的结果中去找到其对偶问题的答对偶问题，如何从原问题的求解的结果中去找到其对偶问题的答案，并介绍对偶问题的经济解释以及对偶单纯形法。先来看一个案，并介绍对偶问题的经济解释以及对偶单纯形法。先来看一个例题。例题。 例例4 某工厂在计划期内安排某工厂在计划期内安排、两种产品，已知生产单位产两种产品，已知生产单位产品所需设备品所需设备A、B、C台时如表所示：台时如表所示：资源限量设备A
27、11300台时设备B21400台时设备C01250台时F 该工厂每生产一该工厂每生产一单位产品单位产品可获利可获利50元，每生产一单位产元，每生产一单位产品品可获利可获利100元，问元，问工厂应分别生产多少工厂应分别生产多少产品和产品和产品，才产品，才能使工厂获利最多能使工厂获利最多?6.2 线性规划的对偶问题 此例题与第二章例1有相同之处，只是不过把原料A、B改成了设备B、设备C，做这些改动是为了使读者更容易理解。 这个问题的数学模型与第二章的例1是一样的，求解的结果也是一样的。 设X1为产品的计划产量，X2为产品的计划产量，则有：目标函数：max Z =50X1+100X2 约束条件：X1
28、+X2300, 2X1+X2400, X2250, X1, X20. 现在从另一个角度来考虑这个问题。假如现在从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢那么该厂的厂长应该如何来确定合理的租金呢? 设设y1，y2，y3分别为设备分别为设备A、B、C的每台时的每台时的租金。为了叙述方便，这里把租金定义为的租金。为了叙述方便，这里把租金定义为扣除成本后的利润，也就是由于出租可以获扣除成本后的利润，也就是由于出租可以获得的利润。建立模型要从两方面来考虑：得的利润。建立模型要从两方面来考虑： 思路：
29、把生产单位思路：把生产单位产品所需各设备的台时总租金产品所需各设备的台时总租金不应当低于原利润不应当低于原利润50元，即元，即y1+2y250，否则就不出租还，否则就不出租还是用于生产是用于生产产品以获利产品以获利50元；同样把生产一单位元；同样把生产一单位产产品所需各设备的台时的总租金也不应当低于原利润品所需各设备的台时的总租金也不应当低于原利润100元，即元，即y1+y2+y3100，否则这些设备台时就不出租，还，否则这些设备台时就不出租，还是用于生产是用于生产产品以获利产品以获利100元。元。租金租金资源限量资源限量设备设备A,y111300台时台时设备设备B,y221400台时台时设备
30、设备C,y301250台时台时怎么做？怎么做？一、作为出租者来说一、作为出租者来说: 这样从两个不同的角度来考虑同一个工厂的最大这样从两个不同的角度来考虑同一个工厂的最大利润利润(最小租金最小租金)的问题，所建立起来的两个线性规划的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题。下面来研究这两个问题在数另外一个就叫对偶问题。下面来研究这两个问题在数学模型上的关系。学模型上的关系。 &他要求在满足上述要求的前提下，也就是在出租者愿他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部
31、设备台时的总租金越低越好，意出租的前提下尽量要求全部设备台时的总租金越低越好，& 即即min 300y1+400y2+250y3，& 这样得到了该问题的数学模型：这样得到了该问题的数学模型：二、对于租用者来说二、对于租用者来说:一样的吗？一样的吗？ 1求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。不等式。 2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 3原
32、问题的约束条件的右边常数项为对偶原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题问题的目标函数中的变量的系数。并且原问题的第的第i 个约束条件的右边常数项就等于对偶问个约束条件的右边常数项就等于对偶问题的目标函数中的第题的目标函数中的第 i个变量的系数。个变量的系数。 4对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A是原是原问题约束条件的系数矩阵的转置问题约束条件的系数矩阵的转置ATnm2n1nm12111Ta.aa.a.aaA 则 ,a.aa.a.aaA mnm2m11n1211设 在例在例4中，对于原问题其约束条件为：中，对于原问题其约束条件为： X1
33、01211对应的对偶问题的约束条件为：对应的对偶问题的约束条件为： Y111021则其对偶问题： min f=bT y AT yCT, y0, 其中 y=(y1, y2, ym)T 用矩阵的形式来表示，则原问题变为：max Z=CX AXb X0其中其中A为为mn矩阵，该问题有矩阵，该问题有m个约束条件个约束条件n个变量，个变量，X=(X1,X2,Xn)T, b=(b1, b2, bm)T, C=(C1,C2,Cn)。 以上问题的原问题已在第五章里用单纯形求出，以上问题的原问题已在第五章里用单纯形求出，现在我们用单纯形法求出其对偶问题的解。现在我们用单纯形法求出其对偶问题的解。 加上剩余变量加
34、上剩余变量S1, S2和人工变量和人工变量a1 ，把此问题，把此问题化成标准型如下：化成标准型如下： max (-f )=-300y1- 400y2 -250y3 Ma1 y1+2y2-S1+a1=50， y1+y2+y3 S2= 100， y1，y2，y3，S1，S3，a10 把上述数据填人单纯形表计算。把上述数据填人单纯形表计算。迭代迭代次数次数基变基变量量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 -
35、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 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 -2
36、7500结果如下：结果如下： 得到最优解得到最优解y1=50，y2=0，y3=50，S1=0，S2=0，a1=0， - f 的最大值为的最大值为 -27500，即目标函数，即目标函数f 的最小值为的最小值为f =27500元。元。 从上面可知每台时的租金如下：从上面可知每台时的租金如下：A设备为设备为50元，元，B设备为设备为0元，元，C设备为设备为50元。这样把工厂的所有设元。这样把工厂的所有设备出租可共得租金备出租可共得租金27500元。这对出租者来说这钱不元。这对出租者来说这钱不比自己生产所得的利润少，对租用者来说这租金是比自己生产所得的利润少，对租用者来说这租金是出租者愿意出租设备的最
37、小费用，因为这是目标函出租者愿意出租设备的最小费用，因为这是目标函数的最小值。数的最小值。 结结 论论 通过与原问题的最优解比较，发现对偶问题的最优解即最佳通过与原问题的最优解比较，发现对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通，讲得通，。 以后不必解此对偶问题，就可以从原问题的最终单纯形以后不必解此对偶问题，就可以从原问题的最终单纯形表上得到其对偶问题的最优解。表上得到其对偶问题的最优解。 对偶问题的解为对偶问题的解为: 目标函数最优值为：目标函数最优值为：27500 变量变量 最优解最优解 相差值相差
38、值 Y1 50 0 Y2 0 50 Y3 50 0 约束约束 松弛剩余变量松弛剩余变量 对偶价格对偶价格 1 0 -50 2 0 -250 在对偶问题的解中，如上表可找到产品在对偶问题的解中，如上表可找到产品I的对偶价格为的对偶价格为 -50元，即当元，即当 每件产品每件产品的利润（租金）增加的利润（租金）增加1元，则求最大值的总元，则求最大值的总租金应减少租金应减少50元（即求最小值的总租金增加元（即求最小值的总租金增加50元），也就是原问元），也就是原问题的总利润将要提高题的总利润将要提高50元，也就是说工厂最优生产计划为生产元，也就是说工厂最优生产计划为生产50件件I产品。同样从对偶问题
39、的解中可找到产品产品。同样从对偶问题的解中可找到产品的对偶价格为的对偶价格为 -250元，也就是说当每件元，也就是说当每件 产品的利润增加产品的利润增加1元，则最低总租金即元，则最低总租金即原问题的总利润将要提高原问题的总利润将要提高250元，这条信息也就是告诉我们工厂元，这条信息也就是告诉我们工厂最优生产计划为生产最优生产计划为生产250件件产品。产品。另外，从对偶问题的最另外，从对偶问题的最低总租金低总租金27500元可得元可得到原问题工厂的最大利到原问题工厂的最大利润为润为27500元。元。说明说明 对于两个有对偶关系的线性规划的问题只要求得了其对于两个有对偶关系的线性规划的问题只要求得
40、了其中一个最优解，就可以从这个问题的对偶价格而求得其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道了其中一个最优值也就找到了对偶问题的最优解，知道了其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。其对偶问题的最优值，因为这两个最优值相等。 故在求解一个线性规划问题时，可以把其对偶问题一故在求解一个线性规划问题时，可以把其对偶问题一起来加以考虑，找一个比较容易求解的来求解，求出了起来加以考虑，找一个比较容易求解的来求解，求出了一个最优解同时也就求出了另一个问题的最优解。一个最优解同时也就求出了另一个问题的最优解。 上述的例题要求租金的合理定价不如求解工厂
41、的最大上述的例题要求租金的合理定价不如求解工厂的最大利润，因为求最大利润比较容易，不需要加上人工变量，利润，因为求最大利润比较容易，不需要加上人工变量，而求出了最大利润的问题。而求出了最大利润的问题。 下面来看看如何从原问题结果中写出对偶规划问题的下面来看看如何从原问题结果中写出对偶规划问题的最优解：最优解： 一、两个问题都有可行解，从而都有最优解。一、两个问题都有可行解，从而都有最优解。 二、一个问题为无界解，另一个问题必有无二、一个问题为无界解，另一个问题必有无可行解。可行解。 三、两个问题都无可行解。三、两个问题都无可行解。 有关证明看相关的书。有关证明看相关的书。想想相互对偶的两个线性
42、规想想相互对偶的两个线性规划问题解的关系是怎样的？划问题解的关系是怎样的？有三种情形啊！ 前面讲了如何写出求最大值前面讲了如何写出求最大值(最最小值小值)的线性规划问题的对偶问题，的线性规划问题的对偶问题， 但要求该最大值但要求该最大值(最小值最小值)线性规划线性规划问题的约束条件都取小于等于号问题的约束条件都取小于等于号(大大于等于等 于号于号)。下面来阐述如何写出。下面来阐述如何写出任一个线性规划的问题的对偶问题。任一个线性规划的问题的对偶问题。将下面的线性规划化为对偶问题：将下面的线性规划化为对偶问题： Max Z=3X1+4X2+6X3 S.t. 2X1+3X2+6X3440 6X1-
43、4X2-X3100 5X1-3X2+X3=200 X1,X2,X30. 为了写出它的对偶问题，不妨把为了写出它的对偶问题，不妨把 它的约束条件都变它的约束条件都变换成取小于等于号的不等式。第一个约束条件不用变，换成取小于等于号的不等式。第一个约束条件不用变，而第二个约束，两边都乘以而第二个约束，两边都乘以-1， 得得 -6X1+4X2+X3-100。 对于第三个约束条件，可以用小于等于和大于等对于第三个约束条件，可以用小于等于和大于等于两个约束条件来替代它。于两个约束条件来替代它。 即有即有 5X1-3X2+X3200 和和 5X1-3X2+X3200 再把第一个两边乘以再把第一个两边乘以 -
44、1得：得：-5X1+3X2-X3-200. 通过这些变换，得到了一个和原线性规划等价的线性通过这些变换，得到了一个和原线性规划等价的线性规划问题：规划问题：? Max Z=3X1+4X2+6X3 S.t. 2X1+3X2+6X3440 -6X1+4X2+X3-100 5X1-3X2+X3200 -5X1+3X2-X3-200. X1,X2,X30. 这个求最大值的线性规划问题的约束条件都取小这个求最大值的线性规划问题的约束条件都取小于等于号，于等于号， 其对偶问题为：其对偶问题为： .,y 0,y 66y 43343y 35562y s.t. 200200100440yfmin 3321333
45、3213321332133213321yyyyyyyyyyyyyyyyyyyy 记为条件于原问题的第三个约束这两个决策变量都来源为了表示量一样都是不同的决策变和这里的书上有错啊！书上有错啊！ 因为在该对偶问题中因为在该对偶问题中y3和和y3的系数只相差一个符的系数只相差一个符号，可以把上面的对偶问题化为号，可以把上面的对偶问题化为:., 0, ,yy 0,y 6)(6y 4)(343y 3)(562y s.t. )(200100440yfmin 33333333213321332133213321可正可负但尽管令yyyyyyyyyyyyyyyyyyy .y, 0,y , 66y 4343y 3
46、562y s.t. 200100440yfmin : 321321321321321没有限制问题化为这样原规划的对偶规划yyyyyyyyy改正过来！改正过来！下面我们用一个例子来说明下面我们用一个例子来说明如何写出一个任意线性规划如何写出一个任意线性规划问题的对偶问题。问题的对偶问题。化为对偶问题的重要做法！化为对偶问题的重要做法！对照原线性规划问题，可以知道当对照原线性规划问题，可以知道当原线性规划问题的第原线性规划问题的第i个约束条件取个约束条件取等号时，则其对偶问题的等号时，则其对偶问题的i个决策变个决策变量没有非负限制。反过来如果当原量没有非负限制。反过来如果当原线性规划问题中的第线性
47、规划问题中的第i个决策变量个决策变量Xi没有非负限制时，用类似的方法知没有非负限制时，用类似的方法知道其对偶问题中第道其对偶问题中第i个约束条件取等个约束条件取等号。号。 .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没有限制没有限制经变换得xxxxxxxxx
48、xxxxxxx如果为如果为5x1+3x20,？3对偶单纯形法 对偶单纯形法和单纯形法一样都是求解原线性规划问题对偶单纯形法和单纯形法一样都是求解原线性规划问题的一种方法。单纯形法是在保持原问题的所有约束条件的常的一种方法。单纯形法是在保持原问题的所有约束条件的常数大于等于零的情况下，通过迭代，使得所有的检验数都小数大于等于零的情况下，通过迭代，使得所有的检验数都小于等于零，最后求得最优解；而对偶单纯形法则是在保持原于等于零，最后求得最优解；而对偶单纯形法则是在保持原问题的所有检验数都小于等于零的情况下，通过迭代，使得问题的所有检验数都小于等于零的情况下，通过迭代，使得所有约束条件的常数都大于等
49、于零，最后求得最优解。所有约束条件的常数都大于等于零，最后求得最优解。 使用对偶单纯形法时初始解可以是非可行解，对于使用对偶单纯形法时初始解可以是非可行解，对于些些大于等于号的约束不等式不需要添加人工变量，只要把该不大于等于号的约束不等式不需要添加人工变量，只要把该不等式两边乘以等式两边乘以-1，化成小于等于不等式的约束，就可用对偶，化成小于等于不等式的约束，就可用对偶单纯形法来求解，简化计算，这是对偶单纯形的优点，但是单纯形法来求解，简化计算，这是对偶单纯形的优点，但是对偶单纯形法在使用上有很大的局限性，这主要是对大多数对偶单纯形法在使用上有很大的局限性，这主要是对大多数线性规划问题，很难找
50、到一个初始解使得其所有检验数都小线性规划问题，很难找到一个初始解使得其所有检验数都小于等于零，因而这种方法在求解线性规划问题时很少单独应于等于零，因而这种方法在求解线性规划问题时很少单独应用。但在灵敏度分析中，有时需要用对偶单纯形法这样可用。但在灵敏度分析中，有时需要用对偶单纯形法这样可使问题处理简化。使问题处理简化。 下面就第二章例下面就第二章例1为例说明在灵敏度分析为例说明在灵敏度分析时如何使用对偶单纯形法以及对偶单纯形法的求解过程。时如何使用对偶单纯形法以及对偶单纯形法的求解过程。 在上节对b的灵敏度分析中已知当250b1325时第一个约束条件的对偶价格不变，现在如果b1=300变成b1