安徽大学：《运筹学》课程理论教案（PPT讲稿）第二章 线性规划的对偶理论

第二章 线性规划的对偶理论和炅敏度分析 线性规划的对偶理论 递减成本和对偶价格 灵敏度分析 3

3 第二章 线性规划的对偶理论和灵敏度分析 线性规划的对偶理论 递减成本和对偶价格 灵敏度分析

第一节 线性规划的树偶问题 一、对偶问题的提出 无论从理论或实践角度，对偶问题是线性规 划中的一个最重要和有趣的概念。支持对偶理论 的基本思想是，每一个线性规划问题都存在一个 与其对应的对偶的问题。我们在求出一个线性规 划问题最优解的同时，也给出了另一线性规划问 题的最优解。下面先通过范例看对偶问题的经济 意义 4

4 第一节 线性规划的对偶问题 一、对偶问题的提出 无论从理论或实践角度，对偶问题是线性规 划中的一个最重要和有趣的概念。支持对偶理论 的基本思想是，每一个线性规划问题都存在一个 与其对应的对偶的问题。我们在求出一个线性规 划问题最优解的同时，也给出了另一线性规划问 题的最优解。下面先通过范例看对偶问题的经济 意义

第一节 线性规划的树偶问题 例1在第一章的范例中，利用三个车间资源 生产两种产品时，其线性规划问题为： max Z=3x+5x2 ≤ 8 2X2 ≤ 12 (2-1) 3 X1+ 4X2 ≤ 36 X1, X2 ≥ 0 5

5 例1 在第一章的范例中，利用三个车间资源 生产两种产品时，其线性规划问题为：         +    = + x x 0 3 x 4 x 36 2 x 12 x 8 max 3 5 1 2 1 2 2 1 1 2 ， Z x x (2-1) 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 现在从另一角度提出问题。假定有另一公司 想租用前进厂三个车间的资源，它至少应付出多 大代价，才能使前进厂愿意放弃生产活动，出让 三个车间的资源。显然前进厂愿出让自己资源的 条件是：出让代价应不低于用同等数量资源由自 已组织生产活动时获取的盈利。分别用y1、y2和y3 代表车间A、B和C单位时间h)的出让代价。 6

6 现在从另一角度提出问题。假定有另一公司 想租用前进厂三个车间的资源，它至少应付出多 大代价，才能使前进厂愿意放弃生产活动，出让 三个车间的资源。显然前进厂愿出让自己资源的 条件是：出让代价应不低于用同等数量资源由自 己组织生产活动时获取的盈利。分别用yl、y2和y3 代表车间A、B和C单位时间(h)的出让代价。 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 因前进厂用A车间1小时和C车间3小时可生产 一件甲产品，盈利3元；用B车间2小时和C车间4 小时可生产一件乙产品，盈利5元。由此y1,y2和 y3的取值应满足： y1+3y3≥3 2y2t4y3≥5 又另一公司希望用最小的代价把前进厂的全 部资源收买过来。 7

7 因前进厂用A车间1小时和C车间3小时可生产 一件甲产品，盈利3元；用B车间2小时和C车间4 小时可生产一件乙产品，盈利5元。由此y1，y2和 y3的取值应满足： y1 +3y3≥3 2y2 +4y3≥5 又另一公司希望用最小的代价把前进厂的全 部资源收买过来。 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 故有 min Z 8y1+12y2+36y3 显然y:≥0(i=1,2,3),这样就得到了下面 的(2-2)式。 minZ=8y1+12y2+36y3 y1+ 3y3≥3 (2-2) 2y2+4y3≥5 1,y2,y3≥0 8

8 故有 min Z = 8y1 +12y2 +36y3 显然yi≥0 (i=1，2，3)，这样就得到了下面 的（2-2）式。       +  +  = + + 0 2 4 5 3 3 min 8 12 36 1 2 3 2 3 1 3 1 2 3 y y y y y y y Z y y y ， ， (2-2) 第一节 线性规划的对偶问题

第一节 线性规划的树偶问题 对于上述(2-1)和(2-2)两个线性规划问题 通常称前者为原问题，后者是前者的对偶问题。 当然，我们也可以称(2-2)式为原问题，而称 (2-1)式为对偶问题 如果我们知道了线性规划的原问题，那么如 何写出它的对偶问题呢？这并不是一件很容易的 事情。 9

9 对于上述(2-1)和(2-2)两个线性规划问题， 通常称前者为原问题，后者是前者的对偶问题。 当然，我们也可以称（2-2）式为原问题，而称 （2-1）式为对偶问题。 如果我们知道了线性规划的原问题，那么如 何写出它的对偶问题呢？这并不是一件很容易的 事情。 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 二、对称形式下对偶问题的一般形式 我们定义满足下列条件的线性规划问题称为 具有对称形式：其变量均具有非负约束，其约束 条件当目标函数求极大时均取“≤”号，当目标函 数求极小时均取“≥”号 对称形式下线性规划原问题的一般形式为： 10

10 二、对称形式下对偶问题的一般形式 我们定义满足下列条件的线性规划问题称为 具有对称形式：其变量均具有非负约束，其约束 条件当目标函数求极大时均取“≤”号，当目标函 数求极小时均取“≥”号。 对称形式下线性规划原问题的一般形式为： 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 maxZ=cx+Cx2++cnn 011X1+12X2+.+1nXn ≤b1 21X1+022x2+.+L2mXm ≤b2 (2-3) amix+am22++am xn ≤bm X1X22,Xm ≥0 11

11           + + +  + + +  + + +  = + + + 0 max 1 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 2 2 n m m mn n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b Z c x c x c x ， ，，      (2-3) 第一节 线性规划的对偶问题

第一节 线性规划的对偶问题 用y1（i=1,2,.,m)代表第i种资源的估 价，则其对偶问题的一般形式为： minw =biy+b2y2 ++bmym a1y1+a21y2++amIym 2C1 012Jy1+422Jy2++0m2Jym 2C2 (2-4) ainy+a2ny2++am ym Cn Jy19Jy2,.,ym ≥0 12

12 (2-4)           + + +  + + +  + + +  = + + + 0 min 1 2 1 1 2 2 1 2 1 2 2 2 2 2 1 1 1 2 1 2 1 1 1 1 2 2 m n n mn m n m m m m m m y y y a y a y a y c a y a y a y c a y a y a y c W b y b y b y ， ，，      用yi（i=1，2，.，m）代表第i种资源的估 价，则其对偶问题的一般形式为： 第一节 线性规划的对偶问题