三、整数规划 第6章 整数规划 清华大学出版社.

Presentation on theme: "三、整数规划 第6章 整数规划 清华大学出版社."— Presentation transcript:

1 三、整数规划 第6章 整数规划 清华大学出版社

2 第6章 整数规划 第1节 整数线性规划问题的提出 第2节 分支定界解法 第3节 割平面解法 第4节 使用MATLAB求解整数规划问题
第6章 整数规划 第1节 整数线性规划问题的提出 第2节 分支定界解法 第3节 割平面解法 第4节 使用MATLAB求解整数规划问题 第5节 0-1型整数线性规划 第6节 指派问题 清华大学出版社

3 第1节 整数线性规划问题的提出 在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。 为满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。 因此，对求最优整数解的问题，有必要另行研究。我们称这样的问题为整数线性规划(integer linear programming)，简称ILP。 清华大学出版社

4 第1节 整数线性规划问题的提出 整数线性规划的分类
第1节 整数线性规划问题的提出 整数线性规划的分类 如果所有的变量都限制为(非负)整数，就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming) 如果仅一部分变量限制为整数，则称为混合整数规划(mixed integer linear programming)。 整数线性规划的一种特殊情形是0-1规划，即变量的取值仅限于0或1。本章最后讲到的指派问题就是一个0-1规划问题。 清华大学出版社

5 第1节 整数线性规划问题的提出 现举例说明用单纯形法求得的解不能保证是整数最优解。
第1节 整数线性规划问题的提出 现举例说明用单纯形法求得的解不能保证是整数最优解。 例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5-1所示。问两种货物各托运多少箱，可使获得利润为最大? 表5-1 清华大学出版社

6 第1节 整数线性规划问题的提出 解：设x1，x2分别为甲、乙两种货物的托运箱数(当然都是非负整数)，这就是一个(纯)整数线性规划问题，用数学模型可表示为： max z =20x1+10x ① 5x1+4x2≤ ② 2x1+5x2≤ ③ (5.1) x1，x2≥ ④ x1，x2整数 ⑤ 该问题和线性规划问题的区别仅在于最后一个约束条件⑤。 现在我们暂不考虑这一条件，即解由①～④构成的线性规划问题(以后我们称这样的问题为与原问题相应的线性规划问题)。 清华大学出版社

7 第1节 整数线性规划问题的提出 容易求得相应的线性规划问题的最优解为 x1=4.8，x2=0，max z=96 清华大学出版社

8 第1节 整数线性规划问题的提出 现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解
第1节 整数线性规划问题的提出 现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解 因为x1表示的是托运甲种货物的箱数，目前得到的最优解不是整数，所以不合条件⑤的要求。 是不是可以把所得的非整数最优解经过“化整”就可得到合于条件⑤的整数最优解呢? 如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件②(关于体积的限制)，因而它不是可行解； 如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0, 时z=80；而当x1=4，x2=1(这也是可行解)时，z=90。 清华大学出版社

9 第1节 整数线性规划问题的提出 图5-1 图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内，而C点又不合于条件⑤。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值为Δz=96-90=6，表示利润的降低，这是由于变量的不可分性(装箱)所引起的。 清华大学出版社

10 第1节 整数线性规划问题的提出 由上例看出，将其相应的线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。 清华大学出版社

11 第2节 分支定界解法 在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举所有可行的整数解，即列出图5-1中所有标有“+”的整数点，然后比较它们的目标函数值，从而确定最优解。 对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。 如在例1中，变量只有x1和x2。由条件②，x1所能取的整数值为0、1、2、3、4共5个；由条件③，x2所能取的整数值为0、1、2共3个。因此所有可能的整数组合(不都是可行的)数是3×5=15个，穷举法还是勉强可用的。 对于大型问题，可行的整数组合数会很大。 例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20，超过2×1018。显然，穷举法是不可取的。 清华大学出版社

12 第2节 分支定界解法 应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。
第2节 分支定界解法 应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。 分支定界法可用于解纯整数或混合整数线性规划问题。 20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的重要方法之一。 分支定界法的基本思想 考虑最大化整数线性规划问题A，与它相应的线性规划记为问题B。我们从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数值z*的上界，记作 ；而A的任意可行解的目标函数值将是z*的一个下界 。分支定界法就是将B的可行域分成子区域(称为分支)的方法，逐步减小 和增大 ，最终求到z*。 清华大学出版社

13 第2节 分支定界解法 例2 求解问题A max z=40x1+90x2 ① 9x1+7x2≤56 ② 7x1+20x2≤70 ③ (5.2)
第2节 分支定界解法 例2 求解问题A max z=40x1+90x2 ① 9x1+7x2≤ ② 7x1+20x2≤ ③ (5.2) x1，x2≥ ④ x1，x2整数 ⑤ 清华大学出版社

14 第2节 分支定界解法 解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)，得最优解x1=4.81，x2=1.82，z0=356
第2节 分支定界解法 解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)，得最优解x1=4.81，x2=1.82，z0=356 可见它不符合整数条件⑤。 这时z0是问题A的最优目标函数值z*的上界，记作z0= 。 而在x1=0，x2=0时， 显然是问题A的一个整数可行解， 这时z=0，是z*的一个下界， 记作 =0，即0≤z*≤356 。 清华大学出版社

15 第2节 分支定界解法 首先注意到相应的线性规划问题（问题B）的解中有一个非整数变量，如x1=4.81。
第2节 分支定界解法 首先注意到相应的线性规划问题（问题B）的解中有一个非整数变量，如x1=4.81。 于是，在原问题中增加两个约束条件：x1≤4和x1≥5，将原问题分解为两个子问题B1和B2(即两支)。 给每支增加一个约束条件后，如图5-3所示，并不影响问题A的可行域。 仍然不考虑整数条件约束，解问题B1和B2，得到最优解为： 清华大学出版社

16 第2节 分支定界解法 x1≤4，x1≥5 图5-3 清华大学出版社

17 第2节 分支定界解法 显然，仍没有得到全部变量是整数的解。因z1＞z2，故将 改为349，那么必存在最优整数解，得到z*，并且
第2节 分支定界解法 显然，仍没有得到全部变量是整数的解。因z1＞z2，故将 改为349，那么必存在最优整数解，得到z*，并且 0≤z*≤349 继续对问题B1和B2进行分解。因z1＞z2，故先分解B1为两支。增加条件x2≤2，称为问题B3；增加条件x2≥3，称为问题B4。相当于在图5-3中再去掉x2＞2与x3＜3之间的区域，进行第二次迭代。 清华大学出版社

18 第2节 分支定界解法 继续对问题B2进行分解 清华大学出版社

19 第2节 分支定界解法 解 题 过 程 清华大学出版社

20 第2节 分支定界解法 从以上解题过程可得到用分支定界法求解整数线性规划(最大化)问题的步骤为（将要求解的整数线性规划问题称为问题A，将与它相应的线性规划问题称为问题B）： (1) 解问题B，可能得到以下情况之一： ① B没有可行解，这时A也没有可行解，则停止。 ② B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。 ③ B有最优解，但不符合问题A的整数条件，记它的目标函数值为 (2) 用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，…，n，试探，求得其目标函数值，并记作 以z*表示问题A的最优目标函数值；这时有 清华大学出版社

21 第2节 分支定界解法 进行迭代 第一步：分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构造两个约束条件 xj≤［bj］和xj≥［bj］+1 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无可行解， 。 清华大学出版社

22 第2节 分支定界解法 第二步：比较与剪支 各分支的最优目标函数中若有小于 者，则剪掉这支(用打×表示)，即以后不再考虑了。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，…，n。 用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。 清华大学出版社

23 第3节 割平面解法 割平面解法的思想 首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线性规划问题。
第3节 割平面解法 割平面解法的思想 首先不考虑变量xi是整数这一条件，仍然是用解线性规划的方法去解整数线性规划问题。 若得到非整数的最优解，则增加能割去非整数解的线性约束条件(或称为割平面)，使得由原可行域被切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。 割平面方法就是指出怎样找到适当的割平面(不见得一次就找到)，使切割后最终得到这样的可行域，它的一个整数极点恰好是问题的最优解。 以下仅讨论纯整数线性规划的情形。 清华大学出版社

24 第3节 割平面解法 例3 求解 约束条件： -x1+x2≤1 ② 3x1+x2≤4 ③ (5-3) x1，x2≥0 ④ x1，x2 整数 ⑤
第3节 割平面解法 例3 求解 目标函数 max z=x1+x2 ① 约束条件： -x1+x2≤ ② 3x1+x2≤ ③ (5-3) x1，x2≥ ④ x1，x2 整数 ⑤ 清华大学出版社

25 第3节 割平面解法 先不考虑条件⑤，求得相应的线性规划的最优解为： x1=34，x2=74，max z=104
第3节 割平面解法 先不考虑条件⑤，求得相应的线性规划的最优解为： x1=34，x2=74，max z=104 最优解是图5-5中域R的极点A，但不符合整数约束条件。 清华大学出版社

26 第3节 割平面解法 现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R′的一个极点。 如在域R′上求解①～④，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。 图5-6 清华大学出版社

27 第3节 割平面解法 在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束： −x1+x2+x3 =1 ⑥
第3节 割平面解法 在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束： −x1+x2+x = ⑥ 3x1+x x4= ⑦ 不考虑条件⑤，用单纯形表解题，见表5-2。 清华大学出版社

28 第3节 割平面解法 从表5-2的最终计算表中，得到非整数的最优解： x1=3/4，x2=7/4，x3=x4=0，max z=5/2
第3节 割平面解法 从表5-2的最终计算表中，得到非整数的最优解： x1=3/4，x2=7/4，x3=x4=0，max z=5/2 清华大学出版社

29 第3节 割平面解法 由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。
第3节 割平面解法 由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解的可行域中分数部分割去，再求最优解。 可从最终计算表中得到非整数变量对应的关系式： 清华大学出版社

30 第3节 割平面解法 为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和
第3节 割平面解法 为了得到整数最优解。将上式变量的系数和常数项都分解成整数和非负真分数两部分之和 (1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 然后将整数部分与分数部分分开，移到等式左右两边，得到： 清华大学出版社

31 第3节 割平面解法 现考虑整数条件⑤ 要求x1、x2都是非负整数，于是由条件⑥、⑦可知x3、x4也都是非负整数,这一点对以下推导是必要的，如不都是整数，则应在引入x3、x4之前乘以适当常数，使之都是整数。在上式中(其实只考虑一式即可)从等式左边看是整数；等式右边也应是整数。但在等式右边的(·)内是正数；所以等式右边必是非正数。就是说，右边的整数值最大是零。于是整数条件⑤可由下式所代替： 即 − 3x3− x4≤ − ⑧ 清华大学出版社

32 第3节 割平面解法 这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。 引入松弛变量x5，得到等式
第3节 割平面解法 这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例3。 引入松弛变量x5，得到等式 − 3x3 − x4+x5= − 3 将这新的约束方程加到表5-2的最终计算表，得表5-3。 清华大学出版社

33 第3节 割平面解法 这从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。 选择x5为换出变量，计算
第3节 割平面解法 这从表5-3的b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。 选择x5为换出变量，计算 清华大学出版社

34 第3节 割平面解法 将x3做为换入变量，再按原单纯形法进行迭代，得表5-4。 清华大学出版社

35 第3节 割平面解法 注意：新得到的约束条件⑧ − 3x3− x4≤ − 3 如用x1、x2表示，由⑥、⑦式得
第3节 割平面解法 注意：新得到的约束条件⑧ − 3x3− x4≤ − 3 如用x1、x2表示，由⑥、⑦式得 3(1+x1− x2)+(4− 3x1− x2)≥3 x2≤1 这就是(x1，x2)平面内形成的新的可行域，即包括平行于x1轴的直线x2=1和这直线下的可行区域，整数点也在其中，没有切割掉,见图5-7。 图5-7 清华大学出版社

36 第3节 割平面解法 求一个切割方程的步骤为： (1) 令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到
第3节 割平面解法 求一个切割方程的步骤为： (1) 令xi是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到 其中i∈Q (Q指构成基变量号码的集合) k∈K (K指构成非基变量号码的集合) 清华大学出版社

37 第3节 割平面解法 (2) 将bi和αik都分解成整数部分N与非负真分数f之和，即 bi=Ni+fi，其中0＜fi＜1
第3节 割平面解法 (2) 将bi和αik都分解成整数部分N与非负真分数f之和，即 bi=Ni+fi，其中0＜fi＜1 αik=Nik+fik，其中0≤fik＜ (5-5) 而N表示不超过b的最大整数。例如： 若b=2.35，则N=2，f=0.35 若b= − 0.45，则N= − 1,f=0.55 代入(5-4)式得 清华大学出版社

38 第3节 割平面解法 这就是一个切割方程。 (3) 现在提出变量(包括松弛变量)为整数的条件(当然还有非负的条件)。
第3节 割平面解法 (3) 现在提出变量(包括松弛变量)为整数的条件(当然还有非负的条件)。 这时，上式由左边看必须是整数，但由右边看，因为0＜fi＜1，所以不能为正，即 这就是一个切割方程。 由(5-4)式，(5-6)式，(5-7)式可知： ① 切割方程(5-7)式真正进行了切割，至少把非整数最优解这一点割掉了。 ② 没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(5-7)式的缘故。 清华大学出版社

39 第4节 使用MATLAB求解整数规划问题 MATLAB2014以后的版本提供了函数intlinprog用于求解整数规划问题
语法：[x,fval,exitflag]= intlinprog(f,intcon,A,b,Aeq,beq,lb,ub) 参数说明： intcon：整数约束变量的位置，如 Intcon=[1,3]表示第1、3两个变量将为整数 其它参数的意义与linprog函数相同 清华大学出版社

40 第4节 使用MATLAB求解整数规划问题 例4：求解例2 max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70
运行程序ch6_1.m可得： x = [ ]’ cost = -340 清华大学出版社

41 第4节 使用MATLAB求解整数规划问题 例5：求解例3 max z=x1+x2 -x1+x2≤1 3x1+x2≤4 x1，x2≥0
运行程序ch6_2.m可得： x = [ ]’ cost = -2 清华大学出版社

42 第5节 0-1型整数线性规划 0-1型整数线性规划是整数线性规划中的特殊情形，它的变量xi仅取值0或1。这时xi称为0-1变量，或称二进制变量。xi仅取值0或1这个条件可由下述约束条件所代替: xi≤1, xi≥0，整数 它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题，再研究解法。 清华大学出版社

43 5.1 引入0-1变量的实际问题 1. 投资场所的选定——相互排斥的计划
例6 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置(点)Ai (i=1，2，…，7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大? 清华大学出版社

44 5.1 引入0-1变量的实际问题 解：先引入0-1变量xi (i=1,2，…，7) 于是问题可列成： 清华大学出版社

45 5.1 引入0-1变量的实际问题 2. 相互排斥的约束条件 在本章开始的例1中，关于运货的体积限制为 5x1+4x2≤24 (5-9)
今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为 7x1+3x2≤ (5-10) 这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令 清华大学出版社

46 5.1 引入0-1变量的实际问题 其中M是充分大的数。 可以验证
于是，(5-9)式和(5-10)式可由下述条件(5-11)式和(5-12)式来代替： x1+4x2≤24+yM (5-11) 7x1+3x2≤45+(1 − y)M (5-12) 其中M是充分大的数。 可以验证 当y=0时，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而是多余的。当y=1时，(5-12)式就是(5-10)式，而(5-11)式是多余的。 引入的变量y不必出现在目标函数内，即认为在目标函数内y的系数为0。 清华大学出版社

47 αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m
5.1 引入0-1变量的实际问题 如果有m个互相排斥的约束条件(≤型)： αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m 为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，且下面这一组m+1个约束条件 αi1x１+αi2x2+…+αinxn≤bi+yiM i=1,2,…，m (5-13) y1+y2+…+ym=m − (5-14) 就合于上述的要求。这是因为，由于(5-14)式，m个yi中只有一个能取0值，设yi*=0，代入(5-13)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。 清华大学出版社

48 5.1 引入0-1变量的实际问题 3. 固定费用的问题 在讨论线性规划时，有些问题是要求使成本为最小。这时，通常设固定成本为常数，不必在线性规划模型中明显列出。但有些固定费用(固定成本)问题不能用一般线性规划来描述，可改变为混合整数线性规划来解决。 清华大学出版社

49 5.1 引入0-1变量的实际问题 例7 某工厂为生产某种产品，有几种生产方式供选择。如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令 xj表示采用第j种方式时的产量； cj表示采用第j种方式时每件产品的变动成本； kj表示采用第j种方式时的固定成本。 为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为 清华大学出版社

50 4.1 引入0-1变量的实际问题 在构成目标函数时，为了统一在一个问题中讨论，引入0-1变量yj，令 于是，目标函数为
min z=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3) 清华大学出版社

51 4.1 引入0-1变量的实际问题 (5-15)式的规定可由以下3个线性约束条件表示： xj≤yjM，j=1,2,3 (5-16)
(5-16)式说明 当xj＞0时，yj必须为1； 当xj=0时，只有yj为0时才有意义。 所以，(5-16)式完全可以代替(5-15)式。 清华大学出版社

52 型整数线性规划的解法 求解0-1型整数线性规划最容易想到的方法（和一般整数线性规划的情形一样），就是穷举法，即检查变量取值为0或1的每一种组合，并比较目标函数值以求得最优解。这就需要检查变量取值的2n个组合。当变量个数n较大(例如n＞10)时，这几乎是不可能的。 因此，需要设计一些特殊的方法，只需要检查变量取值组合中的一部分，就能求到问题的最优解。这样的方法称为隐枚举法(implicit enumeration)。分枝定界法就是一种隐枚举法。 下面举例说明一种解0-1型整数线性规划的隐枚举法。 清华大学出版社

53 4.2 0-1型整数线性规划的解法 例8 目标函数 max z=3x1-2x2+5x3 约束条件： x1+4x2+x3≤4 ② (5-17)
型整数线性规划的解法 例8 目标函数 max z=3x1-2x2+5x3 约束条件： x1+2x2−x3≤ ① x1+4x2+x3≤ ② (5-17) x1+x2≤ ③ 4x1+x3≤ ④ x1，x2，x3=0或1 ⑤ 清华大学出版社

54 型整数线性规划的解法 先通过试探的方法找一个可行解。容易看出(x1，x2，x3)=(1，0，0)就是合于①～④条件的，算出相应的目标函数值z=3。 下面来求最优解。对于极大化问题，当然希望z≥3，于是增加一个约束条件： 3x1 − 2x2+5x3≥3 ◎ 后加上的条件称为过滤条件。这样，原问题的线性约束条件就变成了5个。用全部枚举的方法，3个变量共有23=8个可能的解。原来的4个约束条件，共需32次运算。 现在增加了过滤条件◎，如按下述方法进行，就可减少运算次数。将5个约束条件按◎～④顺序排好(表5-5)。对每个可能的解，依次代入约束条件左侧，求出数值，看是否适合不等式条件。如某一条件不适合，同行以下各条件就不必再检查，因而就减少了运算次数。 清华大学出版社

55 4.2 0-1型整数线性规划的解法 本例计算过程如表5-5，实际只作了24次运算。求得最优解为：
型整数线性规划的解法 本例计算过程如表5-5，实际只作了24次运算。求得最优解为： (x1，x2，x3)=(1，0，1), max z=8 在计算过程中，若遇到z值已超过条件◎右边的值，应改变条件◎，使右边为迄今为止最大者，然后继续作。例如，当检查点(0，0，1)时因z=5(＞3)，所以应将条件◎换成 3x1− 2x2+5x3≥5 ◎ 这种对过滤条件的改进，更可以减少计算量。 清华大学出版社

56 型整数线性规划的解法 表5-5 清华大学出版社

57 4.2 0-1型整数线性规划的解法 注意： 一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写
型整数线性规划的解法 注意： 一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写 z=3x1− 2x2+5x3= − 2x2+3x1+5x3 因为− 2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，…， 这样，最优解容易比较早的发现。 再结合过滤条件的改进，更可使计算简化。 清华大学出版社

58 4.2 0-1型整数线性规划的解法 在上例中 max z=-2x2+3x1+5x3 -2x2+3x1+5x3≥3 ◎
型整数线性规划的解法 在上例中 max z=-2x2+3x1+5x3 -2x2+3x1+5x3≥3 ◎ 2x2+x1-x3≤ ① 4x2+x1+x3≤ ② (5-18) x2+x1≤ ③ 4x2+x3≤ ④ 解题时按下述步骤进行(见表5-6)： 清华大学出版社

59 型整数线性规划的解法 清华大学出版社

60 4.2 0-1型整数线性规划的解法 改进过滤条件，用 -2x2+3x1+5x3≥5 ◎′ 代替◎，继续进行。 再改进过滤条件，用
型整数线性规划的解法 改进过滤条件，用 -2x2+3x1+5x3≥5 ◎′ 代替◎，继续进行。 再改进过滤条件，用 2x2+3x1+5x3≥8 ◎″ 代替◎′，再继续进行。至此，z值已不能改进，即得到最优解，解答如前，但计算已简化。 清华大学出版社

61 4.3 使用MATLAB求0-1规划 使用intlinprog函数，将0-1规划看作一个普通的整数规划问题求解，只是解的上界为1，下界为0而已。 例9：求例8的解： max z=3x1-2x2+5x3 x1+2x2−x3≤2 x1+4x2+x3≤4 x1+x2≤3 4x1+x3≤6 x1，x2，x3=0或1 运行程序ch6_3.m可得：x=[1 0 1]’ z=8 清华大学出版社

62 第6节 指派问题 在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignment problem)。 清华大学出版社

63 第6节 指派问题 例10 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少? 表5-7 清华大学出版社

64 第6节 指派问题 类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题……。对应每个指派问题，需有类似表5-7那样的数表，称为效率矩阵或系数矩阵，其元素cij＞0(i,j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令 清华大学出版社

65 第6节 指派问题 当问题要求极小化时数学模型是： ① ② ③ ④ 清华大学出版社

66 第6节 指派问题 约束条件②说明第j项任务只能由1人去完成；约束条件③说明第i人只能完成1项任务。
第6节 指派问题 约束条件②说明第j项任务只能由1人去完成；约束条件③说明第i人只能完成1项任务。 满足约束条件②～④的可行解xij也可写成表格或矩阵形式，称为解矩阵。 如例7的一个可行解矩阵是 显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最优解。 清华大学出版社

67 第6节 指派问题 指派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1
第6节 指派问题 指派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1 当然可用整数线性规划，0-1规划或运输问题的解法去求解，这就如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。 指派问题的最优解有这样性质，若从系数矩阵(cij)的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)， 那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。 清华大学出版社

68 第6节 指派问题 利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。 若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到zb=0，它一定是最小。 这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。 清华大学出版社

69 第6节 指派问题 以下用例10来说明指派问题的解法。
第6节 指派问题 以下用例10来说明指派问题的解法。 第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。 (1) 从系数矩阵的每行元素减去该行的最小元素； (2) 再从所得系数矩阵的每列元素中减去该列的最小元素。 若某行(列)已有0元素，那就不必再减了。 例10的计算为 清华大学出版社

70 第6节 指派问题 行列都有零元素 清华大学出版社

71 第6节 指派问题 第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。
第6节 指派问题 第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。 经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找，常用的步骤为： 清华大学出版社

72 第6节 指派问题 (1) 从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。这表示对这行所代表的人，只有一种任务可指派。然后划去◎所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。 (2) 给只有一个0元素列(行)的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Φ。 (3) 反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。 (4) 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个(表示对这个可以从两项任务中指派其一)。这可用不同的方案去试探。从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 (5) 若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m＜n，则转入下一步。 清华大学出版社

73 第6节 指派问题 注意：矩阵中符号 即是文中的◎符号。 以下同。
第6节 指派问题 现用例10的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到 注意：矩阵中符号 即是文中的◎符号。 以下同。 清华大学出版社

74 第6节 指派问题 可见m=n=4,所以得最优解为 这矩阵表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少
第6节 指派问题 可见m=n=4,所以得最优解为 这矩阵表示：指定甲译出俄文，乙译出日文，丙译出英文，丁译出德文。所需总时间最少 清华大学出版社

75 第6节 指派问题 例11 求表5-8所示效率矩阵的指派问题的最小解。 清华大学出版社

76 第6节 指派问题 解 按上述第一步，将这系数矩阵进行变换。 经一次运算即得每行每列都有0元素的系数矩阵， 清华大学出版社

77 第6节 指派问题 再按上述步骤运算，得到 这里◎的个数m=4，而n=5；所以解题没有完成， 这时应按以下步骤继续进行。 清华大学出版社

78 第6节 指派问题 第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：
第6节 指派问题 第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行： (1) 对没有◎的行打√号； (2) 对已打√号的行中所有含Φ元素的列打√号； (3) 再对打有√号的列中含◎元素的行打√号； (4) 重复(2)，(3)直到得不出新的打√号的行、列为止。 (5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数。 清华大学出版社

79 第6节 指派问题 令这直线数为l。若l＜n，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：若l=n，而m＜n，应回到第二步(4)，另行试探。 在例8中，对矩阵①按以下次序进行： 先在第五行旁打√，接着可判断应在第1列下打√，接着在第3行旁打√。经检查不再能打√了。对没有打√行，画一直线以覆盖0元素，已打√的列画一直线以覆盖0元素。得 清华大学出版社

80 第6节 指派问题 由此可见l=4＜n。所以应继续对②矩阵进行变换。 转第四步。 清华大学出版社

81 第6节 指派问题 第四步： 对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵(它的最优解和原问题相同)。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。 在例8的矩阵②中，在没有被覆盖部分(第3、5行)中找出最小元素为2，然后在第3、5行各元素分别减去2，给第1列各元素加2，得到新矩阵③。按第二步，找出所有独立的0元素，得到矩阵④。 清华大学出版社

82 第6节 指派问题 ③ ④ 清华大学出版社

83 第6节 指派问题 已具有n个独立0元素。这就得到了最优解，相应的解矩阵为 由解矩阵得最优指派方案： 甲—B，乙—D，丙—E，丁—C，戊—A
第6节 指派问题 已具有n个独立0元素。这就得到了最优解，相应的解矩阵为 由解矩阵得最优指派方案： 甲—B，乙—D，丙—E，丁—C，戊—A 还可以得到另一最优指派方案 甲—B，乙—C，丙—E，丁—D，戊—A 所需总时间为min z=32 清华大学出版社

84 第6节 指派问题 当指派问题的系数矩阵，经过变换得到了同行和同列中都有两个或两个以上0元素时。这时可以任选一行(列)中某一个0元素，再划去同行(列)的其他0元素。这时会出现多重解。 清华大学出版社

85 第6节 指派问题 以上讨论限于极小化的指派问题。 对极大化的问题，即求 可令 bij=M − cij
第6节 指派问题 以上讨论限于极小化的指派问题。 对极大化的问题，即求 可令 bij=M − cij 其中M是足够大的常数(如选cij中最大元素为M即可)， 这时系数矩阵可变换为 B=(bij) 这时bij≥0，符合匈牙利法的条件。目标函数经变换后，即解 清华大学出版社

86 第6节 指派问题 所得最小解就是原问题的最大解，因为 取最小时， 因nM为常数，所以当 便为最大。 清华大学出版社

87 第6节 指派问题 例12 用Matlab求解例10 运行程序ch6_4.m x = cost = 28 例13 用Matlab求解例11 运行程序ch6_5.m x = cost = 32 清华大学出版社

88 http://www.ifors.ms.unimelb. edu.au/tutorial/ 有兴趣的读者可以进入以下网站
提供了网上学习线性规划单纯形法、表上求解和匈牙利法等方法。 清华大学出版社