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

文档介绍：Integer Programming 整数规划
All Integer Programming 全整数规划
Mixed Programming 混合整数规划
第4章整数规划
2006/08
1
--第4章整数规划--
一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润及托运时所受的限制如下表所示,问如何托运能使总收益最大?
货物
体积(米3/箱)
重量(吨/箱)
利润(千元/箱)
甲
乙
2 2 3
3 1 2
14 米3 9 吨
托运限制
2006/08
2
--第4章整数规划--
建模:
解:设托运甲货物x1箱,乙货物x2箱
Max z=3 x1 +2 x2 st . 2 x1+3 x214 2 x1 + x29 x10,x20,且为整数
2006/08
3
--第4章整数规划--
2
4
6
2
4
(, )
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/08
4
--第4章整数规划--
2
4
6
2
4
(, 2)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
2006/08
5
--第4章整数规划--
2
4
6
2
4
(4, 1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
(3, 2)
2006/08
6
--第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/08
7
--第4章整数规划--
LINDO软件及EXCEL求解:
LINDO程序软件:同求解LP模型时的输入及编辑修改过程,在使用‘ GO ’命令求解之前,对整数变量给予说明。命令格式:GIN <变量名>。
EXCEL求解:
2006/08
8
--第4章整数规划--
0-1规划问题及模型
一、0-1规划问题的概念
在整数规划问题中,若变量取值为0或者1,则为0-1规划问题。
0-1变量通常用来表示逻辑性选择的决策。
2006/08
9
--第4章整数规划--
二、0-1变量的应用
例1:某油田在10个有油气构造处要选择若干个钻探采油,设第j个构造开采时需投资aj元,投产后预计年收益为cj元,若该油田投资的总限额为b元,问:应选择哪几个构造开采最为有利?
设 xj=
10
--- 选择开采第j个构造---不选择开采第j个构造
max z=Σcjxj
j=1
10
∑ajxj b
xj=0或1 (j=1,2,---,10)
j=1
10
-----年总收益
----投资额限制
1、表示选择性决策
2006/08
10
--第4章整数规划--