01型整数规划模型

1、.5.4 0 1 型整数规划模型1、 01 型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍， 感兴趣的读者可参考相关书籍）。在整数规划问题中， 0 1 型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0 或 1，在实际问题的讨论中， 01 型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例， 以说明这个事实。01 型整数规划的的数学模型为：目标函数max ( min ) zc1x1 c2 x2cn xn

2、约束条件为：a11 x1a12 x2a1n xn( , )b1a21 x1a22 x2a2 n xn( , )b2am1 x1am2 x2amn xn( , )bmx1 , x2 , xn0 |1这里， 0 | 1 表示 0 或 1。2、01 型整数规划模型的解法01 型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量 x1 , x2 , xn 的每一个 0 或 1 值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数n 较小的情况，当 n 较大时，由于 n 个 0、1 的可能组合数为 2 n ，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。

3、 隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。3. 应用实例例 1 工程上马的决策问题;.1）问题的提出某部门三年内有四项工程可以考虑上马， 每项工程的期望收益和年度费用 （千元）如下表所示： 假定每一项已选定的工程要在三年内完成， 是确定应该上马哪些工程，方能使该部门可能的期望收益最大。工程费用期望收益第 1 年第 2 年第 3 年15182024710403392204861030可用资金1822242）模型分析与变量的假设这是工程上马的决策问题， 对任一给定的工程而言， 它只有两种可能， 要么上马，要么不上马，这两种情况分别对应

4、二进制数中的1、0，大凡这样的实际背景所对应的工程问题， 大都可考虑用 01 型整数规划模型建立其相应的模型。0,第j项工程可上马( j 1, 2,3, 4,)x j第j 项工程不上马设1,因每一年的投资不超过所能提供的可用资金数25 千元，故该 01 型整数规划问题的约束条件为：5x14x23x38x418x17x29x36x4228x110x22x310 x424xi0 |1,j 1,2, 3,4由于期望收益尽可能大，故目标函数为：max z20x140 x220 x330x43）模型的建立与求解至此，我们得到该问题的0 1 型整数规划模型为：max z20x140 x220 x330x4

5、约束条件为：;.5x14x23x38x418(1)x17 x29x36x422(2)8x110x22 x310x424(3)xi0 |1,j 1, 2, 3,4下面用隐枚举法求其最优解。 易知，该 0 1 型整数规划模型有一可行解 （0，0，0，1），它对应的目标函数值为：z30 。自然，该模型的最优解所对应的目标函数值应不小于30，于是，我们增加一过滤条件为：20 x1 40x2 20x3 30x4 30（4）在此过滤条件（过滤条件可不唯一）下，用隐枚举法求01 型整数规划模型的最优解的步骤为：（1）先判断第一枚举点所对应的目标函数值是否满足过滤条件， 若不满足，则转下一步； 若满足，再判断

6、该枚举点是否满足各约束条件， 若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z1（本例中 ， z130 ） 作 为 新 的 目 标 值 ， 并 修 改 过 滤 条 件 为 ：20 x140 x220 x330x4z1 ，再转下一步；(2) 再判断第二枚举点所对应的目标函数值是否满足新的过滤条件，若不满足，则转下一步；若满足，接着判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应的目标函数值z2（z2z1）作为新的目标值，并修改过滤条件为：20x140 x220x330 x4z2 ，再转下一步；(3) 重复步骤（ 2），

7、直至所有的枚举点均比较结束为止。由隐枚举法的求解步骤， 我们可给出该问题的求解过程如下表所示， 并得到最优解为： ( x1 , x2 , x3 , x4 )(0, 1, 1, 1) ，相应的目标值为90（千元）。故应上马的工程为 2 号、 3 号、 4 号工程。当 前 目 标满足约束条件（含过滤条件）？枚举点新目标值值（4） （ 1） （2） （3）（0，0，0，0） 3030（0，0，0，1） 3030;.（0，0，1，0） 3030（0，0，1，1） 3050（0，1，0，0） 5050（0，1，0，1） 5070（0，1，1，0） 7070（0，1，1，1） 7090（1，0，0，0）

8、9090（1，0，0，1） 9090（1，0，1，0） 9090（1，0，1，1） 9090（1，1，0，0） 9090（1，1，0，1） 9090（1，1，1，0） 9090（1，1，1，1） 9090注：在该表中，表示满足相应条件，表示不满足相应条件。例 2工序的流程安排问题1）问题的提出一条装配线由一系列工作站组成， 被装配或制造的产品在装配线上流动的过程中，每站都要完成一道或几道工序， 假定一共有六道工序， 这些工序按先后次序在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无32246，31582634另外工艺流程特别要求， 在任一给定的工作站上， 不管

9、完成哪些工序， 可用的总时间不能超过 10 分钟，如何将这些工序分配给各工作站，以使所需的工作站数;.为最少？2）模型分析与变量的假设下面，我们先讨论工序与工作站的关系，并试图建立起该问题的01 型整数规划模型。对任一工序而言，它要么属于工作站j ，要么不属于工作站 j ，故决策变量可定义为：xij1若工序 i 在工作站 j 上运行0若工序 i 不在工作站 j 上运行这种定义，使我们能根据最优解中xij 的值来很快确定工序 i 与工作站 j 之间的隶属关系。又因工序 1，2，3 所需的工作时间不超过 10 分钟，故工序 1， 2， 3 的工作可以在一个工作站上完成， 此时，工序 4，5，6 只

10、能分别在各自的工作站上工作，该可行解对应的工作站数为 4 个。也就是说，对最优解而言， 该装配线上所需的工作站个数不会多于 4 个。因此，我们再定义变量如下：1若在最 优解中需要工作站 jw j0若在最 优解 中不需要工作站j至此，我们得到所需的目标函数为：max zw1w2w3w 4再考虑该模型的约束条件：（1） 每道工序均隶属于一个工作站， 且每一工序都必须完成， 故有以下 六个约束：xi1xi 2xi 3xi 41(i1, 2, 3, 4, 5, 6)（2）在任一工作站上完成隶属工序所用的时间不能超过 10 分钟，故有以下四个约束：3x1 j5x2 j2x3 j6x4 j8x5 j3x6

11、 j10(j1, 2, 3, 4)（3）最后，我们再考虑各道工序所受的先后次序约束的条件。先考察工序 2 与工序 3 的关系，因工序 2 在工序 3 之前运行，故若工序 3 隶属于工作站 4，则工序 2 无论属于那个工作站均可； 若工序 3 隶属于工作站 3，;.则工序 2 可属于工作站 1 或 2 或 3；此时，变量 x2 j ( j1,2,3) 应满足的约束条件为：x21x22x23x33 ；同理，若工序 3 隶属于工作站2 或 1，则变量 x2 j( j1,2, 3) 应满足的约束条件为：x21x22x32x21x31同理，根据其它工序的优先关系， 可仿此法给出其相应的约束条件，由上图知

12、，六个工序之间有五个优先关系，故这类约束条件共有15 个。另外，在最优解中，若有一个工作站w p ( p 1, 2, 3,4) 不用（即 w p =0），则隶属于该工作站的全部 xip (i1, 2, 3,4,5, 6) 必须为 0，于是，有以下四个约束条件：x1 j x2 j x3 jx4 jx5 jx6 j 6w j (i 1, 2, 3, 4)3）模型的建立与求解至此，我们得到了该问题的0 1 型整数规划模型， 它共包含 28 个变量， 29个约束条件，这样的模型用枚举法求解，人工计算是很难胜任的，这时，只能求助于计算机求解了。 我们给出该问题的模型如下， 求解的过程望感兴趣的读者自己完成之。该问题的目标函数为：max zw1w2w 3w 4约束条件为：xi1xi 2xi 3 xi 41 (i1, 2, 3, 4, 5, 6)3x1 j5x2 j2x3 j6x4 j8x5 j 3x6 j 10 (j 1, 2, 3, 4)xx21x22