文档介绍：第一节问题的提出
例子:某厂拟采用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如下表
问两种货物托运多少箱,可使获得利润为最大?
第三章整数规划(Integer Programming)
分类:1. 纯整数线性规划(Pure Integer Linear Programming)
2. 混合整数线性规划(Mixed Integer Linear Programming)
3. 0-1型整数线性规划(Zero-One Integer Linear Programming)
解:设x1,x2分别表示两种货物托运的箱数,那么其线性规划为
可得最优解为x*=(5/3,8/3)T。
如果选用“向上凑整”的方法可得到x(1)=(2,3)T, 则此时已破坏了体积约束, 超出可行域的范围; 如果“舍去小数”可得x(2)=(1,2)T, 则此时虽是可行解, 值为10,不是最优解, 因为当x*=(2,2)T是, 其利润为14.
由于托运的箱数不能为分数,故上述规划问题是整数规划问题。
若不考虑整数约束,其相应的线性规划问题为:
第二节分枝定界法(Branch and Bound method)
引言:穷举法对小规模的问题可以。大规模问题则不行。
一、基本思想和算法依据
基本思想是:先求出相应的线性规划最优解,若此解不符合整数条件,那么其目标函数的值就是整数规划问题最优值的上界,而任意满足整数条件的可行解的目标函数值将是其下界(定界),然后将相应的线性规划问题进行分枝,分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界, 则剪掉此枝; 如果后续某一分枝问题的最优解满足整数条件,且其最优值大于上述下界,则用其取代上述下界,继续考虑其它分枝,直到最终求得最优的整数解。
算法的依据在于:“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是,对极大化问题,与整数规划问题相应的线性规划问题的目标函数值,是该整数规划问题目标函数的上界;任何满足整数条件的可行解的目标函数值将是其下界。
二、具体步骤(以例子说明)
解:
第一步:先不考虑整数约束条件,求解相应的线性规划问题,得最优解和最优值如下
x1=, x2=, Z=356
此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为 Z=356;用观察法可知x1=0,x2=0是可行解,从而其整数规划问题目标函数的下界应为0,即
0 Z* 356
9x1+7x2=56
7x1+20x2=70
Z=40x1+90x2
LP-1
LP-2
第二步:分枝与定界过程。
将其中一个非整数变量的解,比如x1, 进行分枝,即
x1 =4, x1 =5
并分别加入LP问题的约束条件中, 得两个子LP规划问题LP-1, LP-2, 分别求解此两个子线性规划问题, 其最优解分别是
LP-1: x1=4, x2=, Z1=349
LP-2: x1=5, x2=, Z2=341
没有得到全部决策变量均是整数的解。再次定出上下界
0 Z* 349
继续对问题LP-1,LP-2进行分枝。先对目标函数值大的子问题进行分枝,即分别将
x2 =2, x2 =3
加入到约束条件中去, 得子问题LP-3, LP-4, 分别求解得
LP-3: x1=4, x2=2, Z3=340 (是整数解,定下界)
LP-4: x1=, x2=3, Z4=327(剪掉)
问题LP-3的所有解均是整数解, 而问题LP-4还有非整数解, 但由于 Z3>Z4, 对LP-4分枝已没有必要,剪掉。
上下界为 340 Z* 349
在对问题LP-2进行分枝, x2 =1, x2 =2, 得子问题LP-5, LP-6, 求解得
LP-5: x1=, x2=1, Z5=308 (下界340, 剪掉)
LP-6: 无可行解(剪掉)
于是得到原整数规划问题的最优解为
LP: x1=4, x2=2, Z3=340
x1=
LP: x2=
Z=356
LP-1: x1=4
x1 4 x2=
Z=349
LP-2: x1=5
x15 x2=
Z=341
LP-3: x1=4
x1 4 x2=2
x2 2 Z=340
LP-6
x15 无可行解剪掉
x22
LP-4: x1=
x1 4 x2=3 剪掉
x2 3 Z=327
LP-5: x1=
x15 x2=1 剪掉
x2 1 Z=308
整个过程如下:
步骤:
1