§5.4 0—1型整数规划模型

《§5.4 0—1型整数规划模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、学模型为：目标函数约束条件为：这里，0

3、1表示0或1。2、0—1型整数规划模型的解法0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数较小的情况，当较大时，由于个0、1的可能组合数为，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。3.应用实例例1工程上马的决策问题81）问题的提

4、出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。工程费用期望收益第1年第2年第3年15184710392861020402030234可用资金1822242）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用0—1型整数规划模型建立其

5、相应的模型。设因每一年的投资不超过所能提供的可用资金数25千元，故该0—1型整数规划问题的约束条件为：由于期望收益尽可能大，故目标函数为：3）模型的建立与求解至此，我们得到该问题的0—1型整数规划模型为：约束条件为：8下面用隐枚举法求其最优解。易知，该0—1型整数规划模型有一可行解（0，0，0，1），它对应的目标函数值为：。自然，该模型的最优解所对应的目标函数值应不小于30，于是，我们增加一过滤条件为：（4）在此过滤条件（过滤条件可不唯一）下，用隐枚举法求0—1型整数规划模型的最优解的步骤为：（1）先

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

7、修改过滤条件为：，再转下一步；(3)  重复步骤（2），直至所有的枚举点均比较结束为止。由隐枚举法的求解步骤，我们可给出该问题的求解过程如下表所示，并得到最优解为：，相应的目标值为90（千元）。故应上马的工程为2号、3号、4号工程。枚举点当前目标值满足约束条件（含过滤条件）？新目标值（4）（1）（2）（3）（0，0，0，0）3030×308（0，0，0，1）（0，0，1，0）（0，0，1，1）（0，1，0，0）（0，1，0，1）（0，1，1，0）303050507070909090909090908（

8、0，1，1，1）（1，0，0，0）（1，0，0，1）（1，0，1，0）（1，0，1，1）（1，1，0，0）（1，1，0，1）（1，1，1，0）（1，1，1，1）90√√√√30×30√√√√50×50√√√√70×70√√√√90×90×90×90×90×90√√√×90×90√×90注：在该表中，√表示满足相应条件，×表示不满足相应条件。例2  工序的流程安排问题1）问题的提出一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流动的过程中，每站都要完成一道或几道工序，假定一共有六道工序，这些

9、工序按先后次序在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无322461，35828634另外工艺流程特别要求，在任一给定的工作站上，不管完成哪些工序，可用的总时间不能超过10分钟，如何将这些工序分配给各工作站，以使所需的工作站数为最少？2）模型分析与变量的假设下面，我们先讨论工序与工作站的关系，并试图建立起该问题的0—1型整数规划模型。对任一工序而言，它要么属于工作站，要么不属于工作站，故决策变量可定义为：这种定义，