§1 整数规划的基本特点 §2 分枝定界法 §3 割平面法 §4 分配问题及其解法 §5 整数规划的应用举例 第5章 整数规划 §1 整数规划的基本特点 §2 分枝定界法 §3 割平面法 §4 分配问题及其解法 §5 整数规划的应用举例

§5 整数规划的应用举例 例1 红星日用化工厂为发运产品，下一年度需要6种不同容积的包装箱。每种包装箱的需求量及生产一个的可变费用如下表所示： 由于生产不同容积包装箱时需要进行专门准备、下料等，生产某一容积包装箱的固定费用均为1200元。又若某一容积包装箱数量不够时，可用比它容积大的代替。试问该工厂应定做哪几种代号的包装箱各多少个，使费用最节省？ 包装箱代号 1 2 3 4 5 6 容积（m3） 0.08 0.1 0.12 0.15 0.2 0.25 需求量（个） 500 550 700 900 450 400 可变费用（元/个） 8 10 12.1 16.3 18.2

解：设xj(j=1,...6)为代号j包装箱的定做数量，yj=1,定做第j种包装箱；0，否则。则本例的数学模型为：

本题最优决策为：生产包装箱1—500个，3—1250个，4—900个，6—850个，不生产代号为2、5的包装箱，总计费用为46160元。

Lindo求解程序： Min 1200y1+1200y2+1200y3+1200y4+1200y5+1200y6+5x1+8x2+10x3+12.1x4+16.3x5+18.2x6 St x1+x2+x3+x4+x5+x6=3500 x6>=400 x5+x6>=850 x4+x5+x6>=1750 x3+x4+x5+x6>=2450 x2+x3+x4+x5+x6>=3000 x1-100000y1<=0 x2-100000y2<=0 x3-100000y3<=0 X4-100000y4<=0 X5-100000y5<=0 X6-100000y6<=0 End gin x1 gin x2 gin x3 gin x4 gin x5 gin x6 Int y1 Int y2 Int y3 Int y4 Int y5 Int y6

例2 春江市计划为新建的5个居民小区中的两个分别各设立一所小学。下表给出了各小区及各小区内及各小区间的平均步行时间及各小区的小学生人数。要求为该市提供决策建议，两所小学应分别建于哪两个居民小区，以及各居民小区学生应分别到那所小学上学，使学生总的上学步行时间最少。 小学位于该区 小学生数 至其他区步行时间 1 2 3 4 5 1 2 3 4 5 200 180 300 160 350 5 20 15 25 10 20 4 20 15 25 15 20 6 25 15 25 15 25 4 12 10 25 15 12 5

先将表中每行数字分别乘上该行学生数，表中数字表明该居民区小学生到可能设于各区的小学上学的总的步行时间，用kij表示。 1 2 3 4 5 1 2 3 4 5 1000 4000 3000 5000 2000 3600 720 3600 2700 4500 4500 6000 1800 7500 4500 4000 2400 4000 640 1920 3500 8750 5250 4200 1750

本题最优决策为在第3居民小区（负责2、3小区学生上学）和第5居民小区（负责1、4、5小区学生上学）各建一所小学。以学生每天上下学来回各一次，合计需时22140分钟。

例3 清源市下设八个区，救护车从一个区到另一区的车程时间如下表所示。该市拟建救护中心，要求各区离救护中心的车程时间必须在8分钟内。试为该市提供决策建议：至少建多少个救护中心，建于何处？ 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 11 13 14 8 15 10 12 13 11 17 14 7 7 8 12 10 8 7 10 9 8 14 16 10 7 12

解：先根据上表整理出若干救护中心建于该区时，救护车程8分钟所能覆盖的区： 救护中心设于该区 救护车车程8分钟内覆盖的区 1 2 3 4 5 6 7 8 1 2 7 1 2 3 4 5 6 3 4 5 6 8 1 7 6 8

设

求解结果为x1=1，x6=1，即至少在1、6两个区各设一个救护中心。