天才一秒记住【畅想小说网】地址：http://www.cxtra.net
.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为整数
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！