线性规划对偶问题.pptx

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

1、主要内容一、对偶问题的基本概念二、对称的对偶线性规划三、对偶的基本性质四、对偶单纯形法第1页/共58页一、对偶问题的基本概念载重汽车载重汽车 大轿车大轿车资源限制资源限制钢材钢材劳动力劳动力座椅座椅22.5025116002500400利润（千元利润（千元/辆）辆）34传统的线性规划问题：在有限的资源下如何安排生产以获得最大利润第2页/共58页该问题的线性规划模型为：目标函数：max Z=4x1+3x2 约束条件：2x1 2x2 1600 5x1+2.5x2 2500 x1 400 x1 0,x2 0第3页/共58页现在的问题：如果工厂目前不再打算生产汽车，而是将钢材和座椅以比买价更高的价格卖

2、出去（加价），把生产能力以更高的工时费接受外协加工，那么材料和工时的定价应该是多少才是合算的？第4页/共58页假设y1表示出售单位钢材的利润，y2表示外协加工的工时利润，y3表示出售每套大轿车座椅的利润那么生产一辆载重汽车的材料销售利润和工时利润之和不应低于出售一辆载重汽车所得的利润，即：2y1+2.5y23同样有，2y1+5y2+y3 4第5页/共58页为了不亏本，各种材料的利润（加价）不能为负值，即：y1、y2、y3 0工厂的总利润是出售材料的利润、工时利润和座椅利润之和，即：W=1600y1+2500y2+400y3第6页/共58页从工厂决策者的角度看W越大越好。但为了在市场实现交易，在

3、满足上述条件的基础上，W应尽可能小。从而得到如下线性规划模型：Min W=1600y1+2500y2+400y32y1+2.5y23 s.t.2y1+5y2+y3 4y1、y2、y3 0第7页/共58页线性规划原问题和对偶问题原问题：Max Z=c1x1+cnxn a11x1+a1nxnb1 a21x1+a2nxnb2s.t.am1x1+amnxn bm X1,xn0对偶问题：MinW=b1y1+bmyma11y1+am1ym c1a12y1+am2ym c2s.t.a1ny1+amnym cny1,ym 0第8页/共58页矩阵表述原问题：Max Z=CTX s.t.AXb X 0对偶问题：M

4、in W=bTY s.t.ATY C Y 0第9页/共58页两个模型之间的关系：原问题是求最大值，而对偶问题是求最小值；原问题的约束条件是“”，而对偶问题的约束条件是“”；原问题的目标函数系数是对偶问题的约束条件右端的常数项；原问题的约束条件右端的常数项是对偶问题目标函数的系数；原问题约束条件中xi的系数是对偶问题第i个约束条件的系数，原问题第i个约束条件的系数是对偶问题的约束条件中yi的系数。第10页/共58页对称的对偶线性规划定义：如果一个线性规划具备下面两个条件，则称它具有对称形式：所有的变量都是非负的；所有的约束条件都是不等式，且在目标函数是求极大值的情况下，为“”型，求极小值时，为“

5、”型。第11页/共58页原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数限定向量限定向量价值向量价值向量技术系数技术系数约束条件约束条件变量数目变量数目约束条件个数约束条件个数变量正负变量正负目标函数目标函数价值向量价值向量限定向量限定向量技术系数技术系数对偶变量对偶变量约束条件个数约束条件个数对偶变量数目对偶变量数目约束条件约束条件第12页/共58页非对称形式的对偶问题在原线性规划问题为Max型，且变量非负的前提下：1.原问题约束条件是“”型两边都乘以“-1”转化为“”型，得到对偶规划的变量约束为：yi0第13页/共58页例：Max Z=x1+2x2-

6、3x3 S.t.x1+2x2+5x31 2x1-3x2-4x3 2 x1,x2,x3 0MaxZ=x1+2x2-3x3S.t.-x1-2x2-5x3-12x1-3x2-4x3 2x1,x2,x3 0MinW=-y1+2y2S.t.-y1+2y2 1-2y1-3y2 2-5y1-4y2-3y1,y2 0令y1=-y1，上述模型化为：MinW=y1+2y2S.t.y1+2y2 12y1-3y2 25y1-4y2-3y1 0,y2 0第14页/共58页例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3 2 x1,x2 0,x3 0令x3=-x3，得：Max

7、Z=x1+2x2+3x3S.t.x1+2x2-5x3 12x1-3x2+4x3 2x1,x2,x3 0MinW=y1+2y2S.t.y1+2y2 12y1-3y2 2-5y1+4y2 3y1,y2 0第三个方程两边同乘-1，得MinW=y1+2y2S.t.y1+2y2 12y1-3y2 25y1-4y2-3y1,y2 0第15页/共58页2.原问题约束条件是“=”型看成两个约束条件：”+”组成，得到对偶规划的变量约束为：yi无非负约束（即可正可负）第16页/共58页例：Max Z=x1+2x2-3x3 S.t.x1+2x2+5x3 1 2x1-3x2-4x3=2 x1,x2,x3 0MaxZ=

8、x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 22x1-3x2-4x3 2x1,x2,x3 0MinW=y1+2y2-2y3S.t.y1+2y2-2y3 12y1-3y2+3y3 25y1-4y2+4y3-3y1,y2,y3 0MaxZ=x1+2x2-3x3S.t.x1+2x2+5x3 12x1-3x2-4x3 2-2x1+3x2+4x3-2x1,x2,x3 0第17页/共58页令y4=y2-y3，得：Min W=y1+2y4 S.t.y1+2y4 1 2y1-3y4 2 5y1-4y4 -3 y1 0,y4无符号约束 第18页/共58页原问题与对偶问题的对应关系

9、原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数为目标函数为MaxZ目标函数为目标函数为MinW变量变量n个个 0 0无约束无约束n个个 约束条件约束条件约束约束条件条件m个个 m个个 0 0无约束无约束变量变量价值系数价值系数cj约束条件右端项约束条件右端项bi约束条件的系数矩阵约束条件的系数矩阵A约束条件右端项约束条件右端项cj价值系数价值系数bi约束条件的系数矩阵约束条件的系数矩阵AT第19页/共58页例：写出下面线性规划问题的对偶问题：1.解：根据上述对偶关系，可以写出原问题的对偶问题：第20页/共58页例：写出下面线性规划问题的对偶问题：2.解

10、：根据上述对偶关系，可以写出原问题的对偶问题：第21页/共58页对偶的基本性质原问题：Max Z=CTX s.t.AXb X0对偶问题：Min W=bTY s.t.ATY C Y 0第22页/共58页对称性：对偶问题的对偶是原问题；弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解，则CTX bTY第23页/共58页弱对偶性的证明：AX bXTAT bTXTATY bTY所以：bTY XTATY XTC=CT X第24页/共58页无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。例：说明：无界性质并不存在逆（例见：P57）第25页/共58页可行解是最优解的条件：设X*是原

11、问题的可行解，Y*是对偶问题的可行解，当CTX*=bTY*时，X*，Y*是最优解。证明：由弱对偶性，可知原问题的所有可行解X均满足 CT X bTY*又因为CTX*=bTY*，所以CT X CTX*，即：X*是使目标函数取值最大的可行解。因而是最优解。同理可证Y*也是最优解。第26页/共58页对偶定理：若原问题有最优解，则对偶问题也有最优解，且最优目标函数值相等。第27页/共58页证明：设X*是原问题的最优解，则其对应的基矩阵B必有：CBTB-1A-CT0，（非基变量的检验数大于或等于0，基变量的检验数等于0）即：ATY*C，其中，Y*=CBTB-1T 故Y*是对偶问题的可行解，它使：W=bT

12、Y*=bTCBTB-1T=CBTB-1b 由于X*是原问题的最优解，使目标函数值Z=CTX*=CBTB-1b由此得到：bTY*=CBTB-1b=CTX*因此，Y*是对偶问题的最优解。第28页/共58页原规划的检验数对应于对偶规划的一个解；对偶规划的检验数对应于原规划的一个解。特别地，若原问题的最优基为B，则其对偶问题的最优解为Y*=CBTB-1第29页/共58页互补松驰定理：设原问题和对偶问题的标准型分别为：若X*，Y*分别是原问题和对偶问题的可行解，那么Y*TXs=0和YsTX*=0当且仅当X*、Y*为最优解。第30页/共58页证明：原问题 对偶问题 Max Z=CX Min W=Yb AX

13、+Xs=b YA-Ys=C X,Xs0 Y,Ys 0 Z=CX=(YA-Ys)X=YAX-YsX W=Yb=Y(AX+Xs)=YAX+YXs 充分性：P58 必要性：P58第31页/共58页该定理的隐含结论：当一对对偶规划达到最优时，若一个问题的某个变量为正数，则相应的另一个问题的约束必取等式；或者一个问题中的约束条件取不等式，则相应的另一个问题的变量必为零。理由：由于X*,Y*为最优，故YsTX*=0，Y*TXs=0。如果Xi*0，所以有Ysi=0，也就有对偶问题相应的约束条件为等式约束（因为X,Y都是非负的）；如果Y*j0，所以有Xsj=0，也就有对偶问题相应的约束条件为等式约束。第32页

14、/共58页设原问题是：max Z=CX;AX+Xs=b;X,Xs0 对偶问题是：min W=Yb;YA-Ys=C;Y,Ys0 则原问题单纯形表的检验数行对应于其对偶问题的一个基解，其对应关系为：XBXNXS0CN-CBB-1N-CBB-1YS1YS2-Y第33页/共58页例：已知线性规划问题 的最优解为X*=(0,0,4,4)T，最优值Z*28。试用互补松驰性找出其对偶问题的最优解。第34页/共58页解：写出该问题的对偶问题：Min W=20y1+20y2 S.t.y1+2y21 2y1+y2 2 2y1+3y2 3 3y1+2y2 4 yi 0,i=1,2,3,4 根据互补松驰性，可得：x3

15、*=40,则2y1+3y2=3x4*=40,则3y1+2y2=4解得：y1=6/5,y2=1/5满足对偶问题的前两个约束条件，所以它是对偶问题的可行解。其对应的目标函数W*=28=Z*，从而y1=6/5,y2=1/5为对偶问题的最优解。第35页/共58页例：已知线性规划问题 试用对偶理论证明上述线性规划问题无最优解。第36页/共58页证明：首先看到该问题存在可行解，如X=(0,0,0)，而上述问题的对偶问题为：由第一个约束条件可知对偶问题无可行解，因原问题有可行解，故无最优解（若原问题有最优解，则对偶问题也有最优解）。第37页/共58页对偶单纯形法对偶单纯形法是运用对偶原理求解原问题的一种方法

16、，而不是求解对偶问题的单纯形法。正则解：检验数全部为非负的基本解，叫正则解。正则解一般不可行。如果可行，即为最优解。原理：从一个正则解出发，用单纯形法进行迭代，迭代过程中始终保持解的正则性不变，使解的不可行性逐渐消失，所得第一个可行解即为最优解。第38页/共58页其与单纯形法的区别在于：单纯形法在整个迭代的过程中，始终保持原问题的可行性，即常数列非负，而检验数由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。对偶单纯形法在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数非负，而常数列由有负分量逐步变为全部非负，即同时得到原问题和对偶问题的最优解。第39页/共58页单纯形法单

17、纯形法对偶单纯形法对偶单纯形法从一个初始基可行解出发从一个初始基可行解出发 从一个初始正则解出发从一个初始正则解出发检验数可检验数可正可负正可负保持右边常保持右边常数非负（即数非负（即解的可行性）解的可行性）右边常数右边常数可正可负可正可负保持检验数保持检验数非负（即解非负（即解的正则性）的正则性）检验数均非负，则为最优检验数均非负，则为最优解解常数均非负，则为最优解常数均非负，则为最优解第40页/共58页对偶单纯形法的步骤确定换出变量：在负的基变量中选择最小的基变量为换出变量；确定换入变量：用换出变量的那一行具有负值的系数分别去除同列的检验数，取绝对值最小者所对应的变量为换入变量；进行迭代变

18、换（分别进行行、列变换）；进行最优性检验：如果所得的基本解都是非负的，则此解即为最优解，反之继续迭代，直至所有基变量为非负的数值为止。第41页/共58页对于生产汽车的例子：Min W=1600y1+2500y2+400y3 2y1+5y2+y3 4 s.t.2y1+2.5y2 3 y1、y2、y3 0Max(-W)=-1600y1-2500y2-400y3-My5-My7 2y1+5y2+y3-y4+y5=4 s.t.2y1+2.5y2-y6+y7=3 y1 0,i=1,2,7第42页/共58页Min(-W)=-1600y1-2500y2-400y3-2y1-5y2-y3-4 s.t.-2y1

19、-2.5y2 -3 y1、y2、y3 0Min(-W)=-1600y1-2500y2-400y3-2y1-5y2-y3+y4=-4 s.t.-2y1-2.5y2+y5=-3 y1、y2、y3 0第43页/共58页解的过程：见Word文档第44页/共58页对偶单纯形法的优点及用途初始可行解可以是非可行解，当检验数都是正值时，就可以进行基变换，这样就避免了增加人工变量，使运算简化；对变量较少，而约束条件很多的线性规划问题，可先将其变为对偶问题，再用对偶单纯形法求解，简化计算；可用于灵敏度分析。第45页/共58页影子价格对偶变量yi的意义是在当前的基解中对一个单位的第i种资源的估价。这种估价不是资源

20、的市场价格，而是根据资源在生产中做出的贡献而作出的估价，我们称之为影子价格。yi=W/bi影子价格是一种动态价格，也是一种机会成本。第47页/共58页当bi变为bi+bi 时，（由于，（由于，Z=CBTB-1b，故有：，故有：CBTB-1=Y*T）第48页/共58页影子价格的经济意义是在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化，即对偶变量就是第个约束条件的影子价格。影子价格是针对某一具体的约束条件而言的，而问题中所有其他数据都保持不变，因此影子价格也可以理解为目标函数最优值对资源的一阶偏导数。第49页/共58页影子价格，又称为Lagrange乘子或灵敏率系数，通常指线性规

21、划对偶模型中对偶变量的最优解。如果原规划模型属于在一定资源约束条件下，按一定的生活消耗生产一组产品并寻求总体效益目标函数最大化问题，那么其对偶模型属于对本问题中每一资源以某种方式进行估值以便得出与最优生产计划相一致的一个企业的最低总价值。该对偶模型中资源的估价表现为相应资源的影子价格。第50页/共58页当所有资源按最优方式分配时，第i种资源的影子价格yi给出了第i种资源（单位）追加量的边际利润。即，在原规划模型最优基保持不变的前提下，增加（减少）单位第i种资源，原规划模型的目标函数值将增加或减少一个yi值，因此，人们可以根据yi的大小，对第i种资源紧缺程度和经济效果作出判断，探讨资源的优化利用

22、，为企业决策服务。第51页/共58页影子价格yi随着目标函数、约束条件的经济意义和测度单位不同而有种种不同的具体内容。如：将yi视为第i种资源的边际值。它反映了一定条件下，增加（减少）单位第i种资源占用量对目标函数增加或减少的影响程度。将yi视为第i种资源机会成本或机会损失，它反映了企业若放弃单位第i种资源的利用，将失去一次获利机会，其损失价值为yi；若增加单位第i种资源的利用，企业将赢得一次增值为yi的获利机会。第52页/共58页将yi看作一种附加值或附加价格，它取决于企业对第i种资源使用效果的一种评价。若第i种资源的单位市场价格为mi，当yi mi时，企业愿意购进这种资源。也就是说，如果第

23、i种资源追加一单位，作最优分配时所得利润yi比成本mi要大，单位纯利润为yi-mi，购进这种资源有利可图；如果yimi，企业愿意有偿转让这种资源，可获单位纯利 mi-yi，否则，企业将无利可图，甚至亏损。第53页/共58页影子价格在经济管理中的应用影子价格能指示企业内部挖潜的方向它能指出各种资源在实现企业最优目标时的影响作用：影子价格愈高的资源，表明它对目标增益的影响愈大，同时也表明这种资源对该企业来说愈稀缺和愈贵重，企业的管理者应该更加重视对这种资源的管理。对影子价格为零的资源，则考虑如何加以利用，或转让，或充分利用第54页/共58页影子价格在企业经营决策中的作用影子价格不同市场价格，它是根

24、据企业本身的资源情况、资源消耗系数、产品价值系数计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源，其影子价格也不一定相同。同一个企业不同生产周期，资源的影子价格也不完全一样。因此，企业的决策者可以把本企业资源的影子价格与市场价格进行比较：影子价格高于市价时，可以买进；反之，则卖出第55页/共58页其中，其中，cj表示单位第表示单位第j种产品的利润，而种产品的利润，而 iaijyj表示生产第表示生产第j 种产品所消耗的各项资种产品所消耗的各项资源的影子价格的总和，它可以称为第源的影子价格的总和，它可以称为第j 种产种产品的品的单位隐含成本单位隐含成本。检验数。检验数 j又可以称为是又可以称为是第第j 种产品的种产品的相对价值系数相对价值系数第56页/共58页影子价格在新产品开发决策中的应用企业在新产品投产前，可以利用影子价格，通过分析新产品使用资源的经济效果，以决定新产品是否应该投产。利用影子价格分析现有产品价格变动对资源紧缺情况的影响（即系数c变动对y的影响）第57页/共58页感谢您的观看！第58页/共58页