学好运筹学必备

第八节 线性规划的对偶理论

学好运筹学必备

一、对偶问题的提出二、对偶问题与原问题之间的转化

三、对偶问题的基本性质四、影子价值——对偶问题的经济意义

学好运筹学必备

一、对偶问题的提出例1:常山机器厂生产I,II两种产品，都需分 别在A、B、C三种不同设备上加工，其中生 产I需占用各设备的时间是2h,4h,0h,生产 II需占用的时间是2h,0h,5h,已知设备计 划期的生产能力分别是12h,16h,15h,且 知生产一件I的利润是2元，生产一件II的利润 是3元，问两种产品各生产多少件，总的利润 收入最大？

学好运筹学必备

解：设生产产品I为x1件，生产产品II为x2件。 maxZ=2x1+3x2 S.T 2x1+2x2 ≤12 4x1 ≤16 5x2 ≤15

x1,x2均≥0

学好运筹学必备

例2:四海机器厂想租用常山机器厂的设备， 问对于三台设备A、B、C,常山厂愿意以每 小时多少的价钱，才可能出租？ 对常山厂：租金收入≥自己组织生产的收入 对四海厂：总租金最低 变量改变——产品——设备 设备不再是约束条件，必须从产品入手 设y1,y2,y3是A、B、C每小时的出租价格 对于产品I:每件I自行生产的收入是2元， 租金收入是2y1+3y2元。

学好运筹学必备

Minz=12y1+16y2+15y3(设备租用总收入) S.T 2y1+4y2 ≥2 2y1 + 5y3 ≥3 其中y1,y2,y3均≥0 比较一下与解1线性规划问题的不同？ 1、目标函数 2、变量 3、约束条件

学好运筹学必备

矩阵形式比较： 解1:MaxZ=CX AX ≤b X ≥0 解2:minW=b ` Y A ` Y ≥C` Y ≥0

学好运筹学必备

二、原问题与对偶问题之间的转化1、目标函数 MAX——Min 2、约束条件——变量 约束条件n个——变量n个 约束条件≥0 ——变量≤ 0 约束条件≤ 0 ——变量 ≥ 0 约束条件=0——变量无约束 要点：max为反向关系(约束条件——变量)

学好运筹学必备

二、原问题与对偶问题之间的转化3、变量——约束条件 变量m个——约束条件m个 变量≥0——约束条件≥ 0 变量≤ 0 ——约束条件≤ 0 变量无约束——约束条件=0 4、目标函数中变量的系数C为对偶问题中约 束条件的右端常数项b,个数对等变动。

学好运筹学必备

二、原问题与对偶问题之间的转化记忆要点： 1、把握“三要素”,目标函数、约束 条件——变量、C-b的转化。 2、把握重点——变量与约束条件的关系。 (1)约束条件=0的情况，变量无约束。 (2)在约束条件≠0时候，看原问题目标函数。 1)max:约束条件——变量，反向；变量—— 约束条件，正向。(反正) 2)min:约束条件——变量，正向；变量—— 约束条件，反向。(正反)

学好运筹学必备

二、原问题与对偶问题之间的转化记忆宝典： 1、Max——Min 2、C ——b3、无约束等于0,个数m变n。 4、max就反正，min就正反。(约束条件—— 变量)

学好运筹学必备

例3: 写出下列问题的对偶问题： minz=7x1+4x2-3x3 S.T -4x1+2x2-6x3 ≤24 -

3x1-6x2-4x3 ≥15 5x2+3x3=30 其中，x1 ≤0,x2无约束，x3 ≥0

学好运筹学必备

Maxz=24y1+15y2+30y3 S.T -4y1-3y2 ≥7 2y1-6y2+5y3 =4 -6y1-4y2+3y3 ≤-3 y1 ≤0,y2 ≥0,y3取值无约束。

学好运筹学必备

三、对偶问题的基本性质(一)对称性。 对偶问题的对偶问题是原问题。 (类似于“负负得正”) 例4 写出对偶问题的对偶问题。 Minw=12y1+16y2+15y3 2y1+4y2 ≥2 2y1+5y3 ≥3 y1,y2,y3 ≥0

学好运筹学必备

maxZ=2x1+3x2 2x1+2x2 ≤12 4x1 ≤16 5x2 ≤15 x1,x2 ≥0

学好运筹学必备

(二)若原问题为(弱对偶性定理) maxZ=CX AX ≤b X ≥0 其对偶问题为 Minw=Yb YA ≥C Y ≥0 若X为原问题任一可行解，Y为对偶问题任一 可行解，则必有CX ≤Yb