第三章整数规划运筹学

第三章整数规划用单纯形法求解线性规划问题，其最优解往往是分数或小数．但对于某些实际问题，常要求全部或部分变量的最优解必须是整数．例如，所求的解是人数，机器台数或工厂个数等，若用分数或小数表示答案就显得不够合理．

在一个线性规划问题中，若要求全部变量取整数值，称为纯整数规划问题．若要求部分变量取整数值，称为混合整数规划问题．这两类问题简称为整数规划．

求解整数规划问题，初看起来好像很简单，比如把带有分数或小数的解进行“收尾”或“去尾”处理就可以了．事实上，这样处理有时行得通，有时却行不通．例如，某公司根据市场需要，用线性规划的方法得到一个方案是；增加甲产品的工厂3.7个，乙产品的工厂1.5个．如果用凑整方法求其解，则有四个近似方案：（4，1），（4，2），（3，1），（3，2），显然，这四个方案相互差别很大．对原线性规划问题来说，它们有的是可行解，有的则不是可行解；或虽是可行解，但不一定是最优解．因此，对求最优整数解的问题，有必要另行研究．然而时至今日，求解整数规划还没有一个很满意的有效的解法．下面介绍几种较为常用的方法

§3.1分枝定界法

设有整数规划问题（A）为：

与它对应的线性规划问题（B）（亦称为松弛问题）为：

显然，问题（A）的可行解集是问题（B）的可行解集的子集．因而，（A）的最优值（B）的最优值．第一步

对线性规划（B）求解，其结果有下列三种情形：（1）（B）无可行解，这时（A）也无可行解，停止计算；（2）（B）有整数最优解，且符合（A）的整数条件，这时（B）的最优解就是（A）的最优解，停止计算；（3）（B）有最优解，而其解不全为整数．这时（B）的最优解不是（A）的可行解．但是，（B）的目标函数最优值（设为），是（A）的最优目标函数值S*的上界（求最小值时，为其下界）．

第二步

分枝与定界．设线性规划问题（B）的最优解为

且其中xj*（j=1，2，…，n）不是整数，则必有

其中[xj*]表示小于xj*的最大整数．由此构造两个约束条件：

将其分别加入问题（B），从而得到(B)的两枝子线性规划问题（B1）和（B2），即

对问题（Bl）和（B2）求解．如果子问题有最优解，但其解不全为整数，则选取最优目标函数值的最大者（若目标函数求最小时，选最小者）作为新的上界；如果子问题中有最优整数解，且其目标函数值小于新的上界，则其值可作为新的下界，（原问题(A)的下界可看作0）记作S．

第三步

剪枝．在继续分枝的过程中，各分枝的最优目标函数值如果有小于S，则称这个分枝已被“查清”，将该枝剪掉，不再计算．因为再算下去不会得到更好的目标函数值．若有目标函数值大于下界S，且不符合整数条件，则重复第二步骤，直到找到S*．

例

求解问题（A）：

解

（1）设（A）的松弛问题为（B0），不受整数约束，利用单纯形法求解（B0），得最优解为：x1=2.25，x2=3.75，且S0=41.25．其可行解域如图所示．显然原问题（A）的可行域是问题（B0）的可行域的一个子集，整数最优解应出现在可行域的整数点上，S0=41.25为其上界．

（2）分枝与定界

因x1，x2都是小数，可任选一个进行分枝．今选x2=3.75，对问题（B0）增加约束条件：x2[3.75]=3和x2[3.75]+1=4,则问题（B0）分解为两个子问题（B1）和（B2）（即两枝）．

求解线性规划问题（B1）和（B2），得到如下最优解：问题（B1）

x1=3，x2=3且s1=39．

问题（B2）x1=1.8，x2=4且s2=41．问题（B1）都是整数解，该问题已经查清．然而（B1）虽都是整数解，但s1<s2．这里s1=39可作为新的下界，s2=41可作为新的上界．值得指出的是，增加了约束条件x2≤3和x2≥4之后，虽然缩小了可行解的范围，但原问题（A）的整数可行解没有变，这是因为在3<x2<4内没有整数解，见2图．

(3)重复步骤（2），继续对问题（B2）进行分解．因为在（B2）中x1=1.8，对问题（B2）增加约束条件：x1[1.8]=1和x1[1.8]+1=2,将问题（B2）再分解为两个子问题（B3）和（B4）：

求解问题（B3）和（B4），得问题（B3）的最优解为：

问题（B4）无可行解，这个子问题也已查清．因为在问题（B3）中有

S1<S3<S2，则作为新的上界．继续对（B3）进行分解，使问题（B3）增加约束条件：x24和x25，则问题（B3）又分解为两个子问题（B5）和（B6）：

求解线性规划问题（B5）和（B6），得到如下最优解：问题（B5）

x1=1，x2=4且S5=37；问题（B6）x1=0，x2=5且S6=40．问题（B5）和（B6）都是整数解，均属查清．但S5<S1（下界），故将该枝剪去；又S1<S6<S3（上界），所以S6为原问题（A）的最优值，它对应的解为其最优解．计算终止．综上所述，求解的全过程可用如下图所示的树形图表示．

§3.2割

平

面

法

割平面法是求解整数规划问题最早提出的一种方法．它的基本思想是：首先不考虑变量是整数的条件，但增加特定的约束条件（称为割平面），使得在原凸可行域中切掉一部分，被切割掉的这部分不包含任何的整数可行解．这样经过有限次的切割，最终可得到某个顶点的坐标恰好是整数，并且是问题的最优解．割平面算法的基本类型有纯整数型和混合型．本节仅讨论纯整数型的割平面算法，它的基本要求是：每一个约束条件的所有系数及右端常数项都必须是整数．下面先讨论线性规划问题存在整数解的必要条件．

§3.30一1规划

在整数规划中，如果所有决策变量xi只限于取0和1两个值，则称它为0一1规划问题．0一1规划的一个典型例子就是所谓“背包问题”：

一个旅行者，为了准备旅行的必备物品，要在背包里装一些最有用的东西．但他最多只能携带b公斤的物品．而每件物品都只能整件携带，于是他给每件物品规定了一定的“价值”，以表示其有用程度．如果共有m件物品，第i件物品重ai公斤，其价值为ci．问题就变成：在携带的物品总重不超过b公斤的条件下，携带哪些物品，可使总价值最大．

首先引进变量xi规定

问题的数学形式可写成

求

(m为正整数)，

满足

这是一个0—1规划问题．

解0—1规划问题的一种明显方法就是穷举法（显枚举法），即检查变量取值0或1的每一种组合，看其是否满足给定的约束条件，然后再比较目标函数值的大小，从而求得最优解．如果变量个数是n，就需要检查2n个所有可能的变量组合．对于变量个数n相当大时，利用穷举法几乎是不可能的．因此希望设计一种方法，使在达到最优解之前，只须检查所有可能的变量组合的一部分即可．这就是隐枚举法（或部分枚举法）．下面举例说明．

这是一个0—1规划问题．

例

求解

解

因为变量x1,x2,x3只取0或1，所以利用二进制加法运算，可得这三个变量的所有可能的组合数组．即（0，0，0），（0，0，1），（0，1，0），（0，l，1），…，（l，1，1）．从中任选一组（一般先取较小的），如：(x1,x2,x3)=（0，0，1），代入目标函数，得S=3．由于我们求的是最大化问题，当然希望S≥3（3是S的下界）．于是，很自然地可增加一个约束条件：4x1-2x2+3x33,

(0)这个条件称为过滤性约束条件．这样原问题的约束条件就变成4个．若用显枚举法，3个变量共有23=8个解，原来3个约束条件，共需24次运算．现在增加了过滤性条件(0)，似乎要增加运算次数，但按下述方法进行，就可减少运算次数．具体计算见表3-7．表3-7x1

x2

x3

目标函数值

是否满足约束

最优值下界

S（0）是否下界

(1)(2)(3)0000

0013

3010-2

0111

1004

41017

1102

1115

于是得最优解：(x1,x2,x3)=（1，0，0）且maxS=4．注意：（1）表中第2列对应着变量X的目标函数值，若以后的约束条件均被满足，则应及时改变最优值的下界，即过滤性条件，然后继续做下去．当某检验条件通不过时，即画“”，以后各列都不必计算．在变量X的所有可能的值都检验过之后，计算表就算完成．表中最后一列最下面那个下界，就是所求的最优值，它所在行对应的X就是所求的最优解．(2)为了简化计算，常把目标函数的系数按递增（不减）的次序排列．如在上例中，改写S为：S=4x1-2x2+3x3=-2x2+3x3+4x1，因为系数-2，3，4递增，变量(x2,x3,x1)也按下述顺序取值：（0，0，0），（0，0，1），（0，1，0）…（1，1，1）．这样，将会使目标函数的最优值较早出现，使以后的计算量得到减少．按此法计算例1，其过程见表3-8．表3-8x2x

3x1

目标函数值

是否满足约束

最优值下界

S（0）

是否下界

(1)(2)(3)0000

00014

40103

0117

100-2

1012

1101

1115

显然，最优解仍是x1=1，

x2=x3=0.且S=4，但计算已得到简化．例题：《公司财务学》齐寅峰，经济科学出版社某公司2000年有六个项目通过了单个项目评估，都是大型项目，投资分两期进行，按照公司长期财务计划，这两期的总投资限额分别为8.5亿和6亿，每个项目的净现值已估算完毕（折现率不尽相同）。另外，由于技术工艺和市场原因，项目ABC为三择一项目，项目B为D的预备项目，项目EF为互斥项目，问该公司如何选择一是投资总净现值最大化？项目投资额净现值2000年2001年A100100150B18050100C200150260D150180200E160120130F500100280资本限额850600建模某城市消防总部将全市划分为11个防火区，设有四个消防站。已知消防站代号及可以覆盖的放火区如表所示。问为保证全市消防的前提下，是否可以减少消防站的个数？消防站覆盖的消防区A1、2、3、4、7、8B1、2、8、9C4、5、6、11D6、7、8、9、10、11§3.4指

派

问

题

1．指派问题的数学模型所谓指派问题是指这样一类问题：有n项任务，恰好有n个人可以分别去完成其中任何一项，但由于任务的性质和每个人的技术专长各不相同，因此，各个人去完成各项不同任务的效率也不一样．于是提出如下问题：应当分派哪个人去完成哪项任务，才能使总的效率最高？先看一个具体例子．

例1某公司有Bl，B2，B3，B4四项不同任务，恰有Al，A2，A3，A4四个人去完成各项不同的任务．由于任务性质及每人的技术水平不同，他们完成各项任务所需时间如表，问怎样才能使这项工程花费的总时数最少？

时间任务B1B2B3B4人员A1215134A21041415A39141613A478119解

设

其中i，j=1，2，3，4．

按照每个人仅承担一项任务的要求，则有约束：

再依每项任务只能有一人承担的要求，则有约束：

问题的目标函数是：

一般地，指派问题的数学模型为：

其中，目标函数的系数

通常，把这些数写成矩阵形式：

C称为系数矩阵或效益矩阵．满足约束条件的可行解也可写成矩阵形式，称为解矩阵．如例1的系数矩阵和解矩阵分别为：

解矩阵中各行各列的元素之和都是12．匈牙利法

基本思想是在效益矩阵的任何行或列中，加上或减去一个常数，使得在不同行不同列中至少有一个为零的元素，从而得到与这些零元素相对应的一个最优分配方案．该方法的理论基础是下述定理．定理如果从效益矩阵C=（cij）的每一行元素中分别减去（或加上）一个常数ai，从每一列分别减去（或加上）一个常数bj，得到一个新的效益矩阵C’=（cij’），其中每个元素cij’=cij-ai-bj

，则以（cij’）为系数矩阵的最优解与以（cij）为系数矩阵的最优解相同．

证

事实上，新的目标函数为

上式表明，新目标函数等于原目标函数减去（或加上）两个常数．因此，当新目标函数达到最小值时，相应地原目标函数也达到最小值．

下面用例1来具体说明匈牙利法的计算步骤．

第一步

从效益矩阵的每行减去各行中的最小元素，再从每列中减去各列的最小元素，得

这里（cij’）称为初始缩减矩阵．把各行各列所减去的数之总和称为缩减量，本题的缩减量为

S=2＋4＋9＋7＋4＋2=28．注意：如果某行（或列）有零元素，就不必再减．

第二步

试制一个指派方案，以寻求最优解．经过第一步变换后，系数矩阵中每行每列都已有了零元素，但需要找出n个独立的零元素，即找出n个位于不同行不同列的零元素来．若能找出，则以这些零元素对应的元素为1，其余为零，便得到一个解矩阵，从而得到最优解．寻找n个独立零元素的方法如下：（1）从第一行开始检查．若某一行只有一个零元素，就对这个零元素打上号，然后划去所在列的其他零元素，记作．

（2）再从第一列开始检查，若某列只有一个零元素，就对这个零元素打上号，（不考虑已划去的零元素）．然后再划去所在行的其他零元素，记作．（3）重（l），（2）两步，直到所有零元素打上号或被划去．

现用例1得到的（cij’）矩阵按上述步骤运算，最后得：

从而得最优解为

这表示A1去完成B4，A2去完成B2，A3去完成B1，A4去完成B3所需总时间最少，这时，minS=c14+c22+c31+c43=28．

注意：（1）如果在矩阵中能得到位于不同行不同列的n(=4)个，那么就完成了求最优解的过程；

（2）如果矩阵中的所有零元素或打上号，或被划去（），而不是每一行都有打号的零元素，那么解题过程还没有完成．如下述例2，这时应转下面第三步．例2求缩减矩阵为（cij’）的分配问题的最优解．

第三步

作复盖所有零元素的最少数量的直线，以确定系数矩阵中最多的独立元素数．具体方法步骤如下：

（1）对没有