哈工大运筹学课件整数规划.ppt

哈工大运筹学课件整数规划
一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？
货物
体积(米3/箱)
则
i=1,2
x1 4＋(1-y1) M x2 1－(1-y1) M
M——充分大正数
x1 4－(1-y2) M x2 3＋(1-y2) M
y1＋y2=1 y1，y2=0或1
2006/08
14
5. 分段函数线性表示
设有 f(xj)=
Kj+cjxj 当xj>0
0 当xj=0，
将min f (xj) 表示成线性函数。
设 yj=
1
0
当xj>0
当xj=0
Min f(xj) = kjyj+cjxj st. xjyjM xj0, yj=0或1
M—非常大的正常数
则
f(xj) = kjyj+cjxj xjyjM yjxjM xj0, yj=0或1
或为：
2006/08
15
三、隐枚举法
步骤：
① 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj 4) 使目标函数按变量系数由小→大顺序排列，约束条件变 量排列的顺序要与之对应。
② 令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。
③ 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。
④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) >zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。
2006/08
16
例：求解下述 0-1规划问题：
Max z=8x1+2x2-4x3-7x4-5x5 st. 3x1+3x2+x3+2x4+3x5 4 5x1+3x2- 2x3 - x4+ x5 4 xj=0或1 (j=1,2,3,4,5)
1) 目标函数极小化:
min z=-8x1-2x2+4x3+7x4+5x5
① 化标准形：
2) 约束条件：
-3x1-3x2-x3-2x4-3x5 -4
-5x1-3x2+ 2x3 + x4- x5 -4
xj=0或1 (j=1,2,3,4,5)
2006/08
17
3) 使目标函数系数皆为正：
令 x1=1-x1 ，x2=1-x2
min z=-8+8 x1 -2+2 x2 +4x3+7x4+5x5
st. -3+3 x1 -3+3 x2 -x3-2x4-3x5 -4
-5+5 x1 -3+3 x2 + 2x3 + x4- x5 -4
x1 , x2 ,xj=0或1 (j=3,4,5)
4) 变量按顺序排列：
min z= 2 x2 +4x3 +5x5 +7x4+8 x1 -10
st. 3 x2 -x3 -3x5 -2x4 +3 x1 2
3 x2 + 2x3 - x5 + x4+5 x1 4
x1 , x2 ,xj=0或1 (j=3,4,5)
2006/08
18
求解图示：
1
2
3
4
5
6
7
8
9
10
11
z=-10
z =-8
z=-4
z=-6
z=-5
z=-1
z=1
z=-5
z=-3
z=-6
x2=1
x2=0
x3=1
x3=0
x3=1
x3=1
x5=1
x5=0
x5=1
x5=0
z=-3
√
×
×
×
×
×
2006/08
19
分配问题及匈牙利算法(Assignment Problem)
一、问题的提出和数学模型
例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。
问：如何分配，能使所需的总时间最少？
甲 乙