运筹学对偶问题.pptx

第四章第四章 对偶问题对偶问题l对偶问题的一般形式l对偶问题的经济意义l对偶性质l对偶单纯形法l对偶单纯形法的解题原理一、对偶问题的一般形式一、对偶问题的一般形式 l若设一线性规划问题如下：（A）则以下线性规划问题则以下线性规划问题：（B）称为原问题（A）的对偶线性规划问题，或称A、B互为对偶问题。如果采用向量、矩阵来表示如果采用向量、矩阵来表示（A）（B）其中：可以将以上关系列成以下对偶表：可以将以上关系列成以下对偶表：maxminx1x2xnby1a11a12a1nb1y2a21a22b2ymam1am2amnbmcc1c2cn例例l写出下列线性规划问题的对偶问题解：解：l可以将原问题的有关参数列成下表 maxminx1x2x3by114248y212460c61413 对偶规划问题为对偶规划问题为 比较比较l以上我们介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题。l它满足两个条件：两个条件：两个条件：1、所有变量非负：即X0，Y02、约束条件均为同向不等式。若原问题约束条件均为“”，则它的对偶问题的约束条件都是“”。l当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。例例l分析：l为求对偶问题，可先做过渡，将问题对称化：对称化对称化 则，原问题变为则，原问题变为（A）（A）则（则（A）的对偶问题如下：）的对偶问题如下：（B）（A）对比结果对比结果l以上对偶问题（B）并非原问题（A）的对偶问题，它是线性规划问题（A）的对偶问题。（A）（B）调整调整l对照问题B目标函数系数的符号与原问题A中约束条件右端常数项的符号，可做以下调整：l令y1=y1，y2=-y2，y3=y4-y3令令y1=y1，y2=-y2，y3=y4-y3则得到以下对偶问题则得到以下对偶问题（B）（B）合并合并（B）比较比较l对于任何一个线性规划问题，我们都可以求出它的对偶问题。（A）（B）原问题与对偶问题的相应关系原问题与对偶问题的相应关系 原问题原问题A A（对偶问题（对偶问题B B）对偶问题对偶问题B B（原问题（原问题A A）最大化 max最小化 minA系数矩阵ATB右端常数（列向量）目标函数系数(行向量)C目标函数系数右端常数（列向量）第i个约束条件为等式“=”yi为自由变量第i个约束条件为不等式“”yi0第i个约束条件为不等式“”yi0 xj为自由变量第j个约束条件为等式“=”xj0第j个约束条件为不等式“”xj0第j个约束条件为不等式“”例：写出下列问题的对偶形式：例：写出下列问题的对偶形式：解：解：例：写出下列问题的对偶问题例：写出下列问题的对偶问题 解：解：二、对偶问题的经济意义：l若原规划问题是“在一定条件下，使工作或成果（产品产量、利润等）尽可能的大”，l那么它的对偶问题就是“在另外一些条件下，使工作的消耗（浪费、成本等）尽可能的小”。l实际上是一个问题的两个方面。例：某产品计划问题的例：某产品计划问题的线性规划数学模型为线性规划数学模型为 l假设生产部门根据市场变化，决定停止生产甲、乙产品，而将原有的原料、设备专用于接受外来订货以生产市场急需的紧俏商品，则需要考虑决策的问题就是“在什么样的价格条件下，才能接受外来订货？”。问题的实质就是如何确定原料、设备的收费标准？分析分析l若设y1为单位原材料的价格，y2为设备单位台时价格，由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位，现在不生产甲产品，转而接受外来订货加工，则收取的费用不能低于2个单位，否则自己生产甲产品更有利。因此，可以得到下面的条件：分析分析l同理，将生产乙产品的原料和设备工时用于接受外来加工订货，收取的费用不能低于乙产品的单位利润1个单位：分析分析l另外，为了争取外来加工订货，在满足上述要求的基础上，收费标准应尽可能低从而具有竞争力，因此总的收费 w=15y1+10y2 应极小化。这样，就得到一个目标函数：这样，就得到另一个线性规划模型：这样，就得到另一个线性规划模型：比较比较生产问题（要利用资源）资源利用问题（会影响生产）第二节 对偶理论定理1（对称性定理）l对偶问题（对偶问题（B）的对偶规划为线性规划（）的对偶规划为线性规划（A）l对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。定理2（弱对偶定理）l当原问题当原问题A是求最大值是求最大值max，而对偶问题是求，而对偶问题是求最小值时，如果最小值时，如果X0是原问题的任意可行解，是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成是对偶问题的任意可行解，则有以下关系式成立：立：定理3（最优性定理）l设设 和和 分别是问题分别是问题A和和B的可行解，的可行解，若相应于若相应于 和和 ，A和和B的目标函数值的目标函数值相等，即相等，即 ，则，则 和和 分别是分别是A和和B的最优解。的最优解。定理4（无界性定理）l如果原问题如果原问题A的目标函数值无界，则对偶问题的目标函数值无界，则对偶问题B无可行解；如果对偶问题无可行解；如果对偶问题B的目标函数值无的目标函数值无界，则原问题界，则原问题A无可行解。无可行解。以上三个定理可以这样记忆以上三个定理可以这样记忆l原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反之同理可说明。对偶问题(B)minW原问题(A)maxZy0bcx0定理5（强对偶定理）l若线性规划若线性规划A存在最优解，则对偶规划存在最优解，则对偶规划B也存也存在最优解，并且它们的最优值相等；相反地，在最优解，并且它们的最优值相等；相反地，若规划若规划B存在最优解，则规划存在最优解，则规划A也存在最优解，也存在最优解，并且它们的最优值相等。并且它们的最优值相等。定理6（存在性定理）l若线性规划若线性规划A和和B都存在可行解，则都存在可行解，则A和和B都存都存在最优解。在最优解。第三节第三节 对偶单纯形法对偶单纯形法l条件：lb列中至少有一个bi0；l原问题A的检验数满足符号条件。例例解：解：min maxl解：引入松弛变量，化为标准形式：观察观察A矩阵矩阵解解l以上标准形式中没有完全单位向量组，我们将约束条件进行变换，两边同乘（-1）。lA矩阵中存在完全单位向量组，但bi0时，得到最优解。l否则，进行换基迭代 段段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步骤步骤3：换基迭代：换基迭代l（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-10 01 1Cj-ZjCj-Zj-1-1-4-40 0-3-30 00 0j j（2）计算计算j：l找出主元行Pj*中所有负分量，计算l注：若主元行中没有负分量，则问题无解。段段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-（3）找主元列找主元列lj中绝对值最小者所在的列为主元列，记为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-（4）找主元素找主元素l主元行与主元列相交处的元素即主元素，记为Pi*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-1-4-40 0-3-30 00 0j j-1 12 2-3 3-（5）迭代）迭代l用高斯消去法，使原主元列中除了原主元素为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 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计算结果计算结果段段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 131 12-11-100 0 x x6 6-80 0-3-2-321Cj-ZjCj-Zjj j找主元行、确定调出变量、找主元行、确定调出变量、计算计算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-10 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计算计算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-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-继续换基迭代：继续换基迭代：段段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 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 继续换基迭代：继续换基迭代：段段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 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 34 40 03/23/21 13/23/2-1-1-1/2-1/2Cj-ZjCj-Zjj 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-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-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 得到最优解：得到最优解：l计算到第三段时，b0且Cj-Zj0，得到原问题的最优解：五、对偶单纯形法的求解思路：五、对偶单纯形法的求解思路：l一般单纯形法的思路：l在使用表格单纯形法求解线性规划标准型的最优解时，是从一个初始基本可行解（可行域的一个顶点）开始，按照一定的规则进行迭代，求出第二个基本可行解（另一个可行域的顶点），同时，逐步使检验数都变成正值，目标函数的当前值则逐步变优，直至所有检验数全部变成非负值，对应的基本可行解就成为最优解。l由于迭代过程中出现的基本可行解既是满足约束条件的基本解，又是保持取非负值的可行解，即使解答列中基变量的取值（b列）始终保持非负，通过迭代逐步消除检验数行中的不满足符号条件的检验数。l检验数 也可以用向量形式写出：（这里只写出非基变量的检验数向量）l从 可以很容易得推出 ，这说明原问题的最优基正是对偶问题的可行基。换言之，当原问题的基B即是原问题的可行基又是对偶问题的可行基时，B就是最优基。因此，单纯性法求解过程正是在保持原始可行（解答列基变量取值均非负）的条件下，通过迭代逐步实现对偶可行性。l在对偶关系中，由于价值系数C和约束条件右端常数系数b互换位置，因此可以设想，能否在保持检验数Cj-Zj非正的条件下，逐步消除基本解中的负分量，使之成为可行解。这样，该基本解就是基本最优解。l对偶单纯形法正是基于这种思想而产生的，其基本思想就是在保持对偶可行性的条件下，通过逐步迭代实现原始可行性。l所以，对偶单纯形法的使用条件是：lb列中至少有一个bi0；l原问题A的检验数Cj-Zj0；