分⽀界定法
1．分枝定界法的思想
分枝定界法通过增加附加约束条件，使整数最优解最终成为线性规划的⼀个极点(顶点)，于是整个问题就可使⽤单纯形法到这个整数最优解；对有约束条件的最优化问题（其可⾏解为有限数）的可⾏解空间恰当地进⾏系统搜索，这就是分枝与定界的内容。通常，把全部可⾏解空间反复地分割为越来越⼩的⼦集，称为分枝；并且对每个⼦集内的解集计算⼀个⽬标下界，这称为定界。在每次分枝后，凡是界限不优于已知可⾏解集⽬标值的那些⼦集不再进⼀步分枝，这样，许多⼦集可不予考虑，这称为剪枝。这就是分枝定界法的主要思路。 下⾯通过例⼦说明分枝定界法的步骤。
2．⽤分枝定界法求解整数规划
例1: 某⼚拟购进甲、⼄两类机床⽣产新产品。已知甲、⼄机床进价分别为2万元和3万元；安装占地⾯积分别为4m2和2m2；投后的收益分别为3百元/⽇和2百元/⽇。⼚⽅⽬前仅有资⾦14万元，安装⾯积18m2，为使收益最⼤，⼚⽅应购进甲、⼄机床各多少台？
解：设应购进甲、⼄机床台数分别为x1和x2，对此问题可建⽴整数规划数模如下：
银钎焊（1）去掉约束(4)，⽤图解法求得对应的松弛问题LP0（松弛问题LP0与原模型的区别：仅不含整数约束，⽬标函数与其他约束均同。）的最优解（见图1）。
图1
由图1知，松驰问题的最优解为h点：，Z(0)=14.75
由此可知ILP的最优解为：0≤z* ≤ Z(0)*=14.75, 且必为整数，从⽽可以断⾔： 0≤z* ≤14。因 x1=3.25 ，x2=2.5⾮整数解，故选择⼀个⾮整数变量分枝，这⾥选x1，即对 3 ≤ x1 ≤ 4 进⾏分枝。
（2）对上问题分枝构成两个⼦问题数模LP1和LP2如下：
⼦问题数模 LP1 ⼦问题数模LP2
max Z=3x1+2x2 max z=3x1+2x2
（3）对这两个⼦问题数模⽤图解法求得最优解分别为 (见图1)：
记Z*为当前最好的整数解，则Z*＝Z(2)＝14
（4）由于Z(1)> =14，对⼦问题LP1需继续分枝，选择x2分枝得到⼦问题LP3和LP4如下：
⼦问题数模LP3 ⼦问题数模LP4
max Z=3x1+2x2 max Z=3x1+2x2
（5）对LP3和LP4两个⼦问题数模⽤图解法求得最优解分别为（见2）：
X(3)=(3, 2) T, Z(3)=13
X(4)=(2.5, 3) T, Z(4)=13.5
（6）此时由于所有⼦问题的⽬标值均⼩于或等于Z(2)，故Z* =Z(2)=14。最优解为：
X* =X(2)=(4,1)T , Z * =14
由此可知，例1的最优解是：⼯⼚应购进甲类机床4台，⼄类机床1台，可获最⼤收益为14(百元/⽇)。
3．分枝定界法的⼀般步骤
设有最⼤化的整数规划问题A ，与它相对应的松弛问题为 B。
（1）先不考虑原问题的整数约束，求解相应的松弛问题。⽤图解法或单纯形法求得最优解，记为 。
（2）若求得的最优解 刚好就是整数解，则该整数解就是原整数规划问题的最优解；否则，对原问题进⾏分枝寻求整数最优解。
（3）分枝。根据对变量重要性的了解，在最优解中选择⼀个不符合整数约束条件的xj ，其值为bj ，以[bj]表⽰⼩于bj 的最⼤整数。构造两个约束条件: x≤ [bj]和 x≥[bj]+1分别加⼊原LP问题形成两个⼦问题，因为[bj] 与[bj]+1之间⽆整数，故这两个⼦集内的整数解必定与原可⾏解集合整数解⼀致，这⼀步称为分枝。
（4）定界。⾸先判断各个⼦问题是否存在整数解。若存在，出⽬标函数值最⼤对应的整数解，设为Z*，则A问题的整数解⽬标函数Z≥Z*，这就是定界。⽽且分枝过程中，⼀旦有某个⼦问题Z≥Z*，则令Z*＝Z。
（5）若存在⼤于Z*的⼦问题则需分枝。第（4）步中若不存在整数解，也需继续分枝寻整数解，并从⽬标函数值最⼤对应的⼦问题先分枝。
（6）若所有⼦问题的⽬标值都⼩于等于Z*，则不需继续分枝，Z*所对应的整数解即为最优解。
割平⾯法
1．割平⾯法思想
分枝定界法是对原问题可⾏解域进⾏了切割，切割的⽅法是对取⾮整数解相邻整数作附加约束，这些附加约束从图解的⼏何概念上说，是⼀些相当于切割可⾏解域的超平⾯，它们的特点是与坐标轴平⾏，虽然约束⽅程简单，但⼦问题却由于分枝的增多⽽呈指数增长。为了克服上述缺点，本节介绍的割平⾯法则采⽤另⼀种切割办法，既要切割掉⾮整数解域，⼜不希望对原问题进⾏分枝。
割平⾯法的基础仍然是⽤解线性规划的⽅法去解整数规划问题。⾸先不考虑变量为整数这⼀约束条件。但增加线性约束条件(⽤⼏何术语，称为割平⾯)使得从原可⾏解域中切割掉⼀部分，这部分只包含⾮整数解，但没有切割掉任何整数可⾏解。因此，采⽤割平⾯法的关键是如何到割平⾯约束⽅程，使切割后最终得到这样的可⾏解域，它的⼀个有整数坐标的极点恰好就是问题的最优解（见图1⽰）。
2．割平⾯法的步骤
（1）去掉整数约束，⽤单纯形法求解。若最优解是整数，停⽌计算，否则转下⼀步；
（2）寻求附加约束(割平⾯⽅程)；
① 从最优表中抄下⾮整数解的某个约束⽅程；
② 将该约束⽅程的所有系数和常数分解为整数和正真分数之和；
③ 整数项（包括整系数项和整常数项）归写于⽅程左边，真分数项写于右边；
④ 利⽤整数约束条件求出割平⾯⽅程。
（3）将割平⾯⽅程标准规范化后加到约束⽅程组中求解，如所得最优解仍为⾮整数，则转到第（2）步继续进⾏，直到到最优整数解为⽌。
现举例来说明割平⾯法解题步骤。
例1：求下列整数规划模型：
解：（1）去掉整数约束。如果约束条件系数和右边常数不是整数，则需化约束为整，⽽后才能标准规范化(这是保证所添加的松驰变量均为整数)。如下：
⽤单纯形法迭代得最终表1。
表1
XB x1x2x3x4b
x2011/2-1/25/2
x110-1/43/413/4
-Z00-1/4-5/4-59/4
最优解：X1=13/4，X2=5/2，Z=59/4 为⾮整数解。
（2）寻割平⾯⽅程。从最优表1中抄下⾮整数解的约束⽅程。例如第⼀个约束⽅程：
将①式的所有系数和常数分解为整数和正真分数之和，即：
将上式中的整系数项归写于⽅程左边，真分数项写于右边，即有：
现对②式进⾏分析：考虑整数约束条件，②式左边为整数，右边的(·)内是正数；为保持⽅程平衡，所以②式右边必是负数。因此有：
即有：，③式即为割平⾯⽅程。
对原数模引⼊割平⾯约束，将③式标准规范化（松驰变量x5也必为整数）：加到表1中，⽤对偶单纯形法求解，求解过程⽰于表2。
表2
XB x1x2x3x4x5b
x2011/2-1/205/2
x110-1/43/4013/4
x500[-1/2]-1/21-1/2
-Z00-1/4-5/40-59/4
x2010-112
x11001-1/27/2
x30011-21
Z000-1-1/2-58/4
得最优解为x1=7/2，x2=2，仍为⾮整数，故⼜转⼊第⼆步求割平⾯⽅程。为此从表2中抄下⾮整数解x
1=7/2的约束⽅程为：，按整数、分数归并原则写成：，考虑整数约束条件，上式左边为整数；为保持⽅程平衡，因此上式右边必为负数，有：
④式为割平⾯⽅程。将④式标准规范化：加到表2中，⽤对偶单纯形法求解，求解过程如表3所⽰。得最优解：
x1=4，x2=1，Z=56/4=14，为整数最优解，计算停⽌。
表3
XB x1x2x3x4x5x6b
x2010-1102
x11001-1/207/2
x30011-201
x60000[-1/2]1-1/2
-z000-1-1/20-58/4
x2010-1021
x110010-14
x300110-43
埃及祖玛3
x500001-21
-Z000-10-1-56/4
上述过程中到的两个⽤决策变量表⽰的割平⾯⽅程分别为：
2x1+2x2≤11
x1+x2≤5
它们的切割过程见图1。由图1可知：
①去掉整数约束，求得最优解为(3.25，2.5)，⾮整数解。
②第⼀个割平⾯⽅程：2x1+2x2≤11，得最优解为(3.5，2)，⾮整数解。
③第⼆个割平⾯⽅程：x1+x2≤5，得最优解为(4，1)，整数解。
图1割平⾯寻优
0-1规划和隐枚举法
当决策变量xi的取值仅为0或1时的规划问题称为0-1型整数规划问题。它是整数规划中的特殊情形，应⽤很⼴泛，因此成为整数规划中的⼀个重要分⽀。
0–1整数规划虽然可⽤⼀般求整数规划的⽅法求解。但0–1型整数规划是整数规划的⼀种特例，有⾃⾝的特殊解法――隐枚举法。现举例说明。
1. 0－1规划数学模型
例1：某⼚拟在A，B，C，D，E五个城市中建⽴若⼲产品经销联营点，各处设点都需资⾦、⼈⼒、设备等，需求量以及能提供的利润各处不同，有些点可能亏本，但却能获得贷款和⼈⼒等。假设数据已知，见表1，为使总收益最⼤，问⼚⽅应作何种最优选点决策？
表1
资源城市应投资⾦
（百万元）
应投⼈⼒
（⼈）
应投设备
（套）
sao2
利润
（⼗万元）
A451 4.5
B641 3.8
C121219.5
D-830-2
E1-80-1.5
限制资源20152
解：上述各城市是否被选，可⽤决策变量xj表⽰(j=1,2,…5)，xj=1表⽰被选，否则xj=0，根据已知数据可建数模如下：
每个城市都有可能⼊选和不⼊选，即xj取值有0或1两种状态；有五个变量，这样的0，1组合就共有25=32个。把每种组合列出，代⼊约束⽅程检验是否可⾏，这是⼀项很繁琐的⼯作，并且出可⾏组合后还要代⼊⽬标函数去⽐较得出最优解，因此，⽤枚举法仅对⼀些⼩型问题是可⾏和有效的。当变量个数增多时，组合解个数是按指数规律倍增，⽤枚举法将会⾮常困难。
实际上只要我们按⽬标函数值从优到劣(本例是从⼤到⼩)顺序列出组合，逐个检验其可⾏性，最先满⾜所有约束⽅程的组合就是最优解；⽽劣于最优解的组合即使可⾏，也不⽤去列出和检验，这就相当于把枚举法得出的所有⾮优组合隐去不算了，故称为隐枚举法。
2．隐枚举法求解步骤
（1）变换⽬标函数和约束⽅程组
① 价值系数Cj前的符号统⼀。 在⽬标要求极⼤时，统⼀带负号；求极⼩时统⼀带正号。⽅法是：在不满⾜上述要求时，⽤代⼊⽬标函数。如例1求极⼤，x1，x2，x3前符号不满⾜要求，⽤代⼊⽬标函数和约束⽅程；
② 按∣Cj∣值从⼩到⼤排列决策变量项。上例变换结果如下：
（2）⽤⽬标函数值探索法求最优解
组合⼜满⾜全部约束条件，则它为最优解；否则，按劣于Z0的组合解⽅向探索可⾏解。为此，按公式（1）须由⼩到⼤逐项计算组合解的Σ|Cj|值及其相应的Z值，代⼊约束⽅程组检查可⾏性，如全部满⾜，即为最优解。
⽬标函数值探索法计算过程⽰于表2，得最优解为：x1=1-=1，x2=1-=0，x3=1-=1，x4=0，x5=1，即在A，C，E三个城市中设联营点，可获最⼤收益12.5(⼗万元)。
测井解释表2
分配问题和匈⽛利法
在⽣活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个⼈可承担这些任务。由于每⼈的专
长不同，各⼈完成任务 (或所费时间) 不同，效率也不同。于是产⽣应分派哪个⼈去完成哪项任务，使完成n项任务的总效率最⾼(或所需总时间最短)。这类问题称为分派问题(Assignment Problem)。
1．分派问题数学模型
例1：有A、B、C、D四项任务需分派给甲、⼄、丙、丁四个⼈去做，这四个⼈都能承担上述四项任务，但完成各项任务所需时间如表1所⽰。问应如何分派任务可使完成任务的总⼯时最少？试建⽴基数学模型。
表1
A B C D
平板艺术音响 任务
⼈
甲917167
⼄1271416
丙8171417
丁79119
解：引⼊决策变量xij
指派问题的解矩阵应当是每⾏或每列只能有⼀个元素为1，其余均为 0 的 n 阶⽅阵。如例 1的⼀个解矩阵：
2．匈⽛利法原理
分派问题是0-1规划的特例，也是运输问题的特例。虽然分派问题可⽤整数规划、0-1规划或运输问题的解法去求解，但都很费事。匈⽛利数学家柯尼格（D. Konig）提出了⼀种新颖⽽⼜简便的解法，常称为匈⽛利法。
胡舒立 背景
匈⽛利法是针对⽬标要求极⼩问题提出来的。其基本原理是：为了实现⽬标极⼩，在系数矩阵元素Cij≥0的条件下，如果能使矩阵具有⼀组处于不同⾏⼜不同列的零元素（C’ij＝0）打上括号（），对应该元素的决策变量xij＝1，未打括号元素对应的决策变量xij＝0，那么⽬标函数值Z＝为最⼩，这样的组合解就是最优解。
定理1：从(cij )矩阵的每⾏(或列)减去或加上⼀个常数ui(或vj)构成新矩阵(c′ij)，c′ij= cij±(uI+vj )，则对应(c′ij)的(xij)最优解与原(cij )的最优解等价。
证明：如从新矩阵中得到最优解(xij)，则其⽬标函数值达到极值：其中：K为⼀常数，故当Z‘达到极值时Z也达到极值。所以(xij）也为原矩阵(cij )的最优解。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议