《运筹学第3章线性规划的对偶理论与灵敏度分析》由会员分享，可在线阅读，更多相关《运筹学第3章线性规划的对偶理论与灵敏度分析（43页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 线性规划的对偶理论与灵敏度分析,1 线性规划的对偶问题 2 对偶规划的基本性质 3 对偶单纯形法 4 线性规划的灵敏度分析,2,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。 例题1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？ 解：设 为产品 的计划产量， 为产品的计划产量，则有 目标函数： Max z=50 +100 约束条件：，,1 线性规划的对偶问题,3,现在我们从另一个
2、角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？设 分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润50元，即 ，否则就不出租还是用于生产 产品以获利50元；同样把 生产一单位 产品所需各设备的台时的总租金也不应当低于原利润100元， 即 ，否则这些设备台时就不出租，还是用于生产 产品以获利100元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即min ，这
3、样我们得到了该问题的数学模型：目标函数：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。,4,如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边
4、常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。设A=则,5,如果我们用矩阵形式来表示，则有原问题：其中A是 矩阵m*n，该问题有m个约束条件n个变量，x= ,b= , c= 对偶问题：其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。,6,加上剩余变量 和人工变量 ，把此问题化成标准型如下：把上述数据
5、填入单纯形表计算。,7,8,由上表，最优解： =50， -f 的最大值为-27500，即目标函数f的最大值为f=27500元。从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工 厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出 租设备的最小费用，因为这是目 标函数的最小值。通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种 设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划 的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而 求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最 优值，因为
6、这两个最优值相等。,9,下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。S.T.,10,这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（-1），得,11,通过上面的一些变换，我们得到了一个
7、和原线性规划等价的线性规划问题：s.t.,12,这个求最大值的线性规划问题的约束条件都取小于等于号，我们马 上可以写出其对偶问题：s.t.,13,这里 和 一样都是不同的决策变量，为了表示这两个 决策变量都来源于原问题的第三个约束条件，记为 。因为在该对偶问题中 和 的系数只相差一个符号，我们可以把 上面的对偶问题化为：s.t.,14,进一步，我们可以令 ，这时当 时， ，当 时， 。这也就是说，尽管 但 的取值可以为正，可以为0， 可以为负，即 没有非负限制。这样我们把原规划的对偶问题化为 s.t. 没有限制。对照原线性规划问题，我们可以知道：当原线性规划问题的第i个约束条件取等号时，则其对
8、偶问题的 i个决策变量没有非 负限制。如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里 ， ，用类似的方法知道其对偶问题中第 i个 约束条件取等号。,15,另外，用大于等于0的两个决策变量之差来代替无非负限制的决策变 量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。原线性规划问题为：s.t.无非负限制。,16,2 对偶规划的基本性质,对偶规划的基本性质 1对称性。即对偶问题的对偶是原问题。 2弱对偶性。即对于原问题（）和对偶问题（）的可行解 都有C bT 。由弱对偶性，可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的
9、下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,17,3最优性。如果 是原问题()的可行解， 是对偶问题()的可行解，并且 C = bT ，则 和 分别为原问题()和对偶问题()的最优解。 4强对偶性。即若原问
10、题()及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。 5互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即若yi*0,则有若 ，则有yi*=0,18,3 对偶单纯形法,对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原 有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于0， 最后求得最优解。简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是 大多数线性规划问题很难找到初始解使得其所有检验数都小于0。但
11、是在灵敏度 分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在 b1=300变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？解：求出在第二次迭代表上的常数列,19,1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量,20,4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。,21,4 线性规划的灵敏度分析,一、目标函数中变量Ck系数灵敏度分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与
12、Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变 成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解 仍为最优解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 2.在最终的单纯形表中， X k是基变量 当Ck变成Ck+ Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目 标函数的系数CB变了，则ZJ(J=1,2,N)一般也变了，不妨设CB=(CB1, CB2。, Ck, ， CBm),当CB变
13、成=(CB1, CB2。,Ck+ Ck,CBm),则：ZJ=(CB1, CB2。, Ck,，CBm)(a1j , a2j , aKj , amj)ZJ=(CB1, CB2。, Ck+ Ck,，CBm)(a1j , a2j , aKj , amj) = ZJ + Ck aKj,22,根据上式可知检验数 J (J=1,2,M)变成了 J,有 J=CJ-ZJ= J+ CK aKj 。要使最优解不变，只要当J K时， J =0,23,例：目标函数：Max z=50X1+100X2约束条件：X1+X23002X1+X2400X2250X1，X20 最优单纯形表如下,24,我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里3=-50，所以当c3的增量c350，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11,a12,a13,a14,a15中，除了知道a11和 a13大于0， a15小于0，可知 ，有 。同样有。这样可以知道当-50c150时，也就是x1的 目标函数c1在0c1100时最优解不变。在最终的单纯形表中，用C1代替原来的C1=50,计算得表,
