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