运筹学03整数规划2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,0-1,规划,0-1,规划在线性整数规划中具有重要地位。,定理：任何整数规划都可以化成,0-1,规划。,一般地说，可把整数,x,变成,(k+1),个,0-1,变量公式为：,x=y,0,+2y,1,+2,2,y,2,+,.2,k,y,k,例如,x,为,0,和,9,之间的任意数，则,x=y,0,+2y,1,+2,2,y,2,+2,3,y,3,由于这个原因，数学界曾纷纷寻找,“,背包问题,”,解的方法，但进展缓慢。,1,一、投资场所的选择,京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有,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,万元，问应选择哪几个销售点，可使年利润为最大,?,2,解：设：,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,3,二、固定成本问题,高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。每种容器售出一只所得的利润分别为,4,万元、,5,万元、,6,万元，可使用的金属板有,500,吨，劳动力有,300,人月，机器有,100,台月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是,l00,万元，中号为,150,万元，大号为,200,万元。现在要制定一个生产计划，使获得的利润为最大。,4,解：这是一个整数规划的问题。设,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,。,5,这样我们可建立如下的数学模型：,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,6,三、投资问题,某公司在今后五年内考虑给以下的项目投资。已知：,项目,A,：,从第一年到第四年每年年初需要投资，并于次年末回收本利,115%,，但要求第一年投资最低金额为,4,万元，第二、三、四年不限；,项目,B,：,第三年初需要投资，到第五年未能回收本利,128,，但规定最低投资金额为,3,万元，最高金额为,5,万元；,项目,C,：,第二年初需要投资，到第五年未能回收本利,140%,，但规定其投资额或为,2,万元或为,4,万元或为,6,万元或为,8,万元。,项目,D,：,五年内每年初可购买公债，于当年末归还，并加利息,6%,，此项投资金额不限。,该部门现有资金,10,万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大,?,7,解：,1),设,x,iA,、,x,iB,、,x,iC,、,x,iD,( i,1,，,2,，,3,，,4,，,5),分别表示第,i,年年初给项目,A,，,B,，,C,，,D,的投资额；,设,y,iA,，,y,iB,，是,0,1,变量，并规定取,1,时分别表示第,i,年给,A,、,B,投资，否则取,0,（,i = 1, 2, 3, 4, 5,）。,设,y,iC,是非负整数变量，,并规定：,2,年投资,C,项目,8,万元时,，,取值为,4,；,2,年投资,C,项目,6,万元时，取值为,3,；,2,年投资,C,项目,4,万元时，取值为,2,；,2,年投资,C,项目,2,万元时，取值为,1,；,2,年不投资,C,项目时， 取值为,0,；,8,这样我们建立如下的决策变量,：,第,1,年 第,2,年 第,3,年 第,4,年 第,5,年,A,x,1A,x,2A,x,3A,x,4A,B,x,3B,C,x,2C,(=20000y,2C,),D,x,1D,x,2D,x,3D,x,4D,x,5D,9,2,）约束条件：,第一年：年初有,100000,元，,D,项目在年末可收回投资，故第一年年初应把全部资金投出去，于是,x,1A,+,x,1D,= 100000,；,第二年：,A,次年末才可收回投资故第二年年初的资金为,1.06,x,1D,，于是,x,2A,+,x,2C,+,x,2D,= 1.06,x,1D,；,第三年：年初的资金为,1.15,x,1A,+1.06,x,2D,，于是,x,3A,+,x,3B,+,x,3D,= 1.15,x,1A,+ 1.06,x,2D,；,第四年：年初的资金为,1.15,x,2A,+1.06,x,3D,，于是,x,4A,+,x,4D,= 1.15,x,2A,+ 1.06,x,3D,；,第五年：年初的资金为,1.15,x,3A,+1.06,x,4D,，于是,x,5D,= 1.15,x,3A,+ 1.06,x,4D,；,10,关于项目,A,的投资额规定,:,x,1A, 40000,y,1A,，,x,1A, M,y,1A,，,M,是足够大的数；,保证当,y,1A,= 0,时，,x,1A,= 0,；当,y,1A,= 1,时，,x,1A,40000,关于项目,B,的投资额规定,:,x,3B, 30000,y,3B,，,x,3B, 50000,y,3B,；,保证当,y,3B,= 0,时，,x,3B,= 0,；当,y,3B,= 1,时，,50000,x,3B, 30000,关于项目,C,的投资额规定,:,x,2C,= 20000,y,2C,，,y,2C,= 0,，,1,，,2,，,3,，,4,11,3,）目标函数及模型：,Max z = 1.15,x,4A,+ 1.40,x,2C,+ 1.28,x,3B,+ 1.06,x,5D,s.t.,x,1A,+,x,1D,= 100000,；,x,2A,+,x,2C,+,x,2D,= 1.06,x,1D,；,x,3A,+,x,3B,+,x,3D,= 1.15,x,1A,+ 1.06,x,2D,；,x,4A,+,x,4D,= 1.15,x,2A,+ 1.06,x,3D,；,x,5D,= 1.15,x,3A,+ 1.06,x,4D,；,x,1A, 40000,y,1A,x,1A, M,y,1A,x,3B, 30000,y,3B,x,3B, 50000,y,3B,x,2C,= 20000,y,2C,y,iA,，,y,iB,= 0,或,1,，,i = 1,2,3,4,5,y,2C,= 0,，,1,，,2,，,3,，,4,x,iA,，,x,iB,，,x,iC,，,x,iD, 0 ( i = 1,、,2,、,3,、,4,、,5,）,12,0-1,变量在特殊约束中的应用,互斥约束,矛盾约束,在建立数学模型时，有时会遇到相互矛盾的约束，模型只要求其中的一个约束起作用。,13,例：,下面两个约束是相互矛盾,f(x)-5,0 (1),f(x),0 (2),引入一个整数变量来处理,-f(x)+5,M,（,1-y) (3),f(x),My (4),M,是足够大的整数，,y,是,0-1,变量,14,当,y=1,时,(1)(3),无差别,(4),式显然成立,;,当,y=0,时,(2)(4),无差别,(3),式显然成立。,以上方法可以处理绝对值形式的约束,f(x),a (a0),此时,f(x),a (5),f(x),-a (6),是矛盾约束。,15,引入一个整数变量来处理,-f(x)+a,M,（,1-y),f(x)+a,My,M,是足够大整数，,y,是,0-1,变量,注意：对,|f(x)|,a (a0),不必引入,0-1,变量，因为,f(x),a,和,f(x),-a,并不矛盾。,16,多中选一的约束,例如：模型希望在下列,n,个约束中，只能有一个约束有效，,f,i,(x),0 i=1,2,.n,引入,n,个,0-1,变量,y,i,i=1,2,n,则上式可改写为：,f,i,(x),M(1-y,i,),y,1,+ y,2,+,+ y,n,=1,17,如果希望有,k,个约束有效,则：,f,i,(x),M(1-y,i,), y,1,+ y,2,+,+ y,n,= k,如果希望至多有,k,个约束成立,则：,f,i,(x),M(1-y,i,), y,1,+ y,2,+,+ y,n,k,如果希望至少有,k,个约束成立,则：,f,i,(x),M(1-y,i,), y,1,+ y,2,+,+ y,n,k,18,逻辑关系约束,比较典型的逻辑关系是,if-then,关系，也称,if-then,约束，这类逻辑关系一般涉及两个约束，,如果第一个约束成立，则第二个约束也必须成立，否则，如果第一个约束不成立，则第二个约束也可以不成立。可以描述如下,：,19,如果,f,(x)0,成立，则,g,(x),0,必须成立；,如果,f,(x)0,不成立，则对,g,(x),无限制。,引入,0-1,变量：,f,(x),-M(1-y) (*),g,(x),My,20,如果,f,(x)0,成立，则,y,不能为,1,，否则与（*）矛盾；,所以,y=0, g,(x),0,成立。,如果,f,(x),0,（即,f,(x)0,不成立）,则,y,的取值已无关紧要，因为,y,取任何值（*）总成立，所以,y,的取值由（*）控制，因此,g,(x),的取值不受任何限制。,21,试引入,0,1,变量将下列各题分别表达为一般线性约束条件,（,1,）,x,1,+,x,2,6,或,4,x,1,+6,x,2,10,或,2,x,1,+4,x,2,20,（,2,）若,x,1,5,，则,x,2,0,，否则,x,2,8,（,3,）,x,2,取值,0,，,1,，,3,，,5,，,7,【,解,】,（,1,）,3,个约束只有,1,个起作用,或,22,（,3,）右端常数是,5,个值中的,1,个,（,2,）两组约束只有一组起作用,23,0-1,规划的解法,隐枚举法,(Implicit Enumeration),基本上此法可以从所有变量等于零出发（初始点），然后依次指定一些变量取值为,1,，直到获得一个可行解，于是把第一个可行解记作迄今为止最好的可行解，再重复，依次检查变量为,0,，,1,的各种组合，对迄今为止最好的可行解加以改进，直到获得最优解。,24,例,(p90),求下列问题：,Max Z=3x,1,- 2x,2,+ 5x,3,s.t. x,1,+2x,2,- x,3,2 (1),x,1,+4x,2,+ x,3,4 (2),x,1,+ x,2,3 (3),4x,2,+ x,3,6 (4),x,j,0,或,1 (5),25,解：,容易看出,(1,0,0),满足约束条件，对应,Z=3,，对,Max Z,来说，希望,Z,3,所以增加约束条件：,Z=3x,1,- 2x,2,+ 5x,3,3,(0),称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。,26,最优解,（,1,，,0,，,1,）,Z=8,27,增加约束条件（,0,）（,Z,3),后实际做了,24,次运算，而原问题需要计算,2,3,*4=32,次运算（,3,个变量，,4,个约束条件）。,28,注意：,改进过滤性条件，在计算过程中随时调整右边常数。,价值系数按递增排列。,以上两种方法可减少计算量。,29,改进过滤性条件,Z,5 (0,),30,改进过滤性条件,Z,8 (0,),最优解,(X,2,X,1,X,3,) =,（,0,，,1,，,1,）,Z=8,实际只计算了,16,次,31,例（,p91,）,求下列问题：,Max Z=3x,1,+ 4x,2,+ 5x,3,+ 6x,4,s.t. 2x,1,+ 3x,2,+ 4x,3,+ 5x,4,15,x,j,0,且为整数,解：先变换,x,j,为,0-1,变量,x=y,0,+2y,1,+2,2,y,2,+,.2,k,y,k,32,解：,先变换,x,j,为,0-1,变量,x=y,0,+2y,1,+2,2,y,2,+,.2,k,y,k,x,1,7 x,1,=y,01,+2y,11,+2,2,y,21,x,2,5 x,2,=y,02,+2y,12,+2,2,y,22,x,3,3 x,3,=y,03,+2y,13,x,4,3 x,4,=y,04,+2y,14,代入原问题，得到：,33,Max Z= 3 y,01,+6y,11,+12y,21,+ 4y,02,+8y,12,+16y,22,+ 5 y,03,+10y,13,+ 6 y,04,+12y,14,s.t.,2y,01,+4y,11,+8y,21,+3y,02,+6y,12,+12y,22,+ 4 y,03,+8y,13,+ 5 y,04,+10y,14,15,y,ij,=0,或,=1,34,用隐枚举法可得到：,y,11,=y,21,=y,02,=1,其他全为零,最优解,（,6,，,1,，,0,，,0,）,Z=22,35,有,n,项不同的任务，恰好,n,个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把,n,项任务指派给,n,个人，使得完成,n,项任务的总的效率最高，这就是指派问题。,指派问题（分配问题）,(Assignment Problem),36,指派问题（分配问题）,(Assignment Problem),有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,37,解,：引入,0,1,变量,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,38,引入,0-1,变量,x,ij,=1,分配第,i,人去完成第,j,项任务，,x,ij,=0,不分配第,i,人去完成第,j,项任务。,分配问题的数学模型：,Min Z=, ,c,ij,x,ij,x,ij,=1,(j=1,2,n),x,ij,=1,(i=1,2,n),x,ij,0,或,1,(i=1,2,.m; j=1,2,n),39,x,ij,=1,(j=1,2,n),表示第,j,项任务只能由一人去完成。,x,ij,=1,(i=1,2,n),表示第,i,人只能完成一项任务。,满足约束条件的解称为可行解可写成矩阵形式：,X=,0 1 0 0,0 0 1 0,0 0 0,0 0 0 1,称为解矩阵其各行各列元素之和为,1,。,40,匈牙利算法基本思想：,对同一工作,i,来说，所有机床的效率都提高或降低同一常数，不会影响最优分配；同样，对同一机床,j,来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。,41,分配问题性质：,分配问题的最优解有这样的性质，若从系数矩阵,C,的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵,B,，那么,B,为系数矩阵求得的最优解和用原来的系数矩阵,C,求得的最优解相同。,42,匈牙利算法：矩阵中独立,0,元素定理（匈牙利数学家康尼格）,系数矩阵中独立,0,元素的最多个数等于能覆盖所有,0,元素的最少直线数。,43,例,有一份中文说明书，需翻译成英、日、德、俄四种文字，分别记作,E,、,J,、,G,、,R,，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？,44,任务,人员,E,J,G,R,甲,2,15,13,4,乙,10,4,14,15,丙,9,14,16,13,丁,7,8,11,9,45,匈牙利算法的步骤：,第一步：使分配问题的系数矩阵经变换，在各行各列中都出现,0,元素：,从系数矩阵的每行元素减去该行的最小元素。,再从所得系数矩阵的每列元素减去该列的最小元素。,若某行已经有,0,元素，就不必再减了。,46,(cij)=,2,15 13 4,4,14 15,9,14 16 13,7,8 11 9,2 4 9 7,0 13 11,2,6 0 10 11,0 5 7 4,0 1,4,2,4 2,0 13 7 0,6 0 6 9,0 5 3 2,0 1 0 0,47,第二步：进行试分配，以寻找最优解。,从只有一个,0,元素的行（或列）开始，给这个,0,元素加圈，记,，,然后划去,所在的列（或行）的其他,0,元素，记作,。,给只有一个,0,元素的列（或行）的,0,元素,加圈，记,，然后划去,所在的,行（或列）,的其他,0,元素，记作,。,反复进行上述两步，直到所有的,0,元素都被圈出和划掉为止。,48,若还有没有划,圈的,0,元素，且同,行（或列）,的,0,元素,至少有二个，从剩有,0,元素最少的,行（或列）开始，比较这行各,0,元素所在列中,0,元素的数目，选择,0,元素少的那列的,0,元素加圈，然后划掉同行同列的其他,0,元素，可反复进行，,直到所有的,0,元素都被圈出和划掉为止,。,若,元素的数目,m,等于,矩阵阶数,n,，那么这分配问题的最优解已得到。若,mn,，则转下一步。,49,0 13 7 0,6,6 9,0 5 3 2,0 1 0 0,从只有一个,0,元素的行（或列）开始，给这个,0,元素加圈，记,。,50,0 13 7 0,6,6 9,5 3 2,0 1 0 0,从只有一个,0,元素的行（或列）开始，给这个,0,元素加圈，记,，,51,13 7 0,6,6 9,5 3 2,1 0 0,然后划去,所在的列的其他,0,元素，记作,。,52,13 7 0,6,6 9,5 3 2,1,0,给只有一个,0,元素的列的,0,元素,加圈，记,。,53,13 7 0,6,6 9,5 3 2,1,然后划去,所在的,行,的其他,0,元素，记作,54,13 7,6,6 9,5 3 2,1,给最后一个,0,元素,加圈，记,。,55,0,0 0,1,0,1,0 0,1,0 0 0,0,0,1,0,可见,m=n=4,得到最优解,。,即甲译俄文、乙译日文、丙译英文、丁译德文所需时间最少。,Z=28,小时,56,例,分配问题效率矩阵,任务,人员,A,B,C,D,E,甲,12,7,9,7,9,乙,8,9,6,6,6,丙,7,17,12,14,9,丁,15,14,6,6,10,戊,4,10,7,10,9,57,12,7,9,7,9,8,9,6,6,6,7,17,12,14,9,15,14,6,6,10,4,10,7,10,9,7 6 7 6 4,58,5,0,2,0,2,2,3,0,0,0,0,10,5,7,2,9,8,0,0,4,0,6,3,6,5,59,5,0,2,0,2,2,3,0,0,0,10,5,7,2,9,8,0,0,4,0,6,3,6,5,从只有一个,0,元素的行开始，给这个,0,元素加圈，记,60,5,0,2,0,2,2,3,0,0,0,10,5,7,2,9,8,0,0,4,6,3,6,5,然后划去,所在的列的其他,0,元素，记作,。,61,5,2,0,2,2,3,0,0,0,10,5,7,2,9,8,0,0,4,6,3,6,5,从只有一个,0,元素的列开始，给这个,0,元素加圈，记,62,5,2,2,2,3,0,0,0,10,5,7,2,9,8,0,0,4,6,3,6,5,然后划去,所在的行的其他,0,元素，记作,。,63,5,2,2,2,3,0,0,10,5,7,2,9,8,0,0,4,6,3,6,5,从只有一个,0,元素的列开始，给这个,0,元素加圈，记,64,5,2,2,2,3,10,5,7,2,9,8,0,0,4,6,3,6,5,然后划去,所在的行的其他,0,元素，记作,。,65,5,2,2,2,3,10,5,7,2,9,8,0,4,6,3,6,5,从只有一个,0,元素的列开始，给这个,0,元素加圈，记,66,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,然后划去,所在的行的其他,0,元素，记作,。,67,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,的个数,m=4,而,n=5, mn,，转下一步。,68,第三步：作最少的直线覆盖所有的,0,元素，以确定该系数矩阵中能找到最多的独立元素数。,对没有,的行，打,；,对已打,行中所有含,0,元素的列,打,；,再对打,列中含,0,元素的行,打,；,重复上述两步，直到得不出新的,打,行列为止。,对没有,打,行画横线，有,打,列画纵线，就得到覆盖所有,0,元素的最少直线数。,69,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,对没有,的行，打,70,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,对已打,行中所有含,0,元素的列,打,71,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,再对打,列中含,0,元素的行,打,72,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,对没有,打,行画横线,73,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,有,打,列画纵线,74,第四步：在没有被直线覆盖的部分中找出最小元素，然后在,打,行各元素都减去这,最小元素，,而在打,列中各元素都加上这,最小元素，以保证原来,0,元素不变，这样得到新的系数矩阵（它的最优解和原问题相同）。若得到,n,个独立的,0,元素，则已经得到最优解。否则回到第三步重复进行。,75,5,2,2,2,3,10,5,7,2,9,8,4,6,3,6,5,没有被直线覆盖的最小元素为,2,76,5,0,2,0,2,2,3,0,0,0,0,10,5,7,2,9,8,0,0,4,0,6,3,6,5,77,5,0,2,0,2,2,3,0,0,0,-2,8,3,5,0,9,8,0,0,4,-2,4,1,4,3,在,打,行各元素都减去这,最小元素,2,。,78,7,0,2,0,2,4,3,0,0,0,0,8,3,5,0,11,8,0,0,4,0,4,1,4,3,在打,列中各元素都加上这,最小元素,2,。,79,7,0,2,0,2,4,3,0,0,0,0,8,3,5,0,11,8,0,0,4,0,4,1,4,3,重复第二步，寻找独立,0,元素。,80,7,0,2,0,2,4,3,0,0,0,0,8,3,5,0,11,8,0,0,4,4,1,4,3,从只有一个,0,元素的行开始，给这个,0,元素加圈，记,81,7,0,2,0,2,4,3,0,0,0,8,3,5,0,11,8,0,0,4,4,1,4,3,然后划去,所在的列的其他,0,元素，记作,。,82,7,0,2,0,2,4,3,0,0,0,8,3,5,11,8,0,0,4,4,1,4,3,从只有一个,0,元素的行开始，给这个,0,元素加圈，记,83,7,0,2,0,2,4,3,0,0,8,3,5,11,8,0,0,4,4,1,4,3,然后划去,所在的列的其他,0,元素，记作,。,84,7,2,0,2,4,3,0,0,8,3,5,11,8,0,0,4,4,1,4,3,从只有一个,0,元素的列开始，给这个,0,元素加圈，记,85,7,2,2,4,3,0,0,8,3,5,11,8,0,0,4,4,1,4,3,然后划去,所在的行的其他,0,元素，记作,。,86,7,2,2,4,3,0,0,8,3,5,11,8,0,0,4,4,1,4,3,下面有二种分配方案：,87,7,2,2,4,3,8,3,5,11,8,4,4,1,4,3,下面有二种分配方案：第一种,88,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,0,最优解如下：,Z=32,89,分配问题结果如下：,Z=32,任务,人员,A,B,C,D,E,甲,12,7,9,7,9,乙,8,9,6,6,6,丙,7,17,12,14,9,丁,15,14,6,6,10,戊,4,10,7,10,9,90,7,2,2,4,3,8,3,5,11,8,4,4,1,4,3,下面有二种分配方案：第二种,91,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,最优解如下：,Z=32,92,分配问题结果如下：,Z=32,任务,人员,A,B,C,D,E,甲,12,7,9,7,9,乙,8,9,6,6,6,丙,7,17,12,14,9,丁,15,14,6,6,10,戊,4,10,7,10,9,93,特殊的指派问题,1,。,m,与,n,不相等,若,mn,，虚设,m-n,项工作，使工作数与人数相等，相应的系数为,0,。,2,。最大化问题,对目标函数系数变为,M-c,ij,3,。一个人可以做多件事,将该人化作相同的,“,几个人,”,来接受指派,4,。某事一定不能由某人做的指派问题,将相应的费用系数设为足够大的数,M,94,某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等,5,个类别通过评估，家具超市不能放在第,3,个点，计算机超市不能放在第,4,个点，不同类别的商品投资到各点的年利润（万元）预测值见表,1,该商业集团如何作出投资决策使年利润最大。,表,1,地点,商品,1,2,3,4,电器,120,300,360,400,服装,80,350,420,260,食品,150,160,380,300,家具,90,200,180,计算机,220,260,270,【,解,】,这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表,1,进行转换,（,1,）令,c,43,=c,54,=0,（,2,）转换成求最小值问题，令,M,420,，得到效率表（机会损失表）,（,3,）虚拟一个地点,5,95,表,2,地点,商品,1,2,3,4,5,电器,300,120,60,20,0,服装,340,70,0,160,0,食品,270,260,40,120,0,家俱,330,220,420,240,0,计算机,200,160,150,420,0,Z=1350,转换后得到表,2,用匈牙利法求解得到最优解,最优投资方案,：地点,1,投资建设计算机超市，地点,2,投资建设服装超市，地点,3,投资建设食品超市，地点,4,投资建设电器超市，年利润总额预测值为,1350,万元,96,某商业公司计划开办,5,家新商店，由,3,家建筑公司分别承建。根据实际情况，可以允许每家建筑公司承建一家或二家商店，求使总费用最少的指派方案：,97,98,99,最优指派方案为由,A1,承建,B1,和,B3,，由,A2,承建,B2,，由,A3,承建,B4,和,B5,。这样总费用为,35,万元。,100,谢谢大家！,101,练习,企业计划生产,4000,件某种产品，该产品可自己加工、外协加工任意一种形式生产已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如表,3,2,所示，怎样安排产品的加工使总成本最小,【,解,】,设,xj,为采用第,j,（,j=1,2,3,）种方式生产的产品数量，生产费用为,102,式中,k,j,是固定成本，,c,j,是单位产品成本设,0,1,变量,y,j,，令,数学模型为,（,3.4,）,式（,3.4,）中 是处理,x,j,与,y,j,一对变量之间逻辑关系的特殊约束，当,x,j,0,时,y,j,=1,当,x,j,0,时，为使,Z,最小化，有,y,j,=0,。,求解得到：,X,(0,，,2000,，,2000),T,，,Y,(0,，,1,，,1),T,，,Z,=25400.,103,练习,：华美公司有,5,个项目被列入投资计划，各项目的投资额和期望的投资收益见下表：,项目,投资额,(,万元,),投资收益,(,万元,),1,210,150,2,300,210,3,100,60,4,130,80,5,260,180,104,该公司只有,600,万元资金可用于投资，由于技术原因，投资受到以下约束：,在项目,1,、,2,和,3,中必须有一项被选中；,项目,3,和,4,只能选中一项；,项目,5,被选中的前提是项目,1,必须被选中。,如何在上述条件下，选择一个最好的投资方案，使收益最大。,105,解：令,1,选中该项目,0,未选中该项目,x,i,=,Max Z=150 x,1,+,210x,2,+,60x,3,+80x,4,+,180x,5,s.t.,210 x,1,+,300x,2,+100x,3,+130x,4,+,260x,5,600,x,1,+,x,2,+,x,3,=1,x,3,+ x,4,1,x,5,x,1,x,i,=1,或,0,106,