《整数规划和0-1规划》由会员分享，可在线阅读，更多相关《整数规划和0-1规划（25页珍藏版）》请在金锄头文库上搜索。
1、 整数规划整数规划制作：傅明睿制作：傅明睿Mathematical modeling整数规划是什么整数规划是什么?规划中的变量局部或全部限制为整数时，称为整数规规划中的变量局部或全部限制为整数时，称为整数规划。假设在线性规划模型中，变量限制为整数，那么称为划。假设在线性规划模型中，变量限制为整数，那么称为整数线性规划。目前所流行的求解整数规划的方法，往往整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。解一切整数规划。Mathematical modeling整数规划的分类整数规
2、划的分类变量全限制为整数时，称纯完全整数规划。变量全限制为整数时，称纯完全整数规划。变量局部限制为整数的，称混合整数规划。变量局部限制为整数的，称混合整数规划。变量只能取变量只能取0或或1时，称之为时，称之为0-1整数规划。整数规划。Mathematical modeling整数规划模型的建立整数规划模型的建立整数规划模型的求解整数规划模型的求解 完全枚举法完全枚举法 分支定界法分支定界法 割平面法割平面法0-1数规划模整型数规划模整型Mathematical modeling例1 集装箱运货问题：甲乙两种货物的装运和获利情况如下表所示，问：甲乙两货物各托运多少箱，可使获得利润最大？Mathe
3、matical modeling解：设解：设 为甲乙两货物各托运箱数为甲乙两货物各托运箱数Mathematical modeling(1) 原线性规划有最优解，当自变量限制为原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：整数后，其整数规划解出现下述情况： a原线性规划最优解全是整数，那么整数原线性规划最优解全是整数，那么整数规划最优解与线性规划最优解一致。规划最优解与线性规划最优解一致。 b原线性规划最优解不全是整数，那么整原线性规划最优解不全是整数，那么整数规划最优解小于原线性规划最优解数规划最优解小于原线性规划最优解max或整数规划最优解大于原线性规划或整数规划最优解
4、大于原线性规划最优解最优解min。Mathematical modeling例例2 今有一台机器将一周生产的两种型号的冷饮杯今有一台机器将一周生产的两种型号的冷饮杯存储在存储在150立方米的储藏室立方米的储藏室 里里,并同时进行出售并同时进行出售.这这台机器能在台机器能在6小时内生产一百箱小时内生产一百箱号杯号杯,5小时内生产小时内生产一百箱一百箱号杯号杯,生产以百箱为单位计算生产以百箱为单位计算,预计每周生预计每周生产产60小时小时.如果如果号杯每百箱占体积号杯每百箱占体积10立方米立方米,每百每百箱可获利润箱可获利润500元元,每周售出数量不会超过每周售出数量不会超过800箱箱;号杯每百箱
5、占体积号杯每百箱占体积20立方米立方米, 每百箱可获利润每百箱可获利润450元元,每周售出数量不受限制每周售出数量不受限制.为保证总收益为最大为保证总收益为最大,每每周应安排生产周应安排生产、号杯各多少百箱？号杯各多少百箱？Mathematical modeling解解: 设每周生产设每周生产、号杯各号杯各 百箱百箱,那么有如那么有如下数学模型下数学模型返回返回Mathematical modeling例例3：设整数规划问题如下：设整数规划问题如下 完全枚举法完全枚举法Mathematical modeling 现求整数解最优解：现求整数解最优解：如用如用“舍入取整法可得舍入取整法可得到到4个
6、点即个点即(1，3) (2，3)(1，4)(2，4)。显然，它们。显然，它们都不可能是整数规划的最都不可能是整数规划的最优解。优解。 故按整数规划约束条件，故按整数规划约束条件，其可行解肯定在线性规划其可行解肯定在线性规划问题的可行域内且为整数问题的可行域内且为整数点。故整数规划问题的可点。故整数规划问题的可行解集是一个有限集，如行解集是一个有限集，如下图。下图。 求得求得2，23，1点为最大值，。点为最大值，。 在求解整数规划问题时，可将集合内的整数点一一找出，在求解整数规划问题时，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。其最大目标函数的值为最优解，此法为完
7、全枚举法。返回返回Mathematical modeling对有约束条件的最优化问题其可行解为有限数的对有约束条件的最优化问题其可行解为有限数的所有可行解空间恰当地进行系所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目集，称为分枝；并且对每个子集内的解集计算一个目标下界对于最小值问题，这称标下界对于最小值问题，这称为定界。在每次分枝后，但凡界限超出可行解集目标为定界。在每次分枝后，但凡界限超出可行解集目标值的那些子集不再
8、进一步分枝，这样，许多子集可不值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。予考虑，这称剪枝。这就是分枝定界法的主要思路。分支定界法分支定界法Mathematical modeling 例例4 用分支定界法求以下整数规划用分支定界法求以下整数规划Mathematical modelingMathematical modeling开始开始V0 X1=2.25,X2=3.75;Z0X23X24V1 X1=3,X2=3,Z2=39V2 X1=1.8,X2=4,Z1=41X12X11V3 X1=1,X2=4.44, Z4V6 X1=0,X2=5,Z6=40
9、V5 X1=1,X2=4,Z5=37V4 不可行不可行X24X25Mathematical modeling 0-1整数规划整数规划1.什么是什么是0-1整数规划？整数规划？2.什么时候采用什么时候采用0-1整数规划法？整数规划法？0-1 整数规划是一种特殊形式的整数规划，整数规划是一种特殊形式的整数规划，这时的决策变量这时的决策变量xi 只取两个值只取两个值0或或1，一般的解，一般的解法为隐枚举法。法为隐枚举法。正如计算机只懂得正如计算机只懂得0,1两个数，两个数，1代表是，代表是，0代代表否。同样的，在表否。同样的，在0-1整数规划中的整数规划中的0和和1并不是并不是真真意义上的数，而是一
10、个衡量事件是否发生真真意义上的数，而是一个衡量事件是否发生的标准。一般来说，我们在从多个事物中选出的标准。一般来说，我们在从多个事物中选出其中一局部，在一定的条件下求解最优情况时其中一局部，在一定的条件下求解最优情况时可以采用可以采用0-1整数规划法。整数规划法。Mathematical modeling例例5一个旅行者要到某地作两周的带包旅行一个旅行者要到某地作两周的带包旅行,装背包时装背包时,他发他发现除了已装的必需物件外现除了已装的必需物件外,他还能再装他还能再装5公斤重的东西公斤重的东西.他打他打算从以下算从以下4种东西中选取种东西中选取,使增加的重量不超过使增加的重量不超过5公斤又能
11、使公斤又能使使用价值最大使用价值最大.这这4种东西的重量和使用价值种东西的重量和使用价值(这里用打分数这里用打分数的方法表示价值的方法表示价值)如下表所示如下表所示,问旅行者应该选取哪些物件问旅行者应该选取哪些物件为好？为好？Mathematical modeling解：建立模型为解：建立模型为Mathematical modelingMathematical modeling由上表可知，问题的最优解为由上表可知，问题的最优解为 X*=( x1 =1 x2=0 x3=1 ) X*=( x1 =1 x2=0 x3=1 ) 但但此法太繁琐，工作量相当大。而隐枚举法就是在此根底上，通此法太繁琐，工作
12、量相当大。而隐枚举法就是在此根底上，通过参加一定的条件，就能较快的求得最优解：过参加一定的条件，就能较快的求得最优解： 找到找到x1 =0 x1 =0 x2=0 x3=1 x2=0 x3=1 是一个可行解，为尽快找到最优解，可将是一个可行解，为尽快找到最优解，可将3 x13 x12 2 x2x25 x3 5 5 x3 5 作为一个约束，但凡目标函数值小于作为一个约束，但凡目标函数值小于5 5 的组合不的组合不必讨论，如下表。必讨论，如下表。Mathematical modeling例例6 求解以下求解以下0-1规划问题规划问题Mathematical modeling解：对于解：对于0-1 0
13、-1 规划问题，由于每个变量只取规划问题，由于每个变量只取0 0，1 1两个值，一两个值，一般会用穷举法来解，即将所有的般会用穷举法来解，即将所有的0 0，1 1 组合找出，使目标函数组合找出，使目标函数到达极值要求就可求得最优解。到达极值要求就可求得最优解。Mathematical modeling例例7(指派问题指派问题) 有有5个工人，要分派他们分别完个工人，要分派他们分别完成成5项工作，每人做各项工作所消耗的时间如下项工作，每人做各项工作所消耗的时间如下表，问应如何安排工作，可使总的消耗时间最表，问应如何安排工作，可使总的消耗时间最小？小？Mathematical modeling解：设解：设Mathematical modeling Thank You!Mathematical modeling
