运筹学对偶问题.pptx

《运筹学对偶问题.pptx》由会员分享，可在线阅读，更多相关《运筹学对偶问题.pptx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、对偶问题的一般形式 若设一线性规划问题如下：（A）第1页/共62页则以下线性规划问题：（B）称为原问题（A）的对偶线性规划问题，或称A、B互为对偶问题。第2页/共62页如果采用向量、矩阵来表示（A）（B）其中：第3页/共62页可以将以上关系列成以下对偶表：maxminx1x2xnby1a11a12a1nb1y2a21a22b2ymam1am2amnbmcc1c2cn第4页/共62页例写出下列线性规划问题的对偶问题第5页/共62页解：可以将原问题的有关参数列成下表 maxminx1x2x3by114248y212460c61413第6页/共62页 对偶规划问题为 第7页/共62页比较以上我们

2、介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题。它满足两个条件：第8页/共62页两个条件：1、所有变量非负：即X0，Y02、约束条件均为同向不等式。若原问题约束条件均为“”，则它的对偶问题的约束条件都是“”。当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。第9页/共62页例分析：为求对偶问题，可先做过渡，将问题对称化：第10页/共62页对称化第11页/共62页 则，原问题变为（A）（A）第12页/共62页则（A）的对偶问题如下：（B）（A）第13页/共62页对比结果以上对偶问题（B）并非原问题（A）的对偶问题，它是线性规划问题（A）的对偶问题。（A

3、）（B）第14页/共62页调整对照问题B目标函数系数的符号与原问题A中约束条件右端常数项的符号，可做以下调整：令y1=y1，y2=-y2，y3=y4-y3第15页/共62页令y1=y1，y2=-y2，y3=y4-y3则得到以下对偶问题（B）（B）第16页/共62页合并（B）第17页/共62页比较对于任何一个线性规划问题，我们都可以求出它的对偶问题。（A）（B）第18页/共62页原问题与对偶问题的相应关系 原问题原问题A A（对偶问题（对偶问题B B）对偶问题对偶问题B B（原问题（原问题A A）最大化 max最小化 minA系数矩阵ATB右端常数（列向量）目标函数系数(行向量)C目标函数系数右

4、端常数（列向量）第i个约束条件为等式“=”yi为自由变量第i个约束条件为不等式“”yi0第i个约束条件为不等式“”yi0 xj为自由变量第j个约束条件为等式“=”xj0第j个约束条件为不等式“”xj0第j个约束条件为不等式“”第19页/共62页例：写出下列问题的对偶形式：第20页/共62页解：第21页/共62页例：写出下列问题的对偶问题 第22页/共62页解：第23页/共62页二、对偶问题的经济意义：若原规划问题是“在一定条件下，使工作或成果（产品产量、利润等）尽可能的大”，那么它的对偶问题就是“在另外一些条件下，使工作的消耗（浪费、成本等）尽可能的小”。实际上是一个问题的两个方面。第24页/

5、共62页例：某产品计划问题的线性规划数学模型为 假设生产部门根据市场变化，决定停止生产甲、乙产品，而将原有的原料、设备专用于接受外来订货以生产市场急需的紧俏商品，则需要考虑决策的问题就是“在什么样的价格条件下，才能接受外来订货？”。问题的实质就是如何确定原料、设备的收费标准？第25页/共62页分析若设y1为单位原材料的价格，y2为设备单位台时价格，由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位，现在不生产甲产品，转而接受外来订货加工，则收取的费用不能低于2个单位，否则自己生产甲产品更有利。因此，可以得到下面的条件：第26页/共62页分析同理，将生产乙产品的原料和设

6、备工时用于接受外来加工订货，收取的费用不能低于乙产品的单位利润1个单位：第27页/共62页分析另外，为了争取外来加工订货，在满足上述要求的基础上，收费标准应尽可能低从而具有竞争力，因此总的收费 w=15y1+10y2 应极小化。这样，就得到一个目标函数：第28页/共62页这样，就得到另一个线性规划模型：第29页/共62页比较生产问题（要利用资源）资源利用问题（会影响生产）第30页/共62页第二节 对偶理论第31页/共62页定理1（对称性定理）对偶问题（B）的对偶规划为线性规划（A）对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，

7、那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。第32页/共62页定理2（弱对偶定理）当原问题A是求最大值max，而对偶问题是求最小值时，如果X0是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成立：第33页/共62页定理3（最优性定理）设 和 分别是问题A和B的可行解，若相应于 和 ，A和B的目标函数值相等，即 ，则 和 分别是A和B的最优解。第34页/共62页定理4（无界性定理）如果原问题A的目标函数值无界，则对偶问题B无可行解；如果对偶问题B的

8、目标函数值无界，则原问题A无可行解。第35页/共62页以上三个定理可以这样记忆原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反之同理可说明。对偶问题(B)minW原问题(A)maxZy0bcx0第36页/共62页定理5（强对偶定理）若线性规划A存在最优解，则对偶规划B也存在最优解，并且它们的最优值相等；相反地，若规划B存在最优解，则规划A也存在最优解，并且它们的最优值相等。第37页/共62页定理6（存在性定理）若线性规划A

9、和B都存在可行解，则A和B都存在最优解。第38页/共62页第三节 对偶单纯形法条件：b列中至少有一个bi0；原问题A的检验数满足符号条件。第39页/共62页例第40页/共62页解：min max解：引入松弛变量，化为标准形式：第41页/共62页观察A矩阵第42页/共62页解以上标准形式中没有完全单位向量组，我们将约束条件进行变换，两边同乘（-1）。A矩阵中存在完全单位向量组，但bi0时，得到最优解。否则，进行换基迭代 段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-

10、3-1-1-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j第45页/共62页步骤3：换基迭代（1）找主元行找主元行：找到b列中绝对值最大者所在行为主元行，记为Pi*，主元行对应的变量Xi*为调出变量。段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3-1-1-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-1

11、0 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j第46页/共62页（2）计算计算 j j：找出主元行Pj*中所有负分量，计算注：若主元行中没有负分量，则问题无解。段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3-1-1-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j-1 12 2-3 3-第47页/共62页（3）

12、找主元列找主元列j中绝对值最小者所在的列为主元列，记为Pj*，主元列所对应的变量xj*为调入变量。段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3-1-1-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j-1 12 2-3 3-第48页/共62页（4）找主元素找主元素主元行与主元列相交处的元素即主元素，记为Pi*j*。段段CjCj基基0 0b b

13、-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j-1 12 2-3 3-第49页/共62页（5）迭代用高斯消去法，使原主元列中除了原主元素为1外，其余元素均为0。段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1

14、 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j-1 12 2-3 3-2 2-1-1x x1 11 10 0 x x6 60Cj-ZjCj-Zjj j第50页/共62页计算结果段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-

15、2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j-1 12 2-3 3-2 2-1-1x x1 131 12-11-100 0 x x6 6-80 0-3-2-321Cj-ZjCj-Zjj j第51页/共62页找主元行、确定调出变量、计算zj-cj段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-1

16、0 01 1Cj-ZjCj-Zj-1 14 40 03 30 00 0j j-1-1-2-2-3-3-2 2-1-1x x1 131 12-11-100 0 x x6 6-80 0-3-2-321Cj-ZjCj-Zj-2-1-2-j j第52页/共62页计算j j、确定调入变量段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1

17、-1-4-40 0-3-30 00 0j j-1 12 2-3 3-2 2-1-1x x1 131 12-11-100 0 x x6 6-80 0-3-2-321Cj-ZjCj-Zj-0-2-1-210j j-2/31/22/3-第53页/共62页继续换基迭代：段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40

18、0-3-30 00 0j j-1 12 2-3 3-2 2-1-1x x1 13 31 12 2-1-11 1-1-10 00 0 x x6 6-8-80 0-3-3(-2)(-2)-3-32 21 1Cj-ZjCj-Zj-0 0-2-2-1-1-2-2-1-10 0j j -2/32/31/21/22/32/3-3 3-1-1x x1 10 00 0 x x3 31 1Cj-ZjCj-Zjj j 第54页/共62页继续换基迭代：段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x

19、5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j -1 12 2-3 3-2 2-1-1x x1 13 31 12 2-1-11 1-1-10 00 0 x x6 6-8-80 0-3-3(-2)(-2)-3-32 21 1Cj-ZjCj-Zj-0 0-2-2-1-1-2-2-1-10 0j j -2/32/31/21/22/32/3-3 3-1-1x x1 17 71 17/27/20 05/25/2-2-2-1/2-1/20 0 x x3

20、34 40 03/23/21 13/23/2-1-1-1/2-1/2Cj-ZjCj-Zjj j 第55页/共62页继续换基迭代：段段CjCj基基0 0b b-1-1P P1 1-4-4P P2 20 0P P3 3-3-3P P4 40 0P P5 50 0P P6 6注注1 10 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 00 0 x x6 6-2-22 21 1-4-4-1-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j -1 12 2-3 3-2 2-1-1x x1 13 31 12 2-1-11 1-1-10 00 0

21、x x6 6-8-80 0-3-3(-2)(-2)-3-32 21 1Cj-ZjCj-Zj-0 0-2-2-1-1-2-21 10 0j j -2/32/31/21/22/32/3-3 3-1-1x x1 17 71 17/27/20 05/25/2-2-2-1/2-1/20 0 x x3 34 40 03/23/21 13/23/2-1-1-1/2-1/2Cj-ZjCj-Zj70 0-1/2-1/20 0-1/2-1/2-2-2-1/2-1/2j j 第56页/共62页得到最优解：计算到第三段时，b0且Cj-Zj0，得到原问题的最优解：第57页/共62页五、对偶单纯形法的求解思路：一般单纯形

22、法的思路：在使用表格单纯形法求解线性规划标准型的最优解时，是从一个初始基本可行解（可行域的一个顶点）开始，按照一定的规则进行迭代，求出第二个基本可行解（另一个可行域的顶点），同时，逐步使检验数都变成正值，目标函数的当前值则逐步变优，直至所有检验数全部变成非负值，对应的基本可行解就成为最优解。由于迭代过程中出现的基本可行解既是满足约束条件的基本解，又是保持取非负值的可行解，即使解答列中基变量的取值（b列）始终保持非负，通过迭代逐步消除检验数行中的不满足符号条件的检验数。第58页/共62页检验数 也可以用向量形式写出：（这里只写出非基变量的检验数向量）从 可以很容易得推出 ，这说明原问题的最优基正

23、是对偶问题的可行基。换言之，当原问题的基B即是原问题的可行基又是对偶问题的可行基时，B就是最优基。因此，单纯性法求解过程正是在保持原始可行（解答列基变量取值均非负）的条件下，通过迭代逐步实现对偶可行性。第59页/共62页在对偶关系中，由于价值系数C和约束条件右端常数系数b互换位置，因此可以设想，能否在保持检验数Cj-Zj非正的条件下，逐步消除基本解中的负分量，使之成为可行解。这样，该基本解就是基本最优解。对偶单纯形法正是基于这种思想而产生的，其基本思想就是在保持对偶可行性的条件下，通过逐步迭代实现原始可行性。第60页/共62页所以，对偶单纯形法的使用条件是：b列中至少有一个bi0；原问题A的检验数Cj-Zj0；第61页/共62页感谢您的观看！第62页/共62页