01型整数规划模型

5.4 01 型整数规划模型1、 01 型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用 中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解 法主要有分枝定界解法及割平面解法(这里不作介绍，感兴趣的读者可参考相关 书籍)。在整数规划问题中，01 型整数规划则是其中较为特殊的一类情况，它 要求决策变量的取值仅为 0或1，在实际问题的讨论中，01型整数规划模型也 对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这 个事实。01 型整数规划的的数学模型为：目标函数M a X Mi z = c i x】+ c空x空+ + c x约束条件为：a x + a x +a x , =) b11 1 12 21 n n1a x + a x +a x , =) b21 122 22 n n2 a x + a x +a x , =) bm 11m 22mn nmx , x , ,x = 0 1112n这里，0 | 1表示 0或 1。2、01 型整数规划模型的解法01 型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量x 1, x 2,，xn的每一个0或1值，均比较其目标函数值的大小，以从中 求出最优解。这种方法一般适用于决策变量个数n较小的情况，当n较大时，由 于n个0、1的可能组合数为2n,故此时即便用计算机进行穷举来求最优解，也 几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算 次数，但有的问题并不使用。此时，就只能用穷举法了。3. 应用实例例 1 工程上马的决策问题1）问题的提出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千 元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪 些工程，方能使该部门可能的期望收益最大。工程费用期望收益第1年第2年第3年15184710392861020402030234可用资金1822242）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么 上马，要么不上马，这两种情况分别对应二进制数中的 1、0，大凡这样的实际 背景所对应的工程问题，大都可考虑用 01型整数规划模型建立其相应的模型。0,第j项工程可上马x . =.（j = 1, 2, 3, 4,）设j 1,第j项工程不上马因每一年的投资不超过所能提供的可用资金数 25千元，故该01型整数规划问题的约束条件为：5 x + 4 x + 3 x + 8 x 18 1234x + 7 x + 9 x + 6 x 2212348 x + 10 x + 2 x + 10 x 241234x = 0 11, j = 1, 2, 3, 4 i由于期望收益尽可能大，故目标函数为：m ax z = 20 x + 40 x + 20 x + 30 x12343）模型的建立与求解至此，我们得到该问题的 01型整数规划模型为m ax z = 20 x + 40 x + 20 x + 30 x1234约束条件为：5 X1 + 4 X 2 + 3 X 3 + 8 X 4 18 X1 + 7 X 2 + 9 X 3 + 6 X 4 228 X1 + 10 X 2 + 2 X 3 + 10 X 4 30（4）1234在此过滤条件（过滤条件可不唯一）下，用隐枚举法求 01 型整数规划模型的 最优解的步骤为：（1）先判断第一枚举点所对应的目标函数值是否满足过滤条件，若不满足， 则转下一步；若满足，再判断该枚举点是否满足各约束条件，若有一个约束条件 不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z1 （本例 中 ， z1 30 ） 作 为 新 的 目 标 值 ， 并 修 改 过 滤 条 件 为 ：20 x1 + 40 x2 + 20 x3 + 30 x4 z，再转下一步；（2）再判断第二枚举点所对应的目标函数值是否满足新的过滤条件，若不 满足，则转下一步；若满足，接着判断该枚举点是否满足各约束条件，若有一个 约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值 z2（z2z1）作为新的目标值，并修改过滤条件为：20x 1 + 40x2 + 20x3 + 30x4 z2， 再转下一步；（3）重复步骤（2），直至所有的枚举点均比较结束为止。 由隐枚举法的求解步骤，我们可给出该问题的求解过程如下表所示，并得到最优 解为：（x 1，x2, x3, x4）= h h D，相应的目标值为90 （千元）。故应上马的工 程为 2号、3号、4号工程。枚举点当前目标值满足约束条件（含过滤条件）？新目标值（4）(1)(2)(3)(0, 0, 0, 0)30X30(0, 0, 0, 1)30VVVV30(0,0, 1,0)30X30(0,0, 1, 1)3050(0, 1,0,0)50X50(0, 1,0, 1)5070(0, 1, 1,0)70X70(0, 1, 1, 1)7090(1,0,0,0)90X90(1,0,0, 1)90X90(1,0, 1,0)90X90(1,0, 1, 1)90X90(1, 1,0,0)90X90(1, 1,0, 1)90X90(1, 1, 1,0)90X90(1,1,1,1)90X90注：在该表中，丿表示满足相应条件，X表示不满足相应条件。例 2 工序的流程安排问题1）问题的提出一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流动的过 程中，每站都要完成一道或几道工序，假定一共有六道工序，这些工序按先后次 序在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无322461, 3582634另外工艺流程特别要求，在任一给定的工作站上，不管完成哪些工序，可用的总 时间不能超过 10 分钟，如何将这些工序分配给各工作站，以使所需的工作站数为最少？2)模型分析与变量的假设下面，我们先讨论工序与工作站的关系，并试图建立起该问题的 01 型整 数规划模型。对任一工序而言，它要么属于工作站 j ，要么不属于工作站 j ，故决策变量 可定义为：1若工序i在工作站 j上运行X = Vij 0若工序i不在工作站j上运行这种定义，使我们能根据最优解中xj的值来很快确定工序i与工作站j之间 的隶属关系。又因工序1， 2， 3所需的工作时间不超过10分钟，故工序1， 2， 3的工作 可以在一个工作站上完成，此时，工序 4， 5， 6 只能分别在各自的工作站上工作， 该可行解对应的工作站数为 4个。也就是说，对最优解而言，该装配线上所需的 工作站个数不会多于 4个。因此，我们再定义变量如下：1 若在最 优解中需要工 作站 jw = Vj 0若在最优解中不需要工作站 j至此，我们得到所需的目标函数为：max z = w + w + w + w1 2 3 4再考虑该模型的约束条件：(1) 每道工序均隶属于一个工作站，且每一工序都必须完成，故有以下六 个约束：x + x + x + x = 1(i = 1, 2, 3, 4, 5, 6)i1 i 2i3 i4(2) 在任一工作站上完成隶属工序所用的时间不能超过 10分钟，故有以下 四个约束：3 x + 5 x + 2 x + 6 x + 8 x + 3 x x ；21222333同理，若工序3隶属于工作站2或1,则变量x2j（ j = 1，2, 3）应 满足的约束条件为：x + x x212232x x2131同理，根据其它工序的优先关系，可仿此法给出其相应的约束条件，由上图 知，六个工序之间有五个优先关系，故这类约束条件共有 15个。另外，在最优解中，若有一个工作站wp（P = 1，2, 3, 4）不用（即wp =0），则 隶属于该工作站的全部xip（i = 1，2, 3, 4, 5, 6）必须为0,于是，有以下四个约束 条件：x + x + x + x + x + x 6 w （i = 1, 2, 3, 4）1j 2j 3j 4 j 5j 6jj3）模型的建立与求解至此，我们得到了该问题的 01 型整数规划模型，它共包含28 个变量， 29 个约束条件，这样的模型用枚举法求解，人工计算是很难胜任的，这时，只能求 助于计算机求解了。我们给出该问题的模型如下，求解的过程望感兴趣的读者自 己完成之。该问题的目标函数为：max z = w + w + w + w1234约束条件为：x + x + x + x = 1(i = 1, 2, 3, 4, 5, 6)i1i 2i3 i43 x + 5 x + 2 x + 6 x + 8 x + 3 x x；x+ xx；xx212223332122322131x +x+xxx+ xxxx21222353 ；212252 ；2151x+x+xx；x+ x x ；xx；11121343 ；111242 ；1141 ；x+x+xx；x+ x x ；xx；31323343 ；313242 ；3141 ；x+x+xx；x+ x x ；xx；41424363 ；414262 ；4161 ；x+x+x+x +x +x 6 w(i =1, 2,3, 4)1j2j3j4j5j6jj