第五章整数规划
§1整数规划的数学模型及特点
要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。
其模型为：
Max(或min)z=
s.t
若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。
§5 指派问题
一．指派问题的标准形式及数学模型
在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。
指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。
为了建立标准指派问题的数学模型，引入个0-1变量：
这样，问题的数学模型可写成
（5.1）
s.t （5.3）
其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。
注：○1指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n的运输问题。
○2有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵
C= =（5.5）
为效率矩阵（或价值系数矩阵）。
并称决策变量排成的n×n矩阵
X== （5.6）
为决策变量矩阵。
(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。
其总的费用 z =C⊙X
这里的⊙表示两矩阵对应元素的积，然后相加。
问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵
C=
则
X（1）=，X（2）=
都是指派问题的最优解
例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由
5家建筑公司分别承建。已知建筑公司A i（i=1，2，…5）对新商店B j（1，2，…5）的建造费用的报价（万元）为（i，j=1,2,…5）,见表5-9。商业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？
0-1变量
=
则问题的数学模型为
Min z=4+8+…+10+6
s.t
若看成运输问题，且如上所述，则表5-9为
当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。
二．匈牙利解法原理：
虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn）提出了匈牙利法。
定理1：设指派问题的效率矩阵为C=，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.
证明：设式（5.1）～（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为.则有
==+=+
=+-t=-t·1=Z-t
因此有
Min =min(Z-t)=minZ-t
而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。
推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题有相同的最优解。
证明：结论是显然的。只要反复运用定理1便可得证。
当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵中必然出现一些零元素。设=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i 人来干效率(相对)最高。
定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。
例2:已知
C=
则｛=0，=0，=0，=0｝是一个独立零元素组，=0，=0，=0，=0分别称为独立零元素。｛=0，=0，=0，=0｝也是一个独立零元素组，而｛=0，=0，=0，=0｝就不是一个独立零元素组，因为=0与=0这两个零元素位于同一列中。
根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=1，其余的=0。就可找到指派问题的一个最优解。
就上例中
X（1）=，
就是一个最优解。同理
X（2）=
也是一个最优解。
但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。
定理2效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。
我们不证它，说一下意思：
例3：已知矩阵
C1=，C2=，C3=
分别用最少直线去覆盖各自矩阵中的零元素：
C1=，C2=，C3=
可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。
三．匈牙利法求解步骤：
我们以例题来说明指派问题如何求解：
例4给定效率矩阵
C=
求解该指派问题。
解：ⅰ）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。
C= =
这样得到的新矩阵中，每行每列都必然出现零元素。
ⅱ）用圈0法求出新矩阵中独立零元素。
（1）进行行检验
对进行逐行检验，对每行只有一个未标记的零元素时，用○记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元素用记号×划去。如中第2行、第3行都只有一个未标记的零元素，用○分别将它们圈起。然后用×划去第1列其它未被标记的零元素（第2列没有），见
=
在第i行只有一个零元素=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。
重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。
本题中第1行此时也只有1个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素，再用○圈起，见
=
（2）进行列检验
与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用记号○将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。
这时可能出现以下三种情况：
○1每一行均有圈0出现，圈0的个数m恰好等于n,即m=n.
○2存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。
○3不存在未被标记过的零元素，当圈0的个数m< n.
ⅲ) 进行试指派
若情况○1出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停止计算。
上例中得到后，出现了情况○1，可令=1， =1，=1，=1，其余=0。即为最优指派。
若情况○2出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记○，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况○1或○3，出现情况○1则由上述得到一最优指派，停止计算。
若情况○3出现，则要转入下一步。
ⅳ）：做最少直线覆盖当前所有零元素。
我们还以例12来说明过程：
已知例12指派问题的系数矩阵为：
先对各行元素分别减去本行的最小元素，然后对各列也如此，即
C =
此时，中各行各列都已出现零元素。
为了确定中的独立零元素，对加圈，即
=
由于只有4个独立零元素，少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：
（1）对中所有不含圈0元素的行打√，如第3行。
（2）对打√的行中，所有零元素所在的列打√，如第1列。
（3）对所有打√列中圈0元素所在行打√，如第2行。
（4）重复上述（2），（3）步，直到不能进一步打√为止。
（5）对未打√的每一行划一直线，如第1，3，5行。对已打√的每一列划一纵线，如第1列，既得到覆盖当前0元素的最少直线数。见。
= =
Ⅴ）：对矩阵作进一步变换，以增加0元素。
在未被直线覆盖过的元素中找最小元素，将打√行的各元素减去这个最小元素，将打√裂的各元素加上这个最小元素（以避免打√行中出现负元素），这样就增加了零元素的个数。
如中未被直线覆盖过的元素中，最小元素为==1，对打√的第2，3行各元素都减去2，对打√的第1列各元素都加上1，得到矩阵。
=
Ⅵ）：回到步骤Ⅱ），对已增加了零元素的矩阵，再用圈0法找出独立零元素组。
=
中已有5个独立零元素，故可确定指派问题的最优方案。本例的最优解为
X*=
也就是说，最优指派方案是：让A1B3
A2 B2
A3 B1
A4 B4
A5 B5
这样按排能使总的建造费最少，为z=7＋9＋6＋6＋6=34（万元）
四．一般的指派问题
在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈牙利法求解。
1．最大化的指派问题
其一般形式为
s.t
处理办法：设最大化的指派问题的系数矩阵为C=，m=max｛｝,令
B==，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。
例5：某工厂有4名工人A1，A2，A3，A4，分别操作4台车床B1，B2，B3，B4。每小时单产量
解：C==，m=max｛10,9,8,7,…5,6｝=10,
B=== =
=
中的◎数=n=4, 所以
X=（5。7）
即为最优解。
从而产值最大的分配方案也为（5.7），最大产值为
Z=10＋6＋1＋5=22
2．人数和事数不等的指派问题。
○1若人数<事数，添一些虚拟的“人”，此时这些虚拟的“人”做各件事的费用系数取为0，理解为这些费用实际上不会发生。
○2若人数>事数，添一些虚拟的“事”，此时这些虚拟的“事”被各个人做的费用系数同样也取为0。
解：添加虚拟人A5，构造标准耗时阵：
C= =
所圈0数=4< 5=n,下找最少覆盖0的直线。
=
从未划去的元素中找最小者：｛4，3，7，5，1，4，7，9｝=1。未划去的行减去此最小者1，划去的列加上次最小者1，得。
=
◎个数=n,从而的一最优指派：
=
从而最少耗时为 z=2＋7＋6＋7=22
3.一个人可做几件事的指派问题。
若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。
例6：对例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，让技术力量较强的建筑公司A1、A2、A3来承建。根据实际情况，可以允许每家建筑公司承建一家
或两家商店。求使总费用最少的指派方案。
解：反映投标费用的系数矩阵为：
由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（和，i=1，2，3）。这样，系数矩阵变为：
上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成为标准的指派问题，其系数矩阵为：
C=
C =
的◎数=5< 6=n,下找0元素的最少直线覆盖。
= =
从而得一最优指派：
=
总费用为z=7＋4＋9＋7＋8=35(万元)
4．某事不能由某人去做的指派问题
某事不能由某人去做，可将此人做此时的费用取作足够大的M。
例7：分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：
a). 任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。
b) 其中有一人完成两项，其他人每人完成一项。
解：这是一人数与工作不等的指派问题，若用匈牙利法求解，需作一下处理。
a) 由于任务数大于人数，所以需要有一个虚拟的人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），即戊不能做工作E，其余的假想时间为0，建立的效率矩阵表如下：
C=
由于◎数=4< 5=阶数，下找最少覆盖0的直线
=
m=｛19,18.6.13,1,19,13,22｝=1,第2、4行减去1，第4列加上1得：
=从而得最优指派：
最少的耗时数z=29＋20＋32＋24=105.
b) 思路：方案1：甲，○甲，乙，丙，丁。
方案2：甲，乙，○乙，丙，丁。
方案3：甲，乙，丙，○丙，丁。
方案4：甲，乙，丙，丁，○丁。
方案5：甲，○甲，乙，○乙，丙，○丙，丁，○丁。此为人；而工作：A，B，C，D，E，虚拟工作：F，G，H。
这些思路都比较烦，请看下面的思路：
设有虚拟人戊，它集五人优势为一身。即戊的费用是每人的最低。戊所做的工作即为此项工作的费用最低者的工作。
以下用匈牙利法求解：
C=
=
对加圈确定独立0元素，◎个数=3<5=n,作0元素的最少直线覆盖：
=
在未划去的数中选最小者1，未划取得行都减去1，划去的列都加上1得：
=再圈0且试指派：◎个数=3< 5，再作0元素的最少直线覆盖。从未划取的元素中找最小者4，未划取得行都减去这个4，划去的列都加上这个4，得：
=再圈0试指派，结果为：
其中戊是虚拟人，不能真作，它作C工作是借乙
（此列最小时数26是C所创业绩）优势，应由C来作。即C做两件工作：D，C。
第五章 整数规划 主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。 重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。 要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。 §1 问题的提出 要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。 例1 求解下列整数规划问题 211020m ax x x z += ????? ? ?≥≤+≤+为整数2 1212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为： 96m ax ,0,8.421===z x x 。
用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点 方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ， 最优值为z=90。 由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。 §2 分枝定界法 分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是 A 的最优值 * z 的上界，记为 z ；而A 的任意可行解的目标函数值是* z 的一个下界 z ，采 取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。现举例说明： 例2 求解A 219040m ax x x z += ?????? ?≥≤+≤+为整数 21212121,0 ,7020756 79x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解 =1x 4.81, =2x 1.82, ① ② ③ ④ ⑤
第五章整数规划 1．整数规划的特点 (1)整数规划：决策变量要求取整数的线性规划。 (2)整数规划可分为纯整数规划和混合整数规划。 (3)整数规划的可行域为离散点集。 2．整数规划的建模步骤 整数规划模型的建立几乎与线性规划模型的建立完全一致，只是变量的部分或全体必须限制为整数。 3．求解整数规划的常用方法 1)分支定界法 没有最大化的整数规划问题A，与它相应的线性规划问题为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作，而A的任意可行解的目标函数值将是z*的一个 下界，分支定界法就是将B的可行域分成子区域的方法，逐步减小和增大， 最终求得z*。 将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。 (1)解与整数规划问题A相应的线性规划问题B，可能得到以下几种情况之一： ①B没有可行解，A也没有可行解，停止计算。 ②B有最优解，并符合问题A的整数条件，则此最优解即为A的最优解，停止计算。 ③B有最优解，但不符合A的整数条件，记它的目标函数值为。
(2)用观察法找问题A的一个整数可行解，求得其目标函数值，并记作。 以z*表示问题A的最优目标数值，则≤z*≤。 下面进行迭代。 分支，在B的最优解中任选一个不符合整数条件的变量x i ，其值为b i 。 构造两个约束条件 x j ≤[b j ] ① 和 x j ≥[b j ]+1 ② 其中[b j ]为不超过b j 的最大整数。 将这两个约束条件分别加入问题B，求两个后继规划问题B1和B2。不考虑整数约束条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果。 第一步：先不考虑整数约束，变成一般的线性规划问题，用图解法或单纯形法求其最优解，记为 ) ； 第二步：若求得的最优解，刚好就是整数解，则该整数就是原整数规划的最优解，否则转下步； 第三步：对原问题进行分支寻求整数最优解。 第四步：对上面两个子问题按照线性规划方法求最优解。若某个子问题的解是整数解，则停止该子问题的分支，并且把它的目标值与上一步求出的最优整数解相比较以决定取舍；否则，对该子问题继续进行分支。
第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A & B C D E 甲 9 4 6 8 5 \ 乙 8 5 9 10 6 丙 9 7 3 ' 5 8 丁 4 8 6 9 5 戊 10 ； 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 64 10 154062415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ?? ? 31234311546233 5 3 5? ?? ?? ? ?→ ?? ? ?? ? m=5=n ，得最优解。解矩阵*0001000100X 0000101 00010000?? ? ? ?= ? ? ??? 。
割平面法 求解整数规划问题： Max Z=3x1+2x2 2x1+3x214 4x1+2x218 x1,x20，且为整数 解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。从而有： Max Z=3x1+2x2 2x1+3x2+x3=14 2x1+x2+x4=9 x1,x20，且为整数 利用单纯形法求解，得到最优单纯形表，见表1： 表1 C B X B b 3 2 0 0
j 最优解为：x1=13/4, x2=5/2, Z=59/4 根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1) 将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即： (1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2 把整数及带有整数系数的变量移到方程左
边，分数及带有分数系数的变量称到方程右边，得： x2 - x4-2 =1/2-(1/2x3+1/2x4) (2) 由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。又因为x3,x40，所以必有： 1/2-(1/2x3+1/2x4)<1 由于(2)式右端必为整数，于是有： 1/2-(1/2x3+1/2x4)0 (3) 或 x3+x4 1 (4) 这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有： 2x1+2x211 (5) 从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E，2)成为可行域的一个极点。
第五章 整数规划练习题答案 一. 判断下列说法是否正确 1. 用分枝定界法求解一个极大化的整数规划问题时，任何一个可行整数解的目标函数值是 该问题目标函数值的下界。() 2. 用割平面法求解整数规划时，构造的割平面有可能切去一些不属于最优解的整数解。() 3. 用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值。() 4. 指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。() 二. 设有五项工作要分派给五个工人，每人的作业产值如下表所示，为了使总产值最大，问 应如何分配这五项工作，并求得最大产值。 工作 工人 A B C D E 甲 9 4 6 8 5 乙 8 5 9 10 6 丙 9 7 3 5 8 丁 4 8 6 9 5 戊 10 5 3 6 3 答案： 设原矩阵为A ，因求极大问题，令B=[M-a ij ]，其中M=Max {a ij }=10，则： 16425105 3140 42 13251042510424003B 1 3752102 6410 1540 62 415151 3045 020305 7470574704646111-?????? ? ? ? ? ? ? ? ? ? =→→- ? ? ?- ? ? ? ? ? ??????? --- m 4n 5l m 4 4 21342132432431541545235234 6 4 64 6 4 6=<===? ??? ? ??? ? ? ? ?→→????→?? ? ??? ? ? ? ???? ? ? ? 031023 4003115406020303535?? ? ? ? ? ? ???
第五章整数规划 §1整数规划的数学模型及特点 要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。 其模型为： Max(或min)z= s.t 若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。 §5 指派问题 一．指派问题的标准形式及数学模型 在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。 指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。 为了建立标准指派问题的数学模型，引入个0-1变量： 这样，问题的数学模型可写成 （5.1） s.t （5.3） 其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。 注：○1指派问题是产量（）、销量（）相等，且==1，i，j=1,2,…n的运输问题。 ○2有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵 C= =（5.5） 为效率矩阵（或价值系数矩阵）。 并称决策变量排成的n×n矩阵 X== （5.6） 为决策变量矩阵。 (5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。 其总的费用 z =C⊙X 这里的⊙表示两矩阵对应元素的积，然后相加。 问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1已知效率矩阵 C= 则 X（1）=，X（2）= 都是指派问题的最优解 例12/P-149：某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由
第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择
若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2．…，S 10相应的钻探费用为C 1 ,C 2 ,… C 10，并且井位选择要满足下列限制条件： (1)在s 1，s 2，S 4中至多只能选择两个； （2）在S 5，s 6中至少选择一个；（3）在s 3，s 6，S 7，S 8中至少选择两个。 试建立这个问题的整数规划模型 解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ?? ?==≤++++++++++++=7 ,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 地区1 地区2 地区3 地区4 地区5 地区6 地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0
第五章 整数规划习题 5.1 考虑下列数学模型 )()(m in 2211x f x f z += 且满足约束条件 （1）或101≥x ，或102≥x ； （2）下列各不等式至少有一个成立： ??? ??≥+≥+≥+15 215152212121x x x x x x （3）021=-x x 或5或10 （4）01≥x ，02≥x 其中 )(11x f =?? ?=>+0,0 0,520111x x x 如如 =)(22x f ?? ?=>+0,0 0,612222x x x 如如 将此问题归结为混合整数规划的模型。 解：2211612510m in x y x y z +++= ? ? ?????????????? ????=≥≥=+++++-+-=-≤++-≥+-≥+-≥+?--≥?-≥?≤?≤），，＝（或，）（）（）（；）（11.110;00)4(1 11105503215215152)1(1010102111 1098711109872165462152142132312211i y x x y y y y y y y y y y x x y y y M y x x M y x x M y x x M y x M y x M y x M y x i 5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题 3 3 3221max x x x x z -+=
?? ?==≤++-） ，（或3,2,110332321j x x x x j 解：令=y ???==否则，当,01132x x 故有y x x =32，又21x ，3 1x 分别与1x ，3x 等价，因此题中模型可转换为 31m ax x y x z -+= ? ???? ?? ??-+≤+≤≤≤++-变量均为10,,,1 3 323213 23 2321y x x x y x x x y x y x x x 5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1 要求：（1）装入卫星的仪器装置总体积不超过V ，总质量不超过W ；（2）A 1与A 3中最多安装一件；（3）A 2与A 4中至少安装一件；（4）A 5同A 6或者都安上，或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。 解： j j j x c z ∑==6 1max ??? ?? ?????????????==≥+≤+≤≤∑∑==否则 仪器安装,0,111 654231 6 1 6 1j j j j j j j j A x x x x x x x W x w V x v