第二章--线性规划的对偶理论与灵敏度分析--运筹学.ppt

《第二章--线性规划的对偶理论与灵敏度分析--运筹学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学出版社《运筹学教程》（第二版）运筹学基础胡运权主编教材例一美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如下表所示。问该公司应制造Ⅰ、Ⅱ两种家电备多少件．使获取的利润为最大。设：x1——A产品的生产量x2——B产品的生产量利润maxz=2x1+x2约束条件5x2≤156x1+2x2≤24x1+x2≤5x1，x2≥0st.5x2+x3=156x1+2x2+x4=24x1+x2+x5=5x1，x2，x3，x4，x5≥0约束条件st.利润maxz=2x

2、1+x2+0x3+0x4+0x5一、标准化二、写出初始单纯形表（必定存在有单位矩阵）C21000θCBXBbx1x2x3x4x5000x3x4x515245051006201011001σ21000三、最优解检验（唯一解、无限多解、无界解和无解）X*=(7/2,3/2,15/2,0,0)Z*=17/2C21000θCBXBbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2σ000-1/4-1/25x2≤156x1+2x2≤24x1+x2≤5x1，x2≥0约束条件把解X=(7/2,3/2)代入原问

3、题(因为x3、x4、x5为附加变量)四、分析5×3÷2＝15/2245A有空闲B设备已经饱和调试工序也已经满负荷一个问题？市场上设备A、设备B和调试工序每小时值多少钱？在什么价位时，才能使美佳公司愿意出让自己的资源？＜＝＝6y2+y3分析设：y1—设备A值的价值y2—设备B值的价值y3—调试工序值的价值≥25y1+2y2+y31≥z=15y1+24y2+5y3总价值miny1,y2,y3≥0st.例一6y2+y3≥25y1+2y2+y31≥z=15y1+24y2+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3maxst.6y2+y3–y4=

4、25y1+2y2+y3–y51=y1,y2,y3,y4,y5≥0C-15-24-500-M-MθCBYBby1y2y3y4y5y6y7-M-My6y721061-10105210-101σM-158M-242M-5-M-M00问题求解6y2+y3≥25y1+2y2+y31≥z=15y1+24y2+5y3miny1,y2,y3≥0st.z'=-15y1-24y2-5y3maxst.6y2+y3–y4=25y1+2y2+y3–y51=y1,y2,y3,y4,y5≥0C-15-24-500θCBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41

5、/415/2011/2-3/2σ-15/200-7/2-3/2Y=(0,¼,½,0,0)z'=-17/2z=17/2问题求解Y=(0,¼,½,0,0)问题分析问题的解6y2+y3≥25y1+2y2+y31≥z=15y1+24y2+5y3miny1,y2,y3≥0st.问题：？原问题：利润maxz=2x1+x2约束条件5x2≤156x1+2x2≤24x1+x2≤5x1，x2≥0st.问题的解X*=(7/2,3/2,15/2,0,0)Z*=17/2Z*=17/25*3/2=15/215＜6*7/2+2*3/2=2424=7/2+3/2=55=结论两个问题的最优解的值一致

6、最大值问题可行解的目标值必定不大于最小值问题可行解的目标值一个问题的剩余变量（松弛变量）不为0（即有资源剩余），则对应问题的解为0一个决策变量不为0，则对应的问题的约束条件的剩余变量(松弛变量)为0(即资源彻底用完)估价——影子价格（即增加单位资源所得到的贡献）Z=ω=CX=YbZ/b=(Yb)'=YC21000CBXBbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2σ000-1/4-1/2-σ0001/41/2利润maxz=2x1+x2约束条件5x2≤156x1+2x2≤24x1+x2≤

7、5x1，x2≥0st.6y2+y3≥25y1+2y2+y31≥z=15y1+24y2+5y3miny1,y2,y3≥0st.C-15-24-500CBYBby1y2y3y4y5-24-5y2y31/41/2-5/410-1/41/415/2011/2-3/2σ-15/200-7/2-3/2-σ15/2007/23/2Y=(0,¼,½,0,0)X*=(7/2,3/2,15/2,0,0)问题变量问题剩余松弛变量解的关系一、线性规划的对偶问题1、对偶问题定义对称形式X≥0st.AX≤bmaxz=CX其中：C=（c1，c2,…,cn)b=（b1，b2,…,bm)TX=（