整数规划Integer Programming

《整数规划Integer Programming》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、PartII整数规划IntegerProgramming整数规划问题描述分枝定界法割平面法指派问题匈牙利算法1整数规划的问题描述例1.某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备需要A、B两种材料的消耗以及资源的限制，如下表。问题：工厂应分别生产多少件甲、乙种仪器设备才能使工厂获利最多？甲乙资源限制材料A3210材料B025单件获利1万元1万元1整数规划的问题描述解:目标函数：Maxz=x+x12约束条件：3x+2x≤10122x≤52xx≥0为整数1，2不考虑整数约束得到最优解：x=1.667,x=2.5;z=4.16712考虑

2、整数约束得到最优解：x=2，x=2；z=412整数规划的最优目标值小于相应线性规划的最优目标值(相当于附加一个约束)1整数规划的问题描述整数规划问题：目标函数和约束条件仍旧是关于决策变量的线性函数，只是要求部分或全部决策变量取整数。纯整数规划（PureIntegerProgramming）整数规划混合整数规划（MixIntegerProgramming)如何求解整数规划问题？•枚举法，or穷举法？•相应线性规划求解后“化整”得到的解？将整数规划问题的相应线性规划求解后“化整”得到的解不一定是原问题的最优解，有时甚至不是可行解。1整数规划的问题描述求解整

3、数规划问题的方法：Classical•分枝定界法（BranchandBoundMethod）•割平面法（CuttingPlaneMethod）AdvancedMethod•分枝割平面法（BranchandCutMethod）•分枝定价法（BranchandPriceMethod）•分枝割平面定价法（BranchCutandPriceMethod）•…….2分枝定界法1960s早期，由Doig&Dakin提出B&B。基本思想：B&B算法中包含两个主要部分：分枝（Branch）和定界（Bounding）。分枝是指连续将可行解域分割成几个（经常是两个）互不相交的集

4、合。定界则是指在任何分割出的子集合上能够计算出一个界。2分枝定界法B&B步骤：问题A:整数规划最大化问题问题B:去掉整数约束的问题A，也称为A的松弛问题.第一步：求解问题B，应有以下情况之一：①B无可行解，则A亦无可行解，终止；②B有最优解，并满足整数约束，即同时为A的最优解，那么z*同时是当前问题A最优目标值终止；③B有最优解x及最优值z但不符合整数条件。这时得到当前问题A最优目标值的一个上界。第二步：用观察法找问题A的一个整数可行解，一般取x=0;jj=1,2,…,n，并求得其目标值，得到目标函数值的一个下界。2分枝定界法第三步：分枝，定界①分枝：任取非

5、整数的分量x，构造两个附加约束：jxjxjxjxj1对问题A分别加入这两个约束，可得到两个子问题A和A，12显然这两个子问题的可行解集的并包含问题A的可行解集；②定界：根据前面分析，对每个当前问题A可以通过求解松i弛问题B，以及找A的可行解得到当前问题的上、下界。ii③比较与剪枝：对当前子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪枝：Ⅰ无可行解；Ⅱ最优解符合整数约束；Ⅲ最优值z小于当前的下界。通过比较，若子问题不剪枝则返回①。2分枝定界法B&B终止条件：当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界的可行

6、解即原问题的最优解，算法结束。例：Maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0x1,x2取整数2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法2分枝定界法Exercise:用B&B算法求解下列ILP问题MaxZ=4X+3X12s.t.3X+4X12124X+2X912X,X0,Integer12用单纯形法可解得相应的松驰问题的最优解（6/5，21/10）Z=111/10为各分枝的上界。2分枝定界法x2分枝：X11,X12432P1

7、1P2x1012342分枝定界法再对（P1）分枝：X11x2（P3）X22（P4）X23P4P1P3P2x12分枝定界法P:(2,1/2)Z=9(1/2)2X21X2P:(6/5,21/10)2P:(1,2)Z=103Z=111/10X11P:(1,9/4)1X3Z=10(3/4)2P:(0,3)Z=94原问题的最优解（1，2）Z=102分枝定界法Exercisemaxzxx12s.t.2xx6124x5x2012x,x0,integer122分枝定界法用分枝定界算法求解下面整数规划问题：提示：利用人工变量！maxzxx12s

8、.t.4x2x1124x2x11122x1