清华大学出版社：《运筹学》课程教学资源（PPT课件讲稿，教材第三版）第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论

运筹学 第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