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

2006/08
库文档分享
--1--
一般整数规划问题的特点及分枝定界法
一、引例
某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润及托运时所受的限制如下表所示,问如何托运能使总收益最大?
货物
体积(米3/箱)
重量(吨/箱)
利润(千元/箱)
甲
乙
2 2 3
3 1 2
14 米3 9 吨
托运限制
2006/08
库文档分享
--2--
建模:
解:设托运甲货物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--
2
4
6
2
4
(, )
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/08
库文档分享
--4--
2
4
6
2
4
(, 2)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
2006/08
库文档分享
--5--
2
4
6
2
4
(4, 1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(, 3)
(3, 2)
2006/08
库文档分享
--6--
分枝定界法:
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--
LINDO软件及EXCEL求解:
LINDO程序软件:同求解LP模型时的输入及编辑修改过程,在使用‘ GO ’命令求解之前,对整数变量给予说明。命令格式:GIN <变量名>。
EXCEL求解:
2006/08
库文档分享
--8--
0-1规划问题及模型
一、0-1规划问题的概念
在整数规划问题中,若变量取值为0或者1,则为0-1规划问题。
0-1变量通常用来表示逻辑性选择的决策。
2006/08
库文档分享
--9--
二、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--
2. 表示选择性约束
例2:上述例题中,如果在开采中需用电力,解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度,电网每天供电量限制为f 度。当使用自备柴油机发电时,,而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。
采用电网供电: ∑djxj f
采用自备柴油机发电: ∑ p
j=1
10
j=1
10
+(1-y1)M
+(1-y2)M
y1+y2=1
y1, y2 =0或1
M-----非常大的正数