韩伯棠管理运筹学(第三版)第六章 单纯形法的灵敏度分析与对偶ppt课件.ppt

第六章 单纯形法的灵敏度分析与对偶,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+ck zk=k+ck 。要使得原来的最优解仍为最优解，只要 K+ck 0即可，也就是Ck的增量ck-K 即可。,xk 是非基变量,ck 是系数,2在最终的单纯形表中，xk是基变量。,当ck 变成ck + ck时，同上一样，可知在最终的单纯形表中的约束方程的增广矩阵不变，但是基变量在目标函数中的系数cB变了，则zj (j=1,2,n)一般也变了，不妨设cB=(cB1,cB2, cK, ,cBm) , 当cB 变成 (cB1,cB2,（ cK+ck) , ,cBm) , 则：,这也就是说，要使最优解不变，对于除了akk 外的所有的大于零的akj,ck的增量ck 都要小于等于 j / akj , 对于所有小于零的akj ，ck都要大于等于j / akj 。我们用数学式表示使得最优解不变，c 的变化范围为：,以第2章例1为例在最终的单纯形表上对ck进行灵敏度分析。,目标函数： max z=50 x1+100 x2， 约束条件： x1+x2300， 2x1+x2400， x2250, x10, x20. 此题在第五章里，已得到最终单纯形表为：,先对非基变量s1的目标函数的系数c3进行灵敏度分析。这里3=-50，所以当c3 的增量c3-(-50)即c350时，最优解不变，也就是说s1的目标函数的系数c3=c3+c30+50=50时，最优解不变。 再对基变量x1的目标函数的系数c1进行灵敏度分析。,也可以按以下方法来计算出使最优解不变的c1的变化范围。,在最终的单纯形表中，用c1代替原来的c1=50计算得表如下：,从30，得到-c10，即c10，并且从50， 得到c1-1000，c1100。 从上两式可知：当0c1100 时最优解不变，如果采取了不属于这范围的c1，必存在某个检验数j0，我们可以继续用单纯形表进行迭代，以求出新的最优解。,用最终单纯形表对cj 进行灵敏度分析，求得使最优解保持不变的c1, c3变化范围与我们在第三章里用计算机求解所得的结果是一样，其实管理运筹学软件就是按这种方法进行编程，对cj 进行灵敏度分析的。,二、约束方程右边常数灵敏度分析 我们在第三章对线性规划问题的计算机求解中，也曾经对约束方程右边常数bj 进行了灵敏度分析，根据计算机输出的表格，可知道，约束方程右边常数在什么范围内变化时，其对偶价格不变，那么在用单纯形表对bj 进行灵敏度分析时，首先应从单纯形表中找到有关对偶价格的信息。 在第三章里我们给了对偶价格这样的定义：在约束条件右边量增加一个单位而使最优目标值得到改进的数量。根据这个定义，我们可以发现约束条件的对偶价格与松弛变量(或剩余变量或人工变量)的zj 有关。下面我们仍以第二章例1为例在其最终单纯形表上找出其约束条件的对偶价格。,此题的最终单纯形表如下，这是一个求目标函数最大值的问题。,从上表可以发现设备台时数的约束方程中的松弛变量s1 的zj 值50正好等于计算机解中设备台数的对偶价格，原料A约束方程中的松弛变量s2 的zj 值0正好等于计算机解中的原料A的对偶价格。同样原料B的约束方程中的松弛变量s3 的zj 值50正好等于计算机解中的原料B的对偶价格。,松弛变量的zj 值是否等于对应的约束条件的对偶价格呢?回答是肯定的。,首先知道在最优解中s2=50是基变量，也就是说，原料A有50千克没用完，再增加原料A是不会带来任何利润的，故原料A的对偶价格为零。在最终单纯形表上当松弛变量为基变量时，都有其检验数j 为零，又知道对任何的松弛变量，它在目标函数中的系数cj 都为零，那么为基变量的松弛变量的zj也必然为零，因为zj=cj- j=0-0=0，这正确地反映了对于任何为基变量的松弛变量所对应的约束条件的对偶价格为零。,下面我们来看一看对于非基变量的松弛变量的zj 值是否也正确地给出了与其对应的约束条件的对偶价格?,因为对所有松弛变量都有cj=0所以zj=cj-j=-j，在对非基变量的目标函数的灵敏度分析中，知道当cj-j时最优解不变。也就是说当cj-j 时，非基变量仍然为非基变量，仍然为零。这时与其对应的约束条件譬如说设备台时数全部使用完了。只有当cj-j ，也就是cjzj时，对应为非基变量的松弛变量要变成入基变量了。对于设备台时数来说，当其松弛变量在目标函数中系数从零变到z3=50时，也就是说只有当余下一个台时数的设备不能获利变成能获利50元时，譬如说别人愿意出价50元买一个设备时，就不必为生产、产品而使用完所有的设备台时了，这正说明了设备台数的对偶价格就是z3=50元。同样我们也可以知道原料B的对偶价格为z5=50元。,对于含有大于等于号的约束条件，为了化成标准型就添上了剩余变量。这时这个约束条件的对偶价格就和这个剩余变量的Zj 有关了。只不过当约束条件右边的常量增加一个单位时，约束条件更严格了。这将给满足约束条件带来些困难。就使最优目标函数值特别“恶化”而不是改进，故这时，约束条件的对偶价格应取Zj 值的相反数-Zj。 对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的Zj 值。 下面我们给出一个由最终单纯形表对于不同约束类型的对偶价格的取值表：,从对偶价格的定义，可以知道当对偶价格为正时，它将改进目标函数值。对于求目标函数最大值的线性规划来说改进就是增加其目标函数值，而对求目标函数最小值的线性规划来说改进却是减少其目标函数值。 当对偶价格为负时，它将“恶化”目标函数值，对求目标函数最大值的线性规划来说恶化就是减少其目标函数值，而对求目标函数最小值的线性规划来说“恶化”却是增加其目标函数值。 在第三章我们已提及过影子价格，对于求目标函数最大值的线性规划中对偶价格等于影子价格，而对求目标函数最小值的线性规划中影子价格为对偶价格的相反数。,下面我们就来求出bj 的变化范围，在这个范围内变化其对偶价格不变。,当bj 变成bj =bj+bj 时，由于表的迭代实际是约束方程的增广矩阵行的初等变换，bj的变化并不影响系数矩阵的迭代，故其最终表中的系数矩阵没有变化，要使其对偶价格不变，只要原来最终表中的所有Zj值都不变，而Zj 值是由基变量的系数与系数矩阵中j 列对应元素相乘所得即Zj=CBpTj 。这样基变量的系数CB不变，也就是所有的基变量仍然是基变量，即基不变时，原线性规划问题的对偶价格就不变。而要使所有的基变量仍然是基变量只要当bj 变化成bj =bj+bj时，原来的基不变所得到的基本解仍然是可行解，也就是所求得的基变量的值仍然大于等于零。,一般地，由于bj 的变化，资源投入起了变化，最优解是变化的。从这时也可以看出：所谓使其对偶价格不变的bj的变化范围，也就是使其最优解的所有基变量(最优基)不变，且所得的最优解仍然是可行的bj 的变化范围。 下面我们来看一下当某个bk 变成bk =bk+bk时在原来的最终单纯形表中的基不变的条件下，最终单纯形表会有什么变化。,单纯形表的迭代实际上是约束方程的增广矩阵的行的初等变换，bk的变化不会影响系数矩阵的迭代，所以在最终单纯形表的系数矩阵不变，又已知最终单纯形表中的基不变，可知CB不变，这样Zj=CBpTj 也不变，检验数j=Cj-Zj 也不变，唯一带来变化的只是最终单纯形表中的b列，那么bk变化前后的b列到底有什么关系呢? 原来的约束方程组不妨用矩阵表示为Ax=b，通过一些单纯形表的迭代变成以B为基的最终单纯形表，实际上也就是在原来的约束方程组左乘B-1。即B-1AX=B-1b，在初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里正好就变成了B-1，这里可知： 其实迭代过程也是用矩阵初等变换求B的逆阵B-1的过程。,这样在最终单纯形表里系数矩阵就是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 的变化范围。,知道B-1b就是原来最终单纯形表中基变量xB的值，而B-1b项中的b=(0,0，0, bk,0,0)T，这样可知B-1b就等于矩阵B-1中的第k列乘以bk所得的结果，即B-1b=bkDk ，其中DK是B-1第k列,有,在上述的不等式中求出满足所有不等式的bk 的范围，也就确定了bk 的变化范围，bk在此范围内变化使得其对应的约束条件的对偶价格不变。即bk的变化范围是：,B-1的第K列在最终单纯形表中如何确定?,我们知道初始单纯形表里的系数矩阵中的单位矩阵通过迭代在最终单纯形表里就变成了B-1，B-1的第k列是由初始单纯形表里的系数矩阵中的单位矩阵中的单位列向量ek ，通过迭代在最终单纯形表中就变成了B-1 的第k列。如果第K个的约束方程中有松弛变量，那么这个松弛变量在最终单纯形表上的系数列正好就是B-1的第K列，因为这个松弛变量在初始单纯表上的系数列正好就是单位向量ek 。如果第K个约束方程有剩余变量，那么B-1的第K列正好等于这个剩余变量在最终单纯形表上的系数列的相反数，因为这个剩余变量在初始单纯形表上的系数列正好是单位向量ek 的负向量，如果第K个约束方程只有人工变量，那么B-1第K列正好是这个人工变量在最终单纯形表上的系数列，因为这个人工变量在初始单纯形表上的系数列正好是单位向量ek 。,下面仍以第二章例1为例在最终单纯形表上对bj 进行灵敏度分析。,对b1分析，因为第一个方程中含有松弛变量S1，故松弛变量在最终单纯形表中的系数列 (1, -2，0) T 就是B-1 的第一列。d11=10, d21=-20=-50/1=-50，而min -XB i/di1 dI 1 0=-50/(-2)=25 ，故有当 -50b125时，即当300-50b1=b1+b1300+25，250b1325时，第1个约束条件对偶价格不变。其实际意义即可阐述为：当设备台时数在250与325之间变化时，则该约束条件即设备台时数的对偶价格不变，都为每设备台时50元。这样所得的结果和用计算机计算输出的结果是一样的。,三、约束方程系数矩阵A灵敏度分析,下面分两种情况讨论 1在初始单纯形表上的变量XK 的系数列pK 改变为pK ，经过迭代后，在最终单纯形表上Xk 是非基变量。 由于单纯形表的迭代是约束方程的增广矩阵的行变换，PK变成PK 仅仅影响最终单纯形表上的第K列数据包括XK的系数列、ZK以及K ，这时最终单纯形表上的XK的系数列就变成 B-1 pK ，而ZK就变成CBB-1 pK ，新的检验数: K=CK - CBB-1 pK 。 若K0，则原最优解仍然是最优解。若K 0，则继续进行迭代以求出新的最优解。 下面仍以第二章例1为例来加以说明。,例 该厂除了生产、产品外，现试制成一个新产品，已知生产产品，每件需要设备2台时，并消耗A原料0.5公斤，B原料1.5公斤，获利150元，问该厂是否应生产该产品和生产多少?,解：这是一个增加一个新的变量的问题。可以把它认为是一个改变变 量x3在初始表上的系数列的问题，从(0，0，0)T 变成(2，0.5，1.5)T 。这样在原来的最终表上添上新的一列变量，X3 的一列，把它放在S3 之后的第6列上，显然X3 是非基变量，,这时Z6=500.5+1001.5=175, 6=C6 Z6=150-175=-25。如上表所示，这时新变量的检验数6 小于零，可知原最优解就是新问题的最优解，即该厂还应该生产I产品50件， 产品250件，不生产产品可得最大利润27500元。,例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用设备1.5台时，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的原生产计划是否要修改。,显然，由于6 0，可知这不是最优解，要进行迭代，选取X3为入基变量，X1为出基变量。,可知此规划的最优解x1=0，x2=0，s1=0，s2=0，s3=50，x3=200，此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品200件，可获最大利润32000元。,2在初始表上的变量Xk的系数列pK改变为pK ，经过迭代后，在最终表上Xk是基变量，在这种情况下原最优解的可行性和最优解都可能遭到破坏，问题变得十分复杂。一般不去修改原最终表，而是重新计算。,在学了灵敏度分析之后，我们来看一看如何从“管理运筹学”软件的计算输出上去识别线性规划问题有惟一解呢，还是具有无穷多组解?从单纯形法上我们知道有无穷多组解的识别方法为是否存在一个非基变量的检验数为零，如果存在，则此线性规划有无穷多组解，如不存在，则此线性规划只有惟一解。,我们分两种情况进行讨论。,1如果在最终表上检验数为零的非基变量是松弛变量或剩余变量Sk。显然在计算机输出中没有专门松弛变量与剩余变量栏，但是我们仍然从输出中找到它们的信息。首先由于是非基变量，可知在最优解中其值都为零，也就是在计算机输出的约束条件栏里，某一个约束条件的松弛或剩余变量的值为零，又因为这个非基变量的检验数为零，所以这个约束条件的对偶价格为零。反过来说，如果在计算机输出的约束条件栏里有一个约束条件的松弛或剩余变量为零，且其对偶价格也为零，那么我们就可知道有一个非基变量的松弛变量或剩余变量的检验数为零，这个线性规划有无穷多组解。,2如果在最终单纯形表上，检验数为零的非基变量是一般决策变量XK。在对非基变量XK的目标系数CK的灵敏度分析中知道CKK，对任何非基变量Xi 在计算机输出的相差值一栏中就记录了i 的值，它表示只有目标函数系数Ci 的增量改进了i 的值，Xi 才有可能成为基变量而取正值。因为K=0，所以很容易从计算机输出中识别出Xk ，也就是说只要在计算机输出中存在一个取值为零的决策变量并且其相差值也为零，我们就可以确认这个变量就是最终表上检验数为零的非基变量，可知此线性规划有无穷多组解。如果在计算机输出解的信息中不存在上述这两种情况，我们可以断定此线性规划只有惟一最优解。,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，称其中的任一个为原问题，另一个为对偶问题。在这一节中将揭示原问题与对偶问题的关系，如何将原问题转化为其对偶问题，如何从原问题的求解的结果中去找到其对偶问题的答案，并介绍对偶问题的经济解释以及对偶单纯形法。先来看一个例题。 例4 某工厂在计划期内安排、两种产品，已知生产单位产品所需设备A、B、C台时如表所示：,该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少产品和产品，才能使工厂获利最多?,6.2 线性规划的对偶问题,此例题与第二章例1有相同之处，只是不过把原料A、B改成了设备B、设备C，做这些改动是为了使读者更容易理解。 这个问题的数学模型与第二章的例1是一样的，求解的结果也是一样的。 设X1为产品的计划产量，X2为产品的计划产量，则有：目标函数：max Z =50X1+100X2 约束条件：X1+X2300, 2X1+X2400, X2250, X1, X20.,现在从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢?,设y1，y2，y3分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润，也就是由于出租可以获得的利润。建立模型要从两方面来考虑：,思路：把生产单位产品所需各设备的台时总租金不应当低于原利润50元，即y1+2y250，否则就不出租还是用于生产产品以获利50元；同样把生产一单位产品所需各设备的台时的总租金也不应当低于原利润100元，即y1+y2+y3100，否则这些设备台时就不出租，还是用于生产产品以获利100元。,怎么做？,一、作为出租者来说:,Min f =300y1+400y2+250y3 s.t. Y1+2y250 y1+y2+y3100 y1, y2, y30,这样从两个不同的角度来考虑同一个工厂的最大利润(最小租金)的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题。下面来研究这两个问题在数学模型上的关系。,他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好， 即min 300y1+400y2+250y3， 这样得到了该问题的数学模型：,二、对于租用者来说:,一样的吗？,1求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。,Max z =50 x1+100 x2 min f = 300y1+400y2+250y3 x1+x2300 y1+2y250 2x1+x2400 y1+y2+y3100 x2250 y1,y2,y30 x1,x20,3原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i 个约束条件的右边常数项就等于对偶问题的目标函数中的第 i个变量的系数。 4对偶问题的约束条件的系数矩阵A是原问题约束条件的系数矩阵的转置AT,在例4中，对于原问题其约束条件为： X1+X2300 2X1+X2400 X2250,对应的对偶问题的约束条件为： Y1+2Y250 Y1+Y2+Y3100,则其对偶问题： 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)。,以上问题的原问题已在第五章里用单纯形求出，现在我们用单纯形法求出其对偶问题的解。,加上剩余变量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 把上述数据填人单纯形表计算。,结果如下：,得到最优解y1=50，y2=0，y3=50，S1=0，S2=0，a1=0， - f 的最大值为 -27500，即目标函数f 的最小值为f =27500元。 从上面可知每台时的租金如下：A设备为50元，B设备为0元，C设备为50元。这样把工厂的所有设备出租可共得租金27500元。这对出租者来说这钱不比自己生产所得的利润少，对租用者来说这租金是出租者愿意出租设备的最小费用，因为这是目标函数的最小值。,通过与原问题的最优解比较，发现对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格，这在道理上也能讲得通，各种设备的出租的租金应该等于该种设备每台时给工厂所带来的利润，对偶问题的最优值即所有设备总台时数的总租金的最低价正好等于原问题工厂自己最优安排生产所获得的总利润。 以后不必解此对偶问题，就可以从原问题的最终单纯形表上得到其对偶问题的最优解。,原问题：最优值：27500 对偶问题：最优值：27500 变量 最优解 相差值 变量 最优解 相差值 x1 50 0 y1 50 0 x2 250 0 y2 0 50 y3 50 0 约束 松弛剩余变量 对偶价格 约束 松弛剩余变量 对偶价格 1 0 50 1 0 -50 2 50 0 2 0 -250 3 0 50,对偶问题的解为: 目标函数最优值为：27500 变量 最优解 相差值 Y1 50 0 Y2 0 50 Y3 50 0 约束 松弛剩余变量 对偶价格 1 0 -50 2 0 -250,在对偶问题的解中，如上表可找到产品I的对偶价格为 -50元，即当 每件产品的利润（租金）增加1元，则求最大值的总租金应减少50元（即求最小值的总租金增加50元），也就是原问题的总利润将要提高50元，也就是说工厂最优生产计划为生产50件I产品。同样从对偶问题的解中可找到产品的对偶价格为 -250元，也就是说当每件 产品的利润增加1元，则最低总租金即原问题的总利润将要提高250元，这条信息也就是告诉我们工厂最优生产计划为生产250件产品。,另外，从对偶问题的最低总租金27500元可得到原问题工厂的最大利润为27500元。,对于两个有对偶关系的线性规划的问题只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道了其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。 故在求解一个线性规划问题时，可以把其对偶问题一起来加以考虑，找一个比较容易求解的来求解，求出了一个最优解同时也就求出了另一个问题的最优解。 上述的例题要求租金的合理定价不如求解工厂的最大利润，因为求最大利润比较容易，不需要加上人工变量，而求出了最大利润的问题。 下面来看看如何从原问题结果中写出对偶规划问题的最优解：,原问题：最优值：27500 对偶问题：最优值：27500 变量 最优解 相差值 变量 最优解 相差值 x1 50 0 y1 50 0 x2 250 0 y2 0 50 y3 50 0 约束 松弛剩余变量 对偶价格 约束 松弛剩余变量 对偶价格 1 0 50 1 0 -50 2 50 0 2 0 -250 3 0 50,对偶问题: Min f =300Y1+400Y2+250Y3 s.t. Y1+2Y250， Y1+Y2+Y3100， Y1, Y2, Y30 如果两个问题都有最优解则有如下结果： 1、对偶规划问题的最优解为原问题的对偶价格的绝对值。对偶规划问题的约束条件的对偶价格的绝对值即为原问题的最优解。 2、目标函数值是相同的。如在上例中都为27500。,Max z =50 x1+100 x2 min f = 300y1+400y2+250y3 x1+x2300 y1+2y250 2x1+x2400 y1+y2+y3100 x2250 y1,y2,y30 x1,x20,至于其它情况： 原问题的目标系数的变动范围与对偶规划的约束条件的右边常数项的变动范围的关系。 原问题的约束条件的右边常数项的变动范围与对偶规划问题的目标系数的变动范围的关系。 这几种情况较为复杂，在这里不作进一步讨论。,一、两个问题都有可行解，从而都有最优解。二、一个问题为无界解，另一个问题必有无可行解。三、两个问题都无可行解。 有关证明看相关的书。,想想相互对偶的两个线性规划问题解的关系是怎样的？,有三种情形啊！,前面讲了如何写出求最大值(最小值)的线性规划问题的对偶问题， 但要求该最大值(最小值)线性规划问题的约束条件都取小于等于号(大于等 于号)。下面来阐述如何写出任一个线性规划的问题的对偶问题。,将下面的线性规划化为对偶问题： 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。 对于第三个约束条件，可以用小于等于和大于等于两个约束条件来替代它。 即有 5X1-3X2+X3200 和 5X1-3X2+X3200 再把第一个两边乘以 -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.,这个求最大值的线性规划问题的约束条件都取小于等于号， 其对偶问题为：,书上有错啊！,因为在该对偶问题中y3和y3的系数只相差一个符号，可以把上面的对偶问题化为:,改正过来！,下面我们用一个例子来说明如何写出一个任意线性规划问题的对偶问题。,化为对偶问题的重要做法！对照原线性规划问题，可以知道当原线性规划问题的第i个约束条件取等号时，则其对偶问题的i个决策变量没有非负限制。反过来如果当原线性规划问题中的第i个决策变量Xi没有非负限制时，用类似的方法知道其对偶问题中第i个约束条件取等号。,作业,如果为5x1+3x20,？,3对偶单纯形法,对偶单纯形法和单纯形法一样都是求解原线性规划问题的一种方法。单纯形法是在保持原问题的所有约束条件的常数大于等于零的情况下，通过迭代，使得所有的检验数都小于等于零，最后求得最优解；而对偶单纯形法则是在保持原问题的所有检验数都小于等于零的情况下，通过迭代，使得所有约束条件的常数都大于等于零，最后求得最优解。 使用对偶单纯形法时初始解可以是非可行解，对于些大于等于号的约束不等式不需要添加人工变量，只要把该不等式两边乘以-1，化成小于等于不等式的约束，就可用对偶单纯形法来求解，简化计算，这是对偶单纯形的优点，但是对偶单纯形法在使用上有很大的局限性，这主要是对大多数线性规划问题，很难找到一个初始解使得其所有检验数都小于等于零，因而这种方法在求解线性规划问题时很少单独应用。但在灵敏度分析中，有时需要用对偶单纯形法这样可使问题处理简化。 下面就第二章例1为例说明在灵敏度分析时如何使用对偶单纯形法以及对偶单纯形法的求解过程。,在上节对b的灵敏度分析中已知当250b1325时第一个约束条件的对偶价格不变，现在如果b1=300变成b1=350了，请问这时第一个约束方程的对偶价格应为多少呢?对这个问题用对偶单纯形法进行求解。 先求出在第2次迭代表上的常数列:,从上面单纯形表可知b2=-50。如果要按单纯形法解此题，则第一是把此约束方程乘以-1，把b2化成50，第二再加上人工变量a1，第三在目标函数上加上罚因子-M a1，然后再用单纯形法计算，这是很麻烦的。现在由于在此单纯形表上检验数都小于等于零，所以我们可以用对偶单纯形表来做。,1确定出基变量，在常数列中找一个最小的负常量，则这个负常量所在行的基变量为出基变量，在此例中b1=-50是最小的负常数，所以S2 定为出基变量。 2确定入基变量，在单纯形中检查出基变量xk 所在行的各函数ak j ( j=1，2，n)，如果所有的ak j 都大于等于零，则无可行解，停止计算，若存在a k j 为负数，则计算所有为负数的ak j 与其对应的j 的比值j /ak j ，求出其中的最小值， 即 min j/akj akj o。 即确定具有最小比值j /akj 为入基变量，在本例题中第二行系数里只有a23=-20。故取S1为入基变量，这样做可保证所有j仍有j0。 3以ak j 为主元，按原单纯形法在表中进行迭代运算，得到新的单纯形表，对本例题以a23 为主元，得新的单纯形表如下：,上面的单纯形表是先把第2行除以-2使得a23 变成1，同时也使得b2大于等于零为25，再进行行的初等变换使a13 和a23 变成零，求得上表。 4检查常数列的值，若已经都非负了，则此解就是最优解了。如果还存在负的常数，重复1至4的步骤。在此例中常数列的值已经都非负了，此时的解X1 =75，X2=250，S1=25，S2=0，S3=0为最优解，此时第一约束条件即设备台时的对偶价格为零，起变化。,本章结束 作业： P125, 8,