运筹学对偶问题

运筹学对偶问题演示文稿目前一页\总数六十一页\编于五点运筹学对偶问题目前二页\总数六十一页\编于五点一、对偶问题的一般形式若设一线性规划问题如下：（A）目前三页\总数六十一页\编于五点则以下线性规划问题：（B）

称为原问题（A）的对偶线性规划问题，或称A、B互为对偶问题。目前四页\总数六十一页\编于五点如果采用向量、矩阵来表示（A）（B）其中：目前五页\总数六十一页\编于五点可以将以上关系列成以下对偶表：maxminx1x2…xnby1a11a12…a1n≤b1y2a21a22…≤b2…………………ymam1am2…amn≤bm≥≥…≥cc1c2…cn目前六页\总数六十一页\编于五点例写出下列线性规划问题的对偶问题目前七页\总数六十一页\编于五点解：可以将原问题的有关参数列成下表maxminx1x2x3by1142≤48y2124≤60≥≥≥c61413目前八页\总数六十一页\编于五点∴对偶规划问题为目前九页\总数六十一页\编于五点比较以上我们介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题。它满足两个条件：目前十页\总数六十一页\编于五点两个条件：1、所有变量非负：即X>0，Y>02、约束条件均为同向不等式。若原问题约束条件均为“≤”，则它的对偶问题的约束条件都是“≥”。当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。目前十一页\总数六十一页\编于五点例分析：为求对偶问题，可先做过渡，将问题对称化：目前十二页\总数六十一页\编于五点对称化目前十三页\总数六十一页\编于五点

则，原问题变为（A）（A‘）目前十四页\总数六十一页\编于五点则（A’）的对偶问题如下：（B‘）（A‘）目前十五页\总数六十一页\编于五点对比结果以上对偶问题（B‘）并非原问题（A）的对偶问题，它是线性规划问题（A’）的对偶问题。（A）（B‘）目前十六页\总数六十一页\编于五点调整对照问题B‘目标函数系数的符号与原问题A中约束条件右端常数项的符号，可做以下调整：令y1=y1’，y2=-y2’，y3=y4’-y3’目前十七页\总数六十一页\编于五点令y1=y1’，y2=-y2’，y3=y4’-y3’

则得到以下对偶问题（B‘）（B）目前十八页\总数六十一页\编于五点合并（B）目前十九页\总数六十一页\编于五点比较对于任何一个线性规划问题，我们都可以求出它的对偶问题。（A）（B）目前二十页\总数六十一页\编于五点原问题与对偶问题的相应关系原问题A（对偶问题B）对偶问题B（原问题A）最大化max最小化minA系数矩阵ATB右端常数（列向量）目标函数系数(行向量)C目标函数系数右端常数（列向量）第i个约束条件为等式“=”yi为自由变量第i个约束条件为不等式“≤”yi≥0第i个约束条件为不等式“≥”yi≤0xj为自由变量第j个约束条件为等式“=”xj≥0第j个约束条件为不等式“≥”xj≤0第j个约束条件为不等式“≤”目前二十一页\总数六十一页\编于五点例：写出下列问题的对偶形式：目前二十二页\总数六十一页\编于五点解：目前二十三页\总数六十一页\编于五点例：写出下列问题的对偶问题目前二十四页\总数六十一页\编于五点解：目前二十五页\总数六十一页\编于五点二、对偶问题的经济意义：若原规划问题是“在一定条件下，使工作或成果（产品产量、利润等）尽可能的大”，那么它的对偶问题就是“在另外一些条件下，使工作的消耗（浪费、成本等）尽可能的小”。实际上是一个问题的两个方面。目前二十六页\总数六十一页\编于五点例：某产品计划问题的

线性规划数学模型为假设生产部门根据市场变化，决定停止生产甲、乙产品，而将原有的原料、设备专用于接受外来订货以生产市场急需的紧俏商品，则需要考虑决策的问题就是“在什么样的价格条件下，才能接受外来订货？”。问题的实质就是如何确定原料、设备的收费标准？目前二十七页\总数六十一页\编于五点分析若设y1为单位原材料的价格，y2为设备单位台时价格，由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位，现在不生产甲产品，转而接受外来订货加工，则收取的费用不能低于2个单位，否则自己生产甲产品更有利。因此，可以得到下面的条件：目前二十八页\总数六十一页\编于五点分析同理，将生产乙产品的原料和设备工时用于接受外来加工订货，收取的费用不能低于乙产品的单位利润1个单位：目前二十九页\总数六十一页\编于五点分析另外，为了争取外来加工订货，在满足上述要求的基础上，收费标准应尽可能低从而具有竞争力，因此总的收费w=15y1+10y2应极小化。这样，就得到一个目标函数：目前三十页\总数六十一页\编于五点这样，就得到另一个线性规划模型：目前三十一页\总数六十一页\编于五点比较生产问题（要利用资源）资源利用问题（会影响生产）目前三十二页\总数六十一页\编于五点第二节对偶理论目前三十三页\总数六十一页\编于五点定理1（对称性定理）对偶问题（B）的对偶规划为线性规划（A）对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。目前三十四页\总数六十一页\编于五点定理2（弱对偶定理）当原问题A是求最大值max，而对偶问题是求最小值时，如果X0是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成立：

目前三十五页\总数六十一页\编于五点定理3（最优性定理）设和分别是问题A和B的可行解，若相应于和，A和B的目标函数值相等，即，则和分别是A和B的最优解。

目前三十六页\总数六十一页\编于五点定理4（无界性定理）如果原问题A的目标函数值无界，则对偶问题B无可行解；如果对偶问题B的目标函数值无界，则原问题A无可行解。目前三十七页\总数六十一页\编于五点以上三个定理可以这样记忆原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反之同理可说明。对偶问题(B)minW原问题(A)maxZy0bcx0目前三十八页\总数六十一页\编于五点定理5（强对偶定理）若线性规划A存在最优解，则对偶规划B也存在最优解，并且它们的最优值相等；相反地，若规划B存在最优解，则规划A也存在最优解，并且它们的最优值相等。目前三十九页\总数六十一页\编于五点定理6（存在性定理）若线性规划A和B都存在可行解，则A和B都存在最优解。目前四十页\总数六十一页\编于五点第三节对偶单纯形法条件：①b列中至少有一个bi<0；②原问题A的检验数满足符号条件。目前四十一页\总数六十一页\编于五点例目前四十二页\总数六十一页\编于五点解：minmax解：引入松弛变量，化为标准形式：目前四十三页\总数六十一页\编于五点观察A矩阵目前四十四页\总数六十一页\编于五点解以上标准形式中没有完全单位向量组，我们将约束条件进行变换，两边同乘（-1）。A矩阵中存在完全单位向量组，但bi<0，考虑求解。用单纯形法求解。目前四十五页\总数六十一页\编于五点步骤1判断对偶单纯形法的条件是否满足。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→目前四十六页\总数六十一页\编于五点步骤2在对偶单纯形表中，检验数是b列。当b>0时，得到最优解。否则，进行换基迭代段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→目前四十七页\总数六十一页\编于五点步骤3：换基迭代（1）找主元行：找到b列中绝对值最大者所在行为主元行，记为Pi*，主元行对应的变量Xi*为调出变量。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→目前四十八页\总数六十一页\编于五点（2）计算θj：找出主元行Pj*中所有负分量，计算注：若主元行中没有负分量，则问题无解。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--目前四十九页\总数六十一页\编于五点（3）找主元列θj中绝对值最小者所在的列为主元列，记为Pj*，主元列所对应的变量xj*为调入变量。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3-1-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--目前五十页\总数六十一页\编于五点（4）找主元素主元行与主元列相交处的元素即主元素，记为Pi*j*。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-1100x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--目前五十一页\总数六十一页\编于五点（5）迭代用高斯消去法，使原主元列中除了原主元素为1外，其余元素均为0。段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x110x60Cj-Zj→θj→目前五十二页\总数六十一页\编于五点计算结果段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→θj→目前五十三页\总数六十一页\编于五点找主元行、确定调出变量、

计算zj-cj段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→-140300θj→--1-2--3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→---2-1-2--θj→目前五十四页\总数六十一页\编于五点计算θj、确定调入变量段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3-2-321Cj-Zj→-0-2-1-210θj→-2/31/22/3--目前五十五页\总数六十一页\编于五点继续换基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj→-12-3--2-1x1312-11-100x6-80-3(-2)-321→Cj-Zj→-0-2-1-2-10θj

→--2/31/22/3--3-1x100x31Cj-Zj→θj

→目前五十六页\总数六十一页\编于五点继续换基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj

→-12-3--2-1x1312-11-100x6-80-3(-2)-321→Cj-Zj→-0-2-1-2-10θj

→--2/31/22/3--3-1x1717/205/2-2-1/20x3403/213/2-1-1/2Cj-Zj→θj

→目前五十七页\总数六十一页\编于五点继续换基迭代：段Cj↓→基0b-1P1-4P20P3-3P40P50P6注10x5-3(-1)-21-110→0x6-221-4-101Cj-Zj→--1-40-300θj

→-12-3--2-1x1312-11-100x6-80-3(-2)