《运筹学》胡运权第4版线性规划的对偶理论及灵敏度分析省公开课一等奖全国示范课微课金奖课件

第二章线性规划对偶理论及灵敏度分析OperationalResearch(OR)1/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划2/69对偶原理对偶问题概念：任何一个线性规划问题都有一个伴生线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行描述，其最优解与原问题最优解有着亲密联络，在求得一个线性规划最优解同时也就得到对偶线性规划最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题理论，是线性规划理论主要内容之一。3/69问题导出项目ⅠⅡ天天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21例2-1我们引用第一章中美佳企业例子，如表1其线性规划问题为：？假定有某个企业想把美佳企业资源收买过来，它最少应付出多大代价，才能使美佳企业愿意放弃生产活动，出让自己资源？（LP1）4/69问题导出例2-1条件：出让代价应不低于用同等数量资源由自己组织生产活动时获取赢利。y1,y2,y3分别代表单位时间（h）设备A、设备B和调试工序出让代价。y1,y2,y3取值应满足：美佳企业用6h设备B和1h调试可生产一件家电I,赢利2元用5h设备A,2h设备B及1h调试可生产一件家电Ⅱ，赢利1元该企业希望用最小代价把美佳企业全部资源收买过来，即：5/69问题导出例2-1总而言之，（LP2）LP1和LP2两个线性规划问题，通常称LP1为原问题，LP2为前者对偶问题。6/69对偶问题定义对称形式对偶问题7/69对偶问题定义对称形式对偶问题8/69对偶问题定义对偶问题特点若原问题目标是求极大化，则对偶问题目标是极小化，反之亦然原问题约束系数矩阵与对偶问题约束系数矩阵互为转置矩阵极大化问题每个约束对应于极小化问题一个变量，其每个变量对应于对偶问题一个约束。

9/69对偶问题定义普通线性规划问题对偶问题10/69对偶问题定义对偶问题对应表原问题（对偶问题）对偶问题（原问题）目标函数maxZ目标函数minZ约束条件：m个第i个约束类型为“≤”第i个约束类型为“≥”第i个约束类型为“＝”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量

约束条件：n个第j个约束类型为“≥”第j个约束类型为“≤”第j个约束类型为“＝”11/69对称形式下

对偶问题例2－2标准型对偶问题12/69对称形式下对偶问题例2－313/69非对偶形式原-对偶问题例2-4写出以下问题对偶问题（2.4a）（2.4b）（2.4c）（2.4d）对偶变量y1y2′y2″y3′先转换成对称形式，以下：14/69非对偶形式原-对偶问题例2-4令各约束对应对偶变量分别为y1、y2′、y2″、-y3′令y2=y2′-y2″，y3=-y3′，原问题对偶问题为15/69对应关系总结项目原问题（对偶问题）对偶问题（原问题）A约束系数矩阵其约束系数矩阵转置b约束条件右端项向量目标函数中价格系数向量C目标函数中价格系数向量约束条件右端项向量目标函数maxz=∑CjXjminw=∑

biyi16/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划17/69对偶问题基本性质单纯形法计算矩阵描述对称形式线性规划矩阵表示式加上松弛变量Xs后为：其中松弛变量Xs=（xn+1,xn+2,...,xn+m）,I为m×m单位矩阵项目基变量基变量XBXNXs0XsbBNIcj-zjCBCN0选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，XB在初始单纯形表中系数矩阵为B。A中去掉B若干列后剩下列组成矩阵N。18/69深入迭代,新单纯形表以下：对偶问题基本性质项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N–CBB-1对应初始单纯形表中单位矩阵I，迭代后单纯形表中为B-1初始单纯形表中基变量Xs=b，迭代后表中XB=B-1b初始单纯形表中约束系数矩阵为[A,I]=[B,N,I]，迭代后表中约束系数矩阵为[B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]若初始矩阵中变量xj系数向量为Pj，迭代后为Pj′，则有Pj′=B-1Pj当B为最优基时，表中应有CN-CBB-1N≤0,-CBB-1≤019/69对偶问题基本性质例2-5参看例2-1中原问题和对偶问题，并分别加上松弛变量和剩下变量，以下：对偶变量y1y2y3对偶变量x1x220/69对偶问题基本性质两个问题最终单纯形表以下：项目原问题变量原问题松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2zj-cj0001/41/2变量对偶问题剩下变量对偶问题变量y4y5y1y2y3项目对偶问题变量对偶问题剩下变量y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/2cj-zj15/2007/23/2变量原问题松弛变量原问题变量x3x4x5x1x221/69对偶问题基本性质1.弱对偶性

假如xj（j=1，...，n）是原问题可行解，yi（i=1，...，m）是其对偶问题可行解，则恒有22/69对偶问题基本性质弱对偶性推论：(1)原问题任一可行解目标函数值是其对偶问题目标函数值下界；反之对偶问题任一可行解目标函数值是其原问题目标函数值上界。23/69(2)如原问题有可行解且目标函数值无界(含有没有界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质逆不成立，当对偶问题无可行解时，其原问题或含有没有界解或无可行解，反之亦然。对偶问题基本性质24/69(3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题目标函数值无界。对偶问题基本性质25/69对偶问题基本性质最优性假如(j=1,...,n)是原问题可行解，(i=1,...,m)是其对偶问题可行解，且有则(j=1,...,n)是原问题最优解，(i=1,...,m)是其对偶问题最优解。26/69对偶问题基本性质强对偶性(或称对偶定理)

若原问题及其对偶问题均含有可行解，则二者均含有最优解，且它们最优解目标函数值相等。27/69对偶问题基本性质互补松弛性

在线性规划问题最优解中，假如对应某一约束条件对偶变量值为非零，则该约束条件取严格等式；反之假如约束条件取严格不等式，则其对应对偶变量一定为零。也即若>0，则有，即若，即，则有所以一定有，

28/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划29/69影子价格对偶最优解经济含义――影子价格

代表着当第i个右端常数增加一个单位时，最优目标函数值对应增量。其含义是在当前已给定情况下，最优目标值随资源数量改变改变率；其经济含义是为约束条件所付出代价。

当B是原问题最优基时，Y=CBB-1就是影子价格向量。30/69影子价格资源市场价格是其价值客观表达，相对比较稳定，而它影子价格则有赖于资源利用情况，是未知数。因企业生产任务、产品结构等情况发生改变，资源影子价格也随之改变。影子价格是一个边际价格。资源影子价格实际上又是一个机会成本。伴随资源买进卖出，其影子价格也将随之发生改变，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。31/69影子价格生产过程中假如某种资源未得到充分利用时，该种资源影子价格为零；又当资源影子价格不为零时，表明该种资源在生产中已花费完成。影子价格反应单纯形表中各个检验数经济意义。普通说对线性规划问题求解是确定资源最优分配方案，而对于对偶问题求解则是确定对资源恰当估价，这种估价直接包括资源最有效利用。32/69影子价格举例ABC拥有量工时1113材料1479单件利润233

y1=5/3,y2=1/3

即工时影子价格为5/3，材料影子价格为1/3。假如当前市场上材料价格低于1/3，则企业能够购进材料来扩大生产，反之能够卖掉部分材料。假如有客户以高于5/3价格购置工时，则能够出售一些工时，反之则反33/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划34/69对偶单纯形法对偶单纯形法并不是求解对偶问题解方法，而是利用对偶理论求解原问题解方法。求解单纯形法基本思绪：对原问题一个基可行解，判别是否全部检验数cj-zj≤0(j=1,…,n)。若是，又基变量中无非零人工变量，即找到了问题最优解；若为否，再找出相邻目标函数值更大基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。35/69对偶单纯形法对于标准线性规划问题：可行基B

若B对应基本解是可行解最优基B

若B对应基本解是最优解对偶可行基B

若CBB-1是对偶问题可行解即C-CBB-1A≤0或检验数≤036/69对偶单纯形法对于标准线性规划问题：最优基B可行基B对偶可行基B单纯形法可行基B保持可行性对偶可行基B对偶单纯形法可行基B保持对偶可行性对偶可行基B37/69对偶单纯形法对于标准线性规划问题：对偶单纯形法可行基B保持对偶可行性对偶可行基B①找一个基，建立初始对偶单纯形表，检验数全部非正；②若b列元素非负，则已经是最优基。反之，则取对应行基变量为出基变量；③为确保能对基可行性有所改进，则未来主元应该为负数；为确保下一个基还能是对偶可行基，应使检验数仍为非正。④主元变换38/69对偶单纯形法举例例2－6用对偶单纯形法求解：

39/69cj→-15-24-500CB基by1y2y3y4y50y4-20[-6]-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y3-1/3-50[-2/3]-1/31cj-zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2对偶单纯形法举例40/69对偶单纯形法练习：用对偶单纯形法求解

41/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划42/69灵敏度分析

在生产计划问题普通形式中，A代表企业技术情况，b代表企业资源情况，而C代表企业产品市场情况，在这些原因不变情况下企业最优生产计划和最大利润由线性规划最优解和最优值决定。在实际生产过程中，上述三类原因均是在不停改变，假如按照初始情况制订了最正确生产计划，而在计划实施前或实施中上述情况发生了改变，则决议者所关心是当前所执行计划还是不是最优，假如不是应该怎样修订原来最优计划。更深入，为了预防在各类情况发生时，来不及随时对其改变作出反应，即所谓“计划不如改变快”，企业应该预先了解，当各项原因改变时，应该作出什么样反应。43/69灵敏度分析步骤灵敏度分析步骤可归纳以下：1.将参数改变经过计算反应到最终单纯形表上来。2.检验原问题是否仍为可行解。3.检验对偶问题是否仍为可行解。4.按下表所列情况得出结论或决定继续计算步骤。原问题对偶问题结论或继续计算步骤可行解可行解问题最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新单纯形表重新计算44/69灵敏度分析

CB

XB

cjCBCN

xj

bXBTXNTCBTXBB-1bB-1BB-1N－Ｚ-CBB-1bCB-CBB-1BCN-CBB-1N若B是最优基，则最优表形式以下灵敏度分析总是在最优表上进行45/69灵敏度分析当系数A，b，C发生改变时，当前最优基是否还最优？为保持当前最优基还是最优，系数A，b，C允许改变范围是什么？假设每次只有一个系数改变①目标系数C改变基变量系数发生改变；

非基变量系数发生改变；②右端常数b改变③增加一个变量④增加一个约束⑤技术系数A发生改变46/69灵敏度分析举例分析cj改变例2-7

在第一章例1美佳企业例子中：（1）若家电Ⅰ利润降至1.5元/件，而家电Ⅱ利润增至2元/件时，美佳企业最优生产计划有何改变?cj→1.52000CB基bx1x2x3x4x50x315/2001[5/4]-15/21.5x17/21001/4-1/22x23/2010-1/43/2cj-zj0001/8-9/40x46004/51-61.5x1210-1/5012x23011/500cj-zj00-1/100-3/2即美佳企业随家电Ⅰ，Ⅱ利润改变应调整为生产2件Ⅰ，生产3件Ⅱ。47/69项目21+λ000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21+λx23/2010-1/43/2cj-zj000-1/4+1/4λ-1/2-3/2λ（2）若家电Ⅰ利润不变，则家电Ⅱ利润在什么范围内改变时，该企业最优生产计划将不发生改变？设家电Ⅱ利润为（1+λ）元，以下为确保最优解，-1/4+1/4λ≤0，-1/2-3/2λ

≤0解得-1/3≤λ≤1即家电Ⅱ利润c2改变范围应满足2/3≤c2≤2灵敏度分析举例48/69分析bi改变例2-8

在美佳企业例子中：（1）若设备A和调试工序天天能力不变，而设备B天天能力增加到32h，分析企业最优计划改变；灵敏度分析举例cj→21000CB基bx1x2x3x4x50x335/20015/4-15/22x111/21001/4-1/21x2-1/2010[-1/4]3/2cj-zj000-1/4-1/20x315051002x15110010x420-401-6cj-zj0-100-249/69灵敏度分析举例例2-8

（2）设设备A和设备B天天可用能力不变，则调试工序能力在什么范围内改变时，问题最优基不变。设调试工序天天可用能力为（5+λ）h，因有最终单纯形表中b列数字为因b>0时最优基不变，故-1≤λ≤1。调试工序能力应在4h~6h之间。50/69增加一个变量xj分析若企业在计划期内，有新产品能够生产，则在知道新产品单位利润，单件资源消耗量时，能够在最优表中补充一列，其中前m行能够由基矩阵逆矩阵得到，而检验数行也能够由与其它列相同方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；不然，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新最优解。51/69增加一个变量xj分析灵敏度分析举例增加一个变量在实际问题中反应为增加一个新产品。其分析步骤为：3.若σj′≤0，原最优解不变，只需将计算得到Pj′和σj′直接写入最终单纯形表中；若σj′>0，则按单纯形法继续迭代计算找出最优。52/69例2-9

设美佳企业又计划推出新型号家电Ⅲ，生产一件所需设备A、B及调试工序时间分别为3h、4h、2h，该产品预期盈利为3元/件，试分析该产品是否值得投产；如投产，对该企业最优生产计划有何影响。设生产x6件家电Ⅲ，有c6=3，P6=（3，4，2）T灵敏度分析举例53/69灵敏度分析举例cj→210003CB基bx1x2x3x4x5x60x315/20015/4-15/2-72x17/21001/4-1/201x23/2010-1/43/2[2]cj-zj000-1/4-1/210x351/407/213/8-9/402x17/21001/4-1/203x63/401/20-1/83/41cj-zj0-1/20-1/8-5/40最优生产计划应为天天生产7/2件家电Ⅰ，51/4件家电Ⅲ。54/69灵敏度分析举例分析参数aij改变例2-10在美佳企业例子中，若家电Ⅱ每件需设备A,B和调试工时变为8h、4h、1h，该产品利润变为3元/件，试重新确定该企业最优生产计划。设生产工时改变后新家电Ⅱ生产量为x2′，其中：55/69灵敏度分析举例cj→23000CB基bx1x2′x3x4x50x315/2011/215/4-15/22x17/211/201/4-1/21x23/20[1/2]0-1/43/2cj-zj03/20-1/4-1/20x3-90014-242x121001/2-23x2′3010-1/23cj-zj0001/2-5原问题和对偶问题均为非可行解56/69上表中第二阶段第一行约束为：x3+4x4-24x5=-9-x3-4x4+24x5+x6=9替换后重新得表：灵敏度分析举例cj→23000-MCB基bx1x2′x3x4x5x6-Mx6900-1-4[24]12x121001/2-203x2′3010-1/230cj-zj00-M1/2-4M-5+24M00x53/800-1/24-1/611/242x111/410-1/121/601/123x2′15/8011/800-1/8cj-zj00-5/24-1/30-M+5/24最优生产计划为天天生产11/4台家电Ⅰ，15/8台家电Ⅱ57/69灵敏度分析举例增加一个约束条件在企业生产过程中，经常有一些突发事件产生，造成原本不紧缺某种资源变成为紧缺资源，对生产计划造成影响。若把当前最优解代入新增加约束，能满足约束条件，则说明该增加约束对最优解不组成影响，即不影响最优生产计划实施。若当前最优解不满足新增加约束，则应把新约束添到原问题最优表内新一行中去，用对偶单纯形方法来进行迭代，求出新最优解。58/69增加一个约束条件灵敏度分析举例例2-11

设家电Ⅰ，Ⅱ经调试后，还需经过一道环境试验工序。家电Ⅰ每件需环境试验3h，家电Ⅱ每件需2h，又环境试验工序天天生产能力为12h。试分析增加该工序后美佳企业最优生产计划。（1）检验原问题最优解是否仍适用。将x1=7/2，x2=3/2代入3x1+2x2≤12，27/2>12，所以不适用。（2）加入松弛变量x6，得3x1+2x2+x6=12（3）单纯形表求解。59/69灵敏度分析举例cj→210000CB基bx1x2x3x4x5x60x315/20015/4-15/20①2x17/21001/4-1/20②1x23/2010-1/43/20③0x612320001④cj-zj000-1/4-1/200x315/20015/4-15/20①′2x17/21001/4-1/20②′1x23/2010-1/43/20③′0x6-3/2000-1/4[-3/2]1④′cj-zj000-1/4-1/200x3150015/20-52x141001/30-1/31x20010-1/2010x510001/61-2/3cj-zj000-1/60-1/3注：表中①′②′③′同①②③，④′=④-3×②-2×③。60/69线性规划对偶问题与灵敏度分析线性规划对偶问题对偶问题基本性质影子价格对偶单纯形法灵敏度分析参数线性规划61/69参数线性规划当目标函数中cj值连续改变时，其参数线性规划形式为：当约束条件右端项连续改变时，其参数线性规划形式为：62/69参数线性规划分析步骤分析步骤：（1）令λ=0求解得最终单纯形表；（2）将λC*或λb*项反应到最终单纯形表中去；（3）随λ值增大或减小，观察原问题或对偶问题，一是确定表中现有解（基）允许λ值得变动范围，而是当λ值变动超出这个范围时，用单纯形法或对偶单纯形法求取新解；（4）重复（3），一直到λ值继续增大或减小时，表中解（基）不再出现改变时为止。63/69参数线性规划举例例2-11

分析λ值改变时，下述参数线性规划问题最优解改变。（1）令λ=0求得最优解，并将λC*反应到最终单纯形表中，得下表。cj→2+λ