运筹学--对偶理论课件

《运筹学--对偶理论课件》由会员分享，可在线阅读，更多相关《运筹学--对偶理论课件（80页珍藏版）》请在金锄头文库上搜索。

1、1,第二章 LP的对偶理论(dual theory),1 对偶问题的提出 2 原问题与对偶问题 3 对偶问题的基本性质 4 对偶问题的经济意义影子价格 5 对偶单纯形法 6 灵敏度分析 7 参数线性规划,2,1 对偶问题的提出 一、对偶问题的提出在理论上和实践上，对偶理论都是LP中一个十分重要和有趣的概念。支持对偶理论的基本思想是，每一个LP问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的LP问题。在求出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意义。,【例1】：美佳公司计划制造甲乙两种产品。

2、已知各制造一件产品时分别占用设备A,B的台时，每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？,4,MAX Z= 2X1+X2 满足条件： X1+5X2 17 6X1+2X2 24 X10, X20,列出线性规划模型为：,现从另一个角度提出问题：假定东方公司想把美佳公司 （的资源)收买过来，它至少应付出多大代价（底线）， 才能使美佳公司愿意放弃生产活动，出让自己的资源？显然，该企业愿意出让的条件是，出让的价格不应低 于同等数量资源由自己组织生产活动时获取的利润。分析：设y1 , y2 分别表示单位时间（h）设备A 、设备B 的出让代价，

3、则从东方公司来看，希望用最小的代价把全 部资源收买过来， 故有： min w=17 y1 +24 y2 因生产一件甲产品需两种设备分别为1、6小时，盈利2 元，生产一件乙产品需两种设备分别为5、2小时，盈利1 元。从美佳公司来看，出让资源获得的利润应不少于自己 组织生产获得的利润。因此有：y1 + 6y2 25 y1 +2 y2 1,要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线性规划数学模型： min w=17 y1 +24 y2 y1 + 6y2 2 5 y1 +2 y2 1 y1 0, y2 0,于是，我们得到两个线性规划：,原问题： LP1:maxZ=2X1+X2 X1

4、+5X2 17 6X1+2X2 24 X1 0, X2 0,对偶问题： LP2： min w=17 y1 +24 y2 y1 + 6y2 25 y1 + 2y2 1y1 0, y2 0,我们把LP2称为LP1的对偶问题；若把LP2看成原问题，则LP1就是LP2的对偶问题。 比较两者，看有什么规律？,1）目标函数的目标互为相反(max,min)； 2）目标函数的系数是另一个约束条件右端的向量； 3）约束系数矩阵是另一个的约束系数矩 阵的转置； 4）约束方程的个数与另一个的变量的个数相等； 5）约束条件在一个问题中为“ ”，在另一个问题中为 “”。,9,二、对偶问题的一般提法（对称形式下对偶问题的

5、一般提法） 看书P41 原问题：m种资源bi(i=1m)生产n种产品xj(j=1n)，获利分别为cj (j=1n)元，aij为工艺系数，则原问题为 Maxz=cjxj aijxjbi(i=1m) xj0 (j=1n) 对偶问题：设将上述资源出售定价为yi（i=1m），使获得收益不低于原企业生产产品出售获得的收益，则应满足 Minw=biyiaijyi cj (j=1n)yi0 (i=1m),10,三、LP的对偶问题也可以从数学的角度引出来 （了解） 检验数为B=CB-CBB-1B (1)N=CN-CBB-1N (2)-Y= -CBB-1 (1) (2)合到一起，检验数一般形式为 ：=C-CBB

6、-1A 令Y= CBB-1 ，称为单纯形乘子 当所有j 0时， YA C Y 0 又Z=CX=CBb = CBB-1b=Yb= W,所以：min w=Ybst. YA C Y 0,11,从例子看到，原问题为求max ，对偶问题为求min ，因为： （1）对偶问题的可行解（Y= CBB-1 ）满足原问题的最优化条件（ 0）； （2）因此对原问题来说，只有最优解（X=B-1b）才是其对偶问题的可行解。 （3）也即原问题的最优解目标函数值是它的对偶问题可行解目标函数值最小的一个。(注意对偶问题求min)( Z=CX=CBb= CBB-1b=Yb= W) （4）由此可知，原问题目标函数的最大值对应于对

7、偶问题的目标函数的最小值。 （具体见第三节基本性质）,12,一、对偶关系（对称形式）,2 原问题与对偶问题,原问题 对偶问题 max z=CX min w=Yb st. AX b st. YA CX 0 Y 0 1、看书上表2.1，验证对应关系 2、看教材例1。写出最大化问题的对偶问题 3、对称性：LP的原问题与对偶问题之间存在对称关系， 即LP对偶问题的对偶是原问题。 看例2，通过例子得出结论 第一步，化为对称形式下的原问题形式；第二步，根据对 应关系写出其对偶问题；第三步，做一变换，得到原问题 结论：LP对偶问题与原问题互为对偶。,二、非对称形式原问题与对偶问题之间的关系 看例3，是一个最

8、小化问题 第一步，化为对称形式下的对偶问题形式（min， ，变量非负）； 第二步，引入对偶变量（根据原问题约束条件符号来 设），根据对应关系写出其对偶问题； 第三步，变换为一般形式。设原问题的三个约束条件的对偶变量分别为y1、y2、 y3(每一个约束条件对应一个对偶变量)由此，对于非对称形式原问题与对偶问题之间的关 系可用下表反映：,14,15,【例2】：给出下列线性规划的对偶问题：MAX Z=X1+ 2 X2 + X3 X1+ X2 X3 2 y1X1 X2 + X3 =1 y2 st. 2X1+ X2 + X3 2 y3X1 0, X2 0, X3 无约束,16,【例2】：给出下列线性规划

9、的对偶问题：MAX Z=X1+ 2 X2 + X3 X1+ X2 X3 2 y1X1 X2 + X3 =1 y2 st. 2X1+X2 + X3 2 y3X1 0, X2 0, X3 无约束 其对偶问题为： min w=2 y1 + y2 +2 y3 y1 + y2 +2y3 1 X1st. y1 - y2 + y3 2 X2-y1 +y2 + y3 =1 X3y1 0, y2 无约束，y3 0,17,【例3】：给出下列线性规划的对偶问题：min Z=2X1+ 8 X2 -4X3 X1+3X2 3X3 30 y1 -X1 +5X2 + 4X3 =80 y2 st. 4X1+ 2X2 - 4X3

10、 50 y3X1 0, X2 0, X3 无约束,18,【例3】 ：给出下列线性规划的对偶问题：min Z=2X1+ 8 X2 -4X3 X1+3X2 3X3 30 y1 -X1 +5X2 + 4X3 =80 y2 st. 4X1+ 2X2 - 4X3 50 y3X1 0, X2 0, X3 无约束 其对偶问题为： MAX w=30 y1 +80 y2 +50y3 y1 - y2 + 4y3 2 x1st. 3 y1 +5y2 +2y3 8 x2-3y1 +4y2 - 4y3 =-4 x3y1 0, y2 无约束，y3 0,19,先相同，后相反；先相反，后相同 最大化问题找其对偶问题，约束条件

11、与其对偶变量的符号相同，而其变量的符号与其对应约束条件的符号相反； 最小化问题找其对偶问题，约束条件与其对偶变量的符号相反，而其变量的符号与其对应约束条件的符号相同。,20,3 对偶问题的基本性质,原问题 对偶问题 max z=CX min w=Yb st. AX b st. YA CX 0 Y 0 可行解 X Y本节讨论先假定原LP与对偶问题为对称形式的LP问 题，然后说明对偶问题的基本性质在非对称形式（一般形 式）时也适用。 性质是就对称形式提出的，可行平行的推广到一般 形式的问题中去，只不过叙述上也要有相应的变动。,21,1、弱对偶性：CXYb X，Y是可行解 （证明用到了上面两个约束条

12、件） 性质含义：极大化问题的任一可行解的目标函数值，不大于对偶问题的任一可行解的目标函数值。 也即：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 【例4】已知线性规划问题: maxZ=4 x1 + 7x2+2x3s.t. 应用对偶理论证明该问题最优解的目标函数值不大于25.,22,2、最优性：当原问题与对偶问题均有可行解X、Y，且当 CX=Yb时， 则X、Y分别是原问题与对偶问题的最优解。（由性质1证明） （隐含：两者都存在可行解，则均存在最优解）【例5】已知线性规划问题：MAX Z = 3x1 + 2x2 -x1

13、+2x2 43x1 +2x2 14x1 x2 3x1，x2 0 （1）写出对偶问题；（2）利用对偶问题性质证明原问 题和对偶问题都存在最优解。,23,3、无界性：如果原问题（对偶问题）有无界解，则对偶问题（原问题）无可行解。即原问题有可行解且目标函数值无界（可达正无穷），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界（可达负无穷），则其原问题无可行解。（性质1，CXYb，YbCX） 因此，如果原问题无可行解时，对偶问题无可行解或具有无界解 对偶问题无可行解时，原问题无可行解或具有无界解 （原问题有可行解，对偶问题无可行解，则原问题有无界解）,24,【例6】已知线性规划问题 max

14、Z = x1 - x2 +x3 x1 - x3 4x1 x2 +2x3 3x1 x2 x3 0 试应用对偶理论证明上述线性规划问题无最优解.（无界解属于无最优解）,25,4、强对偶性（对偶定理）：若原问题有最优解，则对偶问题也一定有最优解，且目标函数值相等。 证明： Z=CX=CBb= CBB-1b=Yb= W根据性质2，Y是对偶问题最优解,26,小结： 1、原问题有可行解，则对偶问题： 有可行解，则两者均具有最优解； 无可行解，则原问题具有无界解。 2、原问题无可行解，则对偶问题可以无可行解或者无界解。 3、原问题无界解，对偶问题无可行解。（无界性） 4、原问题有最优解，对偶问题有最优解，且CX=Yb。（对偶定理）,