运筹学课件：第5章 整数规划

《运筹学课件：第5章 整数规划》由会员分享，可在线阅读，更多相关《运筹学课件：第5章 整数规划（111页珍藏版）》请在金锄头文库上搜索。

1、-1-China University of Mining and Technology运筹学 Chapter5 整数整数规划规划 ( Integer Programming )本章主要内容：本章主要内容：本章主要内容：本章主要内容：整数规划的特点及应用整数规划的特点及应用分支定界法分支定界法分配问题与匈牙利法分配问题与匈牙利法-2-China University of Mining and Technology运筹学 学习要点：学习要点：1.掌握一般整数规划问题概念及模型结构；掌握一般整数规划问题概念及模型结构； 2.能够用分支定界法求解一般整数规划问题；能够用分支定界法求解一般整数规划问

2、题； 3.掌握整数规划的求解方法：分枝定界法，割平面掌握整数规划的求解方法：分枝定界法，割平面 法，匈牙利法。法，匈牙利法。 -3-China University of Mining and Technology运筹学 5.1 整数规划问题 及其数学模型-4-China University of Mining and Technology运筹学 整数规划（简称：整数规划（简称：整数规划（简称：整数规划（简称：IPIP） 要求一部分或全部决策变量要求一部分或全部决策变量取整数值取整数值取整数值取整数值的规划问题称为整的规划问题称为整数规划。数规划。 不考虑整数条件，由余下的目标函数和约束条件

3、构成不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该的规划问题称为该整数规划问题的松弛问题整数规划问题的松弛问题整数规划问题的松弛问题整数规划问题的松弛问题。若该松弛问题。若该松弛问题是一个线性规划，则称该整数规划为是一个线性规划，则称该整数规划为整数线性规划整数线性规划整数线性规划整数线性规划。整数线性规划数学模型的一般形式：整数线性规划数学模型的一般形式：整数规划问题整数规划问题-5-China University of Mining and Technology运筹学 整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类：整数线性规划问题的种类： 纯整数

4、线性规划：指全部决策变量都必须取整数值的整数线纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。性规划。 混合整数线性规划：决策变量中有一部分必须取整数值，另混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值型整数线性规划：决策变量只能取值0或或1的整数线性规划。的整数线性规划。整数规划问题整数规划问题-6-China University of Mining and Technology运筹学 整数规划的典型例子整数规划的典型例子整数规划的典型例子整数规划的典型例子 工

5、工 厂厂 A1和和A2生生产产某某种种物物资资。由由于于该该种种物物资资供供不不应应求求，故故需需要要再再建建一一家家工工厂厂。相相应应的的建建厂厂方方案案有有 A3和和A4两两个个。这这种种物物资资的的需需求求地地有有B1,B2,B3,B4四四个个。各各工工厂厂年年生生产产能能力力、各各地地年年需需求求量量、各各厂厂至至各各需需求求地的单位物资运费地的单位物资运费cij，见下表：，见下表：B1B2B3B4年生产能力年生产能力A12934400A28357600A37612200A44525200年需求量年需求量350400300150工厂工厂A3或或A4开工后，每年的生产费用估计分别为开工后

6、，每年的生产费用估计分别为1200万或万或1500万元。万元。现要决定应该建设工厂现要决定应该建设工厂A3还是还是A4，才能使今后每年的总费用最少。，才能使今后每年的总费用最少。整数规划问题整数规划问题-7-China University of Mining and Technology运筹学 解：这是一个物资运输问题，特点是事先不能确定应该建解：这是一个物资运输问题，特点是事先不能确定应该建A3还是还是A4中哪一个，因而不知道新厂投产后的实际生产物资。中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入为此，引入0-1变量：变量：再设再设xij为由为由Ai运往运往Bj的物资数量，单位为

7、千吨；的物资数量，单位为千吨；z表示总费用，表示总费用，单位万元。单位万元。则该规划问题的数学模型可以表示为：则该规划问题的数学模型可以表示为：整数规划问题整数规划问题-8-China University of Mining and Technology运筹学 混合整数规划问题混合整数规划问题B1B2B3B4年生产年生产能力能力A12934400A28357600A37612200A44525200年需年需求量求量350400300150整数规划问题整数规划问题-9-China University of Mining and Technology运筹学 现有资金总额为现有资金总额为B。可供

8、选择的投资项目有。可供选择的投资项目有n个，项目个，项目j所需投资额和预期收益分别为所需投资额和预期收益分别为aj和和cj（j1,2,.,n），此外由），此外由于种种原因，有三个附加条件：于种种原因，有三个附加条件：若选择项目若选择项目1，就必须同时选择项目，就必须同时选择项目2，反之不一定，反之不一定;项目项目3和和4中至少选择一个；中至少选择一个；项目项目5,6,7中恰好选择中恰好选择2个。个。应该怎样选择投资项目，才能使总预期收益最大。应该怎样选择投资项目，才能使总预期收益最大。整数规划问题整数规划问题-10-China University of Mining and Technolo

9、gy运筹学 解：对每个投资项目都有被选择和不被选择两种可能，因此分解：对每个投资项目都有被选择和不被选择两种可能，因此分别用别用0和和1表示，令表示，令xj表示第表示第j个项目的决策选择，记为：个项目的决策选择，记为：投资问题可以表示为：投资问题可以表示为：整数规划问题整数规划问题-11-China University of Mining and Technology运筹学 指派问题或分配问题。人事部门欲安排四人到四个不同指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，

10、如何安排他们的工作使总成绩最好。（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088整数规划问题整数规划问题-12-China University of Mining and Technology运筹学 设设 数学模型如下：数学模型如下：要求每人做一项工作，约束条件为：要求每人做一项工作，约束条件为： 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088整数规划问题整数规划问题-13-China University of Mining

11、 and Technology运筹学 每项工作只能安排一人，约束条件为：每项工作只能安排一人，约束条件为：变量约束：变量约束： 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088整数规划问题整数规划问题-14-China University of Mining and Technology运筹学 整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征：整数规划问题解的特征： 整数规划问题的可行解集合是它松弛问题可行解集合的一个整数规划问题的可行解集合是它松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，

12、因子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。而不一定仍为可行解。 整数规划问题的可行解一定是它的松弛问题的可行解（反之整数规划问题的可行解一定是它的松弛问题的可行解（反之不一定），但其最优解的目标函数值不会优于后者最优解的目不一定），但其最优解的目标函数值不会优于后者最优解的目标函数值。标函数值。整数规划问题整数规划问题-15-China University of Mining and Technology运筹学 设整数规划问题如下设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。首先不考虑整数约束，得到线性规划问题（一般称为松弛问题

13、）。例例1整数规划问题整数规划问题-16-China University of Mining and Technology运筹学 用图解法求出最优解为：用图解法求出最优解为：x13/2, x2 = 10/3，且，且有有Z = 29/6 现求整数解现求整数解(最优解最优解):如用舍入取如用舍入取整法可得到整法可得到4个点即个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能。显然，它们都不可能是整数规划的最优解。是整数规划的最优解。x1x233(3/2,10/3) 按整数规划约束条件，其可行按整数规划约束条件，其可行解肯定在线性规划问题的可行域内解肯定在线性规划问题的可行域

14、内且为整数点。故整数规划问题的可且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。行解集是一个有限集，如右图所示。其中其中(2,2),(3,1)点的目标函数值最点的目标函数值最大，即为大，即为Z=4。整数规划问题整数规划问题-17-China University of Mining and Technology运筹学 整数规划问题的求解方法：整数规划问题的求解方法： 分支定界法和割平面法分支定界法和割平面法 匈牙利法（指派问题）匈牙利法（指派问题）整数规划问题整数规划问题-19-China University of Mining and Technology运筹学 5.2 分枝

15、定界法-20-China University of Mining and Technology运筹学 直接通过枚举法求整数最优解毫无实用价值。直接通过枚举法求整数最优解毫无实用价值。分枝定界法是一种分枝定界法是一种隐枚举法隐枚举法或或部分枚举法部分枚举法，它不是一种有效算，它不是一种有效算法，是枚举法基础上的改进。它是一种法，是枚举法基础上的改进。它是一种“巧妙巧妙”地枚举地枚举整数规整数规划问题的可行解的思想来设计算法的，其关键步骤是划问题的可行解的思想来设计算法的，其关键步骤是分枝和定分枝和定分枝和定分枝和定界界界界。分枝定界法可用于解纯整数或混合的整数规划问题分枝定界法可用于解纯整数或

16、混合的整数规划问题。本世纪六十年代初由本世纪六十年代初由Land Doig 和和Dakin等人提出。由于这种等人提出。由于这种方法灵活且便于用计算机求解，所以现在它是解方法灵活且便于用计算机求解，所以现在它是解整数规划的主整数规划的主整数规划的主整数规划的主要方法要方法要方法要方法。分分 枝枝 定定 界界 法法-21-China University of Mining and Technology运筹学 1）求整数规划的松弛问题最优解；）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则否则转下一步；转

17、下一步；2）分支与定界：分支与定界：分支与定界：分支与定界： 任意选一个非整数解的变量任意选一个非整数解的变量xi，在松弛问题中加上约束：，在松弛问题中加上约束：xixi 和和 xixi+1组成两个新的松弛问题，称为分枝组成两个新的松弛问题，称为分枝。 新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值检查所有分枝的解及目标函数值，若某分枝的解是整数并且目

18、标函数值大于（大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，整数解的目标值，需要继续分枝，再检查，直到得到最优解。直到得到最优解。分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分支定界法的解题步骤：分分 枝枝 定定 界界 法法-22-China University of Mining and Technology运筹学 用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题解：首先去掉整数约束，变成

19、一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题(原整数规划原整数规划问题的松驰问题问题的松驰问题)LPIP例例2分分 枝枝 定定 界界 法法-23-China University of Mining and Technology运筹学 用图解法求松弛问题的最优解，如图所示。用图解法求松弛问题的最优解，如图所示。x1x23(18/11,40/11)21123x118/11, x2 =40/11Z=218/11(19.8)即即Z 也是也是IP最小值的下限最小值的下限对对 于于 x1 18/111.64，取值取值x1 1， x1 2对对 于于 x2 =40/11 3.64，取值取值x2

20、 3 ，x2 4先将（先将（LP）划分为）划分为（LP1）和（）和（LP2）,取取x1 1, x1 2分分 枝枝 定定 界界 法法-24-China University of Mining and Technology运筹学 分支：分支：分别求出（分别求出（LP1）和（）和（LP2）的最优解。）的最优解。分分 枝枝 定定 界界 法法-25-China University of Mining and Technology运筹学 先求先求LP1，如图所示。，如图所示。此时在此时在B点取得最优解。点取得最优解。x11, x2 =3, Z(1)16找到整数解，问题已探找到整数解，问题已探明，此枝停

21、止计算。明，此枝停止计算。x1x233(18/11,40/11)11BAC同理求同理求LP2，如图所示。，如图所示。在在C 点取得最优解。即点取得最优解。即:x12, x2 =10/3, Z(2)56/318.7 Z(2) Z(1)16 原问题有比原问题有比16更小的最更小的最优解，但优解，但 x2 不是整数，故不是整数，故继续分支。继续分支。分分 枝枝 定定 界界 法法-26-China University of Mining and Technology运筹学 在在IP2中分别再加入条件：中分别再加入条件： x23, x24 得下式两支：得下式两支：分别求出分别求出LP21和和LP22的

22、最优解的最优解分分 枝枝 定定 界界 法法-27-China University of Mining and Technology运筹学 x1x233(18/11,40/11)11BACD先求先求LP21,如图所示。此时如图所示。此时D 在点取得最优解。在点取得最优解。即即 x112/52.4, x2 =3, Z(21)-87/5-17.4 Z(211) 如对如对LP212继续分解，其最小继续分解，其最小值也不会低于值也不会低于15.5 ，问题探，问题探明明,剪枝。剪枝。分分 枝枝 定定 界界 法法-30-China University of Mining and Technology运筹

23、学 原整数规划问题的最优原整数规划问题的最优解为解为: x1=2, x2 =3, Z* =17以上的求解过程可以用以上的求解过程可以用一个树形图表示如右：一个树形图表示如右：LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=12/5, x2=3Z(21) 17.4LP22无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13分分 枝枝 定定 界界 法法-31-China Univer

24、sity of Mining and Technology运筹学 用分枝定界法求解用分枝定界法求解解解: 先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）用图解法得到最优解用图解法得到最优解X(3.57,7.14)，Z0=35.7,如下图所示。如下图所示。例例3分分 枝枝 定定 界界 法法-32-China University of Mining and Technology运筹学 1010松弛问题松弛问题LP0的最优解的最优解X=(3.57,7.14)，Z0=35.7x1x2oABC分分 枝枝 定定 界界 法法-33-China University of Mining and T

25、echnology运筹学 10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5分分 枝枝 定定 界界 法法-34-China University of Mining and Technology运筹学 10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336分分 枝枝 定定 界界 法法-35-China University of Mining and Technology运筹学 10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355

26、LP212分分 枝枝 定定 界界 法法-36-China University of Mining and Technology运筹学 上述分枝过程可用下图表示：上述分枝过程可用下图表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6) Z1=34.8LP2:X=(4,6.5) Z2=35.5x13x14LP21:X=(4.33,6) Z21=35.33x26LP211:X=(4,6) Z211=34LP212:X=(5,5) Z212=35x14x15LP22无可行解无可行解x27分分 枝枝 定定 界界 法法-44-China University of Mini

27、ng and Technology运筹学 分分枝枝给定整数规划问题给定整数规划问题IP去掉去掉“X为整数向量为整数向量”的约的约束束,得到相应的线性规划问得到相应的线性规划问题题P0分分 枝枝 定定 界界 法法-45-China University of Mining and Technology运筹学 若若 不满足整数要求，设不满足整数要求，设分量分量 不是整数，则按照不是整数，则按照（1）相应子问题）相应子问题Pi的最优的最优解是整数解；解是整数解；（2）相应子问题）相应子问题Pi无可行解无可行解。此时称点此时称点Pi为分枝数的为分枝数的树叶树叶。直到问直到问题题Pi的解是下面两的解是下

28、面两种情况之一而结束种情况之一而结束:分分枝枝将将P2又分解为问题又分解为问题P3和和P4，如此继续下去。如此继续下去。分分 枝枝 定定 界界 法法-46-China University of Mining and Technology运筹学 定界：定界：注：一般是选择不符合整数要求的最小的变量进行分枝注：一般是选择不符合整数要求的最小的变量进行分枝.分分 枝枝 定定 界界 法法-47-China University of Mining and Technology运筹学 5.3 割平面法-48-China University of Mining and Technology运筹学 割平

29、面法是求解整数规划的最早提出的一个方法。割平面法是求解整数规划的最早提出的一个方法。基本思想基本思想是：首先利用单纯形法（或者其它方法）是：首先利用单纯形法（或者其它方法）求解求解整数整数规划的规划的松弛线性规划松弛线性规划；经过判断，如果达不到变量的整数条件，；经过判断，如果达不到变量的整数条件，则则针对某一个非整变量增加特定割平面针对某一个非整变量增加特定割平面针对某一个非整变量增加特定割平面针对某一个非整变量增加特定割平面，把，把LP问题中对该变量问题中对该变量的非整数部分给去除掉，保留了全部有整数解的部分，同时经的非整数部分给去除掉，保留了全部有整数解的部分，同时经过切割后的可行域其凸

30、性质不改变。过切割后的可行域其凸性质不改变。逐次反复上面的过程，只要整数规划问题有最优整数解，则逐次反复上面的过程，只要整数规划问题有最优整数解，则必定可以在经过必定可以在经过若干次的切割后若干次的切割后若干次的切割后若干次的切割后的凸可行域的顶点中找到最优的凸可行域的顶点中找到最优解。解。割割 平平 面面 法法-49-China University of Mining and Technology运筹学 割平面法在割平面法在1958年由高莫瑞年由高莫瑞(R.E.Gomory)首先提出，故又称首先提出，故又称Gomory割平面法。割平面法。在割平面法中每次增加的用于在割平面法中每次增加的用于

31、“切割切割”的线性约束称为割的线性约束称为割平面约束或平面约束或Gomory约束。约束。构造割平面约束的方法很多，介绍最常用的一种，它可以从构造割平面约束的方法很多，介绍最常用的一种，它可以从相应线性规划的最终单纯形表中直接产生相应线性规划的最终单纯形表中直接产生。实际解题时，经验表明若从最优单纯形表中选择具有最大小实际解题时，经验表明若从最优单纯形表中选择具有最大小(分分)数部分的非整分量所在行构造割平面约束，往往可以提高数部分的非整分量所在行构造割平面约束，往往可以提高“切割切割”效果，减少效果，减少“切割切割”次数。次数。割割 平平 面面 法法-50-China University o

32、f Mining and Technology运筹学 利用割平面的思想求解下面的规划问题利用割平面的思想求解下面的规划问题例例1割割 平平 面面 法法-51-China University of Mining and Technology运筹学 解：将约束条件的系数化整；去掉解：将约束条件的系数化整；去掉“x1, x2是整数是整数”的条件，的条件，得到一个线性规划的标准型（得到一个线性规划的标准型（LP1）为：为：利用单纯形法求解这个线性规划问题，得出最终单纯形表：利用单纯形法求解这个线性规划问题，得出最终单纯形表： 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0

33、1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4割割 平平 面面 法法-52-China University of Mining and Technology运筹学 最优解不是整数解，由最终表得到变量之间的关系：最优解不是整数解，由最终表得到变量之间的关系： 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4将上面的约束条件当中的变量和系数改写成将上面的约束条件当中的变量和系数改写成整数整数与与非负真分数非负真分数的和的和把整数部分放在左边，把整数部分放在左边，

34、非整数部分放在右边。非整数部分放在右边。割割 平平 面面 法法-53-China University of Mining and Technology运筹学 下面增加割平面下面增加割平面，选真分数最大的一个选真分数最大的一个由于上式左端是整数，因此右端也应是整数，由于变量都是由于上式左端是整数，因此右端也应是整数，由于变量都是不小于不小于0的整数，所以上式右端必是一个不大于的整数，所以上式右端必是一个不大于0.5 的整数，的整数，即即称这个不等式为一个称这个不等式为一个割平面。割平面。割割 平平 面面 法法-54-China University of Mining and Technolo

35、gy运筹学 引入一个松弛变量，化割平面为：引入一个松弛变量，化割平面为：将它作为一个新增加的约束条件加入线性规划将它作为一个新增加的约束条件加入线性规划LPLP1 1中得中得到一个新的到一个新的线性规划线性规划LPLP2 2 ；或者直接反映到或者直接反映到LPLP1 1的最终单纯形表中，得的最终单纯形表中，得LPLP2 2单纯形表单纯形表：割平面的处理割平面的处理：割割 平平 面面 法法-55-China University of Mining and Technology运筹学 LP2 的单纯形表：的单纯形表： 3 2 0 0 0 x1 x2 x3 x4 x5x2x1x55/213/4-1

36、/2 0 1 1/2 -1/2 0 1 0 -1/4 3/4 0 0 0 -1/2 -1/2 1 0 0 -1/4 -5/4 0 3 2 0 0 x1 x2 x3 x4 x2 x1 2.5 3.25 0 1 1/2 -1/2 1 0 -1/4 3/4 j 0 0 -1/4 -5/4LP1 ：LP2 ：割割 平平 面面 法法-56-China University of Mining and Technology运筹学 3 2 0 0 0 x1 x2 x3 x4 x5 j 0 0 -1/4 -5/4 0x2x1x32 7/21 0 1 0 -1 1 1 0 0 1 -1/2 0 0 1 1 -2

37、 j 0 0 0 -1 -1/2由于不是整数解，找出不满足条件的基变量由于不是整数解，找出不满足条件的基变量 x1.用对偶单纯型法求解：用对偶单纯型法求解：割割 平平 面面 法法-57-China University of Mining and Technology运筹学 将它作为一个新增加的约束加到线性规划将它作为一个新增加的约束加到线性规划LP2中又得一个线性中又得一个线性规划规划LP3 构造线性规划构造线性规划LP2的割平面的割平面割割 平平 面面 法法-58-China University of Mining and Technology运筹学 LP3 ：LP3的单纯形表：的单纯形

38、表： 3 2 0 0 0 0 x1 x2 x3 x4 x5 x6x2x1x3x6 2 7/2 1 -1/2 0 1 0 -1 1 0 1 0 0 1 -1/2 0 0 0 1 1 -2 0 0 0 0 0 -1/2 1 j 0 0 0 -1 0 -1割割 平平 面面 法法-59-China University of Mining and Technology运筹学 3 2 0 0 0 0 x1 x2 x3 x4 x5 x6 j 0 0 0 -1 -1/2 0x2x1x3x5 1 4 3 1 0 1 0 -1 0 2 1 0 0 1 0 -1 0 0 1 1 0 -4 0 0 0 0 1 -2

39、 j 0 0 0 -1 0 -1从上表中我们可以看到，已经找到了整数最优解：从上表中我们可以看到，已经找到了整数最优解：x1=4, x2=1。故求解结束。故求解结束。用对偶单纯型法求解：用对偶单纯型法求解：割割 平平 面面 法法-63-China University of Mining and Technology运筹学 割平面的性质割平面的性质性质性质1 X0 不是整数规划问题的解；不是整数规划问题的解；性质性质2 LP的整数可行解都满足整数规划约束条件。的整数可行解都满足整数规划约束条件。u割平面法的上述性质说明了在割平面法的上述性质说明了在LP中新增加一个割平面约束，中新增加一个割平面

40、约束，不改变不改变LP中整数可行解的数量中整数可行解的数量.uGoromy的的切切割割法法自自 1958年年提提出出后后，即即引引起起人人们们的的广广泛泛关关注注。但但至至今今完完全全用用它它解解题题的的仍仍是是少少数数，原原因因就就是是经经常常遇遇到到收收敛敛很很慢慢的的情情形形。但但若若和和其其它它方方法法（如如分分枝枝定定界界法法）配配合使用，也是有效的。合使用，也是有效的。割割 平平 面面 法法-64-China University of Mining and Technology运筹学 5.4 0-1型整数规划-65-China University of Mining and T

41、echnology运筹学 若变量只能取值若变量只能取值0或或l，则称其为，则称其为0-10-1变量变量变量变量。 0-1变量作为逻辑变量，常被用来表示系统是否处于某个待定变量作为逻辑变量，常被用来表示系统是否处于某个待定状态，或者决策时是否取某个待定方案。例如状态，或者决策时是否取某个待定方案。例如当决策取方案当决策取方案 P 时时当决策不取方案当决策不取方案 P 时时0-1整整数数规规划划-66-China University of Mining and Technology运筹学 当问题含有多项要素，而每项要素皆有两种选择时，可用一当问题含有多项要素，而每项要素皆有两种选择时，可用一组组

42、0-1变量来描述。变量来描述。一般地，设问题有有限项要素一般地，设问题有有限项要素 El,E2,En。其中每项。其中每项 Ej 有两有两种选择种选择 ， ,( j1,2,n )，则可令，则可令那么那么,向量向量 (x1 , x2 , , xn)T 就描述了问题的特定状态或方案，就描述了问题的特定状态或方案，即即若若 Ej 选择选择若若 Ej 选择选择0-1整整数数规规划划-67-China University of Mining and Technology运筹学 厂址选择问题厂址选择问题厂址选择问题厂址选择问题 在在5个地点中选个地点中选3处建生产同一产品的工厂，在这处建生产同一产品的工厂

43、，在这5个地点建个地点建厂所需投资，占用农田，建成以后的生产能力等数据如下表厂所需投资，占用农田，建成以后的生产能力等数据如下表所示所示. 地点地点12345所需投资（万元）所需投资（万元）320280240210180占用农田（亩）占用农田（亩）201815118生产能力（万吨）生产能力（万吨）7055422811现在有总投资现在有总投资800万元，占用农田指标万元，占用农田指标60亩，应如何选择厂亩，应如何选择厂址，使建成后总生产能力最大址，使建成后总生产能力最大. 0-1整整数数规规划划-69-China University of Mining and Technology运筹学 含有

44、相互排斥的约束条件的问题含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题含有相互排斥的约束条件的问题在在某问题某问题中，设备台时的约束条件为中，设备台时的约束条件为现在假设还有一种新的加工方式，相应的设备台时约束变成现在假设还有一种新的加工方式，相应的设备台时约束变成如果只能从两种加工方式中选择一种，那么，上两式就成为如果只能从两种加工方式中选择一种，那么，上两式就成为两个相互排斥的约束条件。两个相互排斥的约束条件。0-1整整数数规规划划-70-China University of Mining and Technology运筹学 为了统一在一个问题中，引入为了统一在一个问题中，引入

45、0-1变量变量若采用原加工方式若采用原加工方式若不采用原加工方式若不采用原加工方式和和若采用新加工方式若采用新加工方式若不采用新加工方式若不采用新加工方式于是，相互排斥的约束条件于是，相互排斥的约束条件(1)和和(2)可用下列三个约束条件统一：可用下列三个约束条件统一：0-1整整数数规规划划-71-China University of Mining and Technology运筹学 固定费用问题固定费用问题固定费用问题固定费用问题有三种资源被用于生产三种产品。资源量、产品单件可变费用有三种资源被用于生产三种产品。资源量、产品单件可变费用及售价、资源单耗量及组织三种产品生产的固定费用见下表。

46、及售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划，使总收益最大。要求制定一个生产计划，使总收益最大。 单耗量单耗量 产品产品资源资源资源量资源量A248500B234300C123100单件可变费用单件可变费用456固定费用固定费用100150200单件售价单件售价810120-1整整数数规规划划-76-China University of Mining and Technology运筹学 求解求解0-1型整数规划型整数规划例例10-1整整数数规规划划-77-China University of Mining and Technology运筹学 求解过程可以列表表

47、示求解过程可以列表表示(x1, x2, x3)z 值值约束条件约束条件 过滤条件过滤条件（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）10z8z05z5-233860-1整整数数规规划划-78-China University of Mining and Technology运筹学 5.5 指派问题及匈牙利法-79-China University of Mining and Technology运筹学 p匈牙利法是用来解决人员分配问题的一个解法。匈牙利法是用来解决人员分配问题的一个解法。p1955年年，库库恩恩（ W.W.Ku

48、hn)利利用用匈匈牙牙利利数数学学家家康康尼尼格格（D.Knig)的的一一个个定定理理构构造造了了这这个个解解法法，故故称称为为 匈匈牙牙利利法法 。pp指派问题的标准形式：指派问题的标准形式：指派问题的标准形式：指派问题的标准形式： 设设n个个人人被被分分配配去去做做 n件件工工作作，规规定定每每个个人人只只做做一一件件工工作作，每每件件工工作作只只有有一一个个人人做做。已已知知第第 i个个人人去去做做第第 j件件工工作作的的效效率率（时时间间或或费费用用）为为 Cij(i= 1，2，n；j= 1，2，n)并并 假假设设Cij0。 问如何分配才能使总效率问如何分配才能使总效率（时间或费用）最

49、高？（时间或费用）最高？ 任务任务人员人员A1A2An1c11c12c1n2c21c22c2nncn1cn2cnn指指派派问问题题及及匈匈牙牙利利法法-80-China University of Mining and Technology运筹学 此模型也可以看成一个特殊的此模型也可以看成一个特殊的运输问题运输问题，如果用表上作业法，如果用表上作业法得出的一个最优解又满足得出的一个最优解又满足“xij =0,1”的条件，这个解也是分配的条件，这个解也是分配问题的最优解。用表上作业法求解的过程往往出现退化情况。问题的最优解。用表上作业法求解的过程往往出现退化情况。注：注：人员分配问题有各种提法。

50、人员分配问题有各种提法。如果完成任务的效率表现为如果完成任务的效率表现为资源的消耗资源的消耗，则所谓的效率最，则所谓的效率最好是指消耗的资源最少，分配问题就是一个最小化问题；好是指消耗的资源最少，分配问题就是一个最小化问题；如果完成任务的效率表现为如果完成任务的效率表现为生产效率生产效率的高低，则分配问题的高低，则分配问题就是一个最大化问题。就是一个最大化问题。 所有分配问题可以建立相同的数学模型所有分配问题可以建立相同的数学模型所有分配问题可以建立相同的数学模型所有分配问题可以建立相同的数学模型指指派派问问题题及及匈匈牙牙利利法法-81-China University of Mining

51、and Technology运筹学 设决策变量设决策变量设决策变量设决策变量 指派问题的数学模型为：指派问题的数学模型为：指派问题的数学模型为：指派问题的数学模型为：指指派派问问题题及及匈匈牙牙利利法法-82-China University of Mining and Technology运筹学 p效率矩阵效率矩阵p分配问题的一个可行解分配问题的一个可行解X，可以写成一个矩阵形式，可以写成一个矩阵形式，称为分配问题的称为分配问题的解矩阵解矩阵。指指派派问问题题及及匈匈牙牙利利法法-83-China University of Mining and Technology运筹学 线性独立元线性独

52、立元解矩阵解矩阵 X 中各行或各列的元素之和都是中各行或各列的元素之和都是1；并且；并且X中只有中只有n 个元素是个元素是1，位于不同行和不同列中，称之为，位于不同行和不同列中，称之为线性独立的线性独立的.指指派派问问题题及及匈匈牙牙利利法法-84-China University of Mining and Technology运筹学 效率矩阵的效率矩阵的性质性质如如果果效效率率矩矩阵阵 C 中中所所有有元元素素 cij=0，并并且且存存在在 n个个线线性性独独立立的的0元元 素素 ，即即存存在在 n个个位位于于不不同同行行不不同同列列的的零零元元素素，则则令令对对应应于于这这些些零零元元素

53、素位位置置的的 xij = 1，其其余余的的 xij = 0，所所得得的的解解矩矩阵阵 X 就是问题的最优解。就是问题的最优解。但但是是实实际际中中并并不不一一定定出出现现这这样样的的 n个个线线性性独独立立的的 0元元素素。匈匈牙牙利利算算法法的的 基基本本思思想想 就就是是把把这这样样的的 “没没 有有 n个个线线性性独独立立的的 0元元素素的的效效率率矩矩阵阵 ”变变换换成成 “有有n个个线线性性独独立立的的 0元元素素的的效效率率矩矩阵阵”。指指派派问问题题及及匈匈牙牙利利法法-85-China University of Mining and Technology运筹学 康尼格定理康

54、尼格定理康尼格定理康尼格定理 : : 如果从分配问题效率矩阵如果从分配问题效率矩阵aij的每一行元素中分别减去的每一行元素中分别减去(或加上或加上)一个常数一个常数ui，从每一列中分别减去，从每一列中分别减去(或加上或加上)一个常数一个常数vj，得到一个新的效率矩阵，得到一个新的效率矩阵bij，则以，则以bij为效率矩阵的分配为效率矩阵的分配问题与以问题与以aij为效率矩阵的分配问题为效率矩阵的分配问题具有相同的最优解具有相同的最优解。指指派派问问题题及及匈匈牙牙利利法法-86-China University of Mining and Technology运筹学 指派问题的求解步骤：指派问

55、题的求解步骤：指派问题的求解步骤：指派问题的求解步骤：1) 变变换换指指派派问问题题的的系系数数矩矩阵阵(cij)为为(bij)。目目的的使使在在(bij)的的各各行行各列中都出现各列中都出现0元素，即元素，即 从从(cij)的每行元素都减去该行的最小元素；的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。再从所得新系数矩阵的每列元素中减去该列的最小元素。2) 进行试指派，以寻求最优解。进行试指派，以寻求最优解。 在在(bij)中中找找尽尽可可能能多多的的独独立立0元元素素，若若能能找找出出n个个独独立立0元元素素，就就以以这这n个个独独立立0元元素素对对应应

56、解解矩矩阵阵(xij)中中的的元元素素为为1，其其余余为为0，这就得到最优解。，这就得到最优解。指指派派问问题题及及匈匈牙牙利利法法-87-China University of Mining and Technology运筹学 找独立找独立0元素，常用的步骤为：元素，常用的步骤为：p 从从只只有有一一个个 0元元 素素 的的 行行开开始始，给给该该行行中中的的 0元元素素加加圈圈，记记作作 。p 然然 后后 划划 去去 所所在在列列 的的其其它它 0元元素素，记记作作 （这这表表示示该该列列所所代代表表的的任任务已指派完，不必再考虑别人了务已指派完，不必再考虑别人了)。依次进行到最后一行。依

57、次进行到最后一行。p 从从只只有有一一个个 0元元素素的的 列列开开始始（画画 的的不不计计在在内内），给给该该列列中中的的 0元元 素素加加圈圈，记记作作 ；然然后后划划去去 所所在在行行 的的0元元素素，记记作作 (表表示示此此人人已已有有任任 务务 ， 不不 再再 为为 其其 指指 派派 其其 他他 任任 务务 了了 )。 依依 次次 进进 行行 到到 最最 后后 一一 列列 。p 若若仍仍有有没没有有划划圈圈的的 0元元素素，且且同同行行 (列列)的的0元元素素至至少少有有两两个个，比比较较这这行行 各各 0元元素素所所在在列列中中 0元元素素的的数数目目，选选择择 0元元素素少少这这

58、个个 0元元素素加加圈圈 (表表 示示选选择择性性多多的的要要 “礼礼 让让 ”选选择择性性少少的的 )。然然后后划划掉掉同同行行同同列列的的其其它它 0元元素素。可反复进行，直到所有可反复进行，直到所有0元素都已圈出和划掉为止。元素都已圈出和划掉为止。p若若 元素的数目元素的数目m 等于矩阵的阶数等于矩阵的阶数n（即：即：mn），那么这指派问），那么这指派问题的最优解已得到。若题的最优解已得到。若m n, 则转入下一步。则转入下一步。指指派派问问题题及及匈匈牙牙利利法法-88-China University of Mining and Technology运筹学 3) 用最少的直线通过所有

59、用最少的直线通过所有0元素。其方法：元素。其方法： 对没有对没有的行打的行打“”； 对已打对已打“” 的行中所有含的行中所有含元素的列打元素的列打“” ； 再对打有再对打有“”的列中含的列中含 元素的行打元素的行打“” ； 重复重复、直到得不出新的打直到得不出新的打号的行、列为止；号的行、列为止； 对没有打对没有打号的行画横线，有打号的行画横线，有打号的列画纵线，这就得到覆号的列画纵线，这就得到覆盖所有盖所有0元素的最少直线数元素的最少直线数 l 。注注：l 应应等等于于m，若若不不相相等等，说说明明试试指指派派过过程程有有误误，回回到到第第2步步，另另行行试试指指派派；若若 lm n，表表示

60、示还还不不能能确确定定最最优优指指派派方方案案，须须再再变换当前的系数矩阵，以找到变换当前的系数矩阵，以找到n个独立的个独立的0元素，为此转第元素，为此转第4步。步。指指派派问问题题及及匈匈牙牙利利法法-89-China University of Mining and Technology运筹学 4) 变换矩阵变换矩阵(bij)以增加以增加0元素元素在没有被直线通过的所有元素中找出最小值，没有被在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新系数矩阵的最优解和原问题仍元素加上这

61、个最小值。新系数矩阵的最优解和原问题仍相同。转回第相同。转回第2步。步。指指派派问问题题及及匈匈牙牙利利法法-90-China University of Mining and Technology运筹学 有一份中文说明书，需译成英、日、德、俄四种有一份中文说明书，需译成英、日、德、俄四种文字，分别记作文字，分别记作A、B、C、D。现有甲、乙、丙、丁。现有甲、乙、丙、丁四人，他们将中文译成不同语种的说明书所需时间如四人，他们将中文译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？下表所示，问如何分派任务，可使总时间最少？ 任务任务人员人员ABCD甲甲67112乙乙4598

62、丙丙31104丁丁5982例例1指指派派问问题题及及匈匈牙牙利利法法-91-China University of Mining and Technology运筹学 解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素元素52）试指派（找独立）试指派（找独立0元素）元素） 找到找到 3 个独立零元素个独立零元素 但但 m = 3 n = 4指指派派问问题题及及匈匈牙牙利利法法-92-China University of Mining and Technology运筹学 3）作最少的直线覆盖所有）作最少的直线覆盖所有0元素元素 独立零元素的个数独立零元素的个数m等于最等于最少直线数少直线数

63、l，即即lm=3n=4；4）没有被直线通过的元素中选择最小值为没有被直线通过的元素中选择最小值为1，变换系数矩变换系数矩阵，阵，将没有被直线通过的所有元素减去这个最小元素；直将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派步进行试指派指指派派问问题题及及匈匈牙牙利利法法-93-China University of Mining and Technology运筹学 000 0 00试指派试指派 得到得到4个独立零元素，个独立零元素， 所以最优解矩阵为：所以最优解矩阵为： 即完成即完成4

64、个任务的总时间最少个任务的总时间最少为：为：241+8=15指指派派问问题题及及匈匈牙牙利利法法-94-China University of Mining and Technology运筹学 已知四人分别完成四项工作所需时间如下表，求最已知四人分别完成四项工作所需时间如下表，求最 优分配方案。优分配方案。 任务任务人员人员ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119例例2指指派派问问题题及及匈匈牙牙利利法法-95-China University of Mining and Technology运筹学 解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素元素

65、2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数为元素的个数为4 , 指派问题的最指派问题的最优指派方案即为甲负责优指派方案即为甲负责D工作，乙负工作，乙负责责B工作，丙负责工作，丙负责A工作，丁负责工作，丁负责C工工作。这样安排能使总的工作时间最少，作。这样安排能使总的工作时间最少，为为4491128。指指派派问问题题及及匈匈牙牙利利法法-96-China University of Mining and Technology运筹学 已知五人分别完成五项工作耗费如下表，求最优分已知五人分别完成五项工作耗费如下表，求最优分配方案。配方案。 任务任务人员人员ABCDE甲甲7

66、59811乙乙9127119丙丙85468丁丁73696戊戊467511例例3指指派派问问题题及及匈匈牙牙利利法法-97-China University of Mining and Technology运筹学 -1-2解：解：1）变换系数矩阵，增加）变换系数矩阵，增加0元素元素指指派派问问题题及及匈匈牙牙利利法法-98-China University of Mining and Technology运筹学 2）试指派（找独立）试指派（找独立0元素）元素） 独立独立0元素的个数元素的个数l45，故画直线调整矩阵。，故画直线调整矩阵。指指派派问问题题及及匈匈牙牙利利法法-99-China Un

67、iversity of Mining and Technology运筹学 选择直线外的最小元选择直线外的最小元素为素为1；直线外元素；直线外元素减减1，直线交点元素，直线交点元素加加1，其他保持不变。，其他保持不变。指指派派问问题题及及匈匈牙牙利利法法-100-China University of Mining and Technology运筹学 l =m=4 n=5选择直线外最小元素为选择直线外最小元素为1，直线外元素减，直线外元素减1，直，直线交点元素加线交点元素加1，其他，其他保持不变，得到新的系保持不变，得到新的系数矩阵。数矩阵。指指派派问问题题及及匈匈牙牙利利法法-101-Chin

68、a University of Mining and Technology运筹学 总费用为总费用为=5+7+6+6+4=5+7+6+6+4=2828注：此问题有多个最优解注：此问题有多个最优解指指派派问问题题及及匈匈牙牙利利法法-104-China University of Mining and Technology运筹学 n n非标准型的指派问题：非标准型的指派问题：非标准型的指派问题：非标准型的指派问题：p匈牙利法的条件是：模型求最小值、效率匈牙利法的条件是：模型求最小值、效率cij0。p当遇到各种非标准形式的指派问题时，处理方法是先将当遇到各种非标准形式的指派问题时，处理方法是先将其转

69、化为标准形式，然后用匈牙利法来求解。其转化为标准形式，然后用匈牙利法来求解。指指派派问问题题及及匈匈牙牙利利法法-105-China University of Mining and Technology运筹学 1. 1. 最大化指派问题最大化指派问题最大化指派问题最大化指派问题处理方法：处理方法：设设m为最大化指派问题系数矩阵为最大化指派问题系数矩阵C中最大元素。令中最大元素。令矩阵矩阵B（m-cij）nn则以则以B为系数矩阵的最小化指派问题和原为系数矩阵的最小化指派问题和原问题有相同的最优解。问题有相同的最优解。 某人事部门拟招聘某人事部门拟招聘4人任职人任职4项工作，对他们综合考评的得项

70、工作，对他们综合考评的得分如下表（满分分如下表（满分100分），如何安排工作使总分最多。分），如何安排工作使总分最多。例例4指指派派问问题题及及匈匈牙牙利利法法-106-China University of Mining and Technology运筹学 解解: M95，令，令用匈牙利法求解用匈牙利法求解C，最优解为：，最优解为：即甲安排做第二项工作、乙做第三项、丙即甲安排做第二项工作、乙做第三项、丙做第四项、丁做第三项做第四项、丁做第三项, 最高总分最高总分Z92959080357指指派派问问题题及及匈匈牙牙利利法法-107-China University of Mining and

71、Technology运筹学 2. 2. 不平衡的指派问题不平衡的指派问题不平衡的指派问题不平衡的指派问题 当人数当人数m大于工作数大于工作数n时，加上时，加上mn项虚拟工作，例如：项虚拟工作，例如： 当人数当人数m小于工作数小于工作数n时，加上时，加上nm个人，例如个人，例如指指派派问问题题及及匈匈牙牙利利法法-108-China University of Mining and Technology运筹学 3. 3. 一个人可做几件事的指派问题一个人可做几件事的指派问题一个人可做几件事的指派问题一个人可做几件事的指派问题若某人可做几件事，则将该人化作相同的几个若某人可做几件事，则将该人化作相

72、同的几个“人人”来接受来接受指派，且费用系数取值相同。指派，且费用系数取值相同。例如：丙可以同时任职例如：丙可以同时任职A和和C工作，求最优指派方案。工作，求最优指派方案。指指派派问问题题及及匈匈牙牙利利法法-109-China University of Mining and Technology运筹学 4. 4. 某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题某事一定不能由某人做的指派问题将该人做此事的效率系数取做足够大的数，可用将该人做此事的效率系数取做足够大的数，可用M表示。表示。 分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成

73、A、B、C、D、E五项任五项任务。每个人完成各项任务的时间如表所示。由于任务数多于人数，务。每个人完成各项任务的时间如表所示。由于任务数多于人数，考虑任务考虑任务E必须完成，其他必须完成，其他4项中可任选项中可任选3项完成。试确定最优分项完成。试确定最优分配方案，使完成任务的总时间最少。配方案，使完成任务的总时间最少。 任务任务人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345例例5指指派派问问题题及及匈匈牙牙利利法法-110-China University of Mining and Technology运筹学 解解: 1)

74、这是不平衡的指派问题，首先转换为标准型，再用匈这是不平衡的指派问题，首先转换为标准型，再用匈牙利法求解。牙利法求解。2) 由由于于任任务务数数多多于于人人数数，所所以以假假定定一一名名虚虚拟拟人人，设设为为戊戊。因因为为工工作作 E必必须须完完成成，故故设设戊戊完完成成 E的的时时间间为为 M（M为为非非常常大大的的数数），其其余余效效率率系系数数为为 0，则则标标准准型型的的效效率率矩矩阵阵表表示示为为： 任务任务人员人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊0000M指指派派问问题题及及匈匈牙牙利利法法-111-China University of Mining and Technology运筹学 用匈牙利法求出最优指派方案为：用匈牙利法求出最优指派方案为：即甲即甲B，乙，乙D，丙，丙E，丁，丁A, 任务任务C放弃。放弃。最少时间为最少时间为105。指指派派问问题题及及匈匈牙牙利利法法