第二章对偶问题与灵敏度分析.ppt

《第二章对偶问题与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶问题与灵敏度分析2.1线性规划的对偶问题2.2对偶单纯形法2.3灵敏度分析1.6运输问题第二章线性规划的对偶问题与灵敏度分析2.1线性规划的对偶问题LP一个线性规划另一个线性规划极值问题存在同一个研究对象极值问题ABC45809012111345甲乙资源量利润y1y2y3MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥02.1.1.1资源价格问题的数学模型LP2.1.1问题的引入：资源价格问题生产计划问题资源价格问题W(y）=45y

2、1+80y2+90y3y1+2y2+y3ABC45809012111345甲乙资源量利润y1y2y3卖方：买方：Miny1+y2+3y3y1，y2，y3≥0≥4≥5LP资源价格问题2．1．1．2两问题数学模型的对应关系(1)两个问题的系数矩阵互为转置。(2)一个问题变量的个数，等于另一个问题的约束条件的个数。MaxZ（X）=4x1+5x2x1+x2≤452x1+x2≤80x1+3x2≤90x1，x2≥0MinW(y）=45y1+80y2+90y3y1+2y2+y3≥4y1+y2+3y3≥5y1，y2

3、，y3≥0y1x1x2y2y3(3)一个问题的右端常数，是另一个问题的目标函数的系数。(4)若一个问题的目标为“max”，约束为“≤类型；则另一个问题的目标为“min”，约束为“≥”类型。这种关系称为对称型对偶关系。2．1．2对称型对偶问题的一般形式生产计划问题原问题MaxZ（X）=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2………………………………………………….am1x1+am2x2+…+amnxn≤bmx1，x2，…，

4、xn≥0其对偶问题为：MinW(y）=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2……………………………………………a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥0这种模型的特点：所有决策变量均为非负变量，所有约束条件均为“≤”型，目标函数为“Max”。y1y2...ymx1x2xnLP2．1．3非对称型对偶问题例：求下列线性规划的对偶问题MaxZ（X）=2x2-5x3x1+x3≥22x1+x2+6x3≤

5、6x1-x2+3x3=0x1，x2，x3≥0x1-x2+3x3≤0x1-x2+3x3≥0MaxZ（X）=2x2-5x3-x1-x3≤-22x1+x2+6x3≤6x1-x2+3x3≤0-x1+x2-3x3≤0x1，x2，x3≥0其对偶问题为：MinW(y）=-2y1+6y2-y1+2y2+y3/-y3//≥0y1y2y3/y3//y2-y3/+y3//≥2-y1+6y2+3y3/-3y3//≥-5y1，y2，y3/，y3//≥0x1x2x3LPMaxZ（X）=2x2-5x3x1+x3≥22x1+x2+

6、6x3≤6x1-x2+3x3=0x1，x2，x3≥0MaxZ（X）=2x2-5x3-x1-x3≤-22x1+x2+6x3≤6x1-x2+3x3=0x1，x2，x3≥0其对偶问题为：MinW(y）=-2y1+6y2x1-y1+2y2+y3/-y3//≥0x2y2-y3/+y3//≥2x3-y1+6y2+3y3/-3y3//≥-5y1，y2，y3/，y3//≥0MinW(y）=-2y1+6y2x1-y1+2y2+y3≥0x2y2-y3≥2x3-y1+6y2+3y3≥-5y1，y2≥0以：y3=y3/-y

7、3//代入上对偶问题，观察原问题与对偶问题的关系LPMinW(y）=-2y1+6y2-y1+2y2+y3≥0y2-y3≥2-y1+6y2+3y3≥-5y1，y2≥0原问题：MaxZ（X）=2x2-5x3x1+x3≥22x1+x2+6x3≤6x1-x2+3x3=0x1，x2，x3≥0其对偶问题为：MinW(y）=2y1+6y2y1+2y2+y3≥0y2-y3≥2y1+6y2+3y3≥-5y1≤0，y2≥0练习：MinZ（X）=x1+2x2+x3x1+x2+x3≤2x1-x2+x3=12x1+x2+x3

8、≥1x1≥0MinZ（X）=x1+2x2+x3-x1-x2-x3≥-2x1-x2+x3=12x1+x2+x3≥1x1≥0y1y2y3其对偶问题为：MaxW(y）=-2y1+y2+y3-y1+y2+2y3x2x1x3-y1-y2+y3=2y1，y3≥0-y1+y2+y3≤1=1LP练习：MinZ（X）=x1+2x2+x3x1+x2+x3≤2x1-x2+x3=12x1+x2+x3≥1x1≥0其对偶问题为：MaxW(y）=-2y1+y2+y3-y1+y2+2y3x2x1x3