第六章_整数规划(1)

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外整数规划整数规划运筹学教学要求教学要求 重点掌握指派问题的建模与求解重点掌握指派问题的建模与求解。 掌握掌握线性整数规划的建模方法，特别是0-1变量的运用；掌握掌握分支定界求解方法的基本原理；了解了解割平面求解方法的基本原理；p整数规划建模整数规划建模 p分枝定界法分枝定界法 p割平面法割平面法p指派问题指派问题 重点：分枝定界、隐枚举法重点：分枝定界、隐枚举法难点：分枝定界法、指派问题求解难点：分枝定界法、指派问题求解第一节第一节 整数规划实例与模型整数规划实例与模型第二节第二节 0 01 1整数规划的建模方法整数规划的建模

2、方法第三节第三节 分支定界法分支定界法第四节第四节 割平面法割平面法第五节第五节 指派问题指派问题第六节第六节 应用举例和应用举例和ExcelExcel求解求解目目 录录p在现实生活中，经常遇到一些需要变量取整数才有实际意义的问题，例如制定计划、规划时需要确定工人的人数，设备的台数等。p许多有名的最优化问题，如旅行商问题、背包问题、下料问题、工序安排问题等，也都可以归结为整数规划问题。第一节整数规划实例与模第一节整数规划实例与模型型某工厂准备备用集装箱托运甲、乙两种货物，已知，每箱货物的体积、利润、重量、托运限制如下表，问甲乙两种货物各托运多少箱才能使总利润最大？一、实例一、实例1货物每箱体积

3、 每箱重量 每箱利润甲5220乙4510托运限制2413解：设甲乙两种货物各托运x1,x2箱，依题意得：Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20 x1,x2取整数第一节整数规划实例与模第一节整数规划实例与模型型 现有一位于城市B5的工厂，其年生产量是30000件，产品被运往A1，A2，A3三个城市的销售中心。经预测该厂产品的需求量将会增长，工厂决定将在B1，B2，B3，B4四个城市中的一个或多个城市中新建工厂以增加生产力。综合考虑在这四个城市中新建工厂的年固定成本和生产能力，以及每件产品从每个工厂送到每个销售中心的运费。问如何选择新的厂址

4、，才能使该工厂每年的总成本最小。第一节整数规划实例与模第一节整数规划实例与模型型一、实例一、实例2生产地销售中心年固定成本年生产力(千件)A1A2A3B152317510B243430020B397537530B4104250040B5843需求量302020B1B2B3B4B5A3A2A11020304030202030第一节整数规划实例与模第一节整数规划实例与模型型总成本年固定成本运输成本第一节整数规划实例与模第一节整数规划实例与模型型首先做如下假设：首先做如下假设： 如果在如果在B B1 1建新厂，建新厂，y y1 1=1=1；否则，；否则，y y1 1=0=0。 如果在如果在B B2

5、2建新厂，建新厂，y y2 2=1=1；否则，；否则，y y2 2=0=0。 如果在如果在B B3 3建新厂，建新厂，y y3 3=1=1；否则，；否则，y y3 3=0=0。 如果在如果在B B4 4建新厂，建新厂，y y4 4=1=1；否则，；否则，y y4 4=0=0。 x xij ij：表示从工厂：表示从工厂i i 到销售中心到销售中心j j的运输量；的运输量；i=1,i=1,5,5；j=1,2,3j=1,2,3。 利用已知的数据，年运输成本为：利用已知的数据，年运输成本为： TCTC1 1=5x=5x11 11+2x+2x1212+3x+3x1313+4x+4x2121+3x+3x2

6、222+4x+4x2323+9x+9x3131+7x+7x3232 +5x+5x3333+10 x+10 x4141+4x+4x4242+2x+2x4343+8x+8x5151+4x+4x5252+3x+3x5353TCTC2 2=175y=175y1 1+300y+300y2 2+375y+375y3 3+500y+500y4 4；总成本为：总成本为：TC=TCTC=TC1 1+TC+TC2 2；生产能力的约束条件为：生产能力的约束条件为：从新工厂从新工厂B B1 1运到运到A A1 1，A A2 2，A A3 3三个城市销售中心的总量应小于等三个城市销售中心的总量应小于等于于B B1 1的

7、生产能力，所以约束条件为：的生产能力，所以约束条件为： x x11 11+x+x1212+x+x131310y10y1 1 B B1 1的生产能力；的生产能力；同理可得：同理可得：x x2121+x+x2222+x+x232320y20y2 2 B B2 2的生产能力；的生产能力；x x3131+x+x3232+x+x333330y30y3 3 B B3 3的生产能力；的生产能力；x x4141+x+x4242+x+x434340y40y4 4 B B4 4的生产能力；的生产能力；x x5151+x+x5252+x+x535330 B30 B5 5的生产能力；的生产能力；三个销售中心的需求量为

8、：三个销售中心的需求量为：x x11 11+x+x2121+x+x3131+x+x4141+x+x5151=30 A=30 A1 1的需求量；的需求量；x x1212+x+x2222+x+x3232+x+x4242+x+x5252=20 A=20 A2 2的需求量；的需求量；x x1313+x+x2323+x+x3333+x+x4343+x+x5353=20 A=20 A3 3的需求量；的需求量；建新工厂的年固定成本为：建新工厂的年固定成本为：所以选址模型为：所以选址模型为： min TC= TCmin TC= TC1 1+TC+TC2 2s.ts.tx x11 11+x+x1212+x+x1

9、31310y10y1 1 x x2121+x+x2222+x+x232320y20y2 2 x x3131+x+x3232+x+x333330y30y3 3 x x4141+x+x4242+x+x434340y40y4 4 x x5151+x+x5252+x+x53533030 x x11 11+x+x2121+x+x3131+x+x4141+x+x5151=30=30 x x1212+x+x2222+x+x3232+x+x4242+x+x5252=20=20 x x1313+x+x2323+x+x3333+x+x4343+x+x5353=20=20 x xij ij00，对所有的，对所有的i

10、 i，j j； y y1 1，y y2 2，y y3 3，y y4 4=0=0，1 1 第一节整数规划实例与模第一节整数规划实例与模型型nixbbbxatsxciniiiniii,2, 1 ,0 ) ( .min)max(11且为整数或部分为整数或或或第一节整数规划实例与模第一节整数规划实例与模型型二、整数规划一般模型二、整数规划一般模型如果决策变量全部为整数，则称为纯整数规划部分决策变量是整数，其他变量可以是非整数，则称为混合整数规划如果变量仅取0或1，此时的整数规划称为 0-1规划，是整数规划的特殊情况整数规划模型是一类特殊的线性规划模型，但用求解线性规划模型的单纯形法所得到的最优解往往不

11、能保证其一定是整数。解相应的线性规划问题得到最优解之后，采用最优解凑整的方法，往往得不到整数规划的最优解，甚至得不到可行解第一节整数规划实例与模第一节整数规划实例与模型型Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20,且为整数Max z=20 x1+10 x2s.t 5x1+4x224 2x1+5x2 13 x1,x20通过单纯法可求得最优解为x1=4.8,x2=0 maxz=96若采用凑整的方法得 X1=5 x2=0 根本不是原整数规划的可行解(2) x1=4 x2=0 z=80 不是整数规划的最优解实际上原问题的最优解为X1=4,x2=1

12、max z=90将将x1,x2取取整条件去掉整条件去掉第一节整数规划实例与模第一节整数规划实例与模型型用穷举法求解：Max z=20 x1+10 x2s.T 5x1+4x224 2x1+5x2 13 x1,x20,且为整数解：在 中令x2=0 得 x124/5=4 x1 13/2=6 x1 4所以 x1 只能取 0,1,2,3,4同理 在 中令x1=0 得 0 x2 2故 x2只能取0,1,2第一节整数规划实例与模第一节整数规划实例与模型型点点条件条件可行解可行解Z值值(0,0)0(0,1)10(0,2)20(1,0)20(1,1)30(1,2)40(2,0)40(2,1)50(2,2)1(3

13、,0)60(3,1)70(3,2)1(4,0)80(4,1)90(4,2)第一节整数规划实例与模第一节整数规划实例与模型型第二节第二节 01整数规划的建模方法整数规划的建模方法 一、 0-1整数规划 在整数规划中，如果变量只能取0,1两个数，称整数规划为0-1整数规划 在现实世界中存在许多具有组合特性的以及涉及是或非决策的最优化问题，这些问题都可归结为0-1整数规划例 某公司拟在市东西南三区建立门市部，拟议中有7个位置Ai(i=1,27)可供选择，规定（1）在东区A1,A2,A3三个点中至多选两个（2）在西区A4,A5两个点中至少选一个（3）在南区A6,A7两个点中至少选一个如果用Ai点，设备

14、投资估计了bi元，每年可获利估计为ci元，但投资额不超过B元，问应选择哪几个点可使年利润最大？解，引入0-1变量,xi(i=1,27)，令Xi=1，表示Ai点被选用0，表示Ai点没被选用第二节第二节 01整数规划的建模方法整数规划的建模方法X1+x2+x32 X4+x5 1 X6+x7 1 b1x1+b2x2+b3x3+b7x7Bmax Z=c1x1+c2x2+c3x3+c7x7s.t. b1x1+b2x2+b3x3+b7x7B X1+x2+x32 X4+x5 1 X6+x7 1 Xi=0或1 i=1,27第二节第二节 01整数规划的建模方法整数规划的建模方法实例：某电冰箱厂正在考虑随后4年内

15、有不同资金要求的投资方案。面对每年有限的资金，工厂领导需要选择最好的方案，使资金预算方案的当前估算净值最大化。每种方案的现金估算净值（现金估算净值为第一年开始时的净现金流的值）、资金需求和4年内拥有的资金见下表：扩建厂房 扩建仓库 更新机器 新产品研制现值90401037总可用成本第1年资金1510101540第2年资金20151050第3年资金20201040第4年资金15541035项目（千元）第二节第二节 01整数规划的建模方法整数规划的建模方法 x1表示扩建工厂的变量，=1表示扩建工厂，0表示不扩建 同理，变量x2,x3,x4依次表示扩建仓库、更新机器、新产品研制。变变 量量第1年的可

16、用资金为40千元，所以相应的约束条件为：同理得到后三年的约束条件。约束条件约束条件40151010154321xxxx当前估算净值最大，即max 目标函数目标函数432137104090 xxxx扩建仓库 更新机器 新产品研制现值90401037总可用成本第1年资金1510101540第2年资金20151050第3年资金20201040第4年资金15541035项目（千元）第二节第二节 01整数规划的建模方法整数规划的建模方法扩建厂房可得上例的模型Max z=90 x1+40 x2+10 x3+37x4s.t. 15x1+10 x2+10 x3+15x440 20 x1+15x2 +10 x4

17、50 20 x1+20 x2 +10 x440 15x1+5x2 +4x3 +10 x435 xi=0,1 (i=1,2,3,4)第二节第二节 01整数规划的建模方法整数规划的建模方法njxmibxcxczjnjijijnjjj, 2 , 1, 10, 2 , 1, min11或必须 必须大于等于0 解法解法p 全枚举法 p隐枚举法标准型标准型二、 01整数规划的标准型和解法整数规划的标准型和解法第二节第二节 01整数规划的建模方法整数规划的建模方法p（1 1）令全部都是自由变量且取0值，检验解是否可行。若可行，已得最优解；若不可行，进行步骤（2）。p（2 2）将某一变量转为固定变量，令其取值

18、为1或0，使问题分成两个子域。令一个子域中的自由变量都取0值，加上固定变量取值，组成此子域的解。p（3 3）计算此解的目标函数值，与已求出的可行解最小目标函数值比较。如果前者大，则不必检验其是否可行而停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝即使得到可行解，其目标函数值也较大，不会是最优解；如前者小，进行步骤（4）。对第一次算出的目标函数值，不必进行比较，直接转到步骤（4）。p（4 4）检验解是否可行。如可行，已得一个可行解，计算并记下它的z值，并停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝，即使得到可行解，目标函数值也比记下的z值大，不会是最

19、优解；如不可行，进行步骤（5）。隐枚举法求解步骤（一）隐枚举法求解步骤（一）p（5 5）将子域固定变量的值代入第一个不等式约束条件方程，并令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，这就是左端所能取得最小值。若此最小值大于右端值，则称此子域为不可行子域不可行子域，不再往下分枝，若此最小值小于右端值，则依次检验下一个不等式约束方程，直至所有的不等式约束方程都通过，若子域都检验过，转步骤（7），否则，转步骤（6）。p（6 6）定出尚未检验过的另一个子域的解，执行步骤（3）（5），若所有子域都停止分枝，计算停止，目标函数值最小的可行解就是最优解；否则，转（7）。p（7 7）检查有

20、无自由变量。若有，转（2）；如没有，计算停止。目标函数值最小的可行解就是最优解。隐枚举法求解步骤（一）隐枚举法求解步骤（一）第二节第二节 01整数规划的建模方法整数规划的建模方法. , 10423523233 s.t.57428min543215432154321jxxxxxxxxxxxxxxxxzj对一切或(0,0,0,0,0)(0,1,0,0,0)(0,1,0,1,0)(0,1,0,0,0)(0,1,1,0,0)(0,0,0,0,0)(0,1,0,0,0)(0,0,0,0,0)(1,0,0,0,0)说明：说明： 彩色字体为固定变量。Z1=8，可行，停止分支。Z2=0 Z1 ，不可行；可行子

21、域，分支。Z3=2 Z1 ，不可行，可行子域，分支。Z4=0 Z1 ，不可行，不可行子域，停止分支。Z5=6 Z1 ，可行，停止分支。Z6=2 Z5 ，停止分支。Z8=2Z0，则将过滤条件换成ZZ1 一般地，过滤条件是所有约束条件中关键的一个，因而先检查它是否满足，如不满足，其他约束条件也就不再检查了(不论这个变量的组合是否是可行解，对我们都没有用)这样也就减少了计算工作量第二节第二节 01整数规划的建模方法整数规划的建模方法利用隐枚举法求解下面的0-1整数规划第二节第二节 01整数规划的建模方法整数规划的建模方法Max z=3x1-2x2+5x3 s.t x1+2x2-x3 2 x1+4x2

22、+x3 4 x1+ x2 3 4x2+x3 6 xi=0,1 i=1,2,3点点过滤条件过滤条件条件条件满足满足条件条件Z值值3x1-2x2+5x3 3(0,0,0)(0,0,1)53x1-2x2+5x3 5(0,1,0)(0,1,1)(1,0,0)(1,0,1)83x1-2x2+5x3 8(1,1,0)(1,1,1)即最优解为(1,0,1)T，最优值为8Max z=3x1-2x2+5x3 s.t x1+2x2-x3 2 x1+4x2+x3 4 x1+ x2 3 4x2+x3 6 xi=0,1 i=1,2,3第二节第二节 01整数规划的建模方法整数规划的建模方法利用隐枚举法求解下面的0-1整数

23、规划min z=3x1-2x2+5x3 s.t x1-2x2-x3 -2 x1+x2+x3 4 x1-4x2 -3 xi=0,1 i=1,2,3 第二节第二节 01整数规划的建模方法整数规划的建模方法点点过滤条件过滤条件条件条件满足满足条件条件Z值值3x1-2x2+5x3 6(1,1,1)6(1,1,0)(1,0,1)(1,0,0)(0,1,1)33x1-2x2+5x3 3(0,1,0)-23x1-2x2+5x3 -2(0,0,1)(0,0,0)min z=3x1-2x2+5x3 s.t x1-2x2-x3 -2 x1+x2+x3 4 x1-4x2 -3 xi=0,1 i=1,2,3 即最优解

24、为(0,1,0)T，最优值为-2第二节第二节 01整数规划的建模方法整数规划的建模方法 分支定界法的主要思路是首先求解整数规划的伴随规划，如果求得的最优解不符合整数条件，则增加新约束缩小可行域；将原整数规划问题分枝分成两个子规划，再解子规划的伴随规划、通过求解一系列子规划的伴随规划及不断地定界，最后得到原整数规划问题的整数最优解第三节第三节 分支定界法分支定界法例，某公司计划建筑两种类型的宿舍，甲种每栋占地250平米，乙种每栋占地400平米，该公司拥有地地3000平米，计划甲种宿舍不超过8栋，乙种宿舍不超过4栋，甲种宿舍每栋利润为10万元，乙种宿每栋利润为20万元，问该公司应计划甲乙两种类型的

25、宿舍各建多少栋时，能使公司利润最大？解：设计划甲乙两种类型的宿舍分别建x1,x2栋，则本题的数学模型为： max z=10 x1+20 x2 25x1+40 x2300 x1 8 x2 4 x1,x20 x1,x2 取整数第三节第三节 分支定界法分支定界法这个纯整数规划问题称为问题A0，去掉整数条件，得到问题A0的伴随规划，称之为问题B0max z=10 x1+20 x25x1+8x260 x1 8 x2 4 x1,x20求解上述问题，得到最优解X0（5.6,4)最优值为f0=136第三节第三节 分支定界法分支定界法x1x2(5.6,4)(8,2.5)841、计算原问题A0目标函数的初始上界Z

26、上界 因为问题B0的最优解X0不满足整数条件，因此X0不是问题A0的最优解，又因为A0的可行域K0包含问题B0的可行域K0，故问题A0的最优值不会超过问题B0的最优值，即有Zf0 因此可令f0作为Z的初始上界Z，即上界Z上界1362、计算原问题A0目标函数值的初始下界Z下界 若能从问题A0的约束条件中观察到一个整数可行解，则可将其目标函数值作为问题A0目标函数值的初始下界，否则可令初始下界Z，给定下界的目的，是希望在求解过程中寻找比当前Z更好的原问题的目标函数值 对于本例，容易得到一个可行解X（0,0），故可令初始下界Z下界0第三节第三节 分支定界法分支定界法3、增加约束条件将原问题分枝 当问

27、题B0的最优解不满足整数条件时，在x0中任选一个不符合整数条件的变量，如上例x15.6，显然A0的整数最优解只能是x15或x16，而绝不会在5与6之间，因此可将可行域K0切去5x16部分时，并没有切去A0的整数可行解，可以用分别增加约束条件x1 5及x16来达到切去的目的，即将问题A0分为问题A1及问题A2两枝子规划问题A1问题A2max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20，取整数max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x1,x20，取整数第三节第三节 分支定界法分支定界法作出问题A1，A2的伴随规划B1，B2

28、，则问题B1，B2的可行域K1，K2，如下图所示x1x2K1k2第三节第三节 分支定界法分支定界法max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20B14、分别求解一对分枝 在一般情况下，对某个分析问题（伴随规划）求解时，可能出现以下几种可能：（1）无可行解，说明该枝情况已查明，不需要由此再继续分枝，该分枝称为树叶（2）得到整数最优解,若求得整数最优解，则该分枝情况也已查明，不需要再对其继续分枝，该分枝也是树叶（3）得到非整数最优解（包括两种情况） A：该最优解的目标函数值Z不大于当前的下界Z，则该分枝内不可能含有原问题的整数最优解，因此该分枝不需要继续

29、分枝，称之为枯枝 B：若该最优解的目标函数值Z大于当前的下界Z下界，则仍需对该枝继续分枝，以查明该分枝是否有目标函数值比当前的下界Z更好的整数最优解第三节第三节 分支定界法分支定界法 因每个分枝的求解结果不外乎上述各种情况，因此每个分枝求解结果可表明它或是不需要继续分枝（树叶或枯枝）或是要继续分枝， 若一对分枝都需要继续分枝时，首先将目标函数值较优的分枝求解，而对目标函数值稍差的那一枝暂且放下，待目标函数较优的那枝全部分解到不能再分，全部查清时为止，再考虑目标函数值稍差的那枝，也将它全部查清，这样做，有可能减少一部分计算工作量 对于本题问题B1，B2的模型及求解如下：第三节第三节 分支定界法分

30、支定界法问题B1：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 5x1,x20问题B2max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x1,x20解为x1=(5,4) f1=130解为x2=(6,3.75) f2=135问题B1的解是整数解，它当然也是问题A0的整数可行解，故A0的整数最优解Zf1130，此时可将下界Z下界修改为Z下界f1130同时问题B1也被查清，不需要再继续分枝，即问题B1是树叶第三节第三节 分支定界法分支定界法 而问题B2的最优解不是整数最优解，且f2=135Z下界，因此需要继续分枝 故问题A2分别增加约束条件，x

31、24,x23，分为A3，A4两枝，建立相应的伴随规划B3，B4问题B3：max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x2 3x1,x20问题B4：max z=10 x1+20 x25x1+8x260 x1 8x2 4x16x2 4x1,x20求解问题B3，得到最优解为X（7.2，3）f3=132问题B4无可行解第三节第三节 分支定界法分支定界法5、修改上、下界(1)修改下界Z下界 修改下界的时机：每求出一个整数可行解时，都要作修改下界Z的工作 修改原则：在至今所有计算出的整数可行解中，选目标函数值最大的那个作为最新下界Z下界，因此用分枝定界法的求解过程中，下界Z

32、是不断增大的(2)修改上界Z上界 上界Z的修改时机：每求解完一对分枝，都要考虑修改上界 修改原则：挑选在迄今为止所有未被分枝的问题的目标函数值中最大的一个作为新的上界，新的上界Z应该小于原来的上界，在分枝定界法的整个求解过程中，上界的值在不断的减小，第三节第三节 分支定界法分支定界法 本例中，当解完一对分枝问题B1，B2时，因为x1是整数解，因此修改下界Z下界=f1=130 ,而f2是迄今未被分枝的问题中目标函数最大的,因此修改上界Z上界=f2=135 在求解完B3，B4后，因为无新的整数可行解，因此下界Z不变，而迄今为止还没被分枝的问题中(B1，B3，B4)，目标函数值最大为f3=132，因

33、此修改上界Z上界=132 因为B3的最优解x3=(7.2,3),f3=132，还不是整数，但f3z下界=130，故问题A3 还需要继续分枝，增加约束条件x17,x18，A3分为A5，A6两枝，求解相应的伴随规划B5，B6：第三节第三节 分支定界法分支定界法解得x5=(7,3),f5=130 修改下界Z下界=130，X6=(8,2.5) f6=130 修改上界Z上界=f1=f5=f6=130问题B5：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 6x2 3 x1 7x1,x20问题B6：max z=10 x1+20 x25x1+8x260 x1 8x2 4x1 6x

34、2 3x1 8x1,x20第三节第三节 分支定界法分支定界法6、结束准则 当所有分枝均已查明(或无可行解，或为整数可行解，或其目标函数值不大于下界Z)且此时上界与下界相等，则已得到原问题的整数最优解，即目标函数值为下界Z的那个整数解 在本例中，当解完B5，B6后，得到上下界相等，又B5是树叶，B6为枯枝，因此所有分枝(B1,B4,B5,B6) 均已查明，故得问题A0的最优解 X=X5=(7,3) Z=130 或X=X1=(5,4) Z=130第三节第三节 分支定界法分支定界法x1=5.6 x2=4f0=136问题B0A0Z上界 =136Z下界=0 x15x16x17x18x1=5 x2=4f1

35、=130问题B1x1=6 x2=3.75f2=135问题B2Z上界 =135Z下界=130 x23x24x1=7.2 x2=3f3=132问题B3不可行问题B4x1=7 x2=3f5=130问题B5x1=8 x2=2.5f6=130问题B6Z上界 =132Z下界=130Z上界 =130Z下界=130A1A2A3A4A5A6第三节第三节 分支定界法分支定界法分枝定界法计算步骤第1步：将原整数规划称为问题A0，去掉问题A0的整数条件，得到伴随规划B0第2步：求解问题B0，有以下几种可能：(1)B0没有可行解，则A0也没有可行解，停止计算(2)得到最优解，且满足整数条件，则B0的最优解也是A0的最优

36、解，停止计算(3)得到不满足整数条件的最优解，记它的目标函数值为f0，这时需要对问题进行分枝，转下一步第3步：确定初始上下界Z上界，Z下界 以f0作为上界Z上界，观察出问题A0的一个整数可行解，将其目标函数值记为下界Z，若观察不到，则可记Z下界=-，转下一步第三节第三节 分支定界法分支定界法第4步，将问题B0分枝 在B0的最优解中，任选一个不符合整数条件的变量xj，其值为aj，以aj表示小于aj的最大整数，构造两个约束条件： xjaj xjaj+1 将这两个约束条件分别加到问题B0的约束条件中，得到B0的两个分枝：问题B1，B2第5步：求解分枝问题 对每个分枝问题求解，可能得到以下几种可能 (

37、1)分枝无可行解：该分枝是树叶 (2)求得该分枝的最优解，且满足整数条件，将该最优解的目标函数值作为新的下界Z下界，该分枝也是树叶 (3)求得该分枝的最优解，且不满足整数条件，但其目标函数值不大于当前下界Z下界，则该分枝是枯枝，需要剪枝 (4)求得不满足A0的整数条件的该分枝的最优解，且其目标函数值大于当前下界Z下界，则该分枝需要继续进行分枝第三节第三节 分支定界法分支定界法 若是前3种情况，表明该分枝情况已探明，不需要继续分枝 若求解一对分枝的结果表明这一对分枝都需要继续分枝时，则可先对目标函数值大的那个分枝进行分枝计算，且沿着该分枝一直继续进行下去，直到全部探明情况为止，再过来求解目标函数

38、值较小的那个分枝第三节第三节 分支定界法分支定界法第6步 修改上下界(1)修改下界：每求出一次符合整数条件的可行解时，都要考虑修改下界Z下界，选择迄今为止最好的整数可行解相应的目标函数值作为下界(2)修改上界：每求解完一对分枝，都要考虑修改上界，上界的值应是迄今为止，所有未被分枝的问题的目标函数值中最大的一个 在每解完一对分枝，修改完上下界后，若已有Z上界=Z下界，此时所有分枝均已查明，即得到问题的最优值，求解结束，若仍有Z上界Z下界，则说明仍有分枝没有查明，需要继续分枝，回到第4步第三节第三节 分支定界法分支定界法p分支定界的实质是在保留原问题全部整数可行解前提下，将原问题分解为若干子问题，

39、即分支，并利用子问题的目标值来判定分支的界限。 p整数线性规划的分支原则是利用整数规划的相邻整数点之间无可行域这一特点，因而可以按相邻整数为边缘来分支。取整数且 , , 0, 62 2054 . .34max2121212121xxxxxxxxtsxxZ第三节第三节 分支定界法分支定界法0, 62 2054 . .34max21212121xxxxxxtsxxZ最优解:(5/3,8/3)第三节第三节 分支定界法分支定界法一、分支定界法求解过程一、分支定界法求解过程去掉取整约束，求解下面相应的线性规划去掉取整约束，求解下面相应的线性规划B0 x2x1Z上界=14.75Z下界=0最优解:(1,16

40、/5)目标函数最优值：68/5最优解:(2,2)目标函数最优值：140, 1 62 2054 . .34max211212121xxxxxxxtsxxZ0, 2 62 2054 . .34max211212121xxxxxxxtsxxZB1B2整数解不再分支第一次对第一次对x1分支分支:分成分成 x15/3=1 和和x15/3+1=2，将，将约束分别添加到上面的线性规划约束分别添加到上面的线性规划B0中，得到线性规划中，得到线性规划B1和和B2x1x2第三节第三节 分支定界法分支定界法Z上界=14.75 Z下界=14最优解:(1,3)目标函数最优值：11B11最优解:(0,4)目标函数最优值：

41、12整数解不再分支B120, 3 , 1 62 2054 . .34max2121212121xxxxxxxxtsxxZ0, 4 , 1 62 2054 . .34max2121212121xxxxxxxxtsxxZ所有分支都检查完毕，得到最优解所有分支都检查完毕，得到最优解(2, 2)。整数解不再分支B1的最优解中含有非整数，再对的最优解中含有非整数，再对x2分支：分支：x2 16/5=3和和x2 16/5+1=4第三节第三节 分支定界法分支定界法求解过程可用下列树状结构表示求解过程可用下列树状结构表示 X1=5/3X2=8/3X1=1X2=16/5Z=68/5X1=2X2=2Z=14x11

42、x12子问题子问题B1X1=1X2=3Z=11X1=0X2=4Z=12x23x24子问题子问题B2子问题子问题B12子问题子问题B11停止分解，因为解为整数停止分解，因为解为整数Z上界=14.75Z下界=0Z上界=14Z下界=14练习：利用分枝定界法求解max z=x1+x2 14x1+9x251 -2x1+x2 1/3 x1,x20，取整数x1=3/2 x2=10/3f0=29/6问题B0A0Z上界 =29/6Z下界=0 x11x12x12x13x1=1 x2=7/3f1=10/3问题B1x1=2 x2=23/9f2=41/9问题B2Z上界 =41/9Z下界=0 x22x23x1=33/14

43、 x2=2f3=61/14问题B3无可行解问题B4x1=2 x2=3f5=4问题B5x1=3 x2=1f6=4问题B6Z上界 =61/14Z下界=0Z上界 =4Z下界=4A1A2A3A4A5A6第三节第三节 分支定界法分支定界法目目 录录p整数规划实例与模型整数规划实例与模型p0 01 1整数规划的建模方法整数规划的建模方法p分支定界法分支定界法p割平面法割平面法p指派问题指派问题p应用举例和应用举例和ExcelExcel求解求解p 基本思想基本思想：首先求解相应的线性规划，然后不断增加适当的线性约束，将原可行域中不含整数可行解的一部分割掉，最终得到一个极点是整数坐标的可行域，而该极点恰好是原

44、整数规划问题的最优解。p割平面法步骤：步骤：n（1）解除整数约束，用单纯形法求解。如所得到的解为整数解，停止计算；否则转步骤（2）。n（2）寻求附加约束（割平面方程）；n（3）将割平面方程标准规范化后加到约束方程组中求解，如所得到的解仍为非整数，则转步骤（2），直到找到最优整数解。p 难点及重点难点及重点：如何找到割平面方程，并使包含割平面约束在内的新的规划问题的一个极点解成为最优整数解。第三节割平面法第三节割平面法取整数 , , 0, 1824 1432 . .23max2121212121xxxxxxxxtsxxZ原问题去掉整数约束条件，得线性规划问题，并标准化基变量x3x4x1x2bx2

45、0.50-0.500.001.002.50 x1-0.250.751.000.003.25-z-0.25-1.250.000.00-14.75最后的单纯形表0 , , , 18 24 14 32 . .23max432142132121xxxxxxxxxxtsxxZ254213212xxx在最优表b列各分数中有最大小数部分对应的行中写下非整数解约束方程,即第一行： 第三节割平面法第三节割平面法 所有系数和常数项分解为整数和正真分数之和，并把整系数项移到左边 )(24213212142xxxx取整数且 , ,0, 2/12/121/ 1824 1432 .23max212143212121xxx

46、xxxxxxxtsxxZ 考虑到所有变量为非负整数 得到新的整数规划问题：0)(42132121xx143 xx化化简简0)(42132121xx143 xx化化简简重复上面的过程，直到得到整数解第三节割平面法第三节割平面法左边为整数且小于0否则如果大于1(x2-x4-2)-1/2=-1/2x3-1/2x4-1/2x3-1/2x4+x5=-1/2基变量x3x4x1x2x5bx21/2-1/20105/2x1-1/43/410013/4x5-1/2-1/2001-1/2-z-1/4-5/4000-59/4x20-10112x10110-1/27/2x31100-21-z0-100-1/2-58/

47、4最优解为x1=7/2 x2=1仍为非整数解，所以转到第二步再求割平面，从上表写下非整数解x1的约束方程为 x1+x4-1/2x5=7/2重复上述分析过程得第三节割平面法第三节割平面法x1+x4-x5-3=1/2-1/2x50即为割平面方程，将新的约束条件加到原问题中，得到新问题对新问题用单纯形法求解得到最优解X1=4 ,x2=1 z=14 为整数解，计算停止第三节割平面法第三节割平面法p整数规划实例与模型整数规划实例与模型p0 01 1整数规划的建模方法整数规划的建模方法p分支定界法分支定界法p割平面法割平面法p指派问题指派问题p应用举例和应用举例和ExcelExcel求解求解第五节指派问题

48、第五节指派问题p(一)问题的提出n有n项不同的任务需要完成，而恰好有n个人（或n台设备）可以分别完成其中的一项工作，但由于任务的性质和个人的专长不同，因而不同的人去完成不同的工作产生的效率就不一样。那么，应派哪一个人去完成哪一项工作才能使总的效率最高？ 第五节指派问题第五节指派问题例设有4个A、B、C、D四个人，都可以各自完成四种不同工作中的任一种，其花时间如下表：规定每人应做且只做一种工作，问应如何安排，使他们完成四种工作的总时间最少？甲乙丙丁A6583B105415C137211D139710解令A为第1，B为第2，C为第3，D为第4甲为第1工作，乙为第2工作，丙为第3工作，丁为第4工作令

49、xij=1表示分配第i人做第j工作Xij=0表示不分配第i人做第j工作 依题意得：Minz=6x11+5x12+8x13+3x14+10 x21+5x22+4x23+15x24+13x31+7x32+2x33+11x34+13x41+9x42+7x43+10 x44X11+x12+x13+x14=1X21+x22+x23+x24=1X31+x32+x33+x34=1X41+x42+x43+x44=1X11+x21+x31+x41=1X12+x22+x32+x42=1X13+x23+x33+x43=1X14+x24+x34+x44=1Xij=1或0 i,j=1,2,3,4每人只许做一份工作每份工

50、作由一个人负责指派问题模型j.i, 1 0 ,2, 1 , 1 ,2, 1 , 1 .min1111对一切或 ijnjijniijninjijijxnixnjxtsxc第五节指派问题第五节指派问题例 某市计划在今年内修建4座厂房：发电厂、化肥厂、机械厂、食品厂，分别记为B1，B2，B3，B4。该市有4个大的建筑队A1，A2，A3，A4都可以承担这些厂房的建造任务。但由于各个建筑队的技术水平、管理水平等不同，它们完成每座厂房所需要的费用也不一样。为计算简单，设有关数据如下表所示。又因希望尽早把这4座厂房都建造好，故需把这4个建筑队都动用起来，即每个队分配一项任务。市政府经费紧张，于是提出研究下述

51、问题：究竟应该指派哪个队修建哪个厂，才能使建造4座厂房所花的总费用最少？ 各建筑队完成每座厂房所需费用（万元） B1B2B3B4A13452A28576A39645A45366第五节指派问题第五节指派问题这就是一个指派问题，对于指派问题，必须 具有以下条件：(1)每项工作只能分配一个单位或一个人去完成(2)每个单位或人只能接受其中一项任务设cij(i,j=1,2n)为第i个人做第j项工作的费用，由cij组成的方阵C=(cij)nn称为效率矩阵 对上例其效率矩阵为6 6 3 55 4 6 96 7 5 82 5 4 3C定义决策变量如下：xij1，若指派第i人做第j项工作0，若不指派第i人做第j

52、 项工作第五节指派问题第五节指派问题二、可行解的性质指派问题的可行解是矩阵(xij)nn，它是由一些单位向量构成的n阶方阵，方阵的每行每列有一个且只有一个1，其余为0，例如当n=4时，其可行解可以 为：0 0 0 11 0 0 00 0 1 00 1 0 0X第五节指派问题第五节指派问题定理6.1 如果对系数矩阵C=(cij)nn的任一行(列)各元分别减去该行(列)的最小元，得到新矩阵B=(bij)nn，则以B为系数矩阵的指派问题的最优解xij和原问题的最优解相同匈牙利算法：首先通过行(列)变换使系数矩阵出现01。从系数矩阵的每行元减去该行的最小元2。从系数矩阵的每列元减去该列的最小元BC3

53、3 0 11 0 2 41 2 0 20 3 2 03 3 0 21 0 2 51 2 0 30 3 2 16 6 3 55 4 6 96 7 5 82 5 4 3第五节指派问题第五节指派问题定理6.2 设 C=(cij)nn是一个效率矩阵，若可行解X的n 个1所对应的n个cij等于0，则X是最优解即在效率矩阵B中若能找到n 个位于不同行不同列上的0元，则就可找到最优解。定理6.3设矩阵C中一部分元为0，一部分不为0，则划去C中所有0元所需要的最少直线数等于C中不同行不列上0元的个数第五节指派问题第五节指派问题p获取最少数直线的方法：p(1)找出矩阵C中没有圈0并且含有0元最少的一行(列)，从

54、该行(列)中圈出一个0，再通过这个0作一竖(横)线划去此0所在之列(行)p逐行检查，对每行只有一个且未被直线划的零元时，将该零元素圈起，然后对该零元素所在的列划一竖(表示该工作不再指派其他人去完成)p逐列检查，对每列只有一个且未被直线划的零元时，将该零元素圈起，然后对该零元素所在的行划一横p(2)对C中余下的各行各列重复步骤1，但已圈数的行和列不再圈数3 3 0 11 0 2 41 2 0 20 3 2 0由于rn=4 ，所以需要调整1 在所有未划去数中找出最小数，设为d；2 将所有未画去的数都减去d，而对位于两直线交点处的数则加上d。3 得出新的指派方案。2 2 0 01 0 3 40 1

55、0 10 3 3 0第五节指派问题第五节指派问题0 0 1 00 1 0 01 0 0 00 0 0 1也就是最优指派方案为A1队修B1厂A2队修B4厂，A3队修B3厂A4队修B2厂X11=x24=x33=x42=1其余为0总费用为z=c11+c24+c33+c42=16万将所有圈0换成1，其他都换成0得最优解：第五节指派问题第五节指派问题2 2 0 01 0 3 40 1 0 10 3 3 0也就是最优指派方案为A1队修B4厂A2队修B2厂，A3队修B3厂A4队修B1厂X14=x22=x33=x41=1其余为0总费用为z=c14+c22+c33+c41=16万0 0 0 10 1 0 00

56、0 1 01 0 0 0最优解为：总费用z=c41+c22+c33+c41=16万最优解不惟一第五节指派问题第五节指派问题匈牙利算法总结：第一步：使系数矩阵每行每列都出现0元素第二步 画最少0元素的覆盖线，逐行检查，对每行只有一个且未被直线划的零元时，将该零元素圈起，然后对该零元素所在的列划一竖,逐列检查，对每列只有一个且未被直线划的零元时，将该零元素圈起，然后对该零元素所在的行划一横若所画直线等于n，则问题已解决，否则转下一步第三步 在未划去的各数中找出最小的一个，设为d，然后将未划去的各数都减去d，而对位于两直线交叉的各数则都加上d，这样，又得到一个新的矩阵，对此矩阵再重复第二步第五节指派

57、问题第五节指派问题19 16 17 2617 23 21 1918 22 23 1924 21 18 51求根据下面的效能矩阵求最优指派19 16 17 2617 23 21 1918 22 23 1924 21 18 51解(1)根据效能矩阵，使每行每列都出现0元3 0 1 100 6 4 20 4 5 19 6 3 03 0 0 100 6 3 20 4 4 19 6 2 0每行减最小元每列减最小元第五节指派问题第五节指派问题3 0 0 100 6 3 20 4 4 19 6 2 0(2)试求最优解(3)调整并试求最优解4 0 0 100 5 2 10 3 3 010 6 2 0(4)调整并试求最优解5 0 0 110 3 0 10 1 1 010 4 0 0即最优解：X11=x24=x32=x43=1 其余为0最优值为：z=15+18+21+16=700 1 0 00 0 1 01 0 0 00 0 0 1(5)原问题的最优解为第五节指派问题第五节指派问题课堂作业：由4个人完成4项任务，由于能力不同，完成所需要的时