第二章-对偶问题.ppt

某工厂用三台设备生产两种产品，已知的条某工厂用三台设备生产两种产品，已知的条件如表所示，试制订总利润最大的生产计划件如表所示，试制订总利润最大的生产计划设备设备I产品产品II产品产品总有效台时总有效台时A2212B128C039单位产品的利单位产品的利润（千元）润（千元）23求求max引例引例1 1 生产计划问题生产计划问题换一角度：将设备卖出，售价定为多少适宜？换一角度：将设备卖出，售价定为多少适宜？原问题原问题对偶问题对偶问题两个互为对偶规划问题之间的关系两个互为对偶规划问题之间的关系（对称形对称形式）式）1）目标函数的目标互为相反。）目标函数的目标互为相反。(max,min)2）目目标标函函数数的的系系数数是是另另一一个个约约束束条条件件右右端端的向量的向量 3）约约束束系系数数矩矩阵阵是是另另一一个个的的约约束束系系数数矩矩阵阵的转置的转置 4）约约束束方方程程的的个个数数与与另另一一个个的的变变量量的的个个数数相等相等max限定向量限定向量b价值向量价值向量Cm个约束，个约束，n个变量个变量约束条件约束条件“”变量变量“”原问题原问题对偶问题对偶问题min价值向量价值向量限定向量限定向量n个约束，个约束，m个变量个变量变量变量“”约束条件约束条件“”对称式对偶max限定向量限定向量b价值向量价值向量Cm个约束，个约束，n个变量个变量约束条件约束条件“=”原问题原问题对偶问题对偶问题min价值向量价值向量限定向量限定向量n个约束，个约束，m个变量个变量变量自由变量变量自由变量非对称式对偶目标函数目标函数max原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数min目标函数中变量的系数目标函数中变量的系数约束条件右端项约束条件右端项约束条件右端项约束条件右端项目标函数中变量的系数目标函数中变量的系数例例2：给出下列线性规划的对偶问题：给出下列线性规划的对偶问题：minZ=2X1+8X2-4X3X1+3X23X3=30-X1+5X2+4X3=80st.4X1+2X2-4X3=50X1=0,X3无约束无约束其对偶问题为：其对偶问题为：MAXw=30y1+80y2+50y3y1-y2+4y3=2st.3y1+5y2+2y3=0,y2无约束，无约束，y30,Y20和松弛互补定理知和松弛互补定理知:X5,X6,=0从而从而,原问题的约束变为原问题的约束变为:2X3+3X4=203X3+2X4=20解此方程得解此方程得:X3=X4=4于是原问题的最优解为于是原问题的最优解为:(0,0,4,4)七、单纯形表的双重含义七、单纯形表的双重含义例例6：用单纯形法，解线性规划，：用单纯形法，解线性规划，（LP1）maxZ=2X1+X25X2=156X1+2X2=24st.X1+X2=0,X2=0对偶问题对偶问题为:（LP2）minW=15Y1+24Y2+5Y36Y2+Y3=2ST.5Y1+2Y2+Y3=1Y1=0,Y2=0基变量基变量X1X2X3X4X5解解X30015/4-15/2 15/2X11001/4-1/27/2X2010-1/4 3/23/2-Z(目标目标)000-1/4-1/2-17/2检验数全部检验数全部0,于是得到最优解为于是得到最优解为X=(7/2,3/2,15/2,0,0),最优值为最优值为:Z=17/2,把松弛变量的检验数的相反数把松弛变量的检验数的相反数(0,1/4,1/2)带带入对偶问题中入对偶问题中,看有什么规律看有什么规律?1、松松弛弛变变量量与与对对偶偶变变量量的的乘乘积积有有什什么么关关系系？松弛变量与对偶变量的乘积松弛变量与对偶变量的乘积=0=02 2、对偶问题的最优解与什么对偶问题的最优解与什么对应对应？对对偶偶问问题题的的最最优优解解是是原原问问题题松松弛弛变变量量检检验数的相反数验数的相反数.结结论论：将将原原始始单单纯纯形形表表中中松松弛弛变变量量的的检检验数反号恰好得对应对偶问题的一个解。验数反号恰好得对应对偶问题的一个解。事实上，我们把原始问题写成事实上，我们把原始问题写成 （1）其对偶问题写成其对偶问题写成 （2）其中其中其中其中决策变量决策变量 和松弛变量和松弛变量 ，所对应的检验数分别为：所对应的检验数分别为：和和（不一定满足（不一定满足“0”条件）。条件）。设设 为原始问题（为原始问题（1）的一个基本可行解）的一个基本可行解（不一定为最优解），它所对应的基矩阵为（不一定为最优解），它所对应的基矩阵为,令令这时两组检验数分别为：这时两组检验数分别为：和和再根据问题（再根据问题（2），这两组检验数可分别记为），这两组检验数可分别记为 上述对应关系如表上述对应关系如表2.在获得最优解之前，在获得最优解之前，及，及 的各分的各分量中至少有一大于零，即量中至少有一大于零，即 中至少有一个小于零。中至少有一个小于零。这时对应的对偶问题的解为非可行解。这时对应的对偶问题的解为非可行解。和和 即即 ,重要结论：重要结论：1.原始问题的单纯形表中，原始问题的松弛变量原始问题的单纯形表中，原始问题的松弛变量的检验数对应于对偶问题的决策变量，而原始问题的检验数对应于对偶问题的决策变量，而原始问题的决策变量的检验数对应于对偶问题的松弛变量，的决策变量的检验数对应于对偶问题的松弛变量，只是符号相反；只是符号相反；此时对偶问题也同时获得最优解。此时对偶问题也同时获得最优解。和和 当原始问题获得最优解时，表明当原始问题获得最优解时，表明2.4 影子价格一、影子价格的含义一、影子价格的含义根据资源在生产中作出的贡献而作的估根据资源在生产中作出的贡献而作的估价。价。是对第是对第i 种资源实现最大利润的一种估计，种资源实现最大利润的一种估计，是对偶问题的最优解。是对偶问题的最优解。二、影子价格的特点二、影子价格的特点 1.区别于市场价格，市场价格相对稳定；区别于市场价格，市场价格相对稳定；而影子价格不稳定，依赖于资源的利用。而影子价格不稳定，依赖于资源的利用。2.影子价格是一种边际价格。影子价格是一种边际价格。3.影子价格是一种机会成本。影子价格是一种机会成本。4.互补松弛定理指出：互补松弛定理指出：当某种资源未被充分利用，则该种资当某种资源未被充分利用，则该种资源的影子价格为源的影子价格为0；而当资源的影子价格不；而当资源的影子价格不为为0时，表明该种资源已耗尽。时，表明该种资源已耗尽。5.检验数的经济学含义。检验数的经济学含义。第第j种产品的种产品的单位产值单位产值是生产该产品所是生产该产品所耗用的各种资源耗用的各种资源的影子价格，即的影子价格，即隐含成本。隐含成本。2.5 对偶单纯形法对偶单纯形法小结：在单纯形表格中小结：在单纯形表格中1.得到原问题的基本可得到原问题的基本可行解的同时，其检验行解的同时，其检验数的相反数就构成了数的相反数就构成了对偶问题的一个基本对偶问题的一个基本解。解。2.原原对对松弛变量松弛变量决策变量决策变量决策变量决策变量剩余变量剩余变量基变量基变量非基变量非基变量非基变量非基变量基变量基变量化标准型化标准型求一个对偶可求一个对偶可行基本解行基本解 检验最检验最优性优性是是结束结束否否换基换基 再确定入基变量：再确定入基变量：先确定出基变量：先确定出基变量：bl=minbibi0，则对应，则对应xl出基；出基；则对应则对应xk入基。入基。对偶单纯形法步骤：对偶单纯形法步骤：00-15 -24 -5 0 0基基-15 -24 -5 0 00-5-6-2-1-11001 -2 -1-24 0-15 0 -1 -4 00-5101/6-2/3-1/6-1/3011/3-1/3-24-5-15/2 0 0 -7/2 -3/2-5/415/21001-1/4 1/21/4-3/21/41/2Min问题问题基基2 1 0 0 0061521100010 0 0 1 15 24 50002 1 0 0 00010101005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2 51/32/301010001/6-1/6001 15 4 10200 1/3 0 -1/3 0Max问题问题单纯形法单纯形法（1）保持原问题的）保持原问题的可行性，即可行性，即（2）最优性：）最优性：即使对偶问题达到可即使对偶问题达到可行；行；（3）同时得到原问）同时得到原问题与对偶问题最优解题与对偶问题最优解对偶单纯形法对偶单纯形法（1）保持对偶问题）保持对偶问题的可行性，即的可行性，即（2）最优性：）最优性：即使原问题达到可行；即使原问题达到可行；（3）同时得到原问）同时得到原问题与对偶问题最优解题与对偶问题最优解从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。引例：某厂生产引例：某厂生产A、B两种产品，其所需劳动力、材两种产品，其所需劳动力、材料、设备等有关数据见表。要求确定获利最大的生产料、设备等有关数据见表。要求确定获利最大的生产计划？计划？建立数学模型：设建立数学模型：设x1,x2为为A,B产品的产品的产量，则产量，则1）A,B两种产品利润改变；两种产品利润改变；2）增加了材料；）增加了材料；3）开发新项目，增加一新产品）开发新项目，增加一新产品C;4）技术革新，改变）技术革新，改变B产品的工艺；产品的工艺；5）对两种产品增加一道新工序）对两种产品增加一道新工序；是否影响原最是否影响原最优解呢？优解呢？如发生变化：如发生变化：AB可用量可用量设备设备0515材料材料6224劳动力劳动力115单位利润单位利润212.6灵敏度分析灵敏度分析灵敏度分析：灵敏度分析：指对系统或事物因周围条件变化显示指对系统或事物因周围条件变化显示出来的敏感程度分析。出来的敏感程度分析。所研究的问题：所研究的问题：参数参数A、b、C一个或几个一个或几个发生变化，最优解如何？发生变化，最优解如何？以及在多大范围内变化，以及在多大范围内变化，最优解不变？最优解不变？基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最最终终表表1.目标函数系数变为目标函数系数变为2.第二个约束条件右端项变为第二个约束条件右端项变为32；3.增加一个新的变量增加一个新的变量4.5.增加一个约束条件增加一个约束条件作如下灵敏度分析：作如下灵敏度分析：基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最终表最终表1.5 21.5 2 0 0 0 1/8 -9/40010104/5-1/51/5100-6 1 0 6 2 301.5 20 0 -1/10 0 -3/2方法：方法：1.将将Cj的变化体现在最终表上；的变化体现在最终表上；2.用变化后的数据重新计算检验数；用变化后的数据重新计算检验数；3.若所有检验数若所有检验数0，原最优解不变，否则用单纯形，原最优解不变，否则用单纯形法继续迭代。法继续迭代。基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最终表最终表35/211/2-1/251-4010100001 0 1 -615 5 20200 -1 0 0 -2方法：方法：1.找出原问题的最优基的逆找出原问题的最优基的逆B-1；2.求出求出X/B=B-1b/;3.若若X/B 0，原最优基不变，最优解变为，原最优基不变，最优解变为X/B；否则否则将变化后的将变化后的X/B反映在最终表的反映在最终表的b列，用对偶单纯形法列，用对偶单纯形法继续迭代。继续迭代。基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最终表最终表0230 -1/2 0 -1/8 -5/4 03-70217/201/2010100 3/8 1/4-1/8-9/4-1/2 3/45/4 7/23/4001 方法：方法：1.找出原问题的最优基的逆找出原问题的最优基的逆B-1；2.求出求出,计算检验数计算检验数3.若若，原最优解不变，原最优解不变；否则将用单纯形法继续否则将用单纯形法继续迭代。迭代。基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最终表最终表11/21/21/2001010100 41/2-1/2-24 -2 3-9 2 30230 0 0 1/2 -533出现原问题和对偶问题均非可行解出现原问题和对偶问题均非可行解100 9 0 0 -1 -4 240 0 -M -4M+1/2 24M-5 0 基基2 1 0 0 00100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/20210 0 0 -1/4 -1/2最终表最终表0 x6 12 3 2 0 0 0 0 x6000100 0 0 -1/4 -1/2 00 x6 -3/2 0 0 0 -1/4 -3/2 1 0100011005/41/4-1/4-15/2-1/2 3/215/2 7/2 3/2021000灵敏度分析的步骤灵敏度分析的步骤1.将参数的改变计算反映到最终单纯形表中；将参数的改变计算反映到最终单纯形表中；2.检查原问题是否可行，即检查原问题是否可行，即bi0;3.检查对偶问题是否可行，即检查对偶问题是否可行，即j0;4.按表所列决定继续迭代的步骤：按表所列决定继续迭代的步骤：原问题原问题对偶问题对偶问题步骤步骤可行解可行解可行解可行解仍为问题最优解仍为问题最优解可行解可行解非可行解非可行解用单纯形法迭代用单纯形法迭代非可行解非可行解可行解可行解用对偶单纯形法迭代用对偶单纯形法迭代非可行解非可行解非可行解非可行解引入人工变量构造可行基引入人工变量构造可行基1.目标函数系数变为目标函数系数变为2.第一个约束条件右端项变为第一个约束条件右端项变为3；3.增加一个约束条件增加一个约束条件引例：某厂生产引例：某厂生产A、B、C三种产品，其所需劳动力、三种产品，其所需劳动力、材料等有关数据见表。要求：材料等有关数据见表。要求：1）确定获利最大的生产计划；）确定获利最大的生产计划；2）产品）产品A的利润在什的利润在什么范围内变动时，上述最优计划不变；么范围内变动时，上述最优计划不变；3）如果设计）如果设计一种新产品一种新产品D,单位产品的劳动力消耗为单位产品的劳动力消耗为8单位，材料单位，材料消耗为消耗为2单位，每件可获利单位，每件可获利3元，问该种产品是否值得元，问该种产品是否值得生产？生产？4）如果劳动力数量不增，材料不足时可从市）如果劳动力数量不增，材料不足时可从市场购买，每单位场购买，每单位0.4元。问该厂要不要购进原材料扩元。问该厂要不要购进原材料扩大生产，以购多少为宜？大生产，以购多少为宜？ABC可用量可用量劳动力劳动力63545材料材料34530单位利润单位利润314基基3 1 4 0 0 10-1/3 1011/3-1/5-1/3 2/5 5 3340 -2 0 -1/5 -3/5最终表最终表5-/33+2/5 13/5-36/501-11/5 1 0-15+904-9/5 -7/5 0 -4/5 0