2整数规划模型（第1页）

。2整数规划模型

变量取整数的规划称为整数规划。所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划。在线性规划问题中，如果所有的变量都只能取值0或1。这样的线性规划问题称为（纯）0—1整数规划问题。如果一个线性规划问题中，有的变量是连续变量，而另一些变量是0—1变量，这样的问题称为混合0—1规划问题。

1。　背包问题

例4一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：

表54

物品1物品2物品3

重量（公斤件）104120

价值（元件）177235

要在背包中装入这三种物品各多少件，使背包中的物品价值最高。

设装入物品1，物品2和物品3各为x1，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：

maxz=17x1+72x2+35x3〖1〗

s。t。10x1+41x2+20x3≤50

x1，x2，x3≥0，x1，x2，x3是整数

这个问题的最优解是：x1=1件，x2=0件，x3=2件，最高价值为：z=87元。

例5一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg，试选择该队员所应携带的物品。

表55

序号1234567

物品食品氧气冰镐绳索帐篷照相器材通信设备

重量kg55261224

重要性系数201518148410

解：引入0—1变量xi，xi=1表示应携带物品i，xi=0表示不应携带物品I，i=1，2，…，7

maxz=20x1+15x2+18x3+14x4+8x5+4x6+10x7

5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25

xi=0或1，i=1，2，…，7

比较每种物品的重要性系数和重量的比值，比值大的物品首先选取，直到达到重量限制，上述问题就是一个标准的整数规划问题，由分枝定界法，解得：X=（x1，x2，x3，x4，x5，x6，x7）=（1，1，1，1，0，1，1），Z=81

一般地，有一只背包，最大装载重量为W公斤，现有k种物品，每种物品数量无限。第i种物品每件重量为wi公斤，价值为vi元。每种物品各取多少件装入背包，使其中物品的总价值最高。

设取第i种物品xi件（i=1，2，…，k），则规划问题可以写为

maxz=v1x1+v2x2+…+vkxk〖1〗

s。t。kxk≤W〖1〗

x1，x2，…xk≥0〖1〗

x1，x2，…xk为整数

例6集合覆盖和布点问题

某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。

表56

地区1地区2地区3地区4地区5地区6

地区1

地区2

地区3

地区4