运筹学 第2章 对偶理论 和 (第三版) 灵敏度分析 《运筹学》教材编写组编写 第4节 线性规划的 对偶理论 钱颂迪制作 清华大学出版社
运筹学 （第三版） 《运筹学》教材编写组编写 清华大学出版社 第2章 对偶理论 和 灵敏度分析 第4节 线性规划的 对偶理论 钱颂迪制作
第2章对偶理论和灵敏度分析 第4节线性规划的对偶理论 从理论上讨论线性规划的对 偶问题
第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论 •从理论上讨论线性规划的对 偶问题
41原问题与对偶理论 原问题(LP) maxz=cix t c2x2 +.+cnx 12 I 2 1,2 0
4.1 原问题与对偶理论 • 原问题（LP）： 1 2 0 1 2 1 1 2 1 1 1 2 1 1 1 2 2 = = + + + n m n m m m n n n n x ,x , ,x b b x x x a a a a a a max z c x c x c x
对偶问题(D mi=yb1+y2b2+…+ynbn 12 ●●● 1,c2, mI a a 2 y1,y2,…,y ≥0
•对偶问题(DP) ( ) ( ) 1 2 0 1 2 1 2 1 1 1 2 1 1 2 1 1 2 2 m = + + + n n m m m n n m m y , y , , y c ,c , ,c a a a a a a y , y , , y min y b y b y b
标准型原问题与对偶问题的关系 I 原关系mina y 21 2 h2 2 b 对偶关系>≥ maXz c maxz= min
标准型原问题与对偶问题的关系 c c c min y a a a b y a a a b y a a a b x x x y x m n m m m m n m n n n i j = maxz maxz min 1 2 1 2 2 2 1 2 2 2 2 1 1 1 1 2 1 1 1 2 对偶关系 原关系
例2根据表2-3写出原问题与对偶 问题的表达式。 表23 y 8
例2 根据表2-3写出原问题与对偶 问题的表达式。 • 表2-3 x y x1 x2 x2 y1 1 1 1 y2 2 2 2 y3 8 8 8 c 4 4 4
标准形式的变换关系为对称形式 原问题(LP)→→对偶问题(DP maxz=2x,+3x2 miOD=8y1+16y2+12y3 x,+2x<8 4x, <16 y+4 y 4x,≤12 y,y2,y3≥0 x1,x≥0
标准形式的变换关系为对称形式 原问题 （LP） 对偶问题(DP) + + + = + = + + 0 2 3 4 2 0 4 12 4 16 2 8 2 3 8 16 12 1 2 3 1 3 1 2 1 2 2 1 1 2 1 2 1 2 3 y , y , y y y y y x ,x x x x x max z x x min y y y
非对称形式的变换关系 原问题的约束条件中含有等式约束条件 时,按以下步骤处理。 设等式约束条件的线性规划问题 ncx2三 ∑ ≥0
非对称形式的变换关系 • 原问题的约束条件中含有等式约束条件 时，按以下步骤处理。 • 设等式约束条件的线性规划问题 = = = = = = x , j , , ,n a x b , i , , m max z c x j n j i j j i n j j j 0 1 2 1 2 1 1
第一步:先将等式约束条件分解 为两个不等式约束条件。 nax 人) ≤bj a.x.≥b J 1.2 x,≥0,j=1,2,…,n ∑ax≤-b1=12,…,m(2-14)
第一步：先将等式约束条件分解 为两个不等式约束条件。 ( ) ( ) − − = − = = − = = = = = = = = = n j i j j n j i j j n j i j j j n j i j j i n j j j a x b i , , ,m a x b j , , ,m a x b j , , ,m x , j , , ,n a x b , i , , m max z c x 1 1 1 1 1 12 2 14 1 2 1 2 2 13 0 1 2 1 2
第二步:按对称形式变换关系 可写出它的对偶问题 设y;′是对应(2-13)式的对偶变量 y;"是对应(2-14)式的对偶变量。 这里=1,2,,m
第二步：按对称形式变换关系 可写出它的对偶问题 • 设yi ′是对应(2-13)式的对偶变量 yi ″是对应(2-14)式的对偶变量。 • 这里i=1,2,…，m