运筹学-第17讲--复习&分配问题与匈牙利法1市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.ppt

第,*,页,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,第四章整数规划与分配问题,整数规划特点及作用,分枝定界法,割平面法,分配问题与匈牙利法,应用举例,Integer Programming,简称IP,1/39,有纯整数规划、混合整数规划与0-1整数规划等类型。我们只研究,线性整数规划,。,整数规划是研究,决议变量只能取正整数,一类规划问题。,整数规划特点,（1）可行解域为离散点集,（2）不能用舍入取整法,（3）目标函数值最优值,不会优于其,松弛问题,最优值,整数规划特点,2/39,整数规划求解,分枝定界法,割平面法,共同点：,经过增加,附加约束,，使整数最优解最终成为线性规划可行域一个顶点，从而使问题可利用单纯形法求出这个整数最优解；,不一样点：,附加约束条件选取标准及方法不一样。,3/39,实质：,在保留原问题全部整数可行解前提下，将原问题,分枝,为若干轻易求解子问题，并利用子问题整数解目标值来判定分枝界限。,分枝定界法,分,枝,边 界,4/39,解：设应购进甲、乙机床台数分别为,x,1,和,x,2,，数学模型为：,1、去掉变量为整数约束，可用图解法求得最优解；,x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,x,1,=3.25非整数，进行分枝,(2),4,x,1,+2,x,2,=18,(1)2,x,1,+3,x,2,=14,(3.25,2.5),T,X,(0),=(,x,1,x,2,),T,=(3.25,2.5),T,Z,(0),=14.75,【例】,某厂拟购进甲、乙两类机床生产新产品。已知两类机床进价分别为2万元和3万元，安装占地面积分别为4m,2,和2m,2,，投产后收益分别为3百元/日和2百元/日。厂方仅有资金14万元，安装面积18m,2,，为使收益最大，厂方应购进甲、乙机床各多少台？,5/39,x,1,=3.25非整数，进行分枝,2、得两个子问题数学模型:,子问题(1)子问题(2),分别用图解法求得最优解,X,(1),=(3,267),T,Z,(1),=14.33,X,(2),=(4,1),T,Z,(2),=14,子问题1,x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,(2),(1),子问题2,(4,1),Z,(1),Z,(2),=14,子问题2停顿分枝，其整数解作为,界,；,子问题1对,x,2,=2.67,进行分枝,6/39,子问题(3)子问题(4),x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,(3),(0),子问题3,子问题4,(1),(2),(4),子问题(1),Z,(1),Z,(2),=14,子问题2停顿分枝，其整数解作为,界,；,子问题1对,x,2,=2.67,进行分枝,分别用图解法求得最优解,X,(3),=(3,2),T,Z,(3),=13,X,(4),=(2.5,3),T,Z,(4),=13.5,Z,(3),Z,(2),;,Z,(4),Z,(2),7/39,子问题(3)子问题(4),子问题(1),Z,(1),Z,(2),=14,子问题2停顿分枝，其整数解作为,界,；,子问题1对,x,2,=2.67,进行分枝,分别用图解法求得最优解,X,(3),=(3,2),T,Z,(3),=13,X,(4),=(2.5,3),T,Z,(4),=13.5,Z,(3),Z,(2),;,Z,(4),Z,(2),最优解：,X,*,=,X,(2),=(4,1),T,最优值：,Z,*,=14,8/39,问题(0),x,1,=3.25,x,2,=2.5,Z,(0),=14.75,问题(4),x,1,=2.5,x,2,=3,Z,(4),=13.5,问题(3),x,1,=3,x,2,=2,Z,(3),=13,问题(1),x,1,=3,x,2,=8/3,Z,(1),=14.33,问题(2),x,1,=4,x,2,=1,Z,(2),=14,添加,x,2,3,添加,x,1,3,添加,x,2,2,添加,x,1,4,9/39,分枝问题解可能出现情况表,情况 2,4,5 找到最优解,情况 3 在缩减域上继续分枝定界法,情况 6 中问题 1 整数解作为,界,被保留，,用于以后与问题 2 后续分,枝所得到解进行比较,，结论如情况 4或5,10/39,割平面法,割平面法,基础依然是用解线性规划方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件（,Gomory,约束,，称为,割平面,），使得原可行解域中切掉一部分，这部分只包含非整数解，但,没切割掉任何整数可行解,，,切除结果使整数解可能成为顶点,。,分枝定解法,是对原问题可行解域进行了切割，切割方法是对取非整数解相邻整数作附加约束，约束方程简单，但子问题因为分枝增多而成指数增加。,11/39,割平面法,割平面法,基础依然是用解线性规划方法去解整数规划问题：首先不考虑变量为整数这一条件，但增加线性约束条件,（,Gomory约束,，,称为,割平面,），使得原可行解域中切掉一部分，这部分只包含非整数解，但,没切割掉任何整数可行解,，,切除结果使整数解可能成为顶点,。,关键：,怎样找到割平面约束方程,，使切割后最终得到这么可行域它一个整数坐标顶点恰好是问题最优解。,12/39,割平面法步骤,求,松弛问题,最优基可行解,判断是否,为整数解,否,在单纯形表中,加入,一行,利用,对偶单纯,形,算法求最优解,是停顿,得到最优解,附加约束,利用含有,最大,分数部分,非整基变量,13/39,例题：用割平面法求解以下整数规划,max,z,=3,x,1,+,2,x,2,s.t.,x,1,+0.5,x,2,4.52,x,1,+,3,x,2,14,x,1,x,2,0,且均取整数值,第1步.,去掉整数约束找出松弛问题,，若约束条件系数和右边常数不是整数，则必须化为整数,（确保所添加松弛变量均为整数）；,max,z,=3,x,1,+,2,x,2,s.t.,2,x,1,+,x,2,9,2,x,1,+3,x,2,14,x,1,x,2,0,G,0,单纯形法求解松弛问题,G,0,，,得到最终单纯形表：,因最优解不是整数解,需引入附加约束条件,14/39,找出非整数解变量中,分数部分最大,一个基变量，并写出该行在最终表中约束方程,将上式全部常数分写成,整数与正分数,之和：,分数移项到右端，整数项到左端：,依据右端为整数且变量非负要求，得到：,即：,加上松弛变量之后得到,Gomory 约束,第2步.,寻找割平面方程,；,15/39,第3步.在最优单纯形表中求解增加约束条件后LP问题最优解,；,应用,对偶单纯形法,迭代计算最优解,出基,入基,16/39,第3步.在最优单纯形表中求解增加约束条件后LP问题最优解,；,最优解仍为非整数解,继续寻找Gomory约束,17/39,写出该行在最终表中约束方程,将上式全部常数分写成,整数与正分数,之和：,分数移项到右端，整数项到左端：,依据右端为整数且变量非负要求，得到：,加上松弛变量之后得到,反应到最终单纯形表求最优解,直到求出整数最优解,最优解仍为非整数解,继续寻找Gomory约束,18/39,上述过程找到,两个割平面方程,用,决议变量,表示分别为：,切割过程如图。,x,1,x,2,0,1 2 3 4 5 6 7 8 9,654321,2,x,1,+,x,2,=9,2,x,1,+3,x,2,=14,(3.25,2.5),2,x,1,+2,x,2,=11,(3.5,2),(4,1),x,1,+,x,2,=5,使切割后可行域一个,整数坐标顶点,恰好是问题最优解。,19/39,确定割平面方程练习:,20/39,第四章整数规划与分配问题,整数规划特点及作用,分枝定界法,割平面法,分配问题与匈牙利法,应用举例,Integer Programming,简称IP,21/39,分配问题提出,【指派问题】,若干项,工作或任务,需要若,干个人,去完成。因为每人知识、能力、经验不一样，故各人完成不一样任务所需要时间不一样（或其它资源）。,问,应指派哪个人完成何项工作，可使完成全部工作所,消耗总资源最少,？,设某企业准备派,n,个工人,x,1,x,2,x,n,去作,n,件工作,y,1,y,2,y,n,.已知工人,x,i,完成工作,y,j,所需时间为,c,ij,(,i,j,=1,2,n,).,现问：怎样确定一个分配工人去工作方案，使得工人们完成工作,总时间为最少,？,22/39,标准形式分配问题,分配方案满足下述两个条件：,任一个工人都不能去做两件或两件以上工作,任一件工作都不能同时接收两个及以上工人去做,设某企业准备派,n,个工人,x,1,x,2,x,n,去作,n,件工作,y,1,y,2,y,n,.已知工人,x,i,完成工作,y,j,所需时间为,c,ij,(,i,j,=1,2,n,).,现问：怎样确定一个分配工人去工作方案，使得工人们完成工作,总时间为最少,？,23/39,标准形式分配问题,n,个人,n,件事,每件,事,必有且只有一个人去做,每个,人,必做且只做一件事,24/39,数学模型,n,个人,n,件事,c,ij,：,第,i,人做第,j,事费用,x,ij,1,若指派第,i,人做第,j,事,0,若指派第,i,人不做第,j,事,总费用,：,i,，,j,1,.,n,j,1,.,n,i,1,.,n,每件,事,必有且只有一个人去做,每个,人,必做且只做一件事,时间、原料、金钱等资源,25/39,数学模型,j,1,.,n,i,1,.,n,s.t.,线性规划问题,运输问题,0-1型整数规划问题,26/39,匈牙利,法,1955年由美国数学家W.W.kuhn(库恩)提出，利用了匈牙利数学家D.Konig(康尼格)证实2个定理。,系数矩阵,(效率矩阵),解矩阵,(决议变量矩阵),n,个人,n,件事,27/39,定义,：,在系数矩阵,C,中，,处于不一样行不一样列,一组零元素，称为,独立零元素组,，其中每个元素称为,独立零元素,。,最优解,28/39,0,1,4,丙,0,8,5,乙,2,1,0,甲,C,B,A,时 工作,间,人员,0,0,4,丙,0,7,5,乙,2,0,0,甲,C,B,A,时 工作,间,人员,4,5,8,丙,4,12,9,乙,9,8,7,甲,C,B,A,时,工作,间,人员,定理：,若,将分配问题系数矩阵,每一行,及,每一列,分别,减去,各行及各列,最小元素,，,则,新分配问题与原分配问题有,相同最优解,，只有最优值差一常数。,相关定理,使每行每列,都出现零元素,29/39,步骤1：,变换系数矩阵，使其每行每列都出现0元素,把各,行,元素分别减去本行元素最小值，然后,在此基础上,再把每,列,元素减去本列中最小值。,此时每行及每列中必定都有0元素,30/39,步骤2：,进行试分配，判断是否存在,n,个独立零元素,尝试对全部零元素做,标识,，,确定,独立零元素,。,（1）逐,行,检验,对,只有一个,未标识,零元素,行,，用,记号,O,将该零元素圈起，然后将,被圈起零元素所在列,其它,未标识零元素,用,记号/,划去。,重复行检验，直到,每一行都没有未被标识,零元素,或,最少有两个未被标识,零元素为止。,表示此人只能做该事,（此事只能由该人做,）,表示此事已不能由,其它人来做,（此人已不能做其它事,）,31/39,步骤2：,进行试分配，判断是否存在,n,个独立零元素,尝试对全部零元素做,标识,，,确定,独立零元素,。,（1）逐行,检验,对,只有一个,未标识,零元素,行,，用,记号,O,将该零元素圈起，然后将,被圈起零元素所在列,其它,未标识零元素,用,记号/,划去。,重复行检验，直到,每一行都没有未被标识,零元素,或,最少有两个未被标识,零元素为止。,（2）逐,列,检验,与行检验类似：,对只有一个未标识零元素,列,，用记号,O将该零元素圈起，然后将被圈起零元素所在,行,其它未标识零元素用记号/划去。,重复,列,检验，直到,没有未被标识,零元素,或,最少有两个未被标识,零元素为止。,32/39,圈0,即独立零元素,步骤2：,进行试分配，判断是否存在,n,个独立零元素,尝试对全部零元素做,标识,，,确定,独立零元素,33/39,可能出现三种情况,1.每一行都有圈0出现，圈0个数恰好等于,n,2.存在未标识过零元素，但它们所在行和列中，未被标识过零元素个数均最少有两个。,3.不存在未被标识过零元素，但圈0个数,n,可进行分配：令,圈0,位置决议变量取值,为1,，其它为0,（3）判断,独立零元素,个数,34/39,可能出现三种情况,2.存在未标识过零元素，但它们所在行和列中，未被标识过零元素个数均最少有两个。,3.不存在未被标识过零元素，但圈0个数,n,从某,行,（,列,）,两个,未被标识过零元素中,任选一个,加上,圈,，然后给,同,列,、同,行,其它未被标识零元素都加,/,，然后再进行行、列检验，可能出现情况1或3。,（3）判断,独立零元素,个数,圈0个数,等于,n,=5,多重最优解,35/39,可能出现三种情况,3.不存在未被标识过零元素，但圈0个数,n,（3）判断,独立零元素,个数,圈0个数4,n,=5,作,最少直线覆盖当前全部零元素,，便于下步增加独立零元素个数。,36/39,定理：,系数矩阵,C,中,独立零元素最多个数,等于,能覆盖全部零元素,最少线数,。,由匈牙利数学家D.Konig(康尼格)所证实,例,：分别求以下矩阵中独立零元素最多个数。,4,4,独立零元素,个数最多：,37/39,对,不含圈0,行打,；,在打,行中，对全部零元素所在,列,打；,在全部打,列中，对圈0所在,行,打；,重复2,3步，直到不能,打为止。,对,未打每一行,画一横线，对,已打每一列,画一纵线，即得到覆盖当前0元素,最少直线,集。,38/39,对,不含圈0,行打,；,在打,行中，对全部零元素所在,列,打；,在全部打,列中，对圈0所在,行,打；,重复2,3步，直到不能,打为止。,对,未打每一行,画一横线，对,已打每一列,画一纵线，即得到覆盖当前0元素,最少直线,集。,圈0个数4,n,=5,39/39,