第五章
整数规划

1 下列说法中正确的有：

（1）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界；

（2）用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数值；

（3）指派问题可用求解运输问题的表上作业法求解，反过来运输问题经处理后也可用匈牙利解法求解；

（4）一个整数规划问题如存在两个以上最优解，则一定有无穷多最优解。

解： （1）正确，可行解的目标函数值可看作最优解目标函数值的一个界限，对于最大化问题，是下界；对于最小化问题，是上界；

（2）错误，切割保留了整数规划的所有整数可行解；

（3）错误，指派问题可以用表上作业法求解，而运输问题不能用匈牙利算法求解；

（4）错误，两个顶点连线上的整数解个数有限，不会有无穷多最优解。

因此说法正确的有（1）。

2 篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见表2-5-1。

出场阵容应满足以下条件：

（1）必须且只有一名中锋上场；

（2）至少有一名后卫；

（3）如1号或4号上场，则6号不出场，反之如6号上场，则1号和4号均不出场；

（4）2号和8号至少有一个不出场。

问应当选择哪5名队员上场，才能使出场队员平均身高最高，试建立数学模型。

解： 设x _i ＝1表示第i个队员出场，i＝1，2，…，n。

3 一个旅行者要在其背包里装一些最有用的旅行物品。背包容积为a，携带物品总重量最多为b。现有物品m件，第i件物品体积为a _i ，重量为b _i （i＝1，2，…，m）。为了比较物品的有用程度，假设第i件物品的价值为c _i （i＝1，2，…，m）。若每件物品只能整件携带，每件物品都能放入背包中，并且不考虑物品放入背包后相互的间隙。问旅行者应当携带哪几件物品，才能使携带物品的总价值最大，要求建立本问题的数学模型。

解： 设x _i ＝1表示携带第i件物品，i＝1，2，…，m。

4 分别用割平面法和分支定界法解下列整数规划：

（1）

（2）

解： （1）割平面法：

引入松弛变量x ₃ ，x ₄ ，x ₅ ，将问题化为标准形式，用单纯形法解其松弛问题，得最优单纯形表见表2-5-2。

由于b列各分数中x ₁ ＝11/4由最大小数部分3/4，故从表2-5-2中第三行产生割平面约束。割平面约束为

引入松弛变量x ₆ ，得割平面方程

将上式并入表2-5-2，利用对偶单纯形法求解，得表2-5-3。

类似地，从表2-5-3中最后一个单纯形表的第二行产生割平面约束

引入松弛变量x ₇ ，得割平面方程

将上式并入表2-5-3中最后一个单纯形表，然后用对偶单纯形法解之，得表2-5-4。

表2-5-4给出的最优解（x ₁ ，x ₂ ，x ₃ ，x ₄ ，x ₅ ，x ₆ ，x ₇ ） ^T ＝（3，1，1，2，1，0，0） ^T 已满足整数要求，因而，原整数规划问题的最优解为x ₁ ＝3，x ₂ ＝1，max z＝7。

分支定界法：

根据最终单纯形表可以得到，此时最优解为x ₁ ＝11/4，x ₂ ＝9/4，z＝59/8。

选x ₂ 进行分支，可以得到两个约束条件。

第一个约束条件：

最终化为标准式，相当于增加了一个约束条件和变量x ₆ 。

x ₁ ＝8/3，x ₂ ＝2，z＝22/3

第二个约束条件：

最终化为标准式，相当于增加了一个约束条件和变量x ₆ 。

无可行解，继续对第一分支

（2）引入松弛变量x ₃ ，x ₄ ，x ₅ ，将问题化为标准形式，用单纯形法解其松弛问题，得最优单纯形表见表2-5-7。

表2-5-7给出的最优解（x ₁ ，x ₂ ，x ₃ ，x ₄ ，x ₅ ） ^T ＝（0，9，0，4，64） ^T 已满足整数要求，因而，原整数规划问题的最优解为x ₂ ＝9，min z＝9。

5 用隐枚举法解下列0－1型整数规划：

（1）

（2）

解： （1）此题无可行解。

（2）求解过程列表，如表2-5-8所示。

所以，最优解（x ₁ ，x ₂ ，x ₃ ） ^T ＝（1，0，0） ^T ，max z＝2。

6 某城市可划分为11个防火区，已设有4个消防站，见图2-5-1所示。

图2-5-1中，虚线表示该消防站可以在消防允许时间内到达该防火区进行有效的消防灭火。问能否关闭若干消防站，但仍不影响任何一个防火区的消防救灾工作。（提示：对每一个消防站建立一个表示是否将关闭的0-1变量。）

解： 设x _i ＝1表示第i个消防站保留，i＝1，2，3，4

显然，可以关闭2号消防站。

7 现有p个约束条件， 。需要从中选择q个约束条件，试借助0-1变量列出表达式。

解： 设y _i 是0-1变量，i＝1，2，…，p

8 解下列系数矩阵的最小化指派问题：

（1）

（2）

解： 设

（1）先对各行元素分别减去本行的最小元素，然后对各列也如此，即

此时，C′中各行各列都已出现零元素。

为了确定C′中的独立零元素，对C′加圈，即

由于只有4个独立零元素，少于系数矩阵阶数n＝5，故需要确定能够覆盖所有零元素的最少直线数目的集合。结果如下：

为了使C′中未被直线覆盖的元素中出现零元素，将第二行和第三行中各元素都减去未被直线覆盖的元素中的最小元素1，同时为了消除第一列出现负元素，对第一列各元素分别加上1，即

回到步骤2，对C″加圈：

C″中已有5个独立零元素，故可确定指派问题的最优指派方案。即最优解为x ₁₄ ＝x ₂₁ ＝x ₃₂ ＝x ₄₅ ＝1，其余x _ij ＝0。

（2）先对各行元素分别减去本行的最小元素，然后对各列也如此，即

此时，C′中各行各列都已出现零元素。

为了确定C′中的独立零元素，对C′加圈，即

C′中已有6个独立零元素，故可确定指派问题的最优指派方案。即最优解为x ₁₃ ＝x ₂₂ ＝x ₃₁ ＝x ₆₄ ＝1，其余x _ij ＝0。

9 需要分派5人去做5项工作，每人做各项工作的能力评分见表2-5-9。应如何分派，才能使总的得分最大？试分别用匈牙利法和表上作业法求解。

解： 匈牙利法：最大元素是1.4，用它减去所有元素，得到矩阵，再对各行元素分别减去本行的最小元素，然后对各列也如此，即：

此时，C′中各行各列都已出现零元素。

为了确定C′中的独立零元素，对C′加圈，即

由于只有3个独立零元素，少于系数矩阵阶数n＝5，故需要确定能够覆盖所有零元素的最少直线数目的集合。结果如下：

为了使C′中未被直线覆盖的元素中出现零元素，将第四行和第五行中各元素都减去未被直线覆盖的元素中的最小元素0.1，同时为了消除第五列出现负元素，对第五列各元素分别加上0.1，即

回到步骤2，对C″加圈：

C″中已有5个独立零元素，故可确定指派问题的最优指派方案。即最优解为x ₁₁ ＝x ₂₃ ＝x ₃₄ ＝x ₄₅ ＝x ₅₂ ＝1，其余x _ij ＝0，总得分6.1。

表上作业法：

用最小元素法求最优解，可以把人员看成产地，业务看成销地，各地产量和销量均为1，于是转化为运输问题，如表2-5-10所示。

10 上题的指派问题也可用分支定界法求解，试说明求解思路。

答： 用分支定界法时，先根据表列出线性规划模型：例如先不考虑每人完成一项任务的约束，按照谁完成的多进行分配。当不满足问题要求时，按A ₁ ，…，A ₅ 中指定1人完成B ₁ ，其余4人再按得分多的进行分配，这样得5个分支。如5个分支均非可行解时，可选一个边界值最大分支，并指定剩下4人中的1人完成任务B ₂ ，继续分支，依次进行。

11 考虑下列问题

式中0≤y≤10，为整数值，且x的值只能等于0、1、4和6。

（1）请用一等价的整数规划模型来表达这个问题。

（2）如果在目标函数中，用3x ² 来代替3x，请相应地修改（1）的答案。

解： （1）

（2）

12 卡车送货问题（覆盖问题）。龙运公司目前必须向5家用户送货，需在用户A处卸下1个单位重量的货物，在用户B处卸下2个单位重量的货物，在用户C处卸下3个单位重量的货物，在用户D处卸下4个单位重量的货物，在用户E处卸下8个单位重量的货物。公司有各种卡车四辆。1号车载重能力为2个单位重量，2号车载重能力为6个单位重量，3号车载重能力为8个单位重量，4号车载重能力为11个单位重量。每辆车只运货一次，卡车j的一次运费为c _j 。假定一辆卡车不能同时给用户A和C二者送货；同样，也不能同时给用户B和D二者送货。

（1）请列出一个整数规划模型表达式，以确定装运全部货物应如何配置卡车，使其运费为最小。

（2）如果卡车j给用户i运货时需收附加费k _ij （同卸货量无关），试述应如何修改这一表达式。

解： （1）设x _ij 表示卡车j对用户i卸货（i＝1，…，5，j＝1，…，4）。

则数学模型为：

（2）收附加费k _ij 相当于固定费用，因原问题不涉及费用，故可令

则上述模型的目标函数变为

约束条件中增加 qFY3JQwAZkVbgHjgvCWY7d9MX+8y9Vspp9wEarHs7+bMzTU5oZHXgbg4wE3ahxj0