文档介绍：E
2006/3
1
--第4章整数规划--
Integer Programming 整数规划
All Integer Programming 全整数规划
Mixed Programming 混合整数规划
第四章整数规划
2006/3
2
--第4章整数规划--
一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润及托运时所受的限制如下表所示,问如何托运能使总收益最大?
货物
体积(米3/箱)
重量(吨/箱)
利润(千元/箱)
甲
乙
2 2 3
3 1 2
14 米3 9 吨
托运限制
2006/3
3
--第4章整数规划--
建模:
解:设托运甲货物x1箱,乙货物x2箱
Max z=3 x1 +2 x2 st . 2 x1+3 x214 2 x1 + x29 x10,x20,且为整数
2006/3
4
--第4章整数规划--
2
4
6
2
4
(, )
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/3
5
--第4章整数规划--
2
4
6
2
4
(, 2)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
2006/3
6
--第4章整数规划--
2
4
6
2
4
(4, 1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
(3, 2)
2006/3
7
--第4章整数规划--
分枝定界法:
L0:z0=
x1=,x2=
L1:z1=
L2:z2=
L3:z3=13
L4:z4=14
x1=,x2=2
x1=,x2=3
x1=3,x2=2
x1=4,x2=1
x2≤2
x2≥3
x1≤3
x1≥4

2006/3
8
--第4章整数规划--
LINDO软件及EXCEL求解:
LINDO程序软件:同求解LP模型时的输入及编辑修改过程,在使用‘ GO ’命令求解之前,对整数变量给予说明。命令格式:GIN <变量名>。
EXCEL求解:
2006/3
9
--第4章整数规划--
0-1规划问题及模型
一、0-1规划问题的概念
在整数规划问题中,若变量取值为0或者1,则为0-1规划问题。
0-1变量通常用来表示逻辑性选择的决策。
2006/3
10
--第4章整数规划--