—型整数规划与指派问题

1.0-1型整数规划

0-1型整数规划是整数规划的特殊情况，所有的变量都要是0或1（而非任意整数）。实际上，凡是有界变量的整数规划都可以转化为0-1规划问题，因此其具有广泛的应用，多年来一直受到人们重视。0-1变量作为逻辑变量，可以表示系统是否处于某个特定状态，或者决策是否取某特定方案。当问题含有多项要素，每项要素均有两种选择时，可用一组0-1变量来描述。在实际中，0-1变量可以描述开与关、有与无、取与舍等现象所反映的离散变量间的关系，以及相互排斥的约束。因此，0-1型整数规划不仅仅广泛应用于科学技术问题，在经济管理领域也有十分重要的应用。0-1型整数规划非常适合描述和解决工厂选址、线路设计、生产计划安排、背包问题和旅行购物等问题。

0-1型整数规划问题一般有三种解法，即变换法、穷举法和隐枚举法。 目前已有的求解0-1型整数规划的方法一般都属于隐枚举法。本章主要讲解隐枚举法。隐枚举法需要根据目标函数的性质增加一个相应的不等式作为过滤条件，以减少运算次数。为了简化计算，一般还要按目标函数中决策变量系数递增的顺序，重新排列目标函数和约束条件中决策变量的次序。由此，仅仅需要检查变量取值的组合的一部分，就能求到问题的最优解。这也是隐枚举法名称由来的原因，分支定界法也是一种隐枚举法。

在可能的变量组合中，往往仅有部分属于可行解。当变量组合不满足某个约束条件时，不必再去检验其他约束条件是否仍然可行。基于发现的可行解最优目标函数值设计过滤约束，并在计算过程中逐步改进过滤约束。对于最大化问题，可以按照由小到大的顺序排列，对于最小化问题，则相应可以按照由大到小的顺序排列。通过有效减少运算工作量，实现较快地发现最优解的目标。下面我们就举例说明一种解0-1型整数规划的隐枚举法。

例3-7利用隐枚举法求解如下0-1型整数规划问题。

按隐枚举法的求解思路与方法，求解过程可由表3-22表示：

表3-22　隐枚举法求解

续表　3-22

2.指派问题

指派问题是指在满足特定指派要求条件下，使指派方案总体效果最佳。例如：有若干项工作需要分配给若干人来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在若干教室里上课等。指派问题是线性规划问题，是一类特殊的运输问题，也是0-1型整数规划问题。在现实生活中，有各种性质的指派问题，由于指派问题的多样性，有必要定义指派问题的标准形式，以方便系统掌握该类问题的求解思路与基本规律。

指派问题的标准形式是有n个人和n件事，已知第i人做第j件事的费用为cij，要求一个人和事之间一一对应的指派方案，使完成这n件事的总费用最少。在实际问题中，根据cij的具体意义，矩阵C可以是费用矩阵、成本矩阵、时间矩阵等。指派问题的模型如下：

由此，指派问题的数学模型可以描述为：

由于指派问题数学结构的特殊性，可以利用比求解运输问题或0-1型整数规划更简便的方法来求解指派问题，即由匈牙利数学家考尼格证明的匈牙利法。这种方法最初由库恩提出，后经改进而形成，解法基于考尼格给出的一个定理而得名。

指派问题最优解的性质为：如果从系数矩阵的某行或某列中减去一个常数，得到新的系数矩阵代表的指派问题与原问题具有相同的最优解。

基于此性质，匈牙利法的基本思路是：先将系数矩阵的各行分别减去本行的最小元素，再把各列减去本列的最小元素，如果能够得到位于不同行和不同列的n个零元素，则按照零元素的位置做出的分配方案，一定是指派问题的最优解。

匈牙利法求解步骤如下：

在经济管理领域的实际应用中，常常遇到各种非标准形式的指派问题。例如，最大化指派问题、人数和工作数不等的指派问题、特定工人可做几件事的指派问题，以及某件事不能由某人来做的指派问题等。对此，通常的处理方法是将其转化为标准形式，然后利用匈牙利法求解。