1、本讲内容 什么是对偶问题 单纯形法的矩阵描述 对偶问题的性质 线性规划的灵敏度分析什么是对偶问题？例1（生产计划问题）：某工厂在计划期内要安排A、B两种产品的生产，已知生产单位产品的利润与所需的劳力、设备台时及原材料消耗，如下：产品A产品B资源限额劳动力设备原材料9434510360工时200台时300公斤单位产品利润70120问：如何安排生产使该厂获利最大？max z=70 x1+120 x2 s.t.9x14x2360 4x1+5x2200 3x1+10 x2300 x1,x20对偶问题的提出考虑上一讲的生产计划问题，若设备和原料都用于对外加工，工厂收取加工费。试问：该厂设备工时、劳动力和
2、原料该如何定价？P需求供给Q均衡点供给-需求函数显然，工厂给这些生产要素定价，既要保证自己的利益，又要使自己的价格具有竞争力价格越高越好价格越低越好一个合理的定价是：收取的加工费不能低于自己生产所得收益，在此前提下使总加工费尽量小。即：Min w=360y1+200y2+300y3s.t.9y1+4y2+3y370 4y1+5y2+10y3120 y1,y20该线性规划问题与原问题互为对偶问题max z=70 x1+120 x2s.t.9x14x23604x1+5x22003x1+10 x2300 x1,x20对偶的定义 (LP)Max z=CX (DP)Min w=Yb s.t.AX b s
3、.t.YA C X 0 Y 0 若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之，若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000=无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项建立对偶问题的规则约束条件变量右端项价值系数对于上表，特别
4、把握以下要点：maxmin求max的对偶问题时，变量反号求min的对偶问题时，约束反号无限制例1：写出下列规划问题的对偶问题Max z=2x1+2x2-4x3 s.t.X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30解：min w=30y1+80y2 s.t.y1+4y22 3y1+2y22 3y1+4y2-4 y1,y20 例2：写出下列规划问题的对偶问题min z=2x1+8x2-4x3 s.t.X1+3x2-3x330 -x1+5x2+4x3=80 4x1+2x2-4x350 X10,x20,x3无限制解：max w=30y1+80y250y3 s.t.y1-y2
5、+4y32 3y1+5y2+2y38 3y1+4y24y3-4 y10,y2无限制,y30 单纯形法的矩阵描述单纯形法的矩阵描述设有线性规划问题Max z=CX AXb X0加上松弛变量XS=(xn+1,xn+2,xn+m),化为标准型Max z=CX0Xs AX+IXS=b X0,XS0单纯形法的矩阵描述设A中存在一可行基B，相应的变量可分为基变量XB和非基变量XN，价值系数也分为CB,CN，即A=(B,N)X=(XB,XN)TC=(CB,CN)SNBSNBSIXNXBXXXXINBXXIA),(),(Max z=CX0Xs AX+IXS=b X0,XS0bIXNXBXSNB因而SNBXBN
6、XBbBX111于是Max z=CX0Xs AX+IXS=b X0,XS0SNNBBSNBNBXXCXCXXXCC00),(代入XB,目标值SBNBNBXBCXNBCCbBCz111)(检验数),(),0(1111BCABCCBCNBCCBBBBN)0,0,(),(1bBXXXXSNB令XN=0,XS=0,得基可行解目标值bBCzB10zIb0CBCBXBCBXNCNXSXBCBXbB1bBCB1NB1NBCCBN11BCB1B矩阵形式描述的单纯形表关于对偶问题的基本定理定理1（弱对偶定理）若 X(0),Y(0)分别为（LP）和（DP）的可行解，那么 CX(0)Y(0)b。(证明)该定理说明：
7、如果原问题是最大化问题，则它的任意可行解对应的目标函数值都会小于等于其对偶问题(极小化)的任一可行解对应的目标函数值证明：由X(0),Y(0)分别为原问题和对偶问题的可行解则,AX(0)b,X(0)0 Y(0)AC,Y(0)0因此，Y(0)AX(0)Y(0)b于是，CX(0)Y(0)bMax z=2x1+2x2-4x3 s.t.X1+3x2+3x330 4x1+2x2+4x380 X1,x2,x30min w=30y1+80y2 s.t.y1+4y22 3y1+2y22 3y1+4y2-4 y1,y20 例如任意取一些可行解试试看？定理2（无界性）若一个问题无界，则另一个问题不可行max z=
8、x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0可行域Min w=40y1+20y2s.t.-2y1+y2 1 y1-y2 1 y1,y2 0对偶问题显然无可行解！例如定理3（最优性定理）若 X(0),Y(0)分别为（LP）和（DP）的可行解，且 CX(0)=Y(0)b，那么 X(0),Y(0)分别为（LP）和（DP）的最优解证明设X*是LP问题的任一可行解，由弱对偶性CX*Y(0)b=CX(0)从而X(0)是最优解同理Y(0)是最优解定理4（对偶定理）若其中一个问题有最优解，则另一个问题也有最优解，且两者最优值相等证明证明：设X*是LP问题的最优解，相应的最优基为B
9、，则检验数必定满足0,011BCABCCBB令1*BCYB则有0,*YCAY因而Y*是对偶问题的可行解又*1*CXzbBCbYB因而Y*是对偶问题的最优解0zIb0CBCBXBCBXNCNXSXBCBXbB1bBCB1NB1NBCCBN11BCB1B定理5（互补松弛定理）原问题及其对偶问题的可行解X(0)和Y(0)是最优解的充要条件是：Y(0)XS=0，YSX(0)=0XS,YS分别为原问题松弛向量和对偶问题剩余向量该定理说明：一对对偶问题达到最优，当且仅当松约束对应的对偶变量必定是紧的利用互补松驰定理，可以在知道一个问题的最优解时，求解其对偶问题的最优解例：Min z=2x1+3x2+5x3
10、+2x4+3x5s.t.X1+x2+2x3+x4+3x54 2x1-2x2+3x3+x4+x53 xj 0,j=1,5Max w=4y1+3y2s.t.y1+2y22 y1-2y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0对偶问题y1*=4/5,y2*=3/5对偶问题的最优解4/5-2*3/5=-2/50,由互补松弛定理知X(0)ys=0所以x2=0同理，x3=0,x4=0又y1*0,而Y(0)xs=0,知xs0，即原问题第一个约束取等式同理，第2个约束也取等式定理6若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量的检验数和剩余变量的检验数的相反数
11、即为对偶问题最优解对偶最优解的经济含义影子价格由对偶定理miiinjjjybxcZ1*1*求z*对bi的偏导数*iiybz所以对偶最优解为原问题各资源的影子价格影子价格非资源的市场价格，而是指系统达到最优状态时，资源的单位变化引起目标最优值的变化 对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。什么是对偶单纯形法？也就是说，求解原问题（LP）时，可以从（LP）的一个基本解（并不一定是基可行解）开始，逐步迭
12、代，使目标函数值（Z=Y b=CB B-1b=CX）减少，当迭代到XB=B-1b0时，即找到了（LP）的最优解，这就是对偶单纯形法。同原始单纯形求法一样，求解对偶问题（DP），也可以从（DP）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。例一、用对偶单纯形法求解：)3.2.1(01451232102215129min321321321321jxxxxxxxxxxxxxZj 解：将模型转化为 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxZ cj-9-12-15000cBxBbx1x2x3x4x5x
13、60 x4-10-2-2-11000 x5-12-2-3-10100 x6-14-1-1-5001(-9/-1.-12/-1.-15/-5)-Z 0-9-12-15000icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-36/5-9/5-9/5010-1/50 x5-46/5-9/5-14/5001-1/5-15x314/51/51/5100-1/5(-30/-9.-45/-14 .-15/-1)-Z 42-6-9000-3icj-9-12-15000cBxBbx1x2x3x4x5x60 x4-9/7-9/14001-9/14-1/14-12x223/79/14100-5
14、/141/14(-3/-9.-45/-9.-33/-1)-15x315/71/140101/14-3/14-Z 501/7-3/14000-45/14-33/14cj-9-12-15000cBxBbx1x2x3x4x5x6-9x12100-14/911/9-12x220101-10-15x320011/90-2/9-Z 72000-1/3-3-7/3ii 所以，X*=（2.2.2.0.0.0），Z*=72，原问题 Z*=72 其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72 0,43232432min321321321321xxxxxxxxxxxxZ练习：)5.4.3.2.1(0
15、4 323 2432max5153214321321jxxxxxxxxxxxxZcj-2-3-400cBxBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301-Z-2-3-400icj-2-3-400cBxBbx1x2x3x4x50 x4-10-5/21/21-1/2-2x121-1/23/20-1/2-Z 0-4-10-1icj-2-3-400cBxBbx1x2x3x4x5-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5-Z 28/500-3/5-8/5-1/5iY=（8/5.1/5）X=（2/5.11/5.0）Z=28/5 为什么
16、要进行灵敏度分析？前面对线性规划的讨论，价值系数c，资源系数b和技术系数矩阵A都是已知常数。但现实中，这些系数可能只是估计量，存在误差或随着时间的推移可能有些许变化糟糕！这个月产品市场价格与原计划时发生变化了。年初安排的生产计划还是最优的么？价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)max z=70 x1+120 x2s.t.9x14x2360 4x1+5x2200 3x1+10 x2300 x1,x20模型价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解
17、不变呢？例(生产计划问题)最优单纯形表cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5 070120X3X1X28420240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 -0.12 0.1642800 0 0 -13.6 -5.2考虑C2发生变化价值系数变化的灵敏度分析设只有一个价值系数cj发生变化，其它系数不变，那么cj在什么范围内变化而最优解不变呢？例(生产计划问题)最优单纯形表cj70 c2 0 0 0CBXBbX1 X2 X3 X4 X5 070c2X3X1X28420240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0
18、 -0.12 0.1642800 0 0 -28+0.12c2 14-0.16c2 显然只要-28+0.12c2 014-0.16c2 0 成立，则最优解不变！即 87.5 c2233.33右端项变化的灵敏度分析考察单纯形表0zIb0CBCBXBCBXNCNXSXBCBXbB1bBCB1NB1NBCCBN11BCB1Bb变化只影响因此，只要B-1b0,则最优基不变从而对偶最优解不变，也即影子价格不变例如生产计划问题,考虑b3变化的灵敏度分析max z=70 x1+120 x2s.t.9x14x2x3=3604x1+5x2+x42003x1+10 x2x5 300 x1,x500 0 0 -13
19、.6 -5.242800 0 1-3.121.161 0 0 0.4-0.20 1 0 -0.120.16842024X3X1X2070120X1 X2 X3 X4 X5bXBCB70120 0 0 0cj0 0 0 -13.6 -5.242800 0 1-3.121.161 0 0 0.4-0.20 1 0 -0.120.16842024X3X1X2070120X1 X2 X3 X4 X5bXBCB70120 0 0 0cj最优单纯形表由此可见，(p3,p1,p2)是最优基，即1030540491B16.012.002.04.0016.112.311BB-1b0020036016.012.0
20、02.04.0016.112.313b解得 227.586b3400计算机灵敏度分析的例子生产计划问题Excel生产计划问题DM多个参数变化的灵敏度分析百分之百法则：(1)对于所有变化的目标函数系数，当其所有允许增加百分比和允许减少百分比之和不超过100时，则最优解不变(2)对于所有变化的右端项系数，当其所有允许增加百分比和允许减少百分比之和不超过100时，则对偶最优解不变例 上述生产计划问题，若市场条件变化，产品A的单位利润下降为53元，产品B单位利润上升至160元，最优生产计划是否会发生变化？若A产品利润升为95元，而B产品降到90元呢？(1)解：产品A利润降为53元，则C1=-17 产品
21、b利润升为160元，则C2=40。根据前面的计算结果，计算变化率：因此，最优生产计划不会改变！V1=(-17)/(36-70)=0.5=50%V2=40/(233.333-120)=0.353=35.3%V=v1+v2=83.5%(2)解：产品A利润升为95元，则C1=25 产品B利润降为90元，则C2=30。根据前面的计算结果，计算变化率：因此，最优生产计划会改变！V1=25/(96-70)=0.9615=96.15%V2=(-30)/(87.5-120)=0.9231=92.31%V=v1+v2=188.46%100%作业产品消耗定额 原料甲乙丙原料拥有量AB6334554530单件利润415 某厂生产甲、乙、丙三种产品，已知有关数据如表所示，试分别回答下列问题：（a）建立线性规划模型，求使该厂获利最大的生产计划；（b）若产品乙、丙的单件利润不变，则产品甲的利润在什么范围内变化时，上述最优解不变。（c）若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B如数量不足可去市场购买，单价为0.5，问该厂应否购买，以购进多少为宜；
