割平面法-运筹学整数规划.ppt

《割平面法-运筹学整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一节问题的提出例子：某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如下表问两种货物托运多少箱，可使获得利润为最大？第三章整数规划（IntegerProgramming)分类：1.纯整数线性规划（PureIntegerLinearProgramming）2.混合整数线性规划（MixedIntegerLinearProgramming）3.0-1型整数线性规划（Zero-OneIntegerLinearProgramming）分配问题与匈牙利法21分配问题与匈牙利法4821答案：解：设x1

2、，x2分别表示两种货物托运的箱数，那么其线性规划为可得最优解为x*=（5/3，8/3)T。如果选用“向上凑整”的方法可得到x(1)=(2,3)T,则此时已破坏了体积约束,超出可行域的范围;如果“舍去小数”可得x(2)=(1,2)T,则此时虽是可行解,值为10，不是最优解,因为当x*=(2,2)T是,其利润为14.由于托运的箱数不能为分数，故上述规划问题是整数规划问题。若不考虑整数约束，其相应的线性规划问题为：第二节分枝定界法(BranchandBoundmethod)引言：穷举法对小规模的问题可以。大规模问题则不行。

3、一、基本思想和算法依据基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界,则剪掉此枝;如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问

4、题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。二、具体步骤（以例子说明）解：第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下x1=4.81,x2=1.82,Z=356此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为Z=356；用观察法可知x1=0，x2=0是可行解，从而其整数规划问题目标函数的下界应为0，即0Z*3569x1+7x2=567x1+20x2=70Z=40x1+90x2LP-1L

5、P-2第二步：分枝与定界过程。将其中一个非整数变量的解，比如x1,进行分枝，即x14.81=4,x14.81=5并分别加入LP问题的约束条件中,得两个子LP规划问题LP-1,LP-2,分别求解此两个子线性规划问题,其最优解分别是LP-1:x1=4,x2=2.1,Z1=349LP-2:x1=5,x2=1.57,Z2=341没有得到全部决策变量均是整数的解。再次定出上下界0Z*349继续对问题LP-1，LP-2进行分枝。先对目标函数值大的子问题进行分枝，即分别将x22.1=2,x22.1=3加

6、入到约束条件中去,得子问题LP-3,LP-4,分别求解得LP-3:x1=4,x2=2,Z3=340（是整数解，定下界）LP-4:x1=1.42,x2=3,Z4=327（剪掉）问题LP-3的所有解均是整数解,而问题LP-4还有非整数解,但由于Z3>Z4,对LP-4分枝已没有必要，剪掉。上下界为340Z*349在对问题LP-2进行分枝,x21.57=1，x21.57=2,得子问题LP-5,LP-6,求解得LP-5:x1=5.44,x2=1,Z5=308(下界340,剪掉)LP-6:无可行解（剪掉）于是得

7、到原整数规划问题的最优解为LP:x1=4,x2=2,Z3=340x1=4.81LP:x2=1.82Z=356LP-1:x1=4x14x2=2.1Z=349LP-2:x1=5x15x2=1.57Z=341LP-3:x1=4x14x2=2x22Z=340LP-6x15无可行解剪掉x22LP-4:x1=1.42x14x2=3剪掉x23Z=327LP-5:x1=5.44x15x2=1剪掉x21Z=308整个过程如下:步骤:1求解相应的线性规划问题的最优解和最优值,如果a)没有可行解,停止;b)若有满足整数

8、条件的最优解,则已得到整数规划问题的最优解,停止;c)若有最优解,但不满足整数条件,记此最优值为原整数规划问题Z*的上界,然后,用观察法求出下界。2分枝、定界，直到得到最优解为止。注意：a）在以后的各枝中，若某一子规划问题的最优解满足整数条件，则用其最优值置换Z*的下界。B）若某一分枝的最优值小于Z*的下界，则剪掉此枝，即以后不再考虑此枝。三、