运筹学基础对偶线性规划.ppt

运筹学基础对偶线性规划
第1页，本讲稿共37页
一、对偶线性规划问题
某工厂计划安排生产Ⅰ、Ⅱ两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：
【例
1
m
y
y
y
y
=
上述的对偶模型都称作为对称型对偶模型。
而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的，如：
(P) maxZ= cx
. Ax =b
x≥0
. yA
y
≥
c
≥
0
(D) min S= yb
. yA≥c
y为自由变量
(D) minS= yb
原问题与对偶问题的矩阵形式
问题：如何由原模型写出对偶模型？其规律是什么?
第9页，本讲稿共37页
三、原问题与对偶问题的对应关系
当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。
下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。
原问题线性规划模型
对偶线性规划模型
第10页，本讲稿共37页
原问题为maxZ的线性规划问题对偶关系表
原问题（或对偶问题）
对偶问题（或原问题）
目标函数最大化
(maxZ)
n
个变量
m
个约束
约束条件限定向量（右边项）
目标函数价值向量（系数）
≥
0
变量
≤
0
≥
无限制
约束
≤
＝
目标函数最小化（
minS
）
n
个约束
m
个变量
目标函数价值向量（系数）
约束条件限定向量（右边项）
≥
约束
≤
≤0
＝
变量
≥
0
无限制
同号
反号
第11页，本讲稿共37页
原问题 对偶问题
目标函数max 目标函数min
原问题(maxZ)与对偶之关系：
原问题(maxZ)口诀: 约束决定变量是反号
原问题(maxZ)口诀: 变量决定约束是同号
第12页，本讲稿共37页
解：
由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3
（还可依对偶问题写出原问题）
例1
写出下列问题的对偶问题：
变量决定约束是同号,约束决定变量是反号
max Z=2x1+x2
5x2 ≤ 15
6x1 +2x2 ≤ 24
x1+x2 ≤ 5
　　　 x1 , x2 ≥ 0
min w=15y1+24y2+5y3
6y2+y3 ≥ 2
.
y1 , y2 , y3 ≥ 0
5y1 +2y2 +y3 ≥1
第13页，本讲稿共37页
原问题为minS的线性规划问题对偶关系表
原问题（或对偶问题）
对偶问题（或原问题）
目标函数最小化
(minS)
n
个变量
m
个约束
约束条件限定向量（右边项）
目标函数价值向量
≥
0
变量
≤
0
≥
无限制
约束
≤
＝
目标函数最大化（
maxZ
）
n
个约束
m
个变量
目标函数价值向量（系数）
约束条件限定向量
≤
约束
≥
≥ 0
＝
变量
≤ 0
无限制
同号
反号
第14页，本讲稿共37页
原问题 对偶问题
目标函数min 目标函数max
原问题(minS) 与对偶之关系：
原问题(minS)口诀: 约束决定变量是同号
原问题(minS)口诀: 变量决定约束是反号
第15页，本讲稿共37页
解：
由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3
3
2
1
3
4
max
y
y
y
Z
+
-
=
.
1
2
3
2
1
£
-
-
y
y
2y
-3
3
2
1
£
+
-
y