下面的答案哪一个是正确的？为什麽？
MaxW 7 y1 11y 2 14 y3 4 y1 8 y 2 12 y3 4 5 y1 9 y 2 13y3 2 s.t. 6 y1 10 y 2 3 y1符号不限, y 2 0, y3 0 MaxW 7 y1 11y 2 14 y3 4 y1 8 y 2 12 y3 4 5 y1 9 y 2 13y3 2 s.t. 6 y1 10 y 2 3 y1符号不限, y 2 0, y3 0
定义
对于线性规划问题
maxZ=CX AX≤b OX≥0
(2.1)
称线性规划问题
minW=Yb YA≥ C 0 Y≥ 0
(2.2)
是式（2.1）的对偶问题，而称（2.1）为原问题。 其中：C=(c1 ,… ,cn),X=(x1 ,… ,xn)T ,A=(aij)m×n ,b=(b1 ,… ,bm)T Y=(y1 ,… ,ym) 式（2.1）与式（2.2），通常称为一对对称的对偶规划。
产品 资源 Ａ Ｂ 单件收益 ２ ４ ６ ３ ２ ４ 甲 乙 资 源 拥有量 100 120 （千元）
maxZ = 6x1
+
4x2
2x1 + 3x2 ≤100 s.t. 4x1 + 2x2 ≤ 120
x1≥0, x2 ≥0
§2.1对偶问题的提出
设: y1,y2分别表示A、B两 种资源的价格。 对于企业Ⅱ来说，希望付 出的代价越小越好，则目标函 数为： minW=100y1+120y2
第二章 线性规划的对偶理论
§2.1对偶问题的提出 §2.2原问题与对偶问题 §2.3对偶问题的基本性质 §2.4对偶解—影子价格
§2.1对偶问题的提出
例2.1 对例1.1[某企业（企 业Ⅰ）生产两种产品，需要两种原 料，有关数据见表。如何安排生产 计划可使总的收益最大。]从另一 个角度提出问题: 假设有另外一个企业（企业Ⅱ） 想把企业Ⅰ的资源买过来,它至少应 付出多大代价, 企业Ⅰ愿意放弃生产 活动,让出自己的资源. 假设你就是企业Ⅰ的经理，请问 你将如何与企业Ⅱ进行谈判？
MaxZ 2 x1 x 2 3 x1 4 x 2 15 s.t.5 x1 2 x 2 10 x , x 0 1 2
MinW 15y1 10y2
3 y1 5 y2 2
s.t
4 y1 2 y2 1
y1 , y2 0
原问题（或对偶问题）
决策变量数：n个 第j个变量≥0 第j个变量≤0 第j个变量是自由变量
价值系数
课堂练习：写出下面线性规划的对偶规划：
MinZ 4 x1 2 x 2 3 x3 4 x1 5 x 2 6 x3 7 8 x1 9 x 2 10x3 11 s.t. 12x1 13x 2 14 x1 0, x 2 符号不限, x3 0
§2.2原问题与对偶问题
MaxZ CX
（L）s.t. AX b
MinW Yb
（D） s.t.YA C
X 0
Y 0
怎样从原始问题写出其对偶问题？
按照定义；
记忆法则：
“ 上、下”交换，“左、右”换位，
不等式变号，“极大”变“极小”
写出下面线性规划的对偶问题：
对偶问题（或原问题）
目标函数 MaxZ
约束条件数：m个 第i个约束条件类型为“≤”
目标函数 MinW
对偶变量数：m个 第i个变量≥0 第i个变量≤0 第i个变量是自由变量 价值系数 约束条件数：n个 第j个约束条件类型为“≥” 第j个约束条件类型为“≤” 第j个约束条件类型为“=” 资源系数
第i个约束条件类型为“≥” 第i个约束条件类型为“=” 资源系数
产品 资源 Ａ Ｂ 单件收益 ２ ４ ６ ３ ２ ４ 甲 乙 资 源 拥有量 100 120 （千元）
但对于企业Ⅰ来说，让出资源的前提条件是，将资源卖给企业Ⅱ所 获得的收益，至少不应低于自己利用这些资源组织生产所获得的收益。 则约束条件为：
§2.1对偶问题的提出
①让出资源不应低于自 己组织生产所获得的收益。 甲产品：生产一件消耗2个 A和4个B，卖出后获得6千元收 益。将2个A和4个B卖出也不应 低于6千元收益，则有： 2y1 + 4y2
√
×
（原问题是极小化问题，因此应从原始对偶 表的右边往左边查！）
练习
min z 7 x1 4 x2 3x3
4 x1 2 x2 6 x3 24
s.t.
3x1 6 x2 4 x3 15
2 x2 6 x3 30
x1 0, x2无约束，x3 0
§2.3对偶问题的基本性质 定理1 (弱对偶定理)： 若 X, Y分别是原问题和对偶问题的可行解， 推论： 则有
≥产品 资源甲来自乙资 源 拥有量
Ａ Ｂ
单件收益
6
２ ４ ６
３ ２ ４
100 120
（千元）
同理，对于乙产品则有： 3y1 + 2y2 ≥ 4 ②变量非负限制 y1
≥
0 ， y2
≥
0
整理得：
§2.1对偶问题的提出
minW = 100y1 + 120y2 2y1 + 4y2 s.t. 3y1 + 2y2 y1
≥ ≥ ≥ ≥
maxZ
=
6x1
+
4x2
6 4 0
2x1 + 3x2 ≤100 s.t. 4x1 + 2x2 ≤ 120 x1≥0, x2 ≥0 原问题模型 原问题:企业Ⅰ生产两种产 品，需要两种原料，有关数据见 表。如何安排生产计划可使总的 收益最大.
0， y2
对偶问题模型 对偶问题:企业Ⅱ想把企 业Ⅰ的资源买过来,它至少应 付出多大代价,该企业愿意放 弃生产活动,让出自己的资源.
CX Yb
1. LP任一可行解目标函数值是DP目标函数值的下界； DP任一可行解的目标函数值是其原问题目标函数值的上界。 2. LP有可行解 ,且目标函数值无界 DP有可行解，且目标函数值无界 3. LP有可行解，DP无可行解 DP有可行解，LP无可行解 DP无可行解 LP无可行解 LP目标函数值无界； DP目标函数值无界