第六节典型例题及应用

整数规划广泛应用到实践中，其中用得比较多的是0-1规划，0-1决策变量最常见用于建模那些只有做或不做两种选择的决策、选择性约束和条件约束的规划问题。

【例3.5】一登山队员做登山准备，他需要携带的物品及每一件物品的重量和重要性系数见表3-8。假定登山队员允许携带的最大重量为25千克，试确定一最优方案。

表3-8 物品的重量和重要性系数

分析：对于每种物品来说，只有携带或不携带两种决策。给七种物品依次编号，引入0-1变量(=)，

令

要求尽量携带重要的物品，则根据题意可列出如下模型：

WinQSB软件求解线性整数规划仍然是调用子程序Linear and Integer Programming，操作时在建立新问题界面中改变变量类型为整数即可。若为混合整数规划，可在数据输入表中直接修改变量类型。如图3-2，图3-3。

图3-2 WinQSB软件求解线性整数规划

图3-3 WinQSB软件求解线性整数规划

求解结果综合报表见图3-4。

图3-4 例3.5的求解综合报表

从综合报表中可知，此0-1规划问题的最优解为：

最优目标函数值=81。

即除了第五项物品帐篷之外，其它的物品都带上，在满足不超重的条件下可使重要系数之和最大，最大值为81。

【例3.6】某公司拟在市区的东、西、南北四区建立门市部。拟议中有10个位置(点)()可供选择。规定：

在东区，由，，三个点中至多选两个；

在西区，由，两个点中至少选一个；

在南区，由，两个点中至少选一个；

在北区，由，和三个点中至少选两个。

如选用点，其设备投资和每年可获利润估计的取值见表3-9，投资总额不能超过720万元。问应选择哪几个点可使年利润为最大?

表3-9 设备投资和每年获利估计

分析：此类问题也属于互相排斥的计划问题，对于每个点来说，只有建立门市部或不建立两种决策，一般选择0-1整数规划模型。引入0-1变量()。

令

根据题意，可列模型如下：

求解结果综合报表见图3-5。

图3-5 例3.6的求解综合报表

从综合报表中可知，此0-1规划问题的最优解为：

最优目标函数值=245。

即在，，，，和六个点建立门市部，可使年利润为最大，最大年利润为245万元。

【例3.7】某公司制造小、中大三种金属容器，所用资源为金属板、劳动力和机器设备，相关信息见表3-10。此外，不管每种型号的容器制造的数量是多少，都要支付一笔固定的费用：小号是100元，中号是150元，大号是200元，试制定一个生产计划，使获得的利润最大。

表3-10 金属容器及所用资源

分析：设分别为小、中、大三种型号容器的生产数量，由于各种容器的生产所耗用的材料、劳动力、设备及固定费用只有在生产该种型号容器时才投入，所以引入0-1变量。

令，充分大，以保证当=0时，

由此，可列模型如下：

用WinQSB软件求解上述模型，得到综合结果报表如图3-6(输入数据时，取M为相关很大的数2000000)。

图3-6 例 3.7求解结果综合报表

从综合报表中可知，此0-1规划问题的最优解为：

最优目标函数值=300。

即在只生产型的容器，可使利润为最大，最大利润为300万元。

【例3.8】某市共有6个区，每个区都可以设消防站。市政府希望设置消防站最少以便节省费用，但必须保证在城区任何地方发生火警时，消防车能在15分钟之内赶到现场。据实地测定，各区之间消防车行驶的时间见表3-11。

表3-11 消防车行驶时间信息表

分析：引入设0−1决策变量。

令

这样根据消防车15分钟赶到现场的限制，可得到如下模型：

用WinQSB软件求解上述模型，得到综合结果报表如图3-7。

图3-7 例 3.8求解结果综合报表

从综合报表中可知，此0-1规划问题的最优解为：

即只要在二区(管一、二和六区三个区)和四区(管三、四和五区)设站即可。

【例3.9】某医药公司现有两个制药厂₁和₂，三个销售点₁、₂和₃。由于供不应求，公司打算由两个拟建的制药厂₃和₄中选择一个来兴建新厂。新厂投产后，估计每月的固定成本：₃是100万元，₄是120万元。各销售点每月药品需求量、各制药厂每月药品产量和每箱药品运费见表3-12，3-13。在两个拟建的制药厂中，应当选择哪个，使总成本最低(建立数学模型)？

表3-12 销售点每月药品需求量

表3-13 各制药厂每月药品产量和每箱药品运费

解：设

：制药厂每月运到销售点的药品数(万箱)()