y1 +2y2 +y3 ≤ 3
-3y1 +y3 ≤ -5
y1 -y2 +y3＝1
y1 ≥ 0, y2 , y3 ≤ 0
对偶问题（或原问题） 目标函数最大化（ maxZ）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
≥0 变量 ≤ 0
无限制
§2.2 线性规划的对偶理论
n 个变量 m 个约束 约束条件限定向量（右边项） 目标函数价值向量
≥0 变量 ≤ 0
无限制
对偶问题（或原问题） 目标函数最大化（ maxZ）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
-2 x1
x3 3
≥ 约束 ≤
≥0 变量 ≤ 0
x1,x2,x3
＝
无限制
原问题线性规划模型 对偶线性规划模型
max f 2x1 3x2 min g 8y1 16 y2 12 y3
x1 2 x2 8 s.t.44x1xx,12x2 11620
s.t.
y1 4y2 2 2y1 4y3 3
yi 0,i 1,2,3
下列的表给出了原问题模型和模型的对应关系，这些也可以
≥ 约束 ≤
＝
≥ 约束 ≤
＝
反号
Hale Waihona Puke ≤0 变量 ≥ 0无限制
原问题(maxZ)与对偶之关系：
原问题 目标函数max
对偶问题 目标函数min
n个
变 量
无 00约束
n个 约
束
条
件
原问题(maxZ)口诀: 变量决定约束是同号
约 m个
束 条 件
m个
0
变
0
量
无约束
原问题(maxZ)口诀: 约束决定变量是反号
原问题(minS)口诀: 变量决定约束是反号
约 m个
束 条 件
m个
无 00约束
变 量
原问题(minS)口诀: 约束决定变量是同号
例2 写出下列问题的对偶问题：
Min S x1 - 3x2 4x3
s.t.
2x 1-4 x2 x3 1
- x1 3x2 2x3 -4
原问题（或对偶问题） 目标函数最小化 (minS)
工厂把所有设备台时和资源都出租和出让，其收入为：
min g 8y1 16 y2 12 y3
工厂改变策略以后的数学模型为：
min g 8y1 16y2 12y3
用户所付租金最少
s.t.
y1 4y2 2 2y1 4y3 3
yi 0, i 1,2,3
工厂获得相应利润
原模型和对偶模型既有联系又有区别
原（对偶）问题一定无界； 注:此定理可以判定解的情况
一般是：
cx≤yb
定理4 （可行解是最优解的性质） 设X*是原问题的可行解，Y*是对偶问题的可行解，当
(P) max Z= cx s.t. Ax ≤b x ≥0
(D) min S= yb s.t. yA ≥ c y ≥0
其中 y ( y1, y2 ,.., ym )
上述的对偶模型都称作为对称型对偶模型。
而在当原问题转化为标准型以后所建立的对偶模型则是非
对称型的，如：
(P) maxZ= cx
s.t. Ax =b x≥0
原问题的一般模型可定义为： 相应的对偶问题的一般模型可定义为：
maxZ c1x1 c2 x2 ... cn xn
minS b1y1b2 y2 ...bmym
s.t. a11x1 a12x2 ... a1n xn b1 s.t. a11y1 a21y2 ... am1ym c1
a21x1 a22x2 ... a2n xn b2
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
≥0 变量 ≤ 0
无限制
练习：试求下列线性规划问题的对偶问题
max Z 2x1 4x2 - 3x3
s.t.
x1 - x2 x3 10
- x1 4x2 - 3x3 -5
3x1 2x2 - 5x3 8
x1 0 ， x2 0
(D) minS= yb s.t. yA≥c y为自由变量
问题：如何由原模型写出对偶模型？其规律是什么?
三、原问题与对偶问题的对应关系
当我们讨论对偶问题时必定是指一对问题，因为没有原问 题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。 同时，原问题和对偶问题之间也并没有严格的界线，它们互为 对偶，谁都可以是原问题，谁也都可以是对偶问题。
线性规划的对偶理论包括以下几个基本定理。 定理1 （对称性定理）
即对偶问题的对偶是原问题。
定理2 （弱对偶定理） 设x和y分别是原问题和对偶问题的可行解，则必有cx≤yb，
即原问题的目标值小于对偶问题的目标值
定理3 （无界性） 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无
可行解。 若原（对偶）问题有可行解,对偶（原）问题无可行解，则
看作是一个线性规划原问题转化为对偶问题的一般规律。
原问题为maxZ的线性规划问题对偶关系表
原问题（或对偶问题）
目标函数最大化 (maxZ) n 个变量 m 个约束
约束条件限定向量（右边项） 目标函数价值向量（系数）
≥0 变量 ≤ 0
无限制
同号
对偶问题（或原问题） 目标函数最小化（ minS）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量（右边项）
变量决定约束是反号,约束决定变量是同号
解： 由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3
maxZ y1 - 4y2 3y3
s.t.
2y1- y2 - 2y3 1
- 4y13 y2
-3
y1 2y2 y3 4
y1 0 ， y2 0，y3 0
（还可依对偶问题写出原问题）
练习：试求下列线性规划问题的对偶问题
反号
对偶问题（或原问题） 目标函数最大化（ maxZ）
n 个约束 m 个变量 目标函数价值向量（系数） 约束条件限定向量
≤ 约束 ≥
＝
≥ 约束 ≤
＝
同号
≥0 变量 ≤ 0
无限制
原问题(minS) 与对偶之关系：
原问题
目标函数min
n个
变 量
无 00约束
对偶问题
目标函数max
n个约
束 条 件
第二章 线性规划的对偶理 论
§2.1 对偶线性规划问题的提出
任一线性规划问题都存在另一与之伴随的线性规划问题， 他们从不同角度对一个实际问题提出并描述，组成一对互为 对偶的线性规划问题。
一、对偶线性规划问题
【例1】 某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的
利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、 现有原材料和设备台时的定额如下表所示：
1
2
4
0
原材料B
0
4
每单位产品利润（万元）
2
3
8台时 16Kg 12Kg
▪ 改变策略后，需要考虑如何给资源定价的问题！
设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位 原材料A、B的利润.
工厂出租设备、原材料的租金要大于生产的利润才合算。
则： y1+4y2≥2，
2y1+4y3≥3
要寻找使租用者支付的租金最少的策略。
max f 2x1 3x2
min g 8y1 16 y2 12 y3
x1 2x2 8
s.t.4 x1
16 4x2 12
x1, x2 0
s.t.2yy114y2
2 4y3 3
yi 0,i 1,2,3
联系在于，它们都是关于工厂生产经营的模型,并且使用相同 的数据；
区别在于,它们所反映的实质内容是完全不同的：前者是站在 工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在 谈判对手的立场上寻求应付工厂租金最少的策略。
… … ….
a12y1 a22y2 ... am2 ym c2
………
am1x1 am2 x2 ... amnxn bm x1, x2 ,...,xn 0
a1n y1 a2n y2 ...amnym cn y1, y2,...,ym 0
原问题与对偶问题的矩阵形式
上述的原问题P和对偶问题 D还可以用矩阵形式写为：
5x2 ≤ 15 6x1 +2x2 ≤ 24
≥0 变量 ≤ 0
无限制
≥ 约束 ≤
＝
x1+x2 ≤ 5 x1 , x2 ≥ 0
≥ 约束 ≤
＝
≤0 变量 ≥ 0
无限制
变量决定约束是同号,约束决定变量是反号
解： 由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3
min w=15y1+24y2+5y3
n 个变量 m 个约束
x1 x 2 - 3x 3 x 4 5
2x1 2x 2
-x4 4
x2 x3 x4 6
约束条件限定向量（右边项） 目标函数价值向量
≥0 变量 ≤ 0
无限制
x1 0, x 2 , x 3 0, x 4无约束
≥
约束 ≤
答案： maxZ=5y1+4y2+6y3
＝
y1+2y2≥ 2
s.t.
6y2+y3 ≥ 2
5y1 +2y2 +y3 ≥1
y1 , y2 , y3 ≥ 0
（还可依对偶问题写出原问题）
原问题为minS的线性规划问题对偶关系表