-x1+x2-3x3≤0
12
OR:SM
• ③转换成对称型
max Z ( x) 0 x1 2 x2 5x3
Y1
x1 0 x2 x3 2
Y2 Y/3
s.t.
2 x1 x2 x1 x2 3
6 x3 x3 0
6
y//3
x1
x2
3x3
0
x1, x2 , x3 0
（2）写出相应的对偶问题（4个约束，分别对应4个对偶变量 y1、y2、y/3、y//3）
买卖双方开始对资源的出让价格问题进行磋商，希望寻找一
个双方都认为比较满意的合理价格。
• 分析：设A、B、C三种材料的单价分别为y1、y2、y3.
•
对于卖方来说，生产单位甲产品所获收益为4万元，为保
证其总收入不少于405/2万元，则将生产单位甲产品所需资源
转让出去，该企业的收入不能少于4万元。故y1、y2、y3必须
max Z (x) CX minW ( y) Yb
AX b
s.t.
X
0
YA C s.t.Y 0
• 其中Y=（y1,y2,…,ym）,其它同前。
• 3.1.3 一般问题的对偶问题——非对称型对偶问题
• • 线性规划有时以非对称型出现，那么如何从原始问题写出
它的对偶问题呢？
11
OR:SM
• 例1 写出下列线性规划的对偶问题
2
OR:SM
§3-1 线性规划的对偶理论
•
每一个线性规划问题都有一个与之相伴随的另一个问题。
这两个问题：一是，在数学模型上有着对应关系；二是，从
一个问题的最优解完全可以得出另一个问题最优解的全部信
息。
• 3.1.1 问题的提出
•
例1 引入一个资源价格问题。
3
OR:SM
类似于第2章例1的生产计划问题。某企业生产甲、乙两种 产品，需消耗A、B、C三种材料。据市场分析，单位甲、 乙产品的销售收益分别为4万元和5万元。单位甲、乙产品 对材料的消耗量及材料的供应量如表3.1所示。
max Z (x) c1x1 c2 x2 L cn xn
Y1
a11x1 a12 x2 L a1n xn b1
Y2 …
s.t.
La21Lx1
L
a22 x2 L LLLL
a2n xn LL
b2
ym
am1x1 am2 x2 L amn xn bm
x1, x2 ,L , xn 0
•
综上所述，资源价格问题的数学模型可描述为：
minW ( y) 45y1 80 y2 90 y3
y1 2 y2 y3 4
s.t.
y1
y2
3 y3
5
y1, y2 , y3 0
(3 2)
• 上述两个模型（3-1）和（3-2）是对同一问题的两种不 同考虑的数学描述，其间有着一定的内在联系，将逐一剖 析。
始问题，则（3-2）称为对偶问题。
8
OR:SM
• 3.1.2 对称型线性规划问题——对称型对偶问题
•
• 每一个线性规划问题都必然有与之相伴随的对偶问题 存在。先讨论对称型对偶问题；对于非对称型对偶问题， 可以先转化为对称型，然后再进行分析，也可以直接从 非对称型进行分析。
• 对称型线性规划问题数学模型的一般形式为
原问题：应如何制定生产计划，使总收益为最大。
表3.1
产品材料
甲
乙
供应量
A
1
1
45
B
2
1
80
C
1
3
90
收益
4万元/单甲
5万元/单乙
4
OR:SM
设计划安排：x1为甲产品的产量， x2为乙产品的产量。（决策变量）
则，该问题的数学模型为：
max Z (x) 4x1 5x2
x1 x2 45
s.t.2x1x1 3xx22
7
OR:SM
• 首先，分析这两个模型之间的对应关系：
• （1）一个问题的目标函数为极大化，约束条件为“≤”类 型，另一个问题的目标为极小化，约束条件为“≥”类型；
• （2）一个问题的变量个数等于另一个问题的约束条件个数； • （3）一个问题的右端常数（约束系数）是另一个问题的目
标函数的系数（成本系数）； • （4）两个问题的系数矩阵互为转置。 • 我们把这种对应关系称为对偶关系。如果把（3-1）称为原
(3 3)
9
OR:SM
• 这种模型的特点是：
•
（1）目标函数是最大化类型(或是最小化类型)；
• （2）所有约束条件都是“≤”型（或都是“≥”型）；
• （3）所有决策变量都是始问题，根据原始与对偶问题
的对应关系可得（3-3）的对偶问题为
minW ( y) b1 y1 b2 y2 L bm ym
a11 y1 a21 y2 L am1 ym c1
s.t. La12Ly1L
a22 y2 L LLLL
L
am2 ym L
c2
a1n y1 a2n y2 L amn ym cn
y1, y2 ,L , ym 0
(3 4)
10
OR:SM
• 用矩阵表示的原始问题（3-3）和对偶问题（3-4）为
80 90
x1, x2 0
(3 1)
运用单纯形法，可求得其最优解为：
x1 45 / 2, x2 45 / 2 Z (x) 405 / 2
5
OR:SM
• 新问题：现在从另一角度来讨论这个问题。
•
假设该企业经过市场预测，准备进行转产，且把现有三
种材料进行转让，也恰好有一个制造商急需这批材料。于是
满足约束条件： y1+2y2+y3≥4
•
同样，将生产单位乙产品所需的资源转让出去，其收入
不能少于生产单位乙产品的收益5万元，所以y1、y2、y3还必
须满足约束条件： y1+y2+3y3≥5
6
OR:SM
•
对于买方来说，他希望在满足上述约束条件下使总的
支出 • 达到最小。
W（y） =45y1+80y2+90y3
《管理运筹学》
第3章
李存芳 博士/教授/硕士生导师
研究领域：战略管理、组织行为、运营管理 讲授课程：管理运筹学、管理系统工程、运营管理
经济学 单 位：江苏师范大学商学院 物流管理系 E-mail：licf66@
第 3 章 线性规划的对偶问题
内S容ub 提titl要e
第一节 线性规划的对偶理论 第二节 对偶单纯形法
max Z ( x) 2x2 5x3
x1 x3 2 s.t. 2x1x1 x2x23x63x306
x1, x2 , x3 0
解：（1）首先把上述非对称型问题化为对称型问题。
①在第一个约束条件的两边同×（-1）
②把第三个约束方程分解成两个
x1-x2+3x3≤0
和
x1-x2+3x3≥0
再将后一个两边同×（-1）改写成