第2部分线性规划.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,第,2,部分 整数规划,1,整数规划的图解法,2,整数规划的计算机求解,3,整数规划的应用,4,整数规划的分枝定界法,1,规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。,整数规划,2,整数规划特点,（,i,）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：,原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。,整数规划无可行解。,例,1,（,1,）原线性规划为,s.t,.,其最优实数解为：,3,有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。,例,1,（,2,）原线性规划为,s.t,.,其最优实数解为：,若限制整数得：,（,ii,）整数规划最优解不能按照实数最优解简单取整而获得。,4,整数规划的图解法,例,1.,某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。,甲种货物至多托运,4,件，问两种货物各托运多少件，可使获得利润最大。,解：,设,x,1,、,x,2,分别为,甲、乙两种货物托运的件数，建立模型,目标函数：,Max z=2x,1,+3 x,2,约束条件：,s.t.,195,x,1,+273 x,2,1365,4,x,1,+40 x,2,140,x,1,4,x,1,，,x,2,0,为整数。,如果去掉最后一个约束，就是一个线性规划问题。利用图解法，,货物,每件体积,（立方英尺）,每件重量,（百千克）,每件利润,（百元）,甲,乙,195,273,4,40,2,3,托运限制,1365,140,5,得到线性规划的最优解为,x,1,=2.44,x,2,=3.26,目标函数值为,14.66,。,由图表可看出，整数规划的最优解为,x,1,=4,x,2,=2,目标函数值为,14,。,性质,1,：,任何求最大目标函数值的纯整数规划或混合整数规划的最大目,标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目,标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相,应的线性规划的最小目标函数值。,1,整数规划的图解法,整数规划的图解法,1,2,3,4,1,2,3,2x,1,+3x,2,=14.66,x,1,x,2,2x,1,+3x,2,=14,2x,1,+3x,2,=6,*,*,*,*,*,*,*,*,*,*,*,*,6,另外，我们可以用,LINDO,解整数规划,(IP),问题,此时只要在,END,后加上标识,gin n,即可,其中解,0/1,规划的用命令,INT name,或,INT n(n,指前,n,个变量标识为,0/1,型,),解混合型整数规划则用,GIN,来标识。,LINDO,解整数规划对变量的限制为,50,个（指,LINDO 6.1,学生版）。所以，尽管,LINDO,对整数规划问题很有威力,但要有效地使用还是需要一定技术的。,7,用,Lindo,软件求解整数规划：,Linear Interactive and Discrete optimizer,max 3x1+2x2,st,2x1+3x2=14,2x1+x2=NEED(J);,!,切割出的每种部件总数满足需求量,;,FOR(cutfa(I):SUM(buj(J):N(I,J,)*L(J)=16);,!,每种切割方法切割出的部件长度之后大于,15(,即预料小于,4);,FOR(SHUL:GIN(N);FOR(cutfa:GIN(X);!N,和,X,都是整数,;,END,25,如果要求决策变量只取,0,或,1,的线性规划问题,称为,0-1,整数规划,.,0-1,约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进的问题,.,0-1,规划,26,0-1,规划,一、投资场所的选择,例,3,、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有,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,万元，问应选择哪几个销售点，可使年利润为最大,?,27,0-1,规划,解：,设：,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,j,0,且,x,j,为,0-1,变量,，,i,=1,2,3,10,28,相互排斥的约束条件,有两个相互排斥的约束条件,或,为了统一在一个问题中，引入,0-1,变量,y,，则上述,约束条件可改写为：,其中,M,是充分大的数。,29,相互排斥的约束条件,约束条件,或,可改写为：,30,相互排斥的约束条件,如果有,m,个互相排斥的约束条件,为了保证这个约束条件只有一个起作用，我们引入,m,个,0-1,变量 和一个充分大的常数,M,，而下面这一组,m+1,个约束条件,就合于上述的要求，这是因为,m,个,y,i,中只有一个能取,0,值，设,y,i,*,=0,，代入（,1,），就只有的约束条件,i,=,i,*,起作用，而别的式子都是多余的。,31,关于固定费用的问题,在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。,32,固定成本问题,例,4,高压容器公司制造小、中、大三种尺寸的金属容器，,所用资源为金属板、劳动力和机器设备，制造一个容器所需,的各种资源的数量如表所示。不考虑固定费用，每种容器,售出一只所得的利润分别为,4,万元、,5,万元、,6,万元，可使用的,金属板有,500,吨，劳动力有,300,人,/,月，机器有,100,台,/,月，此外,不管每种容器制造的数量是多少，都要支付一笔固定的费用：,小号是,l00,万元，中号为,150,万元，大号为,200,万元。现在要制,定一个生产计划，使获得的利润为最大。,33,固定成本问题,解：这是一个整数规划的问题。,设,x,1,，,x,2,，,x,3,分别为小号容器、中号容器和大号容器的生产数量。各,种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这,种性质，设,y,i,=1(,当生产第,i,种容器,即,x,i,0,时,),或,0（,当不生产第,i,种容,器即,x,i,=0,时）。,引入约束,x,i,M,y,i,，,i=1,，,2,，,3,，,M,充分大，以保证当,y,i,=0,时，,x,i,=0,。,这样我们可建立如下的数学模型：,Max z=4,x,1,+5,x,2,+6,x,3,-100y,1,-150y,2,-200y,3,s.t.2,x,1,+4,x,2,+8,x,3,500,2,x,1,+3,x,2,+4,x,3,300,x,1,+2,x,2,+3,x,3,100,x,i,M,y,i,，,i=1,，,2,，,3,，,M,充分大,x,j,0,y,j,为,0-1,变量,，,i,=1,2,3,34,0-1,型整数规划解法之一（过滤隐枚举法）,解,0-1,型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为,0,或,1,的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的,2,n,个组合。对于变量个数,n,较大（例如,n10,），这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（,Implicit Enumeration,），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。,35,过滤隐枚举法,例,5,s.t,.,求解思路及改进措施：,36,先试探性求一个可行解，易看出,满足约束条件，故为一个可行解，且相应的目标函数值为,z=3,。,因为是求极大值问题，故求最优解时，凡是目标值,z3,的解不必检验是否满足约束条件即可删除，因它肯定不是最优解，于是应增加一个约束条件（目标值下界）：,称该条件为过滤条件,(Filtering,Contraint,),。从而原问题等价于：,过滤隐枚举法,37,过滤隐枚举法,s.t,.,若用全部枚举法，,3,个变量共有,8,种可能的组合，我们将这,8,种,组合依次检验它是否满足条件,(a)(e),，对某个组合，若它不,满足,(a),，即不满足过滤条件，则,(b)(e),即可行性条件不必再,检验；若它满足,(a)(e),且相应的目标值严格大于,3,，则进行,（,iii,）。,38,改进过滤条件。,由于对每个组合首先计算目标值以验证过滤条件，故应优先计算目标值,z,大的组合，这样可提前抬高过滤门槛，以减少计算量。,按上述思路与方法，例,6,的求解过程可由下表来表示：,过滤隐枚举法,39,过滤隐枚举法,目标值,约束条件,过滤条件,a b c d e,(0,0,0),0,(1,0,0),3,(0,1,0),-2,(0,0,1),5,(1,1,0),1,(1,0,1),8,(1,1,1),6,(0,1,1),3,40,前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线性整数规划目前尚未有一种成熟而有效的求解方法，因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。,然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解,。,蒙特卡洛法（随机取样法）,41,整数规划问题的求解可以使用,Lingo,等专用软件。对于一般的整数规划规划问题，无法直接利用,Matlab,的函数，必须利用,Matlab,编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用,Matlab,的函数,linprog,。,数学上，幺模矩阵是所有项都是整数而且行列式为,1,或,-1,的方阵。而幺模矩阵的逆还是幺模矩阵，所以所有的幺模矩阵构成一个乘法群。,整数规划的计算机解法,42,指派问题,有,n,项不同的任务，恰好,n,个人可分别承担这些任务，但由,于每人特长不同，完成各项任务的效率等情况也不同。现假设必须,指派每个人去完成一项任务，怎样把,n,项任务指派给,n,个人，使,得完成,n,项任务的总的效率最高，这就是,指派问题。,例,6,有四个工人，要分别指派他们完成四项不同的工作，每,人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能,使总的消耗时间为最少。,43,指派问题,解,：,引入,01,变量,x,ij,，,并令,x,ij,=1(,当指派第,i,人去完成第,j,项工作时,),或,0,（当不指派第,i,人去完成第,j,项工作时,),这可以表示为一个,0-1,整数规划问题：,Min z=15,x,11,+18,x,12,+21,x,13,+24,x,14,+19,x,21,+23,x,22,+22,x,23,+18,x,24,+26,x,31,+17,x,32,+16,x,33,+19,x,34,+19,x,41,+21,x,42,+23,x,43,+17,x,44,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,11,+,x,21,+,x,31,+,x,41,=1 (A,工作只能一人干,),x,12,+,x,22,+,x,32,+,x,42,=1 (B,工作只能一人干,),x,13,+,x,23,+,x,33,+,x,43,=1 (C,工作只能一人干,),x,14,+,x,24,+,x,34,+,x,44,=1 (D,工作只能一人干,),x,ij,为,0-1,变量,，,i,j,=1,2,3,4,*,求解可用,管理运筹学,软件中整数规划方法。,44,指派问题,拟分配,n,个人去干,n,项工作，每人干且仅干一项工作，若,分配第,i,个人去干第,j,项工作，需花费,c,ij,单位时间，问应如何分,配工作才能使工人花费总时间最少？,容易看出，要给出一个指派问题的实例，只需给出矩阵,C=(,c,ij,),C,被称为指派问题的系数矩阵。,引入变量,x,ij,，若分配,i,干,j,工作，则取,x,ij,=1,，否则取,x,ij,=0,。,上述指派问题的数学模型为,45,指派问题,46,指派问题,47,指派问题,48,指派问题,49,指派问题,容易看出，从变换后的矩阵中只能选出四个位于不同行,不同列的元素，但,n=5,最优指派还无法看出。此时等价变换还,可以进行下去，步骤如下：,1.,对未选出,0,元素的行打；,2.,对行中,0,元素所在列打；,3.,对列中选出的,0,元素所在行打；,重复,2,、,3,，直到无法再打为止。,可以证明，若用直线划没有打的行与打的列，就得到,了能够覆盖住矩阵所以,0,元素的最少条数的直线集合，找出未,覆盖的元素中的最小者，令行元素减去此数，列元素加,上此数，则原先选中的,0,元素不变，而未覆盖元素中至少有一,个已转变为,0,，且新矩阵的指派问题与原问题也等价。上述过,程可反复采用，直到能选取出足够的,0,元素为止。,50,例,9,有四个工人，要分别指派他们完成四项不同的工作，每个人做各项工作所消耗的时间如表。问应该如何指派，才能使总的消耗时间为最小？,这是一道典型的整数规划问题。我们记派,i,去做工作,j,记为,X,ij,注意到每人只能做一项工作，每项工作一人做。我们得到目标函数为约束条件：,工作,所耗,时间,工人,A,B,C,D,甲,15,18,21,24,乙,19,23,22,18,丙,26,17,16,19,丁,19,21,23,17,指派问题,51,min 15x11+19x21+26x31+19x41+18x12+23x22+17x32+21x42+24x13+22x23+16x33+23x43+24x14+18x24+19x34+17x44,ST,x11+x12+x13+x14=1,x21+x22+x23+x24=1,x31+x32+x33+x34=1,x41+x42+x43+x44=1,x11+x21+x31+x41=1,x12+x22+x32+x42=1,x13+x23+x33+x43=1,x14+x24+x34+x44=1,end,int,16,52,运行后我们可得到最优目标值为,70,，取最值时：,x11=x42=1,X33=x24=1,，其余为,0.,（具体的,Reports,略去）,在用,LINDO,解整数规划（,IP,）问题时,只要在,END,后加上标 识,gin n,即可,其中解,0/1,规划的用命令,INT name,或,INT n(n,指前,n,个变量标 识为,0/1,型,),解混合型整数规划则用,GIN,来标识。,LINDO,解整数规划对变量的限制为,50,个（指,LINDO 6.1,学生版）。所以，尽管,LINDO,对整数规划问题很有威力,但要有效地使用还是需要一定技术的。这是因为，人们很容易将一个本质上很简单的问题列成一个输入模型。从而有可能会导致一个冗长的分支定界计算。,53,例,10,一个旅行者的背包最多只能装,6 kg,物品,.,现有,4,件物品,重量为,2 kg,3 kg,3 kg,4 kg,价值为,1,元,1.2,元,0.9,元,1.1,元,.,应携带那些物品使得携带物品的价值最大,?,建模,:,记,x,j,：旅行者是否携带第,j,件物品,x,j,=0,1.,约束条件,2,x,1,+3,x,2,+3,x,3,+4,x,4,6,求,x,j,使目标函数,f,=,x,1,+1.2,x,2,+0.9,x,3,+1.1,x,4,最大,.,54,用,Lingo,软件求解,0-1,规划,Linear Interactive and General Optimizer,Model:,Max=x1+1.2*x2+0.9*x3+1.1*x4;,2*x1+3*x2+3*x3+4*x4=6;,bin(x1);,bin(x2);,bin(x3);,bin(x4);,end,55,练习,1,：混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据,4,位运动员的,4,种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。,蛙泳 蝶泳 自由泳 仰泳,甲,99 60 59 73,乙,79 65 93 87,丙,67 93 63 81,丁,56 79 86 76,56,分布系统设计,例,11,某企业在,A,1,地已有一个工厂，其产品的生产能力为,30,千箱，为了扩大生产，打算在,A,2,，,A,3,，,A,4,，,A,5,地中再选择几个地方建厂。已知在,A,2,，,A,3,，,A,4,，,A,5,地建厂的固定成本分别为,175,千元、,300,千元、,375,千元、,500,千元，另外，,A,1,产量及,A,2,，,A,3,，,A,4,，,A,5,建成厂的产量，那时销地的销量以及产地到销地的单位运价,(,每千箱运费,),如下表所示。,a),问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小,?,b),如果由于政策要求必须在,A,2,，,A,3,地建一个厂，应在哪几个地方建厂,?,57,解：,a),设,x,ij,为从,A,i,运往,B,j,的运输量,(,单位千箱,),，,y,k,=1(,当,A,k,被选中时,),或,0,（当,A,k,没被选中时,),k,=2,3,4,5,这可以表示为一个整数规划问题：,Min z=175,y,2,+300,y,3,+375,y,4,+500,y,5,+8,x,11,+4,x,12,+3,x,13,+5,x,21,+2,x,22,+3,x,23,+4,x,31,+3,x,32,+4,x,33,+9,x,41,+7,x,42,+5,x,43,+10,x,51,+4,x,52,+2,x,53,58,分布系统设计,解：,其中前,4,项为固定投资额，后面的项为运输费用。,s.t.,x,11,+,x,12,+,x,13,30 (A,1,厂的产量限制,),x,21,+,x,22,+,x,23,10,y,2,(A,2,厂的产量限制,),x,31,+,x,32,+,x,33,20,y,3,(A,3,厂的产量限制,),x,41,+,x,42,+,x,43,30,y,4,(A,4,厂的产量限制,),x,51,+,x,52,+,x,53,40,y,5,(A,5,厂的产量限制,),x,11,+,x,21,+,x,31,+,x,41,+,x,51,=30 (B,1,销地的限制,),x,12,+,x,22,+,x,32,+,x,42,+,x,52,=20 (B,2,销地的限制,),x,13,+,x,23,+,x,33,+,x,43,+,x,53,=20 (B,3,销地的限制,),x,ij,0,，,i,=1,2,3,4,5,；,j,=1,2,3,，,y,k,为,0-1,变量，,k,=2,3,4,5,。*,求解可用,管理运筹学,软件中整数规划方法。,59,配料问题,例,12,某工厂要用三种原料,1,、,2,、,3,混合调配出三种不同规格的,产品甲、乙、丙，数据如右表。,问：该厂应如何安排生产，使利,润收入为最大？,解：设,x,ij,表示第,i,种（甲、乙、丙）产品中原料,j,的含量。这样我们建立数学模型时，要考虑：,对于甲：,x,11,，,x,12,，,x,13,；,对于乙：,x,21,，,x,22,，,x,23,；,对于丙：,x,31,，,x,32,，,x,33,；,对于原料,1,：,x,11,，,x,21,，,x,31,；,对于原料,2,：,x,12,，,x,22,，,x,32,；,对于原料,3,：,x,13,，,x,23,，,x,33,；,目标函数：利润最大，利润,=,收入,-,原料支出,约束条件：规格要求,4,个；,供应量限制,3,个。,60,配料问题,利润,=,总收入,-,总成本,=,甲乙丙三种产品的销售单价*产品数量,-,甲乙丙使用的原料单价*原料数量，故有,目标函数,Max 50,（,x,11,+,x,12,+,x,13,）,+35,（,x,21,+,x,22,+,x,23,）,+25,（,x,31,+,x,32,+,x,33,）,-65,（,x,11,+,x,21,+,x,31,）,-25,（,x,12,+,x,22,+,x,32,）,-35,（,x,13,+,x,23,+,x,33,）,=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,从第,1,个表中有：,x,11,0.5(,x,11,+,x,12,+,x,13,),x,12,0.25(,x,11,+,x,12,+,x,13,),x,21,0.25(,x,21,+,x,22,+,x,23,),x,22,0.5(,x,21,+,x,22,+,x,23,),61,配料问题,从第,2,个表中，生产甲乙丙的原材料不能超过原,材料的供应限额，故有,(,x,11,+,x,21,+,x,31,)100,(,x,12,+,x,22,+,x,32,)100,(,x,13,+,x,23,+,x,33,)60,通过整理，得到以下模型：,62,配料问题,例,12,（续）,目标函数：,Max z=-15,x,11,+25,x,12,+15,x,13,-30,x,21,+10,x,22,-40,x,31,-10,x,33,约束条件：,s.t.0.5,x,11,-0.5,x,12,-0.5,x,13,0,（,原材料,1,不少于,50%,）,-0.25,x,11,+0.75,x,12,-0.25,x,13,0,（,原材料,2,不超过,25%,）,0.75,x,21,-0.25,x,22,-0.25,x,23,0,（,原材料,1,不少于,25%,）,-0.5,x,21,+0.5,x,22,-0.5,x,23,0,（,原材料,2,不超过,50%,）,x,11,+,x,21,+,x,31,100 (,供应量限制）,x,12,+,x,22,+,x,32,100 (,供应量限制）,x,13,+,x,23,+,x,33,60 (,供应量限制）,x,ij,0 ,i=1,2,3;j=1,2,3,63,练习,2,：某钻井队要从以下,10,个可供选择的井位中确定,5,个钻井探油，使总的钻探费用为最小。若,10,个井位的代,号为,s,1,，,s,2,，,，,s,10,，相应的钻探费用为,c,1,c,2,c,10,，并,且井位选择上要满足下列限制条件：,(1),或选择,s,1,和,s,2,，或选择钻探,s,9,；,(2),选择了,s,3,或,s,4,就不能选,s,5,，或反过来也一样；,(3),在,s,5,，,s,6,，,s,7,，,s,8,中最多只能选两个；试建立这个问题的整数规划模型,64,