整数规划制作:傅明睿Mathematicalmodeling2整数规划是什么?规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。Mathematicalmodeling3整数规划的分类变量全限制为整数时,称纯(完全)整数规划。变量部分限制为整数的,称混合整数规划。变量只能取0或1时,称之为0-1整数规划。Mathematicalmodeling4·整数规划模型的建立·整数规划模型的求解·完全枚举法·分支定界法·割平面法·0-1数规划模整型Mathematicalmodeling5例1集装箱运货问题:已知甲乙两种货物的装运和获利情况如下表所示,问:甲乙两货物各托运多少箱,可使获得利润最大?Mathematicalmodeling6且为整数0,135224451020max21212121xxxxxxxxz解:设为甲乙两货物各托运箱数12,xxMathematicalmodeling7(1)原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:a原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。b原线性规划最优解不全是整数,则整数规划最优解小于原线性规划最优解(max)或整数规划最优解大于原线性规划最优解(min)。Mathematicalmodeling8例2今有一台机器将一周生产的两种型号的冷饮杯存储在150立方米的储藏室里,并同时进行出售.已知这台机器能在6小时内生产一百箱Ⅰ号杯,5小时内生产一百箱Ⅱ号杯,生产以百箱为单位计算,预计每周生产60小时.如果Ⅰ号杯每百箱占体积10立方米,每百箱可获利润500元,每周售出数量不会超过800箱;Ⅱ号杯每百箱占体积20立方米,每百箱可获利润450元,每周售出数量不受限制.为保证总收益为最大,每周应安排生产Ⅰ、Ⅱ号杯各多少百箱?Mathematicalmodeling912,xx解:设每周生产Ⅰ、Ⅱ号杯各百箱,则有如下数学模型且为整数0,815020106056450500max211212121xxxxxxxxxz返回Mathematicalmodeling10例3:设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxz·完全枚举法Mathematicalmodeling11现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3)(2,3)(1,4)(2,4)。显然,它们都不可能是整数规划的最优解。故按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如图所示。求得(2,2)(3,1)点为最大值,。在求解整数规划问题时,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法。返回Mathematicalmodeling12对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索,这就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。·分支定界法Mathematicalmodeling13例4用分支定界法求以下整数规划1212122max5865945,0xzxxxxxxxx且为整数Mathematicalmodeling141x2xMathematicalmodeling15开始V0X1=2.25,X2=3.75;Z0=41.25X2≤3X2≥4V1X1=3,X2=3,Z2=39V2X1=1.8,X2=4,Z1=41X1≥2X1≤1V3X1=1,X2=4.44,Z4=40.56V6X1=0,X2=5,Z6=40V5X1=1,X2=4,Z5=37V4不可行X2≤4X2≥5Mathematicalmodeling16·0-1整数规划1.什么是0-1整数规划?2.什么时候采用0-1整数规划法?0-1整数规划是一种特殊形式的整数规划,这时的决策变量xi只取两个值0或1,一般的解法为隐枚举法。正如计算机只懂得0,1两个数,1代表是,0代表否。同样的,在0-1整数规划中的0和1并不是真真意义上的数,而是一个衡量事件是否发生的标准。一般来说,我们在从多个事物中选出其中一部分,在一定的条件下求解最优情况时可以采用0-1整数规划法。Mathematicalmodeling17例5一个旅行者要到某地作两周的带包旅行,装背包时,他发现除了已装的必需物件外,他还能再装5公斤重的东西.他打算从下列4种东西中选取,使增加的重量不超过5公斤又能使使用价值最大.这4种东西的重量和使用价值(这里用打分数的办法表示价值)如下表所示,问旅行者应该选取哪些物件为好?Mathematicalmodeling18解:建立模型为12341234maxZ=6x7392345s.t.0,11,2,3,4ixxxxxxxxiMathematicalmodeling19Mathematicalmodeling20由上表可知,问题的最优解为X*=(x1=1x2=0x3=1)但此法太繁琐,工作量相当大。而隐枚举法就是在此基础上,通过加入一定的条件,就能较快的求得最优解:找到x1=0x2=0x3=1是一个可行解,为尽快找到最优解,可将3x1-2x2+5x3≥5作为一个约束,凡是目标函数值小于5的组合不必讨论,如下表。Mathematicalmodeling21例6求解下列0-1规划问题1231231231223123max32522(1)44(2)..3(3)46(4),,01Zxxxxxxxxxstxxxxxxx或Mathematicalmodeling22解:对于0-1规划问题,由于每个变量只取0,1两个值,一般会用穷举法来解,即将所有的0,1组合找出,使目标函数达到极值要求就可求得最优解。Mathematicalmodeling23例7(指派问题)有5个工人,要分派他们分别完成5项工作,每人做各项工作所消耗的时间如下表,问应如何安排工作,可使总的消耗时间最小?Mathematicalmodeling2410,1,2,,5ijijxij分派第工人完成第工作其他解:设111213141521222324253132333435414243444551525354555151min568453466155798..675767462811,2,,511,2,,501,1,2,,5ijiijjijzxxxxxxxxxxxxxxxstxxxxxxxxxxxjxixij或MathematicalmodelingThankYou!Mathematicalmodeling