第二章：线性规划专题.ppt

文档介绍：第二章线性规划专题
对偶规划
灵敏度分析
运输问题与表上作业法
1
对偶规划
一、对偶问题的提出
设备台时价
y1
y2
y3
利润
(元/吨)
设备
产品
A
B
C
甲(x1吨)
3
5
9
70
乙(x2吨)
9
5
3
30
限制工时
540
450
720
原问题:生产计划问题是一个在有限资源的条件下,求使利润最大的生产计划安排问题,其数学模型为:
Max Z =70x1+30x2
. 3x1 + 9x2 ≤ 540
5x1 + 5x2 ≤ 450 最优解为:X* =(75, 15) T
9x1 + 3x2 ≤ 720 Z* = 5700
x1 ,x2 ≥0
现从另一角度考虑此问题。假设有客户提出要求,要租赁工厂的设备工时,为其加工生产别的产品,由客户支付设备工时费,此时工厂应考虑如何为每种资源定价,同样使其获得的利润最大?
2
解: (1)决策变量:设y1 , y2, y3 分别表示出租设备A, B, C的单位工时租金。
(3)约束条件: 工厂决策者考虑:
①出租设备应不少于自己生产产品的获利,否则不如自己生产。因此,有:
3y1 + 5y2 + 9y3 ≥ 70
9y1 + 5y2 + 3y3 ≥ 30
②价格应尽量低,否则没有竞争力(此价格可成为与客户谈判的底价)。
租赁者考虑:希望价格越低越好,否则另找他人。
于是,能够使双方共同接受的是:
Min D =540y1+450y2+720y3
. 3y1 + 5y2 + 9y3 ≥ 70
9y1 + 5y2 + 3y3 ≥ 30
y1 , y2 , y3 ≥ 0
上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的,且是同一个问题从不同角度考虑所产生的,两者密切相关。因此,称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。
(2)目标函数:此时工厂的总收入为W= 540y1+450y2+720y3,这也是租赁方需要付出的成本。在这个问题中,企业不生产,将自己的资源出租,这时起决定作用的是租赁方,因此,此时的目标函数为:
Min W= 540y1+450y2+720y3
Max Z =70x1+30x2
. 3x1 + 9x2 ≤ 540
5x1 + 5x2 ≤ 450
9x1 + 3x2 ≤ 720
x1 ,x2 ≥0
3
二、对偶问题数模之间的关系
1、数模的标准型:凡具备以下两组条件之一的问题都叫标准型对偶问题。
①目标为Max型;
约束条件均为”≤”型;
变量均为非负。
②目标为Min型;
约束条件均为”≥”型;
变量均为非负。
Max Z = CX
. AX ≤ b
X≥0
Min D = bTY
. ATY ≥ CT
Y≥0
例2-1:求下列数模的对偶数模
Max Z = -x1+2x2
. 3x1 + 4x2 ≤ 12
2x1 - x2 ≥ 2
x1 , x2 ≥ 0
解:数模标准化得
Max Z = -x1+2x2
3x1 + 4x2 ≤ 12
. -2x1 + x2 ≤-2
x1 , x2 ≥ 0
对偶数模为:
Min D = 12y1 - 2y2
3y1 - 2y2 ≥-1
. 4y1 + y2 ≥ 2
y1 , y2 ≥ 0
4
例2-2:求下列数模的对偶数模
Max Z = x1 - x2 + 2 x3
. 5x1 + x2 + 8x3 = 10
x1 , x2 , x3 ≥ 0
对偶数模为:
Min D = 10y1 - 10y2
5y1 - 5y2 ≥ 1
. y1 - y2 ≥-1
8y1 - 8y2 ≥ 2
y1 , y2 ≥ 0
解:数模标准化得:
Max Z = x1 - x2 + 2 x3
5x1 + x2 + 8x3 ≤ 10
. -5x1 - x2 - 8x3 ≤-10
x1 , x2 , x3 ≥ 0
Min D = 10(y1 - y2)
5(y1 - y2) ≥ 1
. y1 - y2 ≥-1
8(y1 - y2) ≥ 2
y1 , y2 ≥ 0
令 y1 - y2 = y 得:
Min D = 10 y
5y ≥ 1
. y ≥-1
8y ≥ 2
y 为自由变量
Min D = 10 y
. (5,1,8) y ≥(1,-1,2)T
y 为自由变量
结论:若