运筹学模型(13)

运筹学模型理论

x11 x12 x13 5x21 x22 x23 8x31 x32 x33 7

x,d,d 0 ijkk这里

四、 0—1型整数规划模型

1. 0—1型整数规划模型概述

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

0—1型整数规划的的数学模型为：

Mi)nz c1x1 c2x2 cnxn 目标函数 Ma(x

a11x1 a12x2 a1nxn ( , )b1

a21x1 a22x2 a2nxn ( , )b2

am1x1 am2x2 amnxn ( , )bm x, x, , x 0 | 1

n约束条件为： 12 这里，0 | 1表示0或1。

2. 0—1型整数规划模型的解法

0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决

策变量x1, x2, , xn的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数n较小的情况，当n较大时，由于n个0、1的可能组合数为2n，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算