运筹学-第5章整数规划

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

1、第5章 整数规划,2,第5章 整数规划,Sub title,内容提要,第一节 整数规划问题及数学模型 纯整数规划 0-1规划 混合整数规划 第二节 整数规划求解 分枝定界法 割平面法 隐枚举法 匈牙利法,3,第一节 整数规划问题及数学模型,一、整数规划问题简述 线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数规划(Integer Programming)。 全部决策变量的取值都为整数，全整数规划(A

2、ll IP) 仅要求部分决策变量的取值为整数，混合整数规划(Mixed IP) 要求决策变量只取0或1值，则称0-1规划(0-1 Programming),4,一、全(纯)整数规划,例：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示，问如何安排利润最大(变量取整)？,解：设x1为甲产品的台数，x2为乙产品的台数，则模型为： maxZ = 6x1 +5x2 2x1 + x2 9 5x1 +7x2 35 x1, x2 0,且为整数,5,二、0-1规划,登山队员可携带最大重量为25公斤，问应带哪些物品，重要性最大？,解：对于每一种物品无非有两种状态，带或者不带，不妨设

3、,0-1规划的模型：,6,三、混合整数规划,例：某产品有 n 个区域市场，各区域市场的需求量为 bj 吨/月；现拟在 m 个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i 地建厂，生产能力为 ai 吨/月，其运营固定费用为Fi 元/月；已知址 i 至 j 区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？,解： 假设 yi =1，选择第 i 址建厂， yi =0，不选择第 i 址建厂； 计划从厂址i 至市场 j 的运输 量为xij (连续型决策变量)。,7,第一节 整数规划问题及数学模型,二、整数规划问题建模举例 参见教材： P110: 5.1 P115: 5.1-5

4、.6 P122: 5.9,8,整数规划建模举例,一、生产基地规划,例：某公司拟建A、B两种类型的生产基地若干个，每个基地占地面积，所需经费，建成后生产能力及现有资源情况如下表所示，问A、B类型基地各建设多少个，可使总生产能力最大？,解：设A、B两类基地各建设 x1,x2 个，则其模型为：,9,二、人员安排规划,某服务部门各时段(每2小时为一时段)需要的服务人数如表：,解：设第j 时段开始时上班的服务员人数为xj 第 j 时段来上班的服务员将在第j +3 时段结束时下班，故决策变量有x1, x2, x3, x4, x5 。,按规定，服务员连续工作8小时(4个时段)为一班。如何安排服务员的工作时间

5、，使服务员总数最少？,10,三、项目投资选择,有600万元投资5个项目，收益如表，求利润最大的方案？,11,四、互斥约束问题,例如关于煤资源的限制，其约束条件为： 企业也可以考虑采用天然气进行加热处理： 这两个条件是互相排斥。 引入0-1变量 y ，令 互斥问题可由下述的条件来代替，其中M是任意大的正数。,12,五、租赁生产问题,某服装公司租用生产线拟生产T恤、衬衫和裤子，每年可使用劳动力 8200 h，布料 8800m2，问如何安排利润最大？,假设：yj=1，要租用生产线 j yi=0，不租用生产线 j 第 j 种服装生产量 xj,x1My1 x2My2 x3My3 其中，M为任意大的正数。

6、,13,六、任务指派问题,甲乙丙丁四个人，ABCD四项任务，如何指派总时间最短？,解： 引入0-1变量xij ， xij =1：任务j指派人员i去完成 xij =0：任务j不派人员i去完成,一项任务只由一个人完成 一人只能完成一项任务,14,第二节 整数规划问题求解,一、舍入化整法,maxZ = 6x1 + 5x2 2x1 + x2 9 5x1 + 7x2 35 x1,x20且为整数,(28/9, 25/9),对于本例，松驰问题的最优解：x1*=28/9， x2* =25/9， Z * =293/9,整数规划问题取消整数限制后称为松驰问题。,x1 =3， x2 =3，Z =33，不满足约束条件

7、5 x1 + 7 x2 35，不可行；,x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解；,x1 =4， x2 =1，Z =29，满足约束条件，而且是最优解。,15,从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。,整数规划与线性规划的关系,16,二、穷举整数法,对于决策变量少，整数可行解数量较少时，这种穷举法有时是可行的，并且是有效的。 但对于大型的整数规划问题，可行的整数解数量很多，

8、用穷举法求解是不可能的。例如，指派问题。, (3,3),17,三、分枝定界法,松驰问题：某一整数规划对应的线性规划问题称为松驰问题。 即不考虑决策变量整数限制的整数规划问题。 分支定界法基本思路： 在松驰问题可行域中寻找使目标函数值达到最优的整数解。 定理5-1： 对于某一求max(min)的整数规划问题，其目标函数最优值不超过(低于)其松驰问题的目标函数最优值。,18,分枝定界法基本步骤,不考虑整数限制，先求出相应松驰问题的最优解。 若求得的最优解符合整数要求，则是原IP的最优解。 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。 依次在缩小的可

9、行域中求解新构造的线性规划的最优解，直到获得原整数规划的最优解。 定界的含义： IP是在相应的LP基础上增加整数约束 IP的最优解不会优于相应LP的最优解 对MaxZ的IP，LP的Z*是IP的上界,19,x2,x1,5,3,0,6,3,2,1,(1),(2),分枝定界法举例：,2,4,20,x2,x1,5,3,0,6,3,2,1,(1),(2),第一步：图解法求松驰问题最优解 (定界),2,4,A (3/2 , 10/3),LP0,21,x2,x1,5,3,0,6,3,2,1,(1),(2),第二步：分枝,2,4,A,LP2,选择其中一个取值非整数变量进行分支，如x1。当1x12时，该问题无整

10、数解，因此在可行域中删除此区域，此时原问题模型有何变化？,LP1,B,C,(1 , 7/3),(2 , 23/9),22,x2,x1,5,3,0,6,3,2,1,(1),(2),第三步：比较分枝结果，选择下一步分支区域，定界,2,4,A,LP3,LP1,B,C,因Z(2)Z(1)，故选择LP2进行分支，x2=23/9，分支结果：x22，x23,LP4,D,(33/14 , 2),23,x2,x1,5,3,0,6,3,2,1,(1),(2),第四步：比较分枝结果，选择下一步分支区域，定界,2,4,A,LP3,LP1,B,C,因Z(3)Z(1)，故选择LP3进行分支，x1=33/14，分支结果：x

11、12，x13,LP4,D,E,LP5,LP6,(2, 2),F,(3, 1),24,x11,x1 2,x22,x2 3,x12,x1 3,25,x2,x1,5,7,0,9,4,5,3,(1),(2),分支定界法举例：,26,x2,x1,5,7,0,9,4,5,3,(1),(2),A,( 28/9, 25/9 ),LP0,27,x2,x1,5,7,0,9,4,5,3,(1),(2),A,LP1,LP2,B,B( 3, 20/7 ),C,C( 4, 1 ),28,x2,x1,5,7,0,9,4,5,3,(1),(2),E,E( 14/5, 3),D,LP3,LP4,3,2,D( 3, 2),29,

12、x2,x1,5,7,0,9,4,5,3,(1),(2),F,F( 2, 25/7),D,LP4,3,2,D( 3, 2),2,LP6: 无可行解(x1=3),LP5,30,x2,x1,5,7,0,9,4,5,3,(1),(2),H,G( 2, 3),G,LP8,LP4,3,2,H( 7/5, 4),2,4,LP7,31,x13,x1 4,x22,x2 3,x12,x1 3,x23,x2 4,32,步骤：,步骤1、整数规划问题为A，其松弛问题为B，设为问题A（max）的初始下界（min问题为上界） 步骤2、求解问题B，有三种情况： （a）B 无可行解，此时问题A也无可行解，停止。 （b）B 有最

13、优解且为整数，则问题B的最优解即是问题A的最优解，停止。 （c）B 有最优解但不是整数，设目标函数值为问题A的上（下）界，转入步骤3。,步骤3、分支、定界。 步骤4、比较、剪枝。 步骤5、重复步骤 3 和 4 ，直至求出最优整数解。,33,【练习】用分枝定界法求解整数规划问题,【解】先求对应的松弛问题（记为LP0）：,用图解法得到最优解X(0)(3.57, 7.14)T, Z(0)=35.7, 如下图所示。,34,8.33,10,松弛问题LP0的最优解：X(0)=(3.57,7.14)T, Z(0)=35.7,x1,x2,o,A,B,C,10,35,10,10,x1,x2,o,A,B,C,LP

14、1,LP2,3,4,LP1: X(1)=(3, 7.6)T, Z(1)=34.8,LP2: X(2)=(4, 6.5)T, Z(2)=35.5,36,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3: X(3)=(4.33, 6)T, Z(3)=35.33,6,LP1: X(1)=(3, 7.6)T, Z(1)=34.8,D,37,10,10,x1,x2,o,A,C,LP1,3,4,6,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,

15、E,F,38,尽管还可以对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.8,LP2:X(2)=(4, 6.5)T Z(2) =35.5,x13,x14,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,x14,x15,无可行解,x27,39,四、割平面法,步骤： 1、用单纯形法求解松驰问题； 2、在松驰问题最终单纯形表中任选一约束条 件，构造新的约束条件(割平面约束)； 3、将新的约束条件加入最终单纯形表中，求 解最优整数解。 注意： 割平面约束往往不是一次就可以找到。,40,例：用割平面法求解整数规划问题,解：1、标准化,41,2、单纯形法求解松驰问题,42,3、寻