整数规划
主讲：邢延铭
Integer programming
内容总述
§整数规划的数学模型及解的特点
§ 解整数规划的分枝定界法
§ 割平面法
§ 0-1规划及指派问题
§整数规划的数学模型及解的特点
线性规划的决策变量取值可以是任意的非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。
例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。
要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(Integer Programming)。
不考虑整数条件，由余下的目标函数和约束条件构成的规划问题自然数为该IP的松驰问题（slack problem)
全部决策变量的取值都为整数，则称为全整数规划(All IP)；
仅要求部分决策变量的取值为整数，则称为混合整数规划(Mixed IP)；
要求决策变量只能取0或1值，则称为0-1规划(0-1 Programming)。
一、 问题的提出
为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。
“舍入化整”一般是不可行的：
化整后的解有可能成为非可行解；
虽是可行解，却不是最优解。
例1
产品
资源
甲
乙
现有量
A
2
1
9
B
5
7
35
单台利润
6
5
问如何安排甲、乙两产品的产量，使利润为最大。
解：设x1为甲产品的台数，x2为乙产品的台数。
maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1 , x2 ≥0
x1 , x2取整数
不考虑整数约束则是一个线性规划问题，称为原整数规划问题的松弛问题。
不考虑整数约束的最优解：x1 *=28/9≈， x2 * =25/9≈，Z * =293/9
舍入化整
x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 ≤35，非可行解；
x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解；
x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。
例2：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤。
序号
1
2
3
4
5
6
7
物品
食品
氧气
冰镐
绳索
帐篷
相机
设备
重量
5
5
2
6
12
2
4
重要系数
20
15
18
14
8
4
10
解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:
Max Z= 20x1+15x2 +18x3 +14x4
+8x5 +4x6 +10x7
. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6
+4x7 25
xi=1或xi=0 i=1,2,….7
例3.
某服务部门各时段（每2小时为一个时段）需要的服务员人数见下表。按规定，服务员必须连续工作8小时（4个时段）。现在要求安排服务员的工作时间，在各时段服务员数量够用的前提下，服务部门用的总服务员数量最少。
时段
1
2
3
4
5
6
7
8
服务员
数量
10
8
9
11
13
8
5
3
例4 求下列问题：
Max Z=3x1+13x2
+9x2 40
11x1-8x2 82
x1,x2 0,且取整数值
O 1 2 3 4 5 6 7 8 9 10
5 4 3 2 1
x1
x2
I(2,4)
B(,)
A
D
可行域OABD内整数点，放弃整数要求后，最优解B(,) Z0=，而原整数规划最优解I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。
O 1 2 3 4 5 6 7 8 9 10
5 4 3 2 1
x1
x2
I(2,4)
B(,)
A
D
（1）假如能求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。
E
F
G
H
I
J
O 1 2 3 4 5 6 7 8 9 10
5 4 3 2 1
x1
x2
I(2,4)
B(,)
A
D
（2）可行域分成六个互不相交的子问题 P0 P1 P2 P3 P4 P5,
P1最优解I点(2,4),Z1=3*2+13*4=58
P3最优解J点(6,3),Z2==3*6+13*3=57
P5最优解(9,2),Z4=3*9+13*2=53
P1
P3
P5
J(6,3)
从以上的可以看出，假如放弃整数要求后，用单纯形法求得最优解恰好满足整数性要求，则此解也是原整数规划的最优解。
以上描述了目前解整数规划问题的两种基本途径。即
分枝定界法和割平面法。
二、数学模型
整数规划(IP)的一般数学模型:
Max (min) Z = Σcjxj
. Σaijxj bi(i=1,2,…m)
xj 0 且部分或全部是整数
§ 解整数规划的分枝定界法
分枝定界法(Branch and Bound Method)
基本思想：
先求出整数规划相应的线性规划(即不考虑整数限制)的最优解，
若求得的最优解符合整数要求，则这个解就是原整数规划的最优解；
若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。
然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。
定界的含义：
整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。
对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；
对极小化问题来说，相应线性规划的目标函数的最优值是原整数规划目标函数值的下界。
下面我们用一例说明求解步骤
例 maxZ= 6x1 +5 x2
2x1 + x2 ≤9
5x1 +7 x2 ≤35
x1, x2 ≥0
x1, x2取整数
第一步，不考虑变量的整数约束，求相应的LP(问题1)的最优解：
x1=28/9，x2 =25/9，Z1=293/9
第二步，定界过程
这个解不是原整数规划的最优解，这时目标函值Z1=293/9是原整数规划目标函数的上界；因为x1=x2=0是整数规划问题的可行解，所以下界为0。界限一（0，293/9）
第三步，分枝过程
将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件 x1≤ [28/9]=3，x1 ≥ [28/9] +1=4
并将新约束添加到原问题当中去：
问题2：maxZ= 6x1 +5 x2 问题3： maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≥4
x1, x2 ≥0 x1, x2 ≥0
x1, x2取整数 x1, x2取整数
这样就把相应的线性规划的可行域分成两个部分，如下图所示。
•
•
•
•
•
•
•
•
•
•
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1
2
3
1
2
5
3
4
4
求解问题2相应的线性规划的最优解：
x1=3，x2 =20/7，Z2=226/7≈
求解问题3相应的线性规划的最优解：
x1=4，x2 =1，Z3=29
第四步，定界过程
LP3的解满足整数约束，不必再分枝，它的目标函数值是29，大于原有下界0，则新的下界为29；
现有上界为未分枝子问题中目标函数最大值，即为226/7≈。界限二（29，226/7）
LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于现有下界，则应继续分枝。
第五步，分枝过程
将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：
x2≤ [20/7]=2，x2 ≥ [20/7] +1=3
问题4：maxZ= 6x1 +5 x2 问题5： maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤ 3
x2≤2 x2 ≥3
x1, x2 ≥0 x1, x2 ≥0
x1, x2取整数 x1, x2取整数
x2 =2
x2=3
•
•
•
•
•
•
•
•
•
•
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1
2
3
1
2
5
3
4
4
x1=4
x1=3
求解问题4相应的线性规划的最优解：
x1=3，x2 =2，Z4=28
求解问题5相应的线性规划的最优解：
x1=14/5，x2 =3，Z5=159/5≈
第六步，定界过程
LP4的解满足整数约束，不必再分枝，它的目标函数值是28，小于原有下界29，则下界仍为29；
现有上界为未分枝子问题中目标函数最大值，即为159/5。
界限三（29，159/5）
LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于现有下界29，则应继续分枝。
第七步，分枝过程
将不满足整数约束的变量x1进行分枝，构造两个新的约束条件：
x1≤ [14/5]=2，x1≥ [14/5] +1=3
问题6：maxZ= 6x1 +5 x2 问题7： maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1 ≥ 3
x1, x2 ≥0 x1, x2 ≥0
x1, x2取整数 x1, x2取整数
x2 =2
x2=3
•
•
•
•
•
•
•
•
•
•
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1
2
3
1
2
5
3
4
4
x1=4
x1=3
x1=2
求解问题6相应的线性规划的最优解：
x1=2，x2 =25/7，Z6=209/7≈
求解问题7相应的线性规划的最优解：问题7的可行域是一个空集，所以无最优解。
第八步，定界过程
LP7的无最优解，不必再分枝，下界仍为29；
现有上界为未分枝子问题中目标函数最大值，即为209/7。界限四（29，）
LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。
第九步，分枝过程
将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：
x2≤ 3，x2≥ 4
问题8：maxZ= 6x1 +5 x2 问题9： maxZ= 6x1 +5 x2
2x1 + x2 ≤9 2x1 + x2 ≤9
5x1 +7 x2 ≤35 5x1 +7 x2 ≤35
x1≤3 x1 ≤3
x2 ≥3 x2 ≥3
x1≤2 x1≤2
x2≤3 x2 ≥4
x1, x2 ≥0 x1, x2 ≥0
x1, x2取整数 x1, x2取整数
x2=3
•
•
•
•
•
•
•
•
•
•
5x1 +7 x2 =35
2x1 + x2 =9
x1
x2
1
2
3
1
2
5
3
4
4
x1=4
x1=3
x1=2
x2 =2
x2 =4
求解问题8相应的线性规划的最优解：
x1=2，x2 =3，Z8=27
求解问题9相应的线性规划的最优解：
x1=7/5，x2 =4，Z9=142/5≈
第十步，定界过程
LP8的最优解，满足整数约束，不必再分枝，下界仍为29；
现有上界为未分枝子问题中目标函数最大值，即为142/5。界限五（29， 142/5 ）
虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5小于现有下界29，则不再继续分枝。
上界<=下界，得整数规划问题的最优解为下界： x1=4，x2 =1，Z=29
分枝定界过程
x1≤3
x1 ≥4
x2≤2
x2 ≥3
x1≤2
x1 ≥3
x2≤3
x2 ≥4
分枝定界法的计算过程：
在分枝定界法过程中求解问题(Branch)，应有以下情况之一： (A)为整数规划， (B)为松弛问题
①(B)无可行解，则(A)亦无可行解，停止对此问题的计算；
②(B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z*同时是当前问题(A)最优目标值的上界和下界。停止对这个问题的计算；
③(B)有最优解 x 及最优值 z 但不符合整数条件。这时寻求当前问题(A)最优目标值的一个下界 z ＝z ,于是通过以下判断可对此问题进一步计算。
1、对原问题(A)，求解松弛问题(B)。根据上面分析，若出现情况①，②则停。若情况③发生，得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解，那么对应的目标函数值是(A)最优值的一个上界 z¯ 。即得到 z ＜ z* ＜z¯。(注：找(A)问题的可行解往往需要较大的计算量，这时可简单记 z¯＝+ ，而先不必费很大力量去求较好的上界。从以下分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。)，转2，进行以下一般步的迭代；
2、对当前问题进行分枝和定界：
分技：无妨设当前问题为(A)，其松弛问题(B)的最优解不符合整数约束，任取非整数的分量 xr 。构造两个附加约束： xr ≤ [xr] 和 xr ≥ [xr]+1 ，对(A)分别加入这两个约束，可得到两个子问题(A1)和(A2)，显然这两个子问题的可行解集的并是(A)的可行解集；
定界：根据前面分析，对每个当前问题(A)可以通过求解松弛问题(B)，以及找(A)的可行解得到当前问题的上、下界 z¯和 z 。
对一般迭代步，设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI )，i＝1，2，...，n 之和的分解。这里的同层子问题是指每个子问题(AI)都是(A)经过相同分枝次数得到的。
3、比较与剪枝：
对当前子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪枝：
①(B)无可行解；
②(B)的最优解符合整数约束；
③(B)的最优值 z ≥ z¯ 。
通过比较，若子问题不剪枝则返回 2 。
分枝定界法当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界 z¯ 的可行解即原问题的最优解， 算法结束。
分枝定界法是求整数规划的一种常用的有效的方法，既能解决纯整数规划的问题，也能解决混合整数规划的问题。
例 2
求解A
max z=4x1+9x2 ①
9x1+7x2≤56 ②
7x1+20x2≤70 ③ ()
x1，x2≥0 ④
x1，x2整数 ⑤
解为：X1＝4，X2＝2，Z=34
解 先不考虑条件⑤，即解相应的线性规划B,①～④(见图)，得最优解x1=，x2=，z0=356
可见它不符合整数条件⑤。
这时z0是问题A的最优目标函数值z*的上界，记作z0= 。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作 =0，即0≤z*≤356。
分支定界法的解法
首先注意其中一个非整数变量的解，如x1，在问题B的解中x1=。于是对原问题增加两个约束条件 x1≤4，x1≥5
可将原问题分解为两个子问题B1和B2(即两支)，给每支增加一个约束条件，如图5-3所示。这并不影响问题A的可行域，不考虑整数条件解问题B1和B2，称此为第一次迭代。得到最优解为：
图5-3
x1≤4，x1≥5
显然没有得到全部变量是整数的解。因z1＞z2，故将 改为349，那么必存在最优整数解，得到z*，并且0≤z*≤349
继续对问题B1和B2进行分解
因z1＞z2，故先分解B1为两支。增加条件x2≤2者，称为问题B3；增加条件x2≥3者称为问题B4。在图5-3中再舍去x2＞2与x3＜3之间的可行域，
再进行第二次迭代。
继续对问题B2进行分解
解题的过程都列在图5-4中。
图5-4
可见问题B3的解已都是整数，它的目标函数值Z3＝340，可取为 ，而它大于Z4＝327，所有没有必要再分解B4。问题B2的Z2＝341，所有z*可能在340≤ z* ≤341之间有整数解。于是对B2分解，得问题B5，是非整数解，且Z5＝308 小于Z3，问题B6无可行解。于是可以断定：Z3＝ z* ＝340
问题B3的解X1＝4，X2＝2为最优整数解
优点：
(1) 任何模型均可用；
(2) 思路简单、灵活；
(3)速度快；
(4)适合上机。
分枝定界法注意事项：
(1) 分枝变量选择原则：
① 按目标函数系数：选系数绝对值最大者变 量先分。
对目标值升降影响最大。
② 选与整数值相差最大的非整数变量先分枝。
③ 按使用者经验，对各整数变量排定重要性
的优先顺序。
(2) 分枝节点选择：
② 广探法：
选目标函数当前最大值节点，找到的整数
解质量高。慢。
① 深探法(后进先出法)：
最后打开的节点最先选，尽快找到整数解。
整数解质量可能不高。
§ 割平面法
割平面法是求解整数规划的另一种常用方法，它的基本思想仍然是用求解相应的线性规划的方法来求解整数规划。先不考虑变量是整数的条件，求解相应线性规划的最优解，若求得的最优解不满足整数条件，则有规律地增加特定的线性约束条件(在几何上称为割平面)，将原线性规划问题的可行域切割掉一部分，使得被切割掉的这部分只包含非整数的可行解，但没有切割掉任何整数可行解，同时切割后的可行域仍保持其凸性不变。这样一次次切割，直至得到一个整数顶点，恰好就是原整数规划的最优解。
这种方法是1958年由美国学者高莫瑞()提出来的，所以又叫高莫瑞割平面法。
割平面的概念
例5 求解整数规划：
maxZ=3x1+2x2
2x1+3x2≤14
2x1+x2≤9
x1，x2≥0，且为整数
2x1+x2=9
2x1+3x2=14
O 1 2 3 4 5 6 7 x1
X2
7
6
5
4
3
2
1
为最优解: x1=13/4，x2=5/2，Z=59/4
现在设想找到一个割平面，或者说增加一个约束，把原可行域切割掉一部分区域，并保证切割掉的部分不含整数解，使得缩小后的可行域的一个顶点恰好就是原整数规划的最优解。
割平面法的关键就是如何构造这样的约束条件，此约束条件称为高莫瑞约束。尽管这样的约束可能不是唯一的，也可能不是一步就能找到，但根据这一思路迭代下去，最终就能求得原问题的整数最优解。
检验数j
15/2
0
0
1
5/4
-15/2
7/2
1
0
0
1/4
-1/2
3/2
0
1
0
-1/4
3/2
x3
x1
x2
0
2
1
0
0
0
-1/4
-1/2
最优解 :X*=(,,,0,0)T，Z*=
高莫瑞约束
在它的松驰问题当中，如果没有得以整数解，则需要构造高莫瑞约束，对于最末单纯形表中，XBi为对应的线性规划最优解中的一个分数值，相应的约束方程为
由于bi’不是整数，要根据这个方程来构造一个高莫瑞约束，xBi对应的约束方程就称为产生高莫瑞约束的来源行，其构造过程是：把aij’和bi ’都分解为整数部分和分数部分：
是正的真分数或零（0≤fij<1)
例：aij=-5/2则[aij]=-3+1/2
取整
将（2）式代入（1）式得
将（3）式整数部分和分数部分分开写得
因为xBi和xj都必须为整数，所以，上式左端必为整数，那么右端也必须为整数。由于右端项 ，0＜fi＜1，所以右端要为整数就不可能为正，必有：
上式即为构造的高莫瑞约束，加入一个非负的松驰si,高莫瑞约束就化成等式形式
将上述约束并入原线性规划模型中重新求解，或在原线性规划最优单纯形表的基础上增加一行和一列，填入式上式（5）对应系数，形成一个新的单纯形表，用对偶单纯形法求解。如果求得的新的最优解都满足整数要求，那么这个解就是原整数规划的最优解。如果在新的解中还有分数值，那么再构造一个新的高莫瑞约束求解。继续这一步骤，直到求得最优整数解为止。
用割平面方法求解以下IP
引入松驰变量x3,x4,x5,将问题化为标准化形式，用单纯形法解其松驰问题，得最优单纯形表，如下
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
3
-1
0
0
0
13/7
1
0
1/7
0
2/7
9/7
0
1
-2/7
0
3/7
31/7
0
0
-3/7
1
22/7
x1
x2
x4
3
-1
0
0
0
-5/7
0
-3/7
一般来说，最优表中对应于非整数解的任何一行都可选作产生高莫瑞约束的来源行。但据经验，通常选取对应于max{fi}的方程。表中，f1=6/7，f2=2/7，f4=3/7因此选择x1对应的一行作为构造高莫瑞约束的来源行。构造割平面方程:
X1+1/7X3+2/7X5=13/7
所以割平面方程为：-1/7X3 -2/7X5≤ -6/7
引入松驰变量X6，得割平面方程：
-1/7X3 -2/7X5+X6= -6/7
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
X6
3
-1
0
0
0
0
13/7
1
0
1/7
0
2/7
0
9/7
0
1
-2/7
0
3/7
0
31/7
0
0
-3/7
1
22/7
0
x1
x2
x4
X6
3
-1
0
0
0
0
-5/7
0
-3/7
0
-6/7
0
0
-1/7
0
-2/7
1
X1-1=6/7 -1/7X3 -2/7X5
Cj
比
值
CB
XB
b
检验数j
x1
x2
x3
x4
x5
X6
3
-1
0
0
0
0
13/7
1
0
1/7
0
2/7
0
9/7
0
1
-2/7
0
3/7
0
31/7
0
0
-3/7
1
22/7
0
x1
x2
x4
X6
3
-1
0
0
0
0
-5/7
0
-3/7
0
-6/7
0
0
-1/7
0
-2/7
1
0
0
0
-1/4
0
-17/4
检验数j
x1
x2
x3
x5
3
-1
0
0
1
1
0
0
0
0
1
5/4
0
1
0
-1/4
0
-5/4
5/2
0
0
1
-1/2
0
-11/2
7/4
0
0
0
1/4
1
-3/4
1
3
2
X
2
X
1
2
1
5
4
整数点
松弛问题2的最优解
割平面
类似的，通常选取对应于max{fi}的方程。表中，f2=1/4，f3=1/2，f5=3/4因此选择x5对应的一行作为构造高莫瑞约束的来源行。产生的高莫瑞约束为：
-1/4X4 -1/4X6≤ -3/4
引入松驰变量，得
-1/4X4 -1/4X6+X7= -3/4
然后，代入最后一个单纯形表，然后用对偶单纯形法解之，得（课本P130页表5-5）
从表中得到的最优解为（X1，X2，X3，X4，X5，X6，X7）T=（1，2，3，4，1，0，0）T
原整数规划的最优解为：
X1=1，X2=2， maxZ=1
割平面：
1
3
2
X
2
X
1
2
1
5
4
松弛问题3
的最优解
松弛问题2
的最优解
例3 求解
目标函数 max z=x1+x2 ①
约束条件：
-x1+x2≤1 ② 3x1+x2≤4 ③ (5-3) x1，x2≥0 ④
x1，x2 整数 ⑤
解为：x1=1,x2=2,Z=2
在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束：
-x1+x2+x3 =1 ⑥
3x1+x2 +x4=4 ⑦
不考虑条件⑤，用单纯形表解题，见表5-2。
表5-2
从表5-2的最终计算表中，得到非整数的最优解：
x1=3/4，x2=7/4，x3=x4=0，max z=5/2
该松弛问题的最优解不能满足整数最优解的要求。为此考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。就可以得到整数的最优解。
可从最终计算表中得到非整数变量对应的关系式：
为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和
(1+0)x1+(-1+3/4)x3+1/4x4=0+3/4
x2+(3/4)x3+(1/4)x4=1+3/4
然后将整数部分与分数部分分开，移到等式左右两边，得到：
现考虑整数条件⑤
要求x1、x2都是非负整数，于是由条件⑥、⑦可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在等式右边的( )内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件⑤可由下式所代替；
即 -3x3-x4≤-3 ⑧
这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。
引入松弛变量x5，得到等式
-3x3-x4+x5=-3
将这新的约束方程加到表5-2的最终计算表，得表5-3。
表5-3
将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。
用割平面方法求解：
X1=4
X2=1
Z=14
0—1规划问题
某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。
例:600万元投资5个项目，求利润最大的方案？
项目
投资额
纯利润
约束条件
210
160
1 只选1项
300
210
2 之只选1项
150
60
3选必先选
130
80
260
180
例解：
0 当项目未被选中
1 当项目被选中
max Z=160x1+210x2+60x3+80x4+180x5
210x1+300x2+150x3+130x4+260x5 ≤ 600 X1+x2+x3=1 X3+x4=1 x5 ≤ x1 Xj=0或1 j=1，2,…,5
建模：设xj=
例：含有相互排斥的约束条件的问题
设工序B的每周工时约束条件为
+≤150
现在假设工序B还有一种新的加工方式，相应的每周工时约束变成：
+≤120
如果工序B只能从两种加工方式中选择一种，那么就成为两个相互排斥的约束条件。
现在我们怎样才能把其统一为一个模型中呢？
于是相互排斥的约束条件可用下列两个约束条件统一起来：
二、0-1规划的解法
求解0－1规划时最容易想到的方法就是穷举法，即检查决策变量取值为0或1的每一种组合是否满足给定的约束条件，并比较其目标函数值以求得最优解。如果变量个数为n时，其取值为0或1的组合数就是2n个。当变量个数n较大时，这种组合数就会变的很大，完全穷举几乎是不可能的。因此，人们设计了一种特殊算法，称为隐枚举法。
隐枚举法的基本思想是：先用试算办法给出一个可行解，代入目标函数中求得一个目标值，以此值为右端项与目标函数构成一个新的约束条件，称之为过滤条件。
按一定次序列出所有的解，对每一个解，首先代入过滤条件进行试算，若不满足过滤条件，即该解不优于现有的可行解，无须代入其它约束条件，淘汰；若满足过滤条件，则依次通过约束条件进行试算，若有一个约束条件不满足，此解不是可行解，淘汰；若满足过滤条件，同时又满足所有约束条件，则此解为当前最优解，以其目标函数值取代过滤条件的右端项，构成新的过滤条件，继续试算，直到所有的解检查完毕。这种方法首先通过过滤条件淘汰了非优解，至于其是否可行已不重要，故减少了计算量。
例解
增加过滤条件：160x1+210x2+60x3+80x4+180x5 ≥ 240
Z值
（1，0，0，1，0）
240
（1，1，1，1，1）
X
（1，1，1，1，0）
X
（1，1，1，0，1）
X
（1，1，1，0，0）
X
（1，1，0，1，1）
X
（1，1，0，1，0）
X
（1，1，0，0，1）
X
（1，1，0，0，0）
X
（1，0，1，1，1）
X
X
（1，0，1，1，0）
X
（1，0，0，1，1）
420
………..
例：maxZ = 3x1 -2x2+5x3
x1 +2x2 - x3 2 ①
x1 +4x2 +x3 4 ②
x1 + x2 3 ③
4x2+x3 6 ④
x1 , x2 , x3为0或1
解：观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3
过滤条件：3x1 - 2x2+5x3 3
解(x1 x2 x3 ) 目标值大小 ① ② ③ ④ 当前最好值
(0 ,0 ,0) 0 < Z0=3
(0 ,0 ,1) 5 > Z0=5
(0 ,1 ,0) -2 <
(0 ,1 ,1) 3 <
(1 ,0 ,0) 3 <
(1 ,0 ,1) 8 > Z0=8
(1 ,1 ,0) 1 <
(1 ,1 ,1) 6 <
最优解 x = (1 ,0 ,1 )T Z=8
指派问题
在实际工作中常常会遇到这样的问题：有n项不同的任务，需要n个人分别去完成其中一项，但由于任务的性质和各人的专长不同，因此，各人去完成不同任务的效率(或花费的时间等)也就不同。现在的问题是，应指派哪个人去完成哪项任务，使总的效率最高或花费的总时间最少。这类问题通常称为指派问题或分配问题(AssignmentProblem)。
例 甲、乙、丙、丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高？
任务
人 时间
A B C D
甲
乙
丙
丁
3 5 9 4
6 7 5 4
2 5 8 5
8 2 6 1
指派问题的匈牙利法
根据指派问题的特点，匈牙利数学家狄考尼格()提出了更为简便的解法，通常称为匈牙利法。
匈牙利法的基本思想就是变换价值系数矩阵的行或列，使得在每一行(列)中至少有一个为零的元素，经过多次变换使得在不同行不同列中至少有一个零元素，与这些零元素相对应的指派方案就是最优方案。这种方法的理论基础是依据以下性质。
指派问题最优解的性质：如果从系数矩阵［cij］的一行(列)各元素分别减去该行(列)中的最小元素，得到一个新矩阵［bij］，则以［bij］为系数矩阵的指派问题的最优解［xij］和原问题的最优解相同。
这个性质成立的理由也是明显的，因为解［xij］的一行(或列)元素中只能有一个是1，如果从［cij］的第i行(或列)元素各减去一个常数k，那么使目标函数Z也减去k，从而Z和Zb=Z-k最优解当然也是相同的。
例解
第一步，变换系数矩阵，使各行各列中都出现0元素。变换方法如下：
(1)将系数矩阵的每行各元素减去该行的最小元素；
(2)将系数矩阵的每列各元素减去该列的最小元素。
-3
-4
-2
-1
-1 -1
第二步，试求最优解。
经过上述变换后，矩阵的每行每列都有了0元素，但最终目标是要找出n个位于不同行不同列的0元素。
其方法是：从具有0元素最少的行(列)开始圈0，对已圈0元素上标记符号○，并划去与它同行同列上的其它0元素，表示该行代表的人已指派去完成该列代表的任务，避免再进行指派。重复检查各行，已划去的0不能再作标记。如果能标出n个0元素恰好在不同行不同列，那么就完成了求最优解的过程。令所得到的这n个0元素对应的xij=1，并令其余的xij=0，就是原问题的最优解。如果这样标记出的元素不够n个，说明没有得到最优解，需要继续进行改进。
第三步，用最少的直线覆盖当前所有0元素。为此：
(1)对不含 的行打√号；
(2)对已打√ 号的行中含有0元素的列打√ 号；
(3)再对已打√ 号的列中有
的行打√号；
(4)重复(2)、(3)直到找不到出新的可打√ 号的行列为止；
(5)对没有打√的行画横线，对所有打√号的列画纵线，这样就可得到能覆盖所有零元素的最少的直线集合。
0
0
√
√
√
第四步，对画线的矩阵进行变换，以增加0元素。
(1)对未被直线覆盖的所有元素减去其中的最小元素，便得到新的0元素。
(2)对纵、横直线交叉处的各元素都加上这个最小元素。这两步实际等价于对打√号行的各元素都减去这个最小元素，对打√号列的各元素都加上这个最小元素，以保证原来的0元素仍为0。
√
√
√
第五步，对得到的新矩阵执行第二步，对各行进行检查和标记，结果如下：
至此，恰好得到4个位于不同行不同列的0元素，已得到最优解，最优解的矩阵为
所以
特殊指派问题
1、人数和事数不相等的指派问题
2、一个人可做几件事的指派问题
3、某一事不能由某人做的指派问题
4、最大化指派问题
人数和工作数不等的指派问题
一个人可做几项工作的指派问题
A1可同时做三项工作
某项工作一定不能由某人做的指派问题
A1不能做B4;
A3不能做B3
最大化指派问题
最大化指派问题
最大值
最小化指派问题
本章小结
End
