《运筹学》课程教学课件（PPT讲稿）第二章 线性规划的对偶理论（Dual Linear Programming, DLP）

原问题对偶问题max Z = 2xi +3x2min W =12y +16y2 +15y32x +2x2 ≤12≥2s.t2y +4y2≤164x12y1+5y,≥35x2 ≤15Ji,y2 >0Xi,x2 ≥0V用矩阵将上述原问题对偶问题写出min W = b'Y = (12,16,15)y2Xmax Z（y3A(12 16=bAXV?(15)Y≥0X≥02025/4/5

2025/4/5 7           +  , 0 5 15 4 16 2 2 12 1 2 2 1 1 2 x x x x x x max Z = 2x1 +3x2 min 12 1 16 2 15 3 W = y + y + y s.t 2y1 + 4y2  2 , 0 2 5 3 1 2 1 3  +  y y y y  原问题 对偶问题 用矩阵将上述原问题对偶问题写出 0 15 16 12 0 5 4 0 2 2 max (2,3) 2 1 2 1  =                             =         = = X b x x AX x x Z CX 0 3 2 2 0 5 2 4 0 min (12,16,15) 3 2 1 3 2 1  =                           =           = = Y c y y y A Y y y y W b Y T T T

即:max Z = CXmin W = b'y对原偶AX≤bAY≥CT间问X≥0题Y≥0题2025/4/5

2025/4/5 8 即：原问题 0 max  = X AX bZ CX 0 min  = YA Y C W b Y T T T 对偶问题

S 2 原问题与对偶问题对于一般的线性规划问题max z = Cxi +C2X2 +...+Cnxnaiix +ai2X2 +...+ainx, ≤b→ya21X +a22X2 +...+a2nXn ≤b2→y2amiXj +am2X2 +...+amnXn, ≤bm→ymX,X2,."",X, ≥02025/4/5

2025/4/5 9           + + +  → + + +  → + + +  → 1 , 2 , , 0 1 1 2 2 2 1 1 2 2 2 2 2 2 1 1 1 1 2 2 1 1 1 n m m m n n m m n n n n x x x a x a x a x b y a x a x a x b y a x a x a x b y      n n z = c x + c x ++ c x max 1 1 2 2 §2 原问题与对偶问题 对于一般的线性规划问题

类似于前面的资源定价问题，每一个约束条件对应一个“对偶变量”，它就相当于给各资源的单位定价。于是我们有如下的对偶规划：min W = biyi +by2 +...+bmymanyi+a2iy2 +...+amiym≥ci1→xi-a12J +a22y2 +...+am2ym ≥C2→X2ainy +a2ny2 +...+amnym ≥Cn→xnJ1,Y2,"",ym ≥02025/4/510

2025/4/5 10 类似于前面的资源定价问题，每一个约束条件对应一个“对偶变量”，它就 相当于给各资源的单位定价。于是我们有如下的对偶规划：           + + +  → + + +  → + + +  → 1 , 2 , , 0 1 1 2 2 1 2 1 2 2 2 2 2 2 1 1 1 2 1 2 1 1 1 m n n m n m n n m m m m y y y a y a y a y c x a y a y a y c x a y a y a y c x      m m W = b y +b y ++b y min 1 1 2 2

对偶问题与原问题的关系：目标函数：MIN目标函数：MAXmin W =b'Ymax Z =CX对原偶问(---约束条件：n个约束约束条件：m个约束何题AX≤bA'YZCT题变量：n个变量变量：m个变量X≥0Y≥0这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问是不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题2025/4/511

2025/4/5 11 对偶问题与原问题的关系： 原 问 题 对 偶 问 题 目标函数：MAX 约束条件：m个约束 变量 ： n个变量 目标函数：MIN AX  b X  0 约束条件：n个约束 变量 ： m个变量 max Z =CX W b Y T min = T T A Y  C Y  0 这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题 不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的 原问题，再写出对偶问题