运筹学 第5章整数规划

1、三、第五章整数规划、整数规划的模型、分支边界法、分割平面法、01整数规划、分配问题、(一)、整数规划问题例、例1、合理的材料问题设置有形式的圆钢下部件A1、A2、am的空白。 圆钢的上下材料有B1、B2、Bn种类，各种材料可以得到各种部件的空白数和各部件的需要量。 如何采购材料，满足需求，使使用的原材料最小化？一、整数计划的模型，例2，有公司计划在m地点建设工厂，可以选择的地方是A1、A2、Am，他们的生产能力分别是A1、A2、Am。 第I个工厂的建设费用为fi (i=1.2m )，另外n个地方B1、B2、 Bn需要销售该产品，其销售量分别为B1、B2、 Bn。 工厂到销售地点的单位运费是HR

2、。 试验性地决定应在哪个地方建厂，即满足各地的需求，最大限度地节省总建设费用和总运输费用，例3，机床分配问题设置m台同种机床，加工n种零件。 已知各零件的加工时间分别是a1、a2、an，我们询问了如何分配各机床的总加工任务相等还是尽可能保持平衡。 设定： 1指定第I台机床加工第j种零件xij (i=1.2m，j=1.2n) 0相反。 因此，第I台机床加工各种零件的总时间为：另外，一个零件只能用一台机床加工，所以求xij，(2)根据整数计划的数学模型、一般形式、决定变量的整数要求的差异，整数计划可以分为纯整数计划、全整数计划、混合整数计划、01整数计划纯整数计划：所有决定变量都需要取非负整数(此

3、时导入的缓和变量和剩馀变量不需要求整数)。 全整数计划：除了所有决策变量都要求非负整数外，系数aij和常数bi也要求整数(此时导入的缓和变量和剩馀变量也必须是整数)。 混合整数计划：只有部分决策变量要求非负整数，剩下的部分要求非负实数。 01整数计划：所有决策变量都只能是0或1个整数。 (三)、整数规划与线性规划的关系，从数学模型来看，整数规划就像线性规划的特殊形式，求解只需基于线性规划，四舍五入，求出满足整数要求的解即可。 但是，实际上两者有很大的差异，通过舍入获得的解(整数)不一定是最佳解，有时也不能保证所获得的解是整数可执行解。 举例说明。 /把整数规划问题设定如下，首先不考虑整数制约，

4、得到线性规划问题(一般称为缓和问题)。 求出、x1、x2、3、(3/2，10/3 )、当前的整数解(最佳解):四舍五入法”的话，得到4个点(1，3 )、(1，4 )、(2，4 )。 显然，这些都不是整数计划的最佳解。 根据整数规划约束，其可执行的解在线性规划问题的可执行区域内是整数点。 因此，整数规划问题的可执行解集是如图所示的有限集。因此，能一个个地找到集合内的整数点，其最大目标函数的值是最佳解，该方法是完全枚举法。 在上述的例子中，(2，2 ) (3，1 )点是最大值，Z=4。 现在，求解常用整数计划的方法为分支边界法和截断平面法的特殊01计划问题采用了隐式枚举法和匈牙利法。(1)，考虑基

5、本的想法，纯整数问题：整数问题的缓和问题：二，分支边界法，选择一个分支写出，在解决缓和问题的同时，从分支集中删除该分支，从整数解，初期分支是否可能解集，初期界是否无限大，分支集是否空，现在最佳解是最佳解判定最佳值是否小于当前边界，否，用非整数变量分支加入分支集。、否，用最佳解替换当前最佳解的最佳值。例1 :用分支边界法解整数规划问题(用图式解法计算)，解：首先除去整数制约，成为一般线性规划问题(二)，例题，用图式解法求出(LP )最佳解如图所示。 对于、x1，x2，3， 首先，将(LP )分割为(LP1 )和(LP2 )的x1、x1 2、x118/11、x2=40/11 Z(0)=218/11(19.8 )即Z(0)也设为(IP )最小值的下限。 有下式：现在只求(LP1 )和(LP2 )的最佳解。、x1、x2、3，3、此时，b得到了点的最佳解。 x11，x2=3，z (1) 16，1，1，同样地求(LP2 )。 在c点得到最佳解。 即x12，x2=10/3，Z(2) 56/318.7，b，a，c，Z2 Z116的元问题有比(16 )小的最佳解，但x2不是整数，所以以3 10/34附加条件。 找到了整数解，问题明确了，这个枝停止了计算。 加入条件： x23、x24有下式：