运筹学整数规划ppt课件.ppt

《运筹学整数规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学整数规划ppt课件.ppt（59页珍藏版）》请在三一办公上搜索。

1、上页,下页,返回,整数规划（integer programming),1.几个实例,2.整数规划的算法分支定界法和割平面方法,3.Lingo/Lindo求解整数规划,上页,下页,返回,例1。人员安排问题,整数规划,某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一 班。现要求安排服务员的工作时间，使所需服务员总数最少。,上页,下页,返回,某宾馆一天各时段需要的人数如下所示。按规定，服务员连续工作八小时为一 班。现要求安排服务员的工作时间，使所需服务员总数最少。,上页,下页,返回,解：设xj 表示第j时段开始上班的服务员人数。由于每两小时为一时段，所以第j时段开始上班的服务员将

2、在第j+3时段结束时下班。因此只考虑,相应的模型为：,上页,下页,返回,第4阶段,5阶段,6阶段,7阶段,7阶段,9阶段,上页,下页,返回,整数规划,上页,下页,返回,利用数学软件lingo可求得一个最优解为：,X1 = 12.000000 X2 = 0.000000 X3 = 6.000000 X4 = 2.000000 X5 = 1.000000 X6 = 5.000000,最优值为 26，具体过程如下：,上页,下页,返回,求解程序为,Liti1a,MIN =x1+x2+x3+x4+x5+x6; x16; x1+x212; x1+x2+x310; x1+x2+x3+x48; x2+x3+x

3、4+x59; x3+x4+x5+x614; x4+x5+x68; x5+x66; x64;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);end,上页,下页,返回,OBJECTIVE FUNCTION VALUE (1) 26.00000 VARIABLE VALUE X1 12.000000 X2 0.000000 X3 6.000000 X4 2.000000 X5 1.000000 X6 5.000000,另一最优解为,OBJECTIVE FUNCTION VALUE 1) 26.00000 VARIABLE VALUE X1 6.0000

4、00 X2 6.000000 X3 0.000000 X4 0.000000 X5 3.000000 X6 11.000000,最优解不唯一,liti1b,上页,下页,返回,OBJECTIVE FUNCTION VALUE 1) 26.00000 VARIABLE VALUE REDUCED COST X1 12.000000 1.000000 X2 0.000000 1.000000 X3 6.000000 1.000000 X4 2.000000 1.000000 X5 1.000000 1.000000 X6 5.000000 1.000000,上页,下页,返回,例2（布线问题）,解决某

5、市消防站的布线 问题。该城市共有6个区，每个区都可以建立消防站，市政府希望设置的消防站最少，但必须满足在城市任何地方发生火警时，消防车要在15分钟之内赶到现场，根据实地考察，各区之间消防车行驶的时间见下表,请帮助该市制定一个最节省的计划。,上页,下页,返回,各区之间消防车行驶的时间表,上页,下页,返回,解：每个地区是否设消防站可用一个0-1变量来表示。令,i=1,2,6,本题要求消防站的个数最少，故目标函数为：,约束条件为：,上页,下页,返回,各区之间消防车行驶的时间表,约束条件为：,上页,下页,返回,OBJECTIVE FUNCTION VALUE 1) 2.000000 VARIABLE

6、VALUE REDUCED COST X1 0.000000 1.000000 X2 1.000000 1.000000 X3 0.000000 1.000000 X4 1.000000 1.000000 X5 0.000000 1.000000 X6 0.000000 1.000000,min =x1+x2+x3+x4+x5+x6;x1+x21;x1+x2+x61;x3+x41;x3+x4+x51;x4+x5+x61;x2+x5+x61;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);end,计算程序为,求解报告为,最优方案为x2=x4=1,即

7、在第2区和第4区设置消防站即可。,liti3,bin(x)-表示x取值为0或1,上页,下页,返回,例3（最优装载问题）,例3（美国 1988 年大学生建摸竞赛B题),要把七种规格的包装箱装到两辆平板车上去，箱子的宽、高、相同，而厚度和重量不同。下表给出了他们的厚度和重量及数量。,上页,下页,返回,每辆平板车有10.2米的地方用于装箱，载重40吨。由于货物的限制，对于第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，试把这些包装箱装到平板车上去，使浪费的空间最小。,解：容易计算出所有的包装箱的厚度为27.495米，而两俩平板车共有20.4米长的地方，所以不可能

8、都装上。 记表中所给出的第i种箱子的厚度、重量和数量分别为ti 、 wi 和 ni （i=1,2,.,7),又记第i种箱子装到第1、2辆平板车上的数量分别为 xi1 ,xi2（i=1,2,.,7),上页,下页,返回,上页,下页,返回,问题要求浪费的空间最小，即装载所占的空间最大，故目标函数为：,约束条件为：,厚度约束：,重量约束：,每辆平板车有10.2米的地方用于装箱，载重40吨,记第i种箱子装到第1、2辆平板车上的数量分别为 （i=1,2,.,7),上页,下页,返回,数量约束：,特殊约束：,或,第5、6、7三种包装箱的装载有如下约束：它们所占的空间（厚度）不得超过302.7厘米，,(每辆平板

9、车不超过302.7cm),上页,下页,返回,故得到两个整数规划模型为：,(IP1),(IP2),上页,下页,返回,现解第一个问题：,(IP1),Liti3.ltx,Liti3.txt,上页,下页,返回,利用lindo 求解得到最优解为：,上页,下页,返回,MAX 48.7x11+48.7x12+52.0 x21+52.0 x22+61.3x31+61.3x32+72.0 x41+72.0 x42+48.7x51+48.7x52 +52.0 x61+52.0 x62+64x71+64x72st 48.7x11+52x21+61.3x31+72x41+48.7x51+52x61+64x711020

10、 48.7x12+52x22+61.3x32+72x42+48.7x52+52x62+64x721024 2x11+3x21+x31+0.5x41+4x51+2x61+x7140 2x12+3x22+x32+0.5x42+4x52+2x62+x7240 x11+x128 x21+x227 x31+x329x11+x128 x21+x227 x31+x329 x41+x426 x51+x526 x61+x624 x71+x728 48.7x51+48.7x52+52.0 x61+52.0 x62+64.0 x71+64.0 x72302.7 END GIN 14,上页,下页,返回,objecti

11、ve function value 1) 2039.400variable value reduced cost x11 5.000000 -48.700001 x12 3.000000 -48.700001 x21 1.000000 -52.000000 x22 6.000000 -52.000000 x31 9.000000 -61.299999 x32 0.000000 -61.299999,上页,下页,返回,X41 1.000000 -72.000000 X42 5.000000 -72.000000 X51 2.000000 -48.700001 X52 1.000000 -48.7

12、00001 X61 0.000000 -52.000000 X62 3.000000 -52.000000 X71 0.000000 -64.000000 X72 0.000000 -64.000000,MAX= 48.7*x11+48.7*x12+52.0*x21+52.0*x22+61.3*x31+61.3*x32+72.0*x41+72.0*x42+48.7*x51+48.7*x52+52.0*x61+52.0*x62+64*x71+64*x72;48.7*x11+52*x21+61.3*x31+72*x41+48.7*x51+52*x61+64*x711020;48.7*x12+52*

13、x22+61.3*x32+72*x42+48.7*x52+52*x62+64*x721024;2*x11+3*x21+x31+0.5*x41+4*x51+2*x61+x7140;2*x12+3*x22+x32+0.5*x42+4*x52+2*x62+x7240; x11+x128; x21+x227; x31+x329; x41+x426; x51+x526; x61+x624; x71+x728; 48.7*x51+48.7*x52+52.0*x61+52.0*x62+64.0*x71+64.0*x72302.7;gin(x11);gin(x12);gin(x21);gin(x22);gin

14、(x31);gin(x32);gin(x41);gin(x42);gin(x51);gin(x52);gin(x61);gin(x62);gin(x71);gin(x72); END,model:!平板车装载问题;sets: box/1.7/:t,w,n; car/1,2/; links(box,car):x;endsets!目标函数; max=sum(links(i,j): t(i)*x(i,j);!厚度约束; for(car(j): sum(box(i): t(i)*x(i,j)=1020;);!重量约束; for(car(j): sum(box(i): w(i)*x(i,j)=40;);

15、!数量约束; for(box(i):x(i,1)+x(i,2)=n(i););!特殊约束; sum(box(i)|i#ge# 5:t(i)*x(i,1)+t(i)*x(i,2)=302.7;for(links:gin(x);!这里是数据;data: t=48.7 52.0 61.3 72 48.7 52.0 64.0; w=2 3 1 0.5 4 2 1; n=8 7 9 6 6 4 8;enddataend,liti3a,30,0-1整数规划的实际问题,例4 某公司拟在市东、西、南三区建立门市部，拟议中有7个位置(点)Ai(i=1，2，7)可供择。规定：在东区，由A1，A2，A3三个点中至多

16、选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?,31,解：先引入0-1变量xi (i=1,2，7) 于是问题可列成：,在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5两个点中至少选一个；在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。,为了选修课程门数最少，应学习哪些课程 ？,例5 选课策略,要求至少选两门数学课、三门运筹学课和两门计算

17、机课,选修课程最少，且学分尽量多，应学习哪些课程 ？,0-1规划模型,决策变量,目标函数,xi=1 选修课号i 的课程（xi=0 不选）,选修课程总数最少,约束条件,最少2门数学课，3门运筹学课，2门计算机课。,先修课程要求,最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21,0-1规划模型,约束条件,x3=1必有x1 = x2 =1,模型求解（LINDO）,Qiu4.4-1.Ltx,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以学分最多为目标，不管课程

18、多少。,以课程最少为目标，不管学分多少。,min x1+x2+x3+x4+x5+x6+x7+x8+x9stx1+x2+x3+x4+x52x3+x5+x6+x8+x93x4+x6+x7+x922x3-x1-x20 x4-x702x5-x1-x20 x6-x70 x8-x502x9-x1-x20endint 9,上页,下页,返回,算法1（分支定界法）,分支定界法是一种灵活的枚举法或隐式枚举法。它在枚举过程中，逐步把一部分可行解排斥在考虑之内，从而大大地减少了计算量，是目前求解整数规划的 有效方法。,例4。求解下列线性规划问题,上页,下页,返回,解：利用图解法很容易求得最优解为：,A(4.8,0),

19、B,C,O,上页,下页,返回,但x1 ,x2 不是整数，故不是最优解。若将上述解化整得,它不是可行解。若将尾数去掉，变成,虽然它为可行解，但不是最优解。,显然,从上例知，求解相应的线性规划问题后，再取整并不能得到整数规划的解。,上页,下页,返回,下面我们通过实例来阐述分支定界法的思想。,例5 求解整数规划问题,解：求相应的线性规划问题,(LP),(IP),上页,下页,返回,A(11/5,6/5),由图解法知，(LP)的最优解为：,现将（LP)的可行域按x26/5,x2 6/5分支得两个线性规划：,上页,下页,返回,和,解（P1)得最优解为,再将（P1)利用 x1 9/4和x1 9/4进行分支得

20、：,上页,下页,返回,（s.t.),(P3),(S.t.),(P4),上页,下页,返回,解（P3)得最优解为,而(P4)无可行解。,再回头解一下（P2),得最优解为,比较得最优解为,割平面法的基本思想：,若整数规划IP的松弛规划P0的最优解不是整数解，对P0增加一个约束条件，得线性规划P1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在P1中，若P1的最优解为整数解，则得IP的最优解。若P1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.,割平面法,由松弛问题的

21、可行域向整数规划的可行域逼近方法利用超平面切除要求整数解保留 松弛问题最优值向最优解逼近目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解,47,15.2 割平面解法,例1 求解 目标函数 min z=-x1-x2 约束条件： -x1+x21 3x1+x24 (15-1) x1，x20 x1，x2 整数 ,48,先不考虑整数约束，求得相应的线性规划的最优解为： x1=34，x2=74，min z=-104,最优解是下图中域R的极点A，但不符合整数约束条件。,min z=-x1-x2 约束条件： -x1+x21 3x1+x24 (15-1) x1，x20 ,49,15.2节 割平面解法,

22、现设想，如能找到像CD那样的直线去切割域R(图5-6)，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域R的一个极点。,如在域R上求解，而得到的最优解又恰巧在C点就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。,图5-6,L0的最优单纯形表：,对应于生成行i的方程,(15-2.3) 将bi和yik都分解成整数部分N与非负真分数f之和，即,而a表示不超过a的最大整数。例如： 若b=2.35，则b=2，f=0.35 若b= 0.45，则b= 1,f=0.55 代入(15-2.3)式得,将上述约束加到原约束中去，得到等价的整数规划,解：考虑松弛问题，并化为标准型：,松弛问题最优解为,即：,原方程加上上约束,对应的单纯形表为,对偶单纯形法，x5进基,X1退基,得到原问题的最优解为,