资源描述：
《运筹学 03 对偶理论及灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、对偶理论及灵敏度分析DualTheoryandSensitivityAnalysis对偶理论DualTheory影子价格Shadowprice对偶单纯形法DualSimplexMethod灵敏度分析SensitivityAnalysis参数线性规划ParameterLP1对偶理论对偶问题的提出原问题与对偶问题的数学模型原问题与对偶问题的对应关系对偶问题的基本性质影子价格对偶单纯形法对偶问题的提出例1：某厂利用现有资源(设备A、设备B、调试工序)生产两种产品(产品Ⅰ、产品Ⅱ)，有关数据如下表。问如何安排生产，使厂家利润最大？产品Ⅰ产品Ⅱ资源限量设
2、备A0515设备B6224调试工序115单位利润21分析：设产品Ⅰ的产量为x1，产品Ⅱ的产量为x2；又设利润为z。则该问题的线性规划数学模型为：maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0换一种思路：厂家的资源只出让而不自己生产，该如何解决？设备A出让单价为y1，设备B出让单价为y2，调试工序出让单价为y3。收购收购代价最小厂家出让所得应不低于用同等数量的资源自己生产的利润。厂家接受的条件：利润需要保证，即6y2+y3≥25y1+2y2+y3≥1收购方接受的条件：收购成本最低，即minw=15y1+24y2
3、+5y3于是得到一个线性规划模型minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0原问题与对偶问题的数学模型原问题maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0对偶问题minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1,y2,y3≥0互为对偶问题厂家收购原问题及其对偶问题的最终单纯形表-zx1x2x3x4x5bmax1000-0.25-0.5-8.5x30011.25-7.57.5x11000.25-0.53.5x2010-0.251
4、.51.5-wy1y2y3y4y5y6y7bmin17.5003.5M-3.51.5M-1.5-8.5y2-1.2510-0.250.250.25-0.250.25y37.5010.5-0.5-1.51.50.5尝试求解上述两个线性规划问题，你会发现目标函数值一致两个问题的解都出现在单纯形法表格中其他规律结论原问题与其对偶问题实质上一样两个问题互为对方的另一种表达形式原问题与对偶问题的对应关系原问题对偶问题对称数学模型maxz=CXAX≤bX≥0minf=bTYATY≥CTY≥0目标函数取值maxzminf变量X=(x1,x2,…,xn)TY=
5、(y1,y2,…,ym)T目标函数系数C=(c1,…,cn)bT=(b1,…,bn)常数b=(b1,…,bn)TCT=(c1,…,cn)T约束条件系数A=(aij)m×nAT=(aij)n×m变量-约束变量(n,≥0,≤0,任意)约束(n,≥,≤,=)约束-变量约束(m,≤,≥,=)变量(m,≥0,≤0,任意)例2：将下述线性规划作为原问题，请转换为对偶问题maxz=5x1+3x2+2x3+4x45x1+x2+x3+8x4≤82x1+4x2+3x3+2x4=10x1≥0,x2≥0,x3任意,x4任意解法1：将原问题写成对称形式的线性规划问题。得
6、到maxz=5x1+3x2+2(x3’-x3’’)+4(x4’-x4’’)5x1+x2+(x3’-x3’’)+8(x4’-x4’’)≤82x1+4x2+3(x3’-x3’’)+2(x4’-x4’’)≤10-2x1-4x2-3(x3’-x3’’)-2(x4’-x4’’)≤-10x1≥0,x2≥0,x3’≥0,x3’’≥0,x4’≥0,x4’’≥0设对偶问题变量y1,y2’,y2’’≥0，直接转换，得minf=8y1+10y2’-10y2’’5y1+2y2’-2y2’’≥5y1+4y2’-4y2’’≥3y1+3y2’-3y2’’≥2-y1-3y2’
7、+3y2’’≥-28y1+2y2’-2y2’’≥4-8y1-2y2’+2y2’’≥-4y1,y2’,y2’’≥0令y2=y2’-y2’’(即y2取值任意)，合并第3、4个约束条件和第5、6个约束条件，得到原问题的对偶问题minf=8y1+10y25y1+2y2≥5y1+4y2≥3y1+3y2=28y1+2y2=4y1≥0,y2任意解法2：也可以根据原问题与对偶问题的对应关系，直接得到对偶问题：minf=8y1+10y25y1+2y2≥5y1+4y2≥3y1+3y2=28y1+2y2=4y1≥0,y2任意对偶问题的基本性质对称性：对偶问题的对偶是
8、原问题(对称定理)。证明：设原问题为maxz=CX,AX≤b,X≥0；则其对偶问题为minf=bTY,ATY≥CT,Y≥0。把对偶问题看作原问题，得到
