格格党

手机浏览器扫描二维码访问

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

.2整数规划模型

banner"

>

变量取整数的规划称为整数规划.所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划.在线性规划问题中，如果所有的变量都只能取值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为整数