运筹学课件整形规划问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 整数规划（,IP,）,(Integer Programming),整数规划的模型,整数规划的应用（指派问题）,整数规划的计算机求解,（一）、整数规划问题实例,一、整数规划的模型,1.1,问题的提出,例,1,：某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表,1,所示：,甲种货物至多托运,4,件。,问：两种货物各托运多少件，可使获得利润最大？,货物,每件体积,（立方英尺）,每件重量,（百千克）,每件利润,（百元）,甲,乙,195,273,4,40,2,3,托运限制,1365,140,规划模型：,纯整数规划：,所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。,全整数规划：,除了所有决策变量要求取非负整数外，系数,a,ij,和常数,b,i,也要求取整数（这时引进的松弛变量和剩余变量也必须是 整数）。,混合整数规划：,只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。,0,1,整数规划：,所有决策变量只能取,0,或,1,两个整数,。,（三）、整数规划与线性规划的关系,从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得的解是整数可行解。,举例说明。,例：设整数规划问题如下,首先不考虑整数约束，得到线性规划问题。,用 解法求出最优解,x,1,3/2,x,2,=10/3,且有,Z=29/6,x,1,x,2,3,3,(3/2,10/3),现求整数解（最优解）：如用“舍入取整法”可得到,4,个点即,(1,，,3)(2,，,3)(1,，,4)(2,，,4),。显然，它们都不可能是整数规划的最优解。,按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。,图,因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。,如上例：其中,（,2,，,2,）（,3,，,1,）,点为最大值，,Z=4,。,目前，常用的求解整数规划的方法有：,分支定界法和割平面法（不作为课堂授课内容）；,对于特别的,0,1,规划问题采用隐枚举法和匈牙利法。,四、整数规划问题计算机求解,(P165),例,3,：,Max z=3x,1,+x,2,+3x,3,s.t.,-x,1,+2x,2,+x,3,4,4x,2,-3x,3,2,x,1,-3x,2,+2x,3,3,x,3,1,x,1,x,2,x,3,0,x,1,，,x,3,为整数,x,3,为,0-1,变量,用,管理运筹学,软件求解得：,x,1,=4,x,2,=1.25,x,3,=1 z=16.25,例,4,、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有,10,个位置,A,j,(j,1,，,2,，,3,，,，,10),可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：,在东区由,A,1,，,A,2,，,A,3,三个点至多选择两个；,在西区由,A,4,，,A,5,两个点中至少选一个；,在南区由,A,6,，,A,7,两个点中至少选一个；,在北区由,A,8,，,A,9,，,A,10,三个点中至少选两个。,A,j,各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示,(,单位：万元,),。但投资总额不能超过,720,万元，问应选择哪几个销售点，可使年利润为最大,?,五、投资场所的选择。例,4(P166),解：设：,0-1,变量,x,i,=1(A,i,点被选用）,或,0,(,A,i,点没被选用）。,这样我们可建立如下的数学模型：,Max z=36,x,1,+40,x,2,+50,x,3,+22,x,4,+20,x,5,+30,x,6,+25,x,7,+48,x,8,+58,x,9,+61,x,10,s.t.,100,x,1,+120,x,2,+150,x,3,+80,x,4,+70,x,5,+90,x,6,+80,x,7,+140,x,8,+160,x,9,+180,x,10,720,x,1,+,x,2,+,x,3,2,x,4,+,x,5,1,x,6,+,x,7,1,x,8,+,x,9,+,x,10,2,x,i,0,且,x,i,为,0-1,变量,，,i,=1,2,3,10,在实际中经常会遇到这样的问题，有,n,项不同的任务，需要,n,个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成,n,项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。,（一）、指派问题的数学模型,设,n,个人被分配去做,n,件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第,i,个人去做第,j,件工作的的效率（时间或费用）为,C,ij,(,i,=1.2,n,;,j,=1.2,n,),并假设,C,ij,0,。问应如何分配才能使总效率（时间或费用）最高？,六、,指派问题,指派问题是,01,规划的特例。,库恩（,ww.kuhn,）于,1955,年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于矩阵中,0,元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用这名称。,例,6,有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,设决策变量,1,分配第,i,个人去做第,j,件工作,x,ij,=,0,相反,(,I,j,=1.2.,n,),其数学模型为：,（二）匈牙利法解题步骤,（补充，重点）,指派问题是,0-1,规划的特例，也是运输问题的特例，当然可用整数规划，,0-1,规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即,系数矩阵中独立,0,元素的最多个数等于能覆盖所有,0,元素的最少直线数。,第一步：变换指派问题的系数矩阵（,c,ij,）为,(,b,ij,),，使在,(,b,ij,),的各行各列中都出现,0,元素，即,(1),从（,c,ij,）的每行元素都减去该行的最小元素；,(2),再从所得新系数矩阵的每列元素中减去该列的最小元素。,(4),若仍有没有划圈的,0,元素，且同行,(,列,),的,0,元素至少有两个，则从剩有,0,元素最少的行,(,列,),开始，比较这行各,0,元素所在列中,0,元素的数目，选择,0,元素少的那列的这个,0,元素加圈,(,表示选择性多的要“礼让”选择性少的,),。然后划掉同行同列的其它,0,元素。可反复进行，直到所有,0,元素都已圈出和划掉为止。,（,5,）若,元素的数目,m,等于矩阵的阶数,n,，那么这指派问题的最优解已得到。若,m,n,则转入下一步。,第三步：作最少的直线覆盖所有,0,元素。,(1),对没有,的行打号；,(2),对已打号的行中所有含,元素的列打号；,(3),再对打有号的列中含,元素的行打号；,(4),重复,(2),，,(3),直到得不出新的打号的行、列为止；,(5),对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有,0,元素的最少直线数,l,。,l,应等于,m,，若不相等，说明试指派过程有误，回到第二步,(4),，另行试指派；若,l,m,n,，须再变换当前的系数矩阵，以找到,n,个独立的,0,元素，为此转第四步。,第四步：变换矩阵,(,b,ij,),以增加,0,元素。,在没有被直线覆盖的所有元素中找出最小元素，然后打各行都减去这最小元素；打各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。,指派问题,例：有一份中文说明书，需译成英、日、德、俄四种文字。分别记作,E,、,J,、,G,、,R,。有甲、乙、丙、丁四人。他们将中文说明书译成不同语种的说明书所需的时间如表所示。问应指派何人去完成何工作，使所需总时间最少？,人员 任务,E,J,G,R,甲,乙,丙,丁,2,10,9,7,15,4,14,8,13,14,16,11,4,15,13,9,2,4,9,7,4,2,甲、乙、丙、丁四个人加工,A,、,B,、,C,、,D,四种工件所需时间（单位：,min,）如表所示。应指派何人加工何种工件，能使总的加工时间最少？,工件,人员,A,B,C,D,甲,14,9,4,15,乙,11,7,9,10,丙,13,2,10,5,丁,17,9,15,13,例二、,指派问题是,01,规划的特例。,库恩（,ww.kuhn,）于,1955,年提出了指派问题的解法。他引用了匈牙利数学家康尼格一个关于矩阵中,0,元素的定理，所以把这解法称为匈牙利法。以后在方法上虽有不断改进，但仍沿用这名称。,有一份中文说明书，需译成英、日、德、俄四种文字，分别记作,A,、,B,、,C,、,D,。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？,任务,人员,A,B,C,D,甲,6,7,11,2,乙,4,5,9,8,丙,3,1,10,4,丁,5,9,8,2,例二、,求解过程如下：,第一步，变换系数矩阵：,5,第二步，试指派：,找到,3,个独立零元素,但,m,=,3,n=,4,第三步，作最少的直线覆盖所有,0,元素：,独立零元素的个数,m,等于最少直线数,l,，即,l,m,=3,n,=4,；,第四步，变换矩阵,(,b,ij,),以增加,0,元素：没有被直线覆盖的所有元素中的最小元素为,1,，然后打各行都减去,1,；打各列都加上,1,，得如下矩阵，并转第二步进行试指派：,第三步：作最少的直线覆盖所有,0,元素。,(1),对没有的行打号；,(2),对已打号的行中所有含,元素的列打号；,(3),再对打有号的列中含 元素的行打号；,(4),重复,(2),，,(3),直到得不出新的打号的行、列为止；,(5),对没有打号的行画横线，有打号的列画纵线，这就得到覆盖所有,0,元素的最少直线数,l,。,0,0,0,0,0,0,得到,4,个独立零元素，所以最优解矩阵为：,15,第四步，变换矩阵,(bij),以增加,0,元素：,没有被直线覆盖的所有元素中的最小元素为,1,，,然后打各行都减去,1,；打各列都加上,1,，得如下矩阵，并转第二步进行试指派：,已知下列五名运动员各种姿势的游泳成绩（各为,50,米），如表所示，试问如何从中选拔一个参加,200,米混合泳的接力队，使预期比赛成绩为最好。单位：秒,任务,人员,A,B,C,D,甲,37.7,43.4,33.3,29.2,乙,32.9,24.7,38.9,26.4,丙,33.8,42.2,28.5,29.6,丁,37.0,33.1,30.4,28.5,例三、,戊,35.4,41.8,33.6,31.1,第一步：增加一种泳姿，各位运动员的成绩均为零，得方阵：,分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间为最少的指派方案。,任务,人员,A,B,C,D,甲,25,29,31,43,乙,38,37,25,20,丙,37,27,28,40,丁,44,41,35,23,例二、,E,37,32,32,23,任务,人员,A,B,C,D,甲,25,29,31,43,乙,38,37,25,20,丙,37,27,28,40,丁,44,41,35,23,E,37,32,32,23,从甲、乙、丙、丁、戊五人中挑选四人去完成四项任务。每人完成各项任务时间如表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第,4,项任务。在满足上述条件下，如何分配工作，使完成四项工作所花费时间为最少。,任务,人员,A,B,C,D,甲,10,5,15,20,乙,2,10,5,15,丙,2,15,14,13,丁,15,2,7,6,例三、,戊,9,4,15,8,-2,-5,先增加一种假想工作,5,，再据题中给的条件列出矩阵：,-8,任务,人员,A,B,C,D,甲,20,19,20,28,乙,18,24,27,20,丙,26,16,15,18,丁,17,20,24,19,例四、,P182,（,6,）,（,2,）如果把消耗时间数据看成创造效益的数据，那么应如何指派，可使得总的效益最大？,解决办法：,转化成最小化问题，找出最大元素，用最大元素分别减去表中各元素求解。,任务,人员,A,B,C,D,甲,20,19,20,28,乙,18,24,27,20,丙,26,16,15,18,丁,17,20,24,19,例四、,P182,（,6,）,（,4,）如果再增加一个人戊，他完成,A,，,B,，,C,，,D,的时间分别为,16,，,17,，,20,，,21,分钟，这时应指派哪四个人去干这四项工作，使得消耗时间最少？,要求建立模型：,解：引入,0,1,变量,x,ij,，,并令,x,ij,=1(,当指派第,i,人去完成第,j,项工作时,),或,0,（当不指派第,i,人去完成第,j,项工作时,),这可以表示为一个,0-1,整数规划问题：,Minz=20,x,11,+19,x,12,+20,x,13,+28,x,14,+18,x,21,+24,x,22,+27,x,23,+20,x,24,+26,x,31,+16,x,32,+15,x,33,+18,x,34,+17,x,41,+20,x,42,+24,43,+19,x,44,+16,x,51,+17,x,52,+20,53,+21,x,54,s.t.,x,11,+,x,12,+,x,13,+,x,14,1 (,甲最多只能干一项工作,),x,21,+,x,22,+,x,23,+,x,24,1 (,乙最多只能干一项工作,),x,31,+,x,32,+,x,33,+,x,34,1 (,丙最多只能干一项工作,),x,41,+,x,42,+,x,43,+,x,44,1 (,丁最多只能干一项工作,),x,51,+,x,52,+,x,53,+,x,54,1 (,戊最多只能干一项工作,),x,11,+,x,21,+,x,31,+,x,41,+,x,51,=1 (A,工作只能一人干,),x,12,+,x,22,+,x,32,+,x,42,+,x,52,=1 (B,工作只能一人干,),x,13,+,x,23,+,x,33,+,x,43,+,x,53,=1 (C,工作只能一人干,),x,14,+,x,24,+,x,34,+,x,44,+,x,54,=1 (D,工作只能一人干,),x,ij,为,0-1,变量,，,i,=1,2,3,4,5;,j=1,2,3,4,*,求解可用,管理运筹学,软件中整数规划方法。,练习：,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,费 工作,用,人员,-1,-2,l,=,m,=4,n,=5,l,=,m,=4,n,=5,此问题有多个最优解,28,用匈牙利法求解下列指派问题，已知效率矩阵分别如下：,