设生产三种产品各为x1, x2, x3公斤，总利 为Z元。于是得 max Z 3x1 5x2 4x3
2x1 3x2 1500
s.t. 2x2 4x3 800
3x1 2x2 5x3 2000 x1, x2 , x3 0
8
对偶问题
设出售材料的定价为每单位 yi 元，
* 获利为 W 元
12
原问题（或对偶问题） 对偶问题（或原问题）
目标函数 MaxZ
目标函数 MinW
约束条件数：m个 第i个约束条件类型为“≤” 第i个约束条件类型为“≥” 第i个约束条件类型为“=”
对偶变量数：m个 第i个变量≥0 第i个变量≤0 第i个变量是自由变量
决策变量数：n个 第j个变量≥0 第j个变量≤0 第j个变量是自由变量
（3）对偶问题的解正是原问题的最优表中松驰变 量 在检验数行中的数。反之，原问题的解正是对 偶问题的最优表中松驰变量 在检验数行中的数。
（4）对偶问题的解yi称为资源的影子价格。
26
原问题
对偶问题
每次迭代，检验数行的数
基解（最优表中是最优解
------影子价格）
松馳变量
决策变量
决策变量
松馳变量
基变量
对偶问题 (min)
技术系数矩阵 AT
右端项 b
价值系数 C
对偶变量 yi 0
对偶变量 yi 0
对偶变量 yi 不限
第 j 行约束条件为 型
第 j 行约束条件为 型
第 j 行约束条件为 = 型
• 约束条件的类型与非负条件对偶 • 非标准的约束条件类型对应非正常的非负条件 • 对偶变换是一一对应的
非基变量
非基变量
基变量
目标函数值 =
目标函数值
练习P.30例14
27
2.4.5 对偶变量的经济意义和影子价格
1、影子价格（Shadow Pyice)：对资源在生产中做出的贡献而 做出的评价。它不是市场价格。资源的市场价格是已知的， 而影子价格有赖于资源的利用情况，是未知的。
对偶变量的经济意义就是影子价格.
s.t5 y1 2 y2 y3 y5 1
y1,
y2，y3 ,
y4 ,
y5
0
23
约束条件两端乘以“-1”得
max w 15y1 24y2 5y3 0y4 0y5
6 y2 y3 y4 2
s.t 5y1 2 y2 y3 y5 1
y1,
y2，y3
,
y4
,
y5
0
24
cj
约束条件数：n
第i个约束条件类型为“≥”
第i个约束条件类型为“≤”
第i个约束条件类型为“=”
13
课堂练习：写出下面线性规划的对偶规划：
MinZ 4x1 2x2 3x3
4x1 5x2 6x3 7
s.t.182x1x191x32 x2
10x3 14ຫໍສະໝຸດ 11x1 0, x2符号不限, x3 0
4、对偶定理：若两个互为对偶问题之一有最优解，则 另一个必有最优解，且目标函数值相等。
5、互补松弛性定理： X* 、Y*分别是原问题和对偶问题的
可行解，则 和Y*XL=0
X*
、Y*是最优解的充分必要条件是X*YS
=0
6、解的对应定理：原问题的单纯形表的检验数行对应
其对偶问题的一个基解.
由解的对应定理可知，当在检验数行得到对偶问题的 解可行时，原问题已达到最优解。
21
出基原则：小于0的 bi中最小者（绝对值最大者）所对应的行变
量。即在所有bi <0中，
原b问r 题m的iin进b对基i 应原的则变：量j yr出CB基B，-1Pyj r-所C在j 中行0最为小主对元应行的。列变量。
（4）确定“进基”变量
若主元行中没有负元素，可以证明问题没有可行解，计算结束。
2
对偶问题?
• 任何线性规划问题都有其对偶问题 • 对偶问题有其明显的经济含义
假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？
3
原问题—简单的生产计划问题
某工厂生产甲、乙两种产品，单位产品 利润、耗工耗料及工料限额为下表
产品 甲
项目
材料
2
工时
3
利润(元)/件 4
乙 限额
3
24
第4章 主要内容：
• 对偶规划 • 对偶理论 • 对偶单纯形算法
1
4.1对偶问题的提出
现从另一个角度来讨论，假定工厂考虑不 安排生产，而是出售原材料，出租工时或转产 新产品等。问如何定价，可使工厂获利不低于 安排生产所获得的收益，且又能使这些定价具 有竞争力？
设出售原料的定价为毎公斤y1元，出租工时 的定价为毎工时y2元.从工厂考虑，这些定价下 的获利不应低于安排生产所获得的收益。否则 工厂宁可生产，而不出售或出租或转产等,由此 考虑出售或出租或转产的数学模型.
16
2.4.3 对偶问题的基本性质定理
1、对称性定理：对偶问题的对偶是原问题。
2、弱对偶定理：若X(0)是原问题的可行解, Y(0)是对偶问 题的可行解,则有CX(0) ≤ Y(0)b.
3、最优性定理：若X(0)是原问题的可行解, Y(0)是对偶问 题的可行解,且有CX(0) = Y(0)b则 X(0) 、Y(0)分别是原问题和 对偶问题的最优解。
0 J
1/6 -1/6 0
[-2/3] -1/3 1
1 40
0 -1/4 1/4
1 1/2 -3/2
w
-17/2 15/2 0
0 2/7 3/2 25
原问题的最优解为(0,1/4,1/2),最优值为17/2
由上例得结论：
（1）当约束条件为“≥”时，不必引进人工变量， 使计算简化。
（2）由对偶问题的性质知道：用单纯形法求解L.P 问题时，每一次迭代可得一个基解，这时检验数 行的数是对偶问题的一个基解。原问题的松驰变 量对应着对偶问题的决策变量，对偶问题的松驰 变量对应着原问题的决策变量。在一个问题中是 基变量，则在另一个问题中就是非基变量 ，反之 亦然。
y1符号不限, y2 0, y3 0 y1符号不限, y2 0, y3 0
√
×
（原问题是极小化问题，因此应从原始对偶
表的右边往左边查！）
15
（二）非对称形式的对偶问题 （1） 如果原问题约束中包含等式约束，如AX=b 等价于
AX b AX b
(2)如果x j 0,可用xj x j 0代替。 （3）如果x j取值无约束，可用x j xj xj代替 （xj，xj 0）
每迭代一次，就使目标函数值增大一次， 当问题取得最优解时，目标函数达到最大 值。
对偶单纯形法特点：将单纯形法应用于对偶 问题的计算，在保持对偶问题有可行解的 基础上，每迭代一次，就使目标函数值减 少一次，当问题得到最优解时，目标函数 取到最小值。
20
2、对偶单纯形法的计算步骤 （1）把对偶问题化为标准形，但允许主约束条件右
CB YB b
0 y4 -2
0 y5 -1
w
0
-24 y2 1/3 0 y5 -1/3
w -8
-24 y2 1/4 -5 y3 1/2
-15 y1 0 -5 15
0 -5 15 -5/4 15/2
-24 y2 [-6]
-2 24
1 0 0 1 0
-5 0 y3 y4
0
y5
-1 1 0
-1 0 1
5
0
,2xx22
26
0
目标函数 约束条件
“s.t.”:Subject to
线性规划
5
新问题—简单的生产计划问题
设出售原料的定价为毎公斤y1元，出租工时的 定价为毎工时 y元2 .
min w 24 y1 26 y2
s.t. 2 y1 3y2 4
3y1 2 y2 3 y1, y2 0.
6
2
26
3
如何安排一天的生产计划，使企业利润最大？
4
解：设甲、乙产品的产量分 别为x1, x2 ,则
利润 Z 4x1 3x2
决策变量
限制条件：
2x1 3x2 24
3x1 2x2 26
x1 0, x2 0
数学模型： max Z 4x1 3x2
2x1 3x2 24
s.t.3xx11
min W 1500 y1 800 y2 2000 y3 2 y1 3y3 3
s.t. 3y1 2 y2 2 y3 5
4 y2 5 y3 4 y1, y2 , y3 0
定义 2.4.1：称上述的两问题之一 为原问题，则另一问题称为对偶问题， 两者互为对偶。
9
原问题与对偶问题的关系
17
对偶定理
是揭示原始问题的解与对偶问 题的解之间重要关系的一系列定理。
18
2.4.4 对偶单纯形法
什麽是对偶单纯形法？ 对偶单纯形法是应用对偶原理求解原始 线性规划的一种方法——在原始问题的单 纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！
19
2.4.4 对偶单纯形法
1、两种方法的特点 单纯形法特点：在保持基可行解的情况下，
• （一）对称形式的对偶问题 • 比较上述的两个互为对偶问题：
max Z 3x1 5x2 4x3
2x1 3x2 1500 s.t. 2x2 4x3 800
3x1 2x2 5x3 2000 x1, x2 , x3 0
min W 1500y1 800y2 2000y3 2 y1 3y3 3
显然：对称形式的对偶问题，若已知其中 一个问题，立即就可以写出相应的对偶问 题。
11
表2.13 对偶变换的规则
原问题 (max)
技术系数矩阵 A 价值系数 C 右端项 b