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

该【哈工大运筹学课件整数规划 】是由【闰土】上传分享，文档一共【43】页，该文档可以免费在线阅读，需要了解更多关于【哈工大运筹学课件整数规划 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。IntegerProgramming整数规划
AllIntegerProgramming全整数规划
MixedProgramming混合整数规划
第4章整数规划
2006/08
1
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第1页!

一、引例
某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润及托运时所受的限制如下表所示,问如何托运能使总收益最大?
货物
体积(米3/箱)
重量(吨/箱)
利润(千元/箱)
甲
乙
2 2 3
3 1 2
14 米3 9吨
托运限制
2006/08
2
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第2页!
建模:
解:设托运甲货物x1箱,乙货物x2箱
Maxz=3x1+2x2 +3x214 2x1+x29 x10,x20,且为整数
2006/08
3
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第3页!
2
4
6
2
4
(,)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
2006/08
4
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第4页!
2
4
6
2
4
(4,1)
x1
x2
2x1+3x2=14
2x1+x2=9
3x1+2x2=6
(,3)
(3,2)
2006/08
5
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第5页!
LINDO软件及EXCEL求解:
LINDO程序软件:同求解LP模型时的输入及编辑修改过程,在使用‘GO’命令求解之前,对整数变量给予说明。命令格式:GIN<变量名>。
EXCEL求解:
2006/08
6
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第6页!
二、0-1变量的应用
例1:某油田在10个有油气构造处要选择若干个钻探采油,设第j个构造开采时需投资aj元,投产后预计年收益为cj元,若该油田投资的总限额为b元,问:应选择哪几个构造开采最为有利?
设xj=
10
---选择开采第j个构造---不选择开采第j个构造
maxz=Σcjxj
j=1
10
∑ajxjb
xj=0或1(j=1,2,---,10)
j=1
10
-----年总收益
----投资额限制
1、表示选择性决策
2006/08
7
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第7页!

例3:若在开采时还需满足下述条件:
(a)若开采8号,则必须同时开采6号;(b)若开采5号,则不许开采3号;(c)2号和4号至少开采一个; (d)8号与7号必须同时开采; (e)1号、4号、6号、9号开采时不能超过两 个,试表示上述约束条件。
2006/08
8
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第8页!

若x14,则x21,否则(x14),则x23。
设yi=
1
0
第i组条件起作用
第i组条件不起作用
则
i=1,2
x14+(1-y1)Mx21-(1-y1)M
M——充分大正数
x14-(1-y2)Mx23+(1-y2)M
y1+y2=1y1,y2=0或1
2006/08
9
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第9页!
三、隐枚举法
步骤:
①化标准形(隐枚举法):1)目标函数极小化2)约束条件化成 3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj 4)使目标函数按变量系数由小→大顺序排列,约束条件变 量排列的顺序要与之对应。
②令所有变量xj=0,计算边界目标函数值z,检查是否满足所有约束条件,若满足,即为最优解;否则,分枝计算。
③分枝:按变量次序依次令各变量取“1”和“0”值,计算边界值,然后检查是否满足所有约束,若满足,转下步;否则继续分枝。
④剪枝:在得到一个可行解后,分枝过程中要进行剪枝工作。 (a)对可行解,保留边界值最小的一枝zmin,其余全剪掉; (b)>zmin分枝,剪掉; (c)能判断出为无可行解的分枝,剪掉; (d)非上述情况,继续分枝。
2006/08
10
--第4章整数规划--
哈工大运筹学课件整数规划共43页,您现在浏览的是第10页!