资源预览内容
第1页 / 共91页
第2页 / 共91页
第3页 / 共91页
第4页 / 共91页
第5页 / 共91页
第6页 / 共91页
第7页 / 共91页
第8页 / 共91页
第9页 / 共91页
第10页 / 共91页
亲,该文档总共91页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
运筹学讲授:毕德春辽东学院信息技术学院信息管理系Date1运筹学第4章 整数规划与分配问题第4章 整数规划与分配问题Date2运筹学第4章 整数规划与分配问题例4.1 某服务部门各时段(每2小时为一时段)需要的服务员人数如下表,按规定,服务员连续工作8小时(即4个时段)为一班,现要求安排服务员的工作时间,使服务部门服务员总数最小。时时段12345678服务员务员最少数目108911138534.1 整数规划问题的数学模型Date3运筹学第4章 整数规划与分配问题解:设在第j时段开始时上班的服务员人数为xj,由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班,故决策变量只需考虑x1,x2,x3,x4,x5,此问题的数学模型为:Date4运筹学第4章 整数规划与分配问题此类问题数学模型的一般形式为:求一组变量X1,X2,Xn,使 Date5运筹学第4章 整数规划与分配问题例4.2 某单位有5个拟选择的投资项目,其所需投资额与期望收益如下表。由于各项目之间有一定联系,A、C、E之间必须选择一项且仅需选择一项;B和D之间需选择也仅需选择一项;又由于C和D两项目密切相关,C的实施必须以D的实施为前提条件,该单位共筹集资金15万元,问应该选择哪些项目投资,使期望收益最大?项项目所需投资额资额(万元)期望收益(万元) A610B48C27D46E59Date6运筹学第4章 整数规划与分配问题解:决策变量:设目标函数:期望收益最大约束条件:投资额限制条件 6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项:x1+x3+x5=1项目C的实施要以项目D的实施为前提条件: x3 x4项目B、D之间必须且只需选择一项:x2+x4=1归纳起来,其数学模型为:Date7运筹学第4章 整数规划与分配问题上面此例表明,利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源对可供选择的n个项目进行投资的数学模型为:求一组决策变量X1,X2,Xn,使 Date8运筹学第4章 整数规划与分配问题根据变量取整数的情况,将整数规划分为:(1)纯整数规划,所有变量都取整数.(2)混合整数规划,一部分变量取整数,一部分变量取实数(3)0-1整数规划 ,所有变量均取0或1对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多经济管理的实际问题中,决策变量只有非负整数才有实际意义。对求整数最优解的问题,称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。Date9运筹学第4章 整数规划与分配问题考虑纯整数问题:整数问题的松弛问题:Date10运筹学第4章 整数规划与分配问题求解ILP问题方法的思考:“舍入取整”法:即先不考虑整数性约束,而去求解其相应的LP问题(称为松驰问题),然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解?但在处理个别实际问题时,如果允许目标函数值在某一误差范围内,有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。Date11运筹学第4章 整数规划与分配问题例4.3 设整数规划问题如下 首先不考虑整数约束,得到线性规划问题(松弛问题)。Date12运筹学第4章 整数规划与分配问题用图解法求出最优解x13/2, x2 = 10/3且有Z = 29/6x1x233(3/2,10/3)现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3) (2,3)(1,4)(2,4)。显然,它们都不可能是整数规划的最优解。按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集,如图所示。Date13运筹学第4章 整数规划与分配问题因此,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法。如上例:其中(2,2)(3,1)点为最大值,Z=4。目前,常用的求解整数规划的方法有: 割平面法和分支定界法,对于特别的01规划问题采用隐枚举法和匈牙利法。Date14运筹学第4章 整数规划与分配问题在实际中经常会遇到这样的问题,有n 项不同的任务,需要n 个人分别完成其中的一项,但由于任务的性质和各人的专长不同,因此各人去完成不同的任务的效率(或花费的时间或费用)也就不同。于是产生了一个问题,应指派哪个人去完成哪项任务,使完成 n 项任务的总效率最高(或所需时间最少),这类问题称为指派问题或分派问题。4.2 分配问题与匈牙利法Date15运筹学第4章 整数规划与分配问题分配第i个人去完成第j项任务不分配第i个人去完成第j项任务例4.4 有一份说明书,要分别译成英、日、德、俄四种文字,交甲、乙、丙、丁四个人去完成。因各人专长不同,他们完成翻译不同文字所需的时间(h)如下表,应如何分配,使这四个人分别完成这四项任务总的时间为最小?Date16运筹学第4章 整数规划与分配问题Date17运筹学第4章 整数规划与分配问题u分配问题的数学模型:设n 个人被分配去做n 件工作,规定每个人只做一件工作,每件工作只有一个人去做。已知第I 个人去做第j 件工作的的效率( 时间或费用)为Cij(i=1.2n;j=1.2n)并假设Cij 0。问应如何分配才能使总效率( 时间或费用)最高?设决策变量 1 分配第i 个人去做第j 件工作xij =0 相反 ( I,j=1.2. n )其数学模型为:Date18运筹学第4章 整数规划与分配问题4.2.2匈牙利法指派问题是0-1 规划的特例,也是运输问题的特例,当然可用整数规划,0-1 规划或运输问题的解法去求解,这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法,这就是匈牙利法,即系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数。 第一步:变换指派问题的系数矩阵(cij)为(bij),使在(bij)的各行各列中都出现0元素,即(1)从(cij)的每行元素都减去该行的最小元素;(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。Date19运筹学第4章 整数规划与分配问题第二步:进行试指派,以寻求最优解。在(bij)中找尽可能多的独立0元素,若能找出n个独立0元素,就以这n个独立0元素对应解矩阵(xij)中的元素为1,其余为0,这就得到最优解。找独立0元素,常用的步骤为:(1)从只有一个0元素的行(列)开始,给这个0元素加圈,记作 。然后划去 所在列(行)的其它0元素,记作 ;这表示这列所代表的任务已指派完,不必再考虑别人了。(2)给只有一个0元素的列(行)中的0元素加圈,记作;然后划去 所在行的0元素,记作 (3)反复进行(1) , (2)两步,直到尽可能多的0元素都被圈出和划掉为止。Date20运筹学第4章 整数规划与分配问题(4)若仍有没有划圈的0元素,且同行(列)的0元素至少有两个,则从剩有0元素最少的行(列)开始,比较这行各0元素所在列中0元素的数目,选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行,直到所有0元素都已圈出和划掉为止。 (5)若 元素的数目m 等于矩阵的阶数n,那么这指派问题的最优解已得到。若m Z(5) F如对 Z(6) 继续分解,其最小值也不会低于15.5 ,问题探明,剪枝。Date62运筹学第4章 整数规划与分配问题至此,原问题(IP)的最优解为:x1=2, x2 =3, Z* = Z(5) 17以上的求解过程可以用一个树形图表示如右:LP1 x1=1, x2=3 Z(1) 16LP x1=18/11, x2=40/11 Z(0) 19.8LP2 x1=2, x2=10/3 Z(2) 18.5LP3 x1=12/5, x2=3 Z(3) 17.4LP4 无可 行解LP5 x1=2, x2=3 Z(5) 17LP6 x1=3, x2=5/2 Z(6) 15.5x11x12x23x24x12x13 Date63运筹学第4章 整数规划与分配问题练习:用分枝定界法求解整数规划问题(图解法)Date64运筹学第4章 整数规划与分配问题LP1 x1=1, x2=7/3 Z(1) 10/3LP x1=3/2, x2=10/3 Z(0) 29/6LP2 x1=2, x2=23/9 Z(2) 41/9x11x12LP5 x1=1, x2=2 Z(5) 3LP6 无可 行解x22x23LP3 x1=33/14, x2=2 Z(3) 61/14LP4 无可 行解x22x23LP7 x1=2, x2=2 Z(7) 4LP8 x1=3, x2=1 Z(8) 4x12x13 Date65运筹学第4章 整数规划与分配问题LP1 x1=1, x2=7/3 Z(1) 10/3LP x1=2/3, x2=10/3 Z(0) 29/6LP2 x1=2, x2=23/9 Z(2) 41/9LP3 x1=33/14, x2=2 Z(3) 61/14LP4 无可 行解LP7 x1=2, x2=2 Z(7) 4LP8 x1=3, x2=1 Z(8) 4x11x12x22x23x12x13Date66运筹学第4章 整数规划与分配问题3200CB XB b x1x2x3x40x3921109/20x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例4.10 用分枝定界法求解整数规划问题(单纯形法)Date67运筹学第4章 整数规划与分配问题x1=13/4 x2=5/2 Z(0) =59/414.75选 x2 进行分枝,即增加两个约束,2 x2 3 有下式:分别在(LP1)和(LP2)中引入松弛变量x5和x6 ,将新加约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表:Date68运筹学第4章 整数规划与分配问题32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝,加入约束3 x1 4LP1Date69运筹学第4章 整数规划与分配问题32000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝Date70运筹学第4章 整数规划与分配问题
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号