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

第二章线性规划的对偶理论(Dual Linear Programming, DLP)原问题与对偶问题对偶问题的基本性质影子价格对偶单纯形法灵敏度分析参数线性规划2025/4/5

2025/4/5 2 第二章 线性规划的对偶理论 ( Dual Linear Programming, DLP) ◼ 原问题与对偶问题 ◼ 对偶问题的基本性质 ◼ 影子价格 ◼ 对偶单纯形法 ◼ 灵敏度分析 ◼ 参数线性规划

81对偶问题的提出线性规划单纯形法的矩阵描述设有线性规划问题的标准形式max z = CX[AX =bA=(B,NI)将系数矩阵表示成：s.tX≥0初始解非基变量基变量BNI初始单纯形表Clbaj0→ON基可行解基变量非基变量初等行变换后CBN'b'B-110a_→On'-yi..-ym初始表中是I的位置，经变换后成为B-12025/4/53

2025/4/5 3 §1 对偶问题的提出 一、 线性规划单纯形法的矩阵描述 设有线性规划问题的标准形式     = = 0 . max X AX b st z CX 将系数矩阵表示成： A = (B,N I) 初始单纯形表 初始解 非基变量 基变量 0 b B N I  j →  N 基可行解 基变量 非基变量 0 初等行变换后 b −1 B N I  j →  N m − y .,−y 1, CI CB 初始表中是I 的位置，经变换后成为 −1 B

其中 Y=(yi,y2.. ym)-Y=0-C,B-1Y=C,B-1记则（αn"=C-C,B-"N=C-YNb'= B-'b;N'=B-'N,或 P'=B-"P例：书P36例10，验证上述公式。上述公式对于灵敏度分析很有帮助。2025/4/5

2025/4/5 4 其中 ( , ,., ) 1 2 m Y = y y y 1 0 − −Y = −CB B 记 −1 Y = CB B 则 N = CN −CB B N = CN −YN −  1  例：书 P36 例10，验证上述公式。 N B N Pj B Pj 1 1 , − − ;  = 或  = 1 b B b −  = 上述公式对于灵敏度分析很有帮助

对偶问题的提出二设有原问题例 甲方生产计划问题：乙方租借设备：1II能力22设备A12甲方以何种价格将设备A、B、设备B4016C租借给乙方比较合理？请为设备C0515其定价。利润23I，Ⅱ各生产多少,可获最大利润?解：假设A、B、C的单位租金分别为 Ji,2,Y3思路：就甲方而言，租金收入应不低于将设备用于自已生产时的利润。2025/4/5

2025/4/5 5 例 甲方生产计划问题： Ⅰ Ⅱ 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 Ⅰ，Ⅱ各生产多少, 可获最大利润? 二、 对偶问题的提出 设有原问题 乙方租借设备： 甲方以何种价格将设备A、B、 C租借给乙方比较合理？请为 其定价。 解： 假设A、B、C的单位租金 分别为 y1 , y2 , y3 。 思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润

所以：生产产品I的资源用于出租时，租金收入应满足：2y +4y, ≥2类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：2y +5y, ≥3总的租金收入：12yi+16y2+15y3而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：min W =12y +16y2 +15y3≥22yi +4y2s.t2y1+5y,≥3Ji,y2, y, > 02025/4/5

2025/4/5 6 而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好， 这样双方才可能达成协议。 于是得到下述的线性规划模型： 所以：生产产品Ⅰ的资源用于出租时，租金收入应满足： 2y1 + 4y2  2 类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足： 2y1 + 5y3  3 总的租金收入： 12 1 16 2 15 3 y + y + y min 12 1 16 2 15 3 W = y + y + y s.t 2y1 + 4y2  2 , , 0 2 5 3 1 2 3 1 3  +  y y y y y

原问题对偶问题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 这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题 不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的 原问题，再写出对偶问题