当前位置:文档之家› 运筹学 五章(整数规划)

运筹学 五章(整数规划)

无解
(2,2)
(11/4,9/4) (3,3/2) (19/6,1)
2016/11/11
浙江科技学院经济管理学院管工系
16
5.3 0-1整数规划
背包问题
厂址选择问题
多决策问题
固定费用问题
2016/11/11
浙江科技学院经济管理学院管工系
17
1.背包问题
一只背包最大装载重量为50公斤。现有三种物品,每种 物品数量无限。每种物品每件的重量、价格如下表: 物品1 物品2 重量(公斤/件) 10 41 物品3 20
B(5, 3)
2016/11/11
浙江科技学院经济管理学院管工系
012345678
6
4 3 2 1
A(2.6, 3.8)
B(5, 3)
0
1
2
3
4
5
6
7
8
线性规划的最优解A(x1, x2)=(2.6, 3.8)不是整数解,目标 函数值为z=17.8。整数规划的最优解B(x1, x2)=(5,3)目标函数值 为z=17。线性规划最优解A(2.6, 3.8)四舍五入得到的解为(3,4), 不是可行解;舍去尾数取整的解为(2,3),目标函数值z=14。 因此整数规划的最优解一般不能由线性规划的最优解通过 简单的取整得到。
设五种产品产量之间有以下逻辑关系:
五种产品中,安排生产的产品不能超过3种 每一种产品如果安排生产,最小批量为50件
如果产品1安排生产,产品2就不能生产
如果产品4生产,产品5必须生产,而且至少生产50件 设5个0-1变量y1,y2,y3,y4,y5
0 产品i不生产 yi (i 1,2,3,4,5) 1 产品 i 生产
例(接上):
cj 1 1 0 0 0

4 4 4 x5 ( x 3 x4 2 x5 ) 5 5 5
XB
X1
b
5/3
x1
1
x2
0
x3
x4
x5
0
5/6 -1/6
1
0
X2 δj
θ
8/3
0
0
1
0
-2/3 1/3
0
1
cj CB XB 1 1 0 0 1 1 0 0 X1 b 1
1 x1 1 0 0 0 4 2 1 1 0 0 0
则该约束方程等价于:
f ik xk
2016/11/11
f bi
11
浙江科技学院经济管理学院管工系
1.割平面法
例:
CB 0 0 1 0 1 1
Cj
XB x3 x4 δj x1 x4 δj x1 x2 δj 5/3 8/3 3 8 b 6 20
1
1
0
x3 1 0 0
0
x4 0 1 0 0 1 0 Θ 3 5
2016/11/11
浙江科技学院经济管理学院管工系
21
3.多决策问题
一个工厂用3种设备生产5种产品,三种设备的能力(小 时),生产每种产品需要占有的各种设备的能力(小时 /件)以及5种产品的利润(元/件)如下:
产品
设备A 设备B
1
5.0 -
2
1.0 3.0
3
3.0 4.0
4
2.0 1.0
5
4.0 5.0
X2 16/5 0 x3 4/5 δj X1 X2 X3 x5 x6 -4/5 0
-4/5 0 -6/5 0 -1/5 0 0 0 5/4 -1
1 1 0
X1 x3 δj
0 -4/5 1
X2 16/5
0 -3/2 1 -5/4
由上面结果构造割平面束
x 3 x4
2016/11/11
6 4 x5 5 5
2016/11/11 浙江科技学院经济管理学院管工系 7
3.整数线性规划(ILP)解的特点
ILP是其中LP的一个子问题,所有解也是
LP的可行解,所以如果LP的最优解满足ILP的
整数条件,则已得最优解。
2016/11/11
浙江科技学院经济管理学院管工系
8
5.2 割平面法和分支定界法
割平面法(Gomory法)
δj
0
0
0
0
0 -1/4
X * (0,4,2,0,1,0)T Z* 4
13
浙江科技学院经济管理学院管工系
2. 分支定界法
原理:
首先,不考虑变量的整数约束,求解松弛问题线性规 划的最优解。如果线性规划的最优解恰好是整数解,则 这个解就是整数规划的最优解。 如果线性规划的最优解中至少有一个变量不是整数, 把线性规划的可行域切割成两部分,分别求解两个线性 规划的最优解。 如果这两个线性规划的最优解还不是整数解,分别把 每一个可行域再进行分割。这个过程,叫做“分支”。 分支过程得到的整数解中,目标函数值最优的一个叫 做整数规划目标函数值的“界”。分支过程中非整数的 线性规划的最优解,如果目标函数值劣于或等于这个 “界”,就停止继续分支。这个过程,叫做“定界”。
价值(元/件)
17
72
35
求背包中装入每种物品各多少件,使背包中物品总价值 最高。
2016/11/11
浙江科技学院经济管理学院管工系
18
物品1 物品2 重量(公斤/件)
价值(元/件)
物品3 20
35
10
17
41
72
设三种物品的件数各为x1,x2,x3件,总价值为z。 max z=17x1+72x2+35x3
在5个备选地点中选择3处建设生产同一产品的工厂,每 个地点建厂所需投资,占用农田,建成以后的生产能力 如下。总投资不超过800万元,占有农田不超过60亩。 如何选择厂址,使总生产能力最大。
1 2 3 4 建厂备选地点 所需投资(万元) 320 280 240 210 20 18 15 11 占有农田(亩) 55 42 28 生产能力(万吨) 70
2016/11/11 浙江科技学院经济管理学院管工系 10
1.割平面法
割平面束构造:
设具有最大真分数部分的非整分量所在行为:
x i a ik x k bi
将该约束方程所在系数和常数分解为整数N和正
真分数f之和,即:
x i ( N ik f ik ) x k N bi f bi
2016/11/11
浙江科技学院经济管理学院管工系
5
2.整数线性规划(ILP)实例
线性规划模型 max z=x1+4x2 s.t. 14x1+42x2≤196 -x1+ 2x2≤ 5 x1, x2≥0
4 3 2 1
A(2.6, 3.8)
整数规划模型 max z=x1+4x2 s.t. 14x1+42x2≤196 -x1+ 2x2≤ 5 x1, x2≥0 x1,x2 为整数
设5个0-1变量x1,x2,x3,x4,x5,
5 180 8 11
0 在i地不建厂 xi (i 1,2,3,4,5 ) 1 在i地建厂
2016/11/11 浙江科技学院经济管理学院管工系 20
max z=70x1+55x2+42x3+28x4+11x5 s.t. 320x1+280x2+240x3+210x4+180x5≤800 20x1+ 18x2+ 15x3+ 11x4+ 8x5≤ 60 x1+ x 2+ x3 + x4+ x5 = 3 x1,x2,x3,x4,x5 为 0-1变量 这个0-1规划问题的最优解为: x1=1,x2=0,x3=1,x4=1,x5=0,max z=140 即在地点1、3和4建3个厂,总生产能力最大,可以达到 140万吨。
x1入 x3出
MaxZ x1 x 2 2 x1 x2 x 3 6 4 x1 5 x2 x4 20 x 0, j 1,,4, 且为整数 j
x1 x2 [2 ] 1 4 [1] 1 0 0 1 0 0 1 5
由右边结果构造割平面束
x1 5 1 5 x 3 x4 6 6 3
1 0 1 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 1 0
0 x4 -1 1 1 0 -1 1 1 0
0 x5 1
0 x6 0
x5 -2/3
-5/6 -5/6
-1/6 -1/6
1/5 0 0 1 0 1/5 -1 1 1 0
x2 x3
0
1 4/5 1 0 0 0
0
0 1 0 0
0
1 -4/5 -6/5 -1/5
运筹学
——管理科学与工程系 经济与管理学院
第五章 整数规划
5.1 整数规划数学模型和解的特点 5.2 割平面法和分支定界法 5.3 0-1整数规划
5.4 隐枚举法
5.5 匈牙利法
浙江科技学院经济管理学院管工系
2016/11/11
2
本章学习要求
熟悉分支定界法和割平面法的原理及其应用 掌握求解0-1规划问题的隐枚举法
2. Z用观察法找问题ILP的一个整数可行解,求得其目标函 数值,并记作 ,以Z*表示ILP的最优目标函数值,则
Z
Z Z * Z xj为非整数值bj,则可以构造两个 分支,如松弛问题有一个最优解 分支。 xj≤[bj] xj≥[bj]+1 定界,以每个后继问题为一分支表明求解的结果。
设备能 力 1800
2500
设备C
3.0
2.0
ቤተ መጻሕፍቲ ባይዱ
1.0
3.0
相关主题