运筹学-第5章整数规划

1、第第5章章 整数规划整数规划 OR:SM2 第一节第一节 整数规划问题及数学模型整数规划问题及数学模型 纯整数规划纯整数规划 0-1规划规划 混合整数规划混合整数规划 第二节第二节 整数规划求解整数规划求解 分枝定界法分枝定界法 割平面法割平面法 隐枚举法隐枚举法 匈牙利法匈牙利法 OR:SM3 第一节第一节 整数规划问题及数学模型整数规划问题及数学模型 一、整数规划问题简述一、整数规划问题简述 线性规划的决策变量取值可以是任意非负实数，但许多实际线性规划的决策变量取值可以是任意非负实数，但许多实际 问题中，只有当决策变量的取值为整数时才有意义问题中，只有当决策变量的取值为整数时才有意义 例如

2、，产品的件数、机器的台数、装货的车数、完成工作的人例如，产品的件数、机器的台数、装货的车数、完成工作的人 数等，分数或小数解显然是不合理的。数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称要求全部或部分决策变量的取值为整数的线性规划问题，称 为整数规划为整数规划( (Integer Programming) )。 全部决策变量的取值都为整数，全整数规划全部决策变量的取值都为整数，全整数规划(All IP) 仅要求部分决策变量的取值为整数，混合整数规划仅要求部分决策变量的取值为整数，混合整数规划(Mixed IP) 要求决策变量只取要求决策变量只取0或或1

3、值，则称值，则称0-1规划规划(0-1 Programming) OR:SM4 一、全一、全( (纯纯) )整数规划整数规划 产品产品 资源资源 甲甲乙乙现有量现有量 A219 B5735 单台利润单台利润65 例：例：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台 产品的获利能力如下表所示，产品的获利能力如下表所示，问如何安排利润最大问如何安排利润最大(变量取整变量取整)？ 解：解：设设x1为甲产品的台数，为甲产品的台数，x2为乙产品的台数，则模型为：为乙产品的台数，则模型为： maxZ = 6x1 +5x2 2x1 + x2 9

4、 5x1 +7x2 35 x1, x2 0,且为整数且为整数 OR:SM5 二、二、0-10-1规划规划 登山队员可携带最大重量为登山队员可携带最大重量为2525公斤，问应带哪些物品，重要性最大？公斤，问应带哪些物品，重要性最大？ 解：对于每一种物品无非有两种状态，带或者不带，不妨设解：对于每一种物品无非有两种状态，带或者不带，不妨设 序号序号1234567 物品物品食品食品氧气氧气冰镐冰镐绳索绳索帐篷帐篷相机相机设备设备 重量重量55261224 重要性系数重要性系数201518148410 0-1规划的模型：规划的模型： OR:SM6 三、混合整数规划三、混合整数规划 例：例：某产品有某产

5、品有 n 个区域市场，各区域市场的需求量为个区域市场，各区域市场的需求量为 bj 吨吨/月；现月；现 拟在拟在 m 个地点中选址建生产厂，一个地方最多只能建一家工厂；若个地点中选址建生产厂，一个地方最多只能建一家工厂；若 选选 i 地建厂，生产能力为地建厂，生产能力为 ai 吨吨/月，其运营固定费用为月，其运营固定费用为Fi 元元/月；已知月；已知 址址 i 至至 j 区域市场的运价为区域市场的运价为cij元元/吨。如何选址和安排调运，可使总费吨。如何选址和安排调运，可使总费 用最小？用最小？ 解：解： 假设假设 yi =1，选择第，选择第 i 址建厂，址建厂， yi =0，不选择第，不选择第

6、 i 址建厂；址建厂； 计划从厂址计划从厂址i 至市场至市场 j 的运输的运输 量为量为xij (连续型决策变量连续型决策变量)。 OR:SM7 第一节第一节 整数规划问题及数学模型整数规划问题及数学模型 二、整数规划问题建模举例二、整数规划问题建模举例 参见教材：参见教材： P110: 5.1 P115: 5.1-5.6 P122: 5.9 OR:SM8 整数规划建模举例整数规划建模举例 一、生产基地规划一、生产基地规划 例：例：某公司拟建某公司拟建A、B两种类型的生产基地若干个，每个基地占地两种类型的生产基地若干个，每个基地占地 面积，所需经费，建成后生产能力及现有资源情况如下表所示，问面

7、积，所需经费，建成后生产能力及现有资源情况如下表所示，问A、 B类型基地各建设多少个，可使总生产能力最大？类型基地各建设多少个，可使总生产能力最大？ 解：设解：设A、B两类基地各建两类基地各建 设设 x1,x2 个，则其模型为：个，则其模型为： OR:SM9 二、人员安排规划二、人员安排规划 某服务部门各时段某服务部门各时段( (每每2 2小时为一时段小时为一时段) )需要的服务人数如表：需要的服务人数如表： 解：设第解：设第j 时段开始时上班的服时段开始时上班的服 务员人数为务员人数为xj 第第 j 时段来上班的服务员将在时段来上班的服务员将在 第第j +3 时段结束时下班，故决策时段结束时

8、下班，故决策 变量有变量有x1, x2, x3, x4, x5 。 按规定，服务员连续工作按规定，服务员连续工作8 8小小 时时(4(4个时段个时段) )为一班。如何安排为一班。如何安排 服务员的工作时间，使服务员服务员的工作时间，使服务员 总数最少？总数最少？ OR:SM10 三、项目投资选择三、项目投资选择 有有600万元投资万元投资5个项目，收益如表，求利润最大的方案？个项目，收益如表，求利润最大的方案？ OR:SM11 四、互斥约束问题四、互斥约束问题 例如关于煤资源的限制，其约束条件为：例如关于煤资源的限制，其约束条件为： 企业也可以考虑采用天然气进行加热处理：企业也可以考虑采用天然

9、气进行加热处理： 这两个条件是互相排斥。这两个条件是互相排斥。 引入引入0-1变量变量 y ，令，令 互斥问题可由下述的条件来代替，其中互斥问题可由下述的条件来代替，其中M是任意大的正数。是任意大的正数。 OR:SM12 五、租赁生产问题五、租赁生产问题 某服装公司租用生产线拟生产某服装公司租用生产线拟生产T恤、衬衫和裤子，每年可使用劳动恤、衬衫和裤子，每年可使用劳动 力力 8200 h，布料，布料 8800m2，问如何安排利润最大？，问如何安排利润最大？ T恤恤衬衫衬衫裤子裤子 劳动力劳动力(h)326 布料布料(m2)0.81.11.5 售价售价(元元)250400600 可变成本可变成本

10、(元元)100180300 生产线租金生产线租金(万万)201510 假设：假设：yj=1，要租用生产线，要租用生产线 j yi=0，不租用生产线，不租用生产线 j 第第 j 种服装生产量种服装生产量 xj x1My1 x2My2 x3My3 其中，其中，M为任意大的正数。为任意大的正数。 OR:SM13 六、任务指派问题六、任务指派问题 甲乙丙丁四个人，甲乙丙丁四个人，ABCD四项任务，如何指派总时间最短？四项任务，如何指派总时间最短？ 解：解： 引入引入0-1变量变量xij ， xij =1：任务：任务j指派人员指派人员i去完成去完成 xij =0：任务：任务j不派人员不派人员i去完成去完

11、成 一项任务只由一个人完成一项任务只由一个人完成 一人只能完成一项任务一人只能完成一项任务 OR:SM14 第二节第二节 整数规划问题求解整数规划问题求解 一、舍入化整法一、舍入化整法 maxZ = 6x1 + 5x2 2x1 + x2 9 5x1 + 7x2 35 x1,x20且为整数且为整数 x1 x2 369 3 5 9 (28/9, 25/9) 对于本例，松驰问题对于本例，松驰问题的最的最 优解：优解：x1*=28/9， x2* =25/9， Z * =293/9 整数规划问题取消整数限制整数规划问题取消整数限制 后称为松驰问题。后称为松驰问题。 x1 =3， x2 =3，Z =33，

12、不满足约束条件，不满足约束条件5 x1 + 7 x2 35，不可行；，不可行； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解；，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，而且是最优解。，满足约束条件，而且是最优解。 OR:SM15 从数学模型上看整数规划似乎是线性规划从数学模型上看整数规划似乎是线性规划 的一种特殊形式，求解只需在线性规划的基础的一种特殊形式，求解只需在线性规划的基础 上，通过舍入取整，寻求满足整数要求的解即上，通过舍入取整，寻求满足整数要求的解即 可。但实际上两者却有很大的不同，通过舍入可。但实际

13、上两者却有很大的不同，通过舍入 得到的解（整数）也不一定就是最优解，有时得到的解（整数）也不一定就是最优解，有时 甚至不能保证所得倒的解是整数可行解。甚至不能保证所得倒的解是整数可行解。 OR:SM16 二、穷举整数法二、穷举整数法 对于决策变量少，整数可行解对于决策变量少，整数可行解 数量较少时，这种穷举法有时是可数量较少时，这种穷举法有时是可 行的，并且是有效的。行的，并且是有效的。 但对于大型的整数规划问题，但对于大型的整数规划问题， 可行的整数解数量很多，用穷举法可行的整数解数量很多，用穷举法 求解是不可能的。例如，指派问题。求解是不可能的。例如，指派问题。 5x1 +7 x2 =35

14、 2x1 + x2 = 9 x1 x2 123 1 2 5 3 4 4 17 ( 3, 2) 99 OR:SM17 三、分枝定界法三、分枝定界法 松驰问题：某一整数规划对应的线性规划问题称为松驰问题。松驰问题：某一整数规划对应的线性规划问题称为松驰问题。 即不考虑决策变量整数限制的整数规划问题。即不考虑决策变量整数限制的整数规划问题。 分支定界法基本思路：分支定界法基本思路： 在松驰问题可行域中寻找使目标函数值达到最优的整数解。在松驰问题可行域中寻找使目标函数值达到最优的整数解。 定理定理5-1： 对于某一求对于某一求max(min)的整数规划问题，其目标函数最优值的整数规划问题，其目标函数最

15、优值 不超过不超过(低于低于)其松驰问题的目标函数最优值。其松驰问题的目标函数最优值。 OR:SM18 分枝定界法基本步骤分枝定界法基本步骤 不考虑整数限制，先求出相应松驰问题的最优解。不考虑整数限制，先求出相应松驰问题的最优解。 若求得的最优解符合整数要求，则是原若求得的最优解符合整数要求，则是原IP的最优解。的最优解。 若不满足整数条件，则任选一个不满足整数条件的变量来构造若不满足整数条件，则任选一个不满足整数条件的变量来构造 新的约束，在原可行域中剔除部分非整数解。新的约束，在原可行域中剔除部分非整数解。 依次在缩小的可行域中求解新构造的线性规划的最优解，直依次在缩小的可行域中求解新构造

16、的线性规划的最优解，直 到获得原整数规划的最优解。到获得原整数规划的最优解。 定界的含义：定界的含义： IP是在相应的是在相应的LP基础上增加整数约束基础上增加整数约束 IP的最优解不会优于相应的最优解不会优于相应LP的最优解的最优解 对对MaxZ的的IP，LP的的Z*是是IP的上界的上界 OR:SM19 x2 x1 5 3 0 6 3 21 (1) (2) 分枝定界法举例：分枝定界法举例： 12 12 12 12 951 1414 1 2 3 0 max , Zxx xx xx x x 且且为为整整数数 2 4 OR:SM20 x2 x1 5 3 0 6 3 21 (1) (2) 第一步：图

17、解法求松驰问题最优解第一步：图解法求松驰问题最优解 (定界定界) 12 12 12 12 951 1414 1 2 3 0 max , Zxx xx xx x x 且且为为整整数数 2 4 A (3/2 , 10/3) (0 ) 0 (0 ) 3 10 (,) 23 : 29 6 T X LP Z LP0 29 6 0 上上 界界 ： 下下 界界 ： OR:SM21 x2 x1 5 3 0 6 3 21 (1) (2) 第二步：分枝第二步：分枝 2 4 A LP2 选择其中一个取值非整数变量进行分支，如选择其中一个取值非整数变量进行分支，如x1。 当当1x1Z(1)，故选择，故选择LP2进行分

18、支，进行分支， x2=23/9，分支结果：，分支结果：x22，x23 LP4 D 3 12 12 12 1 2 12 951 1414 1 2 3 2 2 0 ( ) max , Zxx xx xx x x xx 4 12 12 12 1 2 12 951 1414 1 2 3 2 3 0 ( ) max , Zxx xx xx x x x x (33/14 , 2) (3) 3 (3) 33 (, 2) 14 : 61 14 T X LP Z 4 :LP无 可 行 解 6 1 1 4 0 上上 界界 ： 下下 界界 ： OR:SM23 x2 x1 5 3 0 6 3 21 (1) (2) 第

19、四步：比较分枝结果，选第四步：比较分枝结果，选 择下一步分支区域，择下一步分支区域，定界定界 2 4 A LP3LP1 B C 因因Z(3)Z(1)，故选择，故选择LP3进行分支，进行分支， x1=33/14，分支结果：，分支结果：x12，x13 LP4 D 5 12 12 12 1 2 1 12 951 1414 1 2 3 2 2 2 0 ( ) max , Zxx xx xx x x x xx 6 12 12 12 1 2 1 12 951 1414 1 2 3 2 2 3 0 ( ) max , Zxx xx xx x x x x x E LP5 LP6 (2, 2) (5) 5 (5

20、) (2, 2) : 4 T X LP Z F (3, 1) (6) 6 (6) (3,1) : 4 T X LP Z 4 4 上上 界界 ： 下下 界界 ： OR:SM24 1 (1) 12 710 1, 33 LP xxZ ： 0 (0 ) 12 31029 , 236 LP xxZ ： 2 (2) 12 2341 2, 99 LP xxZ ： x11x1 2 29 6 0 上上 界界 ： 下下 界界 ： 4 1 9 0 上上 界界 ： 下下 界界 ： x22x2 3 3 (3 ) 12 3361 ,2, 1414 L P xxZ ： 4 LP ： 无可行解 6 1 1 4 0 上上 界界

21、 ： 下下 界界 ： x12x1 3 5 (5) 12 2,2,4 LP xxZ ： 6 (6) 12 3,1,4 LP xxZ ：4 4 上上 界界 ： 下下 界界 ： OR:SM25 x2 x1 5 7 0 9 453 (1) (2) 12 12 12 1212 max65 5735 29 ,0;, Zxx xx xx xxxxI 分支定界法举例：分支定界法举例： OR:SM26 x2 x1 5 7 0 9 453 (1) (2) A ( 28/9, 25/9 ) (0) 0 (0) 17 (3, 2) 99 : 5 32 9 T X LP Z LP0 OR:SM27 x2 x1 5 7

22、0 9 453 (1) (2) A (1) 1 (1) 6 (3, 2) 7 : 2 32 7 T X LP Z LP1 LP2 B B( 3, 20/7 ) C C( 4, 1 ) (2) 2 (2) (4,1) : 29 T X LP Z OR:SM28 x2 x1 5 7 0 9 453 (1) (2) E (3) 3 (3) 4 (2,3) 5 : 4 31 5 T X LP Z E( 14/5, 3) D (4) 4 (4) (3, 2) : 28 T X LP Z LP3 LP4 3 2 D( 3, 2) OR:SM29 x2 x1 5 7 0 9 453 (1) (2) F (5

23、) 5 (5) 4 (2,3) 7 : 6 29 7 T X LP Z F( 2, 25/7) D LP4 3 2 D( 3, 2) 2 LP6: 无可行解(x1=3) LP5 OR:SM30 x2 x1 5 7 0 9 453 (1) (2) H (7) 7 (7) (2,3) : 27 T X LP Z G( 2, 3)G LP8 LP4 3 2 H( 7/5, 4) 2 (8) 8 (8) 7 (, 4) 5 : 2 28 5 T X LP Z 4 LP7 OR:SM31 1 (1 ) 12 62 3,2,3 2 77 L P xxZ ： 0 (0 ) 12 175 3,2,32 999

24、 LP xxZ ： 2 (2) 12 4,1,29 LP xxZ ： 3 (3) 12 3,2,28 LP xxZ ：4 (4) 12 44 2,3,31 55 LP xxZ ： 5 ( 5 ) 12 46 2 ,3,2 9 77 L P xxZ ： 6 LP ： 无 可 行 解 7 (7) 12 2,3,27 LP xxZ ： 8 (8 ) 12 22 1,4,28 55 LP xxZ ： x13x1 4 x22x2 3 x12x1 3 x23x2 4 0 9 5 32 下界： 上界： 29 7 2 32 下界： 上界： 29 5 4 31 下界： 上界： 29 7 6 29 下界： 上界：

25、 29 29 下界： 上界： OR:SM32 步骤步骤1、整数规划问题为、整数规划问题为A，其松弛问题为，其松弛问题为B，设为问，设为问 题题A（max）的初始下界（）的初始下界（min问题为上界）问题为上界） 步骤步骤2、求解问题求解问题B，有三种情况：，有三种情况： （a）B 无可行解，此时问题无可行解，此时问题A也无可行解，停止。也无可行解，停止。 （b）B 有最优解且为整数，则问题有最优解且为整数，则问题B的最优解即是的最优解即是 问题问题A的最优解，停止。的最优解，停止。 （c）B 有最优解但不是整数，设目标函数值为问题有最优解但不是整数，设目标函数值为问题 A的上（下）界，转入步骤

26、的上（下）界，转入步骤3。 步骤步骤3、分支、定界。分支、定界。 步骤步骤4、比较、剪枝。比较、剪枝。 步骤步骤5、重复步骤重复步骤 3 和和 4 ，直至求出最优整数解。，直至求出最优整数解。 OR:SM33 【练习练习】用分枝定界法求解整数规划问题用分枝定界法求解整数规划问题 【解解】先求对应的松弛问题（记为先求对应的松弛问题（记为LP0）：）： 12 12 012 12 max43 1.20.810 :22.525 ,0 Zxx xx LPxx x x 用图解法得到最优解用图解法得到最优解X(0)(3.57, 7.14)T, Z(0)=35.7, 如下图所示。如下图所示。 12 12 12

27、 12 43 1 20 810 22 525 0 m ax . . , Zxx xx xx xx 且且 为为 整整 数数 OR:SM34 8.33 10 108 . 02 . 1 21 xx 255 . 22 21 xx 松弛问题松弛问题LP0的最优解：的最优解： X(0)=(3.57,7.14)T, Z(0)=35.7 x1 x2 o A B C 10 OR:SM35 10 10 x1 x2 o A B C 12 12 12 1 1 12 max43 1.20.810 22.525 : 3 ,0 Zxx xx xx LP x x x LP1 LP2 34 LP1: X(1)=(3, 7.6)

28、T, Z(1)=34.8 LP2: X(2)=(4, 6.5)T, Z(2)=35.5 12 12 12 2 1 12 max43 1.20.810 22.525 : 4 ,0 Zxx xx xx LP x x x 11 34xx增增加加约约束束及及得得到到两两个个线线性性规规划划问问题题 OR:SM36 10 10 x1 x2 o A B C LP1 LP3 34 LP3: X(3)=(4.33, 6)T, Z(3)=35.33 12 12 12 3 12 12 max43 1.20.810 22.525 : 46 ,0 Zxx xx xx LP xx x x ， 2 222 677 LP

29、xxx 选择目标值最大的分枝进行分枝，增加约束 及，显然不可行，得到线性规划 6 不可行7 2 x LP1: X(1)=(3, 7.6)T, Z(1)=34.8 D OR:SM37 10 10 x1 x2 o A C LP1 34 12 12 12 4 121 12 1 max43 1.20.810 22.525 : 464 ,0 4, Zxx xx xx LP xxx x x x ， 即可行域是一条线段 (3)(1) 3 1145 45 ZZLP xxLPLP 由于，选择进行分枝，增加约束 及，线性规划及： 6 12 12 12 5 12 12 max43 1.20.810 22.525 :

30、 56 ,0 Zxx xx xx LP xx x x ， LP4: X(4)=(4, 6)T, Z(4)=34 LP5:X(5)=(5, 5)T, Z(5)=35 5 LP1: X(1)=(3, 7.6)T, Z(1)=34.8 LP3 LP5 E F OR:SM38 尽管还可以对尽管还可以对Z(1)中的中的x2分支，但分支，但Z(5)Z(1)，因此，因此LP5的最的最 优解就是原整数规划的最优解。优解就是原整数规划的最优解。 上述分枝过程可用下图表示上述分枝过程可用下图表示 LP0:X(0)=(3.57, 7.14)T, Z0=35.7 LP1:X(1)=(3, 7.6)T Z(1)=34.

31、8 LP2:X(2)=(4, 6.5)T Z(2) =35.5 x13x14 LP3:X(3)=(4.33, 6)T Z(3)=35.33 x26 LP4:X(4)=(4, 6)T Z(4)=34 LP5:X(5)=(5, 5)T Z(5)=35 x14x15 无可行解无可行解 x27 3 5 7 0 .上上 界界 ： 下下 界界 ： 3 5 5 0 .上上 界界 ： 下下 界界 ： 3 5 3 3 0 .上上 界界 ： 下下 界界 ： 3 5 3 5 上上 界界 ： 下下 界界 ： OR:SM39 四、割平面法四、割平面法 步骤：步骤： 1、用单纯形法求解松驰问题；、用单纯形法求解松驰问题；

32、 2、在松驰问题最终单纯形表中任选一约束条、在松驰问题最终单纯形表中任选一约束条 件，构造新的约束条件件，构造新的约束条件(割平面约束割平面约束)； 3、将新的约束条件加入最终单纯形表中，求、将新的约束条件加入最终单纯形表中，求 解最优整数解。解最优整数解。 注意：注意： 割平面约束往往不是一次就可以找到。割平面约束往往不是一次就可以找到。 OR:SM40 例：用割平面法求解整数规划问题例：用割平面法求解整数规划问题 12 12 12 12 max43 30 . .10 ,0, 64 2 Z st I xx xx xx x x 解：解：1、标准化、标准化 1234 123 124 max 30

33、 .10 0,1,2,3,4 4300 64 2 j Z st I j xxxx xxx xxx x OR:SM41 2、单纯形法求解松驰问题、单纯形法求解松驰问题 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 30 10 6 4 1 0 1 2 0 1 j 4 3 0 0 4 0 x1 x4 5 5 1 2/3 1/6 0 0 4/3 -1/6 1 j 0 1/3 -2/3 0 4 3 x1 x2 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 * 5/2,15/4,0,0 T X * 85/4Z OR

34、:SM42 3、寻找割平面约束（、寻找割平面约束（1） cj 4 3 0 0 CB XB b x1 x2 x3 x4 4 3 x3 x4 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 1234 115 0 422 xxxx 134 111 12 422 xxx 1434 111 2 242 xxxx 思考：等式左端在什么条件下有可能为整数？思考：等式左端在什么条件下有可能为整数？ OR:SM43 1434 111 2 242 xxxx 34 1/2 11 0,1/2) 42 (1/2,) xx 14 0 20 0 xx 整数整数 可能为整

35、数可能为整数 所以，等式左端若为整数，则有：所以，等式左端若为整数，则有： 34 111 0 242 xx 34 111 422 xx 345 111 422 xxx 即为所寻找的割平面约束。即为所寻找的割平面约束。 OR:SM44 4、求最优整数解、求最优整数解 345 111 422 xxx cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM45 4、求最优整数解、

36、求最优整数解 345 22 xxx cj 4 3 0 0 0 CB XB b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM46 新的约束新的约束(割平面约束割平面约束)： 34 111 422 xx 34 22xx 松驰问题原约束：松驰问题原约束： 123 124 6430 210 xxx xxx 312 412 3064 102 xxx xxx 将原约束代入割平面约束：将原约束代入割平面约束： 12 6

37、xx OR:SM47 加入割平面约束后加入割平面约束后 约束条件变为：约束条件变为： 12 12 12 6430 210 6 xx xx xx x1 x2 O 10 5 10 (5/2, 15/4) 12 6430 xx 12 210 xx 7.5 6 56 2, 4 3,3 OR:SM48 3、寻找割平面约束（、寻找割平面约束（2） cj 4 3 0 0 CB XB b x1 x2 x3 x4 4 3 x3 x4 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 234 1315 844 xxx 234 733 13 844 xxx 233

38、4 373 3 484 xxxx 等式左端在什么条件下有可能为整数？等式左端在什么条件下有可能为整数？ OR:SM49 2334 373 3 484 xxxx 34 3/4 73 0,3/4) 84 (3/4,) xx 23 0 30 0 xx 整数整数 可能为整数可能为整数 所以，等式左端若为整数，则有：所以，等式左端若为整数，则有： 34 373 0 484 xx 34 733 844 xx 345 733 844 xxx 即为所寻找的割平面约束。即为所寻找的割平面约束。 OR:SM50 4、求最优整数解、求最优整数解 345 733 844 xxx cj 4 3 0 0 0 CB XB

39、b x1 x2 x3 x4 x5 4 3 x1 x2 x5 5/2 15/4 1 0 1/4 -1/2 0 1 -1/8 3/4 j 0 0 -5/8 -1/4 4 3 x1 x2 j * 3,3,0,1,0 T X * 21Z OR:SM51 新的约束新的约束(割平面约束割平面约束)： 34 733 844 xx 34 766xx 松驰问题原约束：松驰问题原约束： 123 124 6430 210 xxx xxx 312 412 3064 102 xxx xxx 将原约束代入割平面约束：将原约束代入割平面约束： 12 6533xx OR:SM52 加入割平面约束后加入割平面约束后 约束条件变

40、为：约束条件变为： 12 12 12 6430 210 6533 xx xx xx x1 x2 O 10 5 10 (5/2, 15/4) 12 6430 xx 12 210 xx 7.5 6 56 1627 , 77 3,3 OR:SM53 第三节第三节 整数规划求解整数规划求解 五、隐枚举法五、隐枚举法 u用于求解用于求解0-1整数规划问题的一种方法。整数规划问题的一种方法。 u求解步骤：求解步骤： u1、寻找目标函数值下界；、寻找目标函数值下界；(max) u2、构造过滤约束，并将其加入到原约束条件中；、构造过滤约束，并将其加入到原约束条件中； u3、写出所有解组合，比较、写出所有解组合

41、，比较Z值，并检查是否满足约值，并检查是否满足约 束条件和过滤条件，得出最优解。束条件和过滤条件，得出最优解。 u例：例： OR:SM54 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 过滤约束过滤约束(目标函数目标函数)： 3x1 - 2x2 + 5x30 (0,0,0)T 解组合解组合 (x1, x2, x3)T Z值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1,

42、 1, 0)T (1, 1, 1)T * * 1,0,1 8 T X Z OR:SM55 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 过滤约束过滤约束(目标函数目标函数)： 3x1 - 2x2 + 5x33 (1,0,0)T 解组合解组合 (x1, x2, x3)T Z值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,

43、0,1 8 T X Z OR:SM56 123 123 123 12 23 max325 22 44 3 46 0,1;1,2,3 j Zxxx xxx xxx xx xx xj 过滤约束过滤约束(目标函数目标函数)： 3x1 - 2x2 + 5x35 (0,0,1)T 解组合解组合 (x1, x2, x3)T Z值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,0,1 8 T X Z OR:SM57 123 1

44、23 123 23 max432 2534 433 1 0,1;1,2,3 j Zxxx xxx xxx xx xj 过滤约束：过滤约束： 4x1 + 3x2 + 2x3 0 (0,0,0)T 解组合解组合 (x1, x2, x3)T Z值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,1,1 9 T X Z OR:SM58 123 123 123 23 max432 2534 433 1 0,1;1,2,3 j

45、 Zxxx xxx xxx xx xj 过滤约束：过滤约束： (0,0,1)T 4x1 + 3x2 + 2x3 2 解组合解组合 (x1, x2, x3)T Z值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0)T (0, 0, 1)T (0, 1, 0)T (0, 1, 1)T (1, 0, 0)T (1, 0, 1)T (1, 1, 0)T (1, 1, 1)T * * 1,1,1 9 T X Z OR:SM59 1234 1234 1234 1234 min2534 40 24244 1 0,1;1,2,3,4 j Zxxxx xxxx xxxx xxxx xj 过滤约束：过

46、滤约束： (1,1,1,1)T 2x1 +5x2 +3x3 +4x314 解组合解组合 (x1, x2, x3, x4)T Z 值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0, 0)T (0, 0, 0, 1)T (0, 0, 1, 0)T (0, 0, 1, 1)T (0, 1, 0, 0)T (1, 0, 0, 0)T (1, 1, 1, 1)T * * 0,0,0,1 4 T X Z OR:SM60 1234 1234 1234 1234 min2534 40 24244 1 0,1;1,2,3,4 j Zxxxx xxxx xxxx xxxx xj 过滤约束：过滤约束：

47、 (0,1,0,0)T 2x1 +5x2 +3x3 +4x35 解组合解组合 (x1, x2, x3, x4)T Z 值值 约束约束 条件条件 过滤过滤 约束约束 (0, 0, 0, 0)T (0, 0, 0, 1)T (0, 0, 1, 0)T (0, 0, 1, 1)T (0, 1, 0, 0)T (1, 0, 0, 0)T (1, 1, 1, 1)T * * 0,0,0,1 4 T X Z OR:SM61 六、匈牙利法六、匈牙利法 1955年，库恩根据匈牙利数学家康尼格得年，库恩根据匈牙利数学家康尼格得 出的结论，提出了求解指派问题的方法出的结论，提出了求解指派问题的方法 匈牙利法。匈牙

48、利法。 1、原理、原理 若指派问题的系数矩阵若指派问题的系数矩阵C = (cij)n n的某行 的某行 (或某列或某列)各元素分别减去一个常数各元素分别减去一个常数k，得到一个，得到一个 新的矩阵新的矩阵C = (cij)n n ，则两个矩阵所对应的指 ，则两个矩阵所对应的指 派问题的最优解相同。派问题的最优解相同。 OR:SM62 六、匈牙利法六、匈牙利法 2、求解步骤、求解步骤 (1)让效率矩阵中的每行每列都出现零元素。让效率矩阵中的每行每列都出现零元素。 (2)寻找独立零元素寻找独立零元素(分别位于不同的行和列中分别位于不同的行和列中)。 若独立零元素个数等于若独立零元素个数等于n，计算

49、停止；若小，计算停止；若小 于于n，则继续寻找独立零元素，至其数量为，则继续寻找独立零元素，至其数量为n。 (3)变换矩阵元素，将独立零元素改写为变换矩阵元素，将独立零元素改写为1，其，其 它元素改写为它元素改写为0，即得到最优解。，即得到最优解。 OR:SM63 匈牙利法举例：匈牙利法举例： 48715 12 79 17 14 10 69 1287 67 14610 69 12 106 C 4 7 6 6 6 OR:SM64 每行减去该行最小元素后：每行减去该行最小元素后： 04311 8 02 1073 03621 01804 03640 C 13 OR:SM65 第第2 2、3 3列分别

50、减去其最小元素后：列分别减去其最小元素后： 030 11 8 01773 02321 00504 02340 C OR:SM66 寻找独立零元素：寻找独立零元素： 030 11 8 01773 02321 00504 02340 C OR:SM67 第第2 2、3 3行分别减去最小元素行分别减去最小元素( (除除0 0外外) )： 030 11 8 1 0662 1 1210 00504 02340 C OR:SM68 第第1 1列元素加上列元素加上“1” 1” ： 130 11 8 00662 01210 10504 12340 C OR:SM69 继续寻找独立零元素：继续寻找独立零元素：

51、130 11 8 00662 01210 10504 12340 C OR:SM70 求出最优解：求出最优解： * 00100 01000 10000 00010 00001 X * 6976634Z * 7966634Z OR:SM71 匈牙利法练习匈牙利法练习1 1： 215 134 10414 15 914 16 13 78119 C OR:SM72 匈牙利法练习匈牙利法练习1 1： 215 1340 13 112 10414 156010 11 914 16 130574 781190142 C OR:SM73 匈牙利法练习匈牙利法练习1 1： 0 13 1120 1370 6010 116069 05740532 01420100 C OR:SM74 匈牙利法练习匈牙利法练