整数规划和规划专业知识讲座.ppt

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