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

a11x1a12x2a1
x
b1

a21x1
a22x2
a2
x


b2
am1x1am2x2am
x
bm
约束条件为：x1x2x
01
这里，01表示0或1。
201型整数规划模型的解法
01型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量x1x2x
的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数
较小的情况，当
较大时，由于
个0、1的可能组合数为2
，故此时即便用计算机进行穷举来求最优解，
也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。
3应用实例
例1工程上马的决策问题
1）问题的提出
某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。
工程
123
第1年5
费用第2年1
第3年8
期望收益20
f4
4
7
10
40
3
9
2
20
8
6
10
30
可用资金
18
22
24
2）模型分析与变量的假设
这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用01型整数规划模型建立其相应的模型。
0第j项工程可上马
xj
设

1
第j项工程不上马
j1234
因每一年的投资不超过所能提供的可用资金数25千元，故该01型整数规划问题的约束条件为：
5x14x23x38x418
8x1x171x02x2
9x32x3
6x42210x4
24
xi01j1234
由于期望收益尽可能大，故目标函数为：
maxz20x140x220x330x4
3）模型的建立与求解至此，我们得到该问题的01型整数规划模型为：
maxz20x140x220x330x4
5x14x23x38x418
1r