第八章整数规划.ppt

《第八章整数规划.ppt》由会员分享，可在线阅读，更多相关《第八章整数规划.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 整数规划整数规划第一节第一节 整数规划的图解法整数规划的图解法第二节第二节 分枝定界法分枝定界法整数规划（整数规划（Integer Programming，简称，简称IP）v整数规划中要求部分或全部决策变量取整数整数规划中要求部分或全部决策变量取整数值。值。v根据规划模型是否为线性，可分为整数线性根据规划模型是否为线性，可分为整数线性规划（规划（ILP）和整数非线性规划（）和整数非线性规划（INLP）。）。v根据受整数约束的变量范围，可分为纯整数根据受整数约束的变量范围，可分为纯整数规划（规划（Pure IP）、混合整数规划（）、混合整数规划（Mixed IP）和）和01规划。规

2、划。第一节第一节 整数规划的图解法整数规划的图解法v对二维对二维ILP问题，图解法是最简单的。问题，图解法是最简单的。v解法：在解法：在LP问题最优解基础上，让目标函数问题最优解基础上，让目标函数等值线逆着其法线方向朝可行域内平移，首等值线逆着其法线方向朝可行域内平移，首次碰到的整数点（次碰到的整数点（ILP的整数可行解），即为的整数可行解），即为ILP问题的最优解。问题的最优解。例例、某某厂厂拟拟用用火火车车装装运运甲甲、乙乙两两种种货货物物集集装装箱箱，每每箱箱的的体体积积、重重量量、可可获获利利润润以以及及装装运运所所受限制如下：受限制如下：货物集装箱货物集装箱 体积体积(米米3 3)重

3、量重量(百斤百斤)利润利润(百元百元)甲甲 5 2 205 2 20 乙乙 4 5 104 5 10 托运限制托运限制 2424 13 13问问两两种种货货物物各各装装运运多多少少箱箱，可可使使获获得得利利润润最最大大？例：设甲、乙两种货物装运箱数分别为例：设甲、乙两种货物装运箱数分别为x1和和x2。显然，显然，x1、x2都要求为整数都要求为整数,于是可建立于是可建立整数规划模型如下：整数规划模型如下：Max z20 x1+10 x2 s.t.5x1+4x224 (1)2x1+5x213 (2)x1,x20 (3)x1,x2为整数为整数 (4)它和线性规划问题的区别在于条件它和线性规划问题的区

4、别在于条件(4)。x1x2（4.8，0）O找到的第一个整数找到的第一个整数点（点（4，1），即），即IP问题的最优解问题的最优解解决整数规划的两种初始想法：解决整数规划的两种初始想法：v1、一一列举所有可行方案；、一一列举所有可行方案；v2、先放弃整数性要求，求得一个、先放弃整数性要求，求得一个LP问问题的最优解后，然后用四舍五入法取整题的最优解后，然后用四舍五入法取整数解。数解。v整数规划问题的解法值得探讨。整数规划问题的解法值得探讨。第二节第二节 分枝定界法分枝定界法v首先，理解一个问题：首先，理解一个问题：v原问题与松弛问题解的关系？原问题与松弛问题解的关系？v一般将一个规划问题去掉若干

5、约束条件一般将一个规划问题去掉若干约束条件而得到的规划问题称为原问题的而得到的规划问题称为原问题的松弛问松弛问题题；例如：例如：S1 S2（松弛问题）（松弛问题）Max z=6x1+5 x2 2x1+x29 5x1+7x235 x1 0，x2 0 x22s.t.减少条件形成减少条件形成松弛问题松弛问题S2 减少条件减少条件x22后，后，x1、x2的的取值范围（设为取值范围（设为 S2）比最初比最初（设为（设为S1）大，如图）大，如图S2S1 因为因为S1 S2，所以，所以z=6x1+5 x2在在S2上上的最大值不超过的最大值不超过S2上的最大值（因上的最大值（因S1上的最大值也是上的最大值也是

6、S2上的值）。上的值）。对于目标函数最小化的问题亦然。对于目标函数最小化的问题亦然。意义：松弛问题的目标函数值比原问题意义：松弛问题的目标函数值比原问题的目标函数值更优。的目标函数值更优。vIP问题去掉整数性约束，一般称为该问题去掉整数性约束，一般称为该IP问题的问题的伴随伴随LP问题问题；v伴随伴随LP问题是问题是IP问题的一个松弛问题；问题的一个松弛问题；v对伴随对伴随LP问题的解，可称之为问题的解，可称之为IP问题的问题的LP解；解；v伴随伴随LP问题的最优值一定比问题的最优值一定比IP问题的更问题的更优。优。例例 求解求解IP问题问题 Max z=40 x1+90 x2 9x1+7x2

7、 56 7x1+20 x270 x1,x20,整数整数R0:z0=356 x1=4.81 x2=1.82R1:z1=349 x1=4.00 x2=2.10R2:z2=341 x1=5.00 x2=1.57R12:z12=327x1=1.42x2=3.00 x23R11:z11=340 x1=4.00 x2=2.00R21:z21=308x1=5.44x2=1.00R22:无可无可行解行解x1 4x2 1x15x22伴随问题伴随问题R0为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 x1,x20问题问题R2为为:Max z=40 x1+90 x2 9x1+7

8、x256 7x1+20 x2 70 x1 5 x1,x2 0问题问题R1为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x1,x20 x2 2问题问题R11为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 2 x1,x20问题问题R12为为:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 4 x2 3 x1,x2 0三点说明三点说明v1、分支顺序：目标值大的先分支；、分支顺序：目标值大的先分支；v2、下级分支问题的最优值一定比上、下级分支问题的最优值一

9、定比上级分支问题的最优值小。级分支问题的最优值小。v3、各分支的取舍：若已取得一整数、各分支的取舍：若已取得一整数可行解，凡是目标函数值小于该整可行解，凡是目标函数值小于该整数可行解的分支都可以舍去。数可行解的分支都可以舍去。对目标函数最大化的对目标函数最大化的IP问题问题R，其伴随，其伴随LP问问题为题为R0，分枝定界法的步骤为：，分枝定界法的步骤为：(1)用观察法求用观察法求R的一个可行解。的一个可行解。其目标值便是其目标值便是R的最优目标值的最优目标值z*的一个下界的一个下界z。(2)求解求解R0，得，得R0的最优解的最优解x(0)和最优值和最优值z0。若若x(0)符合符合R的整数条件，

10、则显然的整数条件，则显然x(0)也是也是R的的最优解，结束；最优解，结束；否则，以否则，以R0作为一个分枝标明求解的结果，作为一个分枝标明求解的结果，z0是问题是问题R的最优目标值的最优目标值z*的一个上界的一个上界z。(3)分枝。分枝。取目标函数值最大的一个枝取目标函数值最大的一个枝Rs，在，在Rs的解中的解中任选一不符合整数条件的变量任选一不符合整数条件的变量xj，其值为其值为bj，构造两个约束条件构造两个约束条件xjbj和和xjbj+1。将两个约束条件分别加入问题将两个约束条件分别加入问题Rs，得两个后得两个后继规划问题继规划问题Rs1和和Rs2。不考虑整数条件求解这两个后继问题，以每不

11、考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。个后继问题为一分枝标明求解的结果。(4)定界。定界。在各分枝中找出目标函数值最大者作为新的在各分枝中找出目标函数值最大者作为新的上界上界z；从已符合整数要求的各分枝中，找出从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界目标函数值最大者作为新的下界z。(5)比较与剪枝。比较与剪枝。各分枝的最优目标函数值中如果有小于各分枝的最优目标函数值中如果有小于z者，者，则剪掉这一枝（用打则剪掉这一枝（用打表示），即以后不再考表示），即以后不再考虑了。虑了。若已没有大于若已没有大于z的分枝，则已得到的分枝，则已得到R的最优解，的最优解，结束；否则，转结束；否则，转(3)。