数学建模运筹模型学习教案.pptx

会计学1数学数学(shxu)建模运筹模型建模运筹模型第一页，共83页。例例例例 下料问题下料问题下料问题下料问题 某工厂要做某工厂要做某工厂要做某工厂要做100100100100套钢架，每套用长为套钢架，每套用长为套钢架，每套用长为套钢架，每套用长为2.9m2.9m2.9m2.9m，2.1m2.1m2.1m2.1m，1.5m1.5m1.5m1.5m的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长的圆钢各一根，已知原料每根长7.4m7.4m7.4m7.4m。应如。应如。应如。应如何何何何(rh)(rh)(rh)(rh)下料，可使所用原料最省？下料，可使所用原料最省？下料，可使所用原料最省？下料，可使所用原料最省？解：共可设计下列解：共可设计下列解：共可设计下列解：共可设计下列5 5 5 5种下料方案种下料方案种下料方案种下料方案线性规划(xin xn u hu)第2页/共83页第二页，共83页。第3页/共83页第三页，共83页。建模步骤：建模步骤：建模步骤：建模步骤：(1)(1)(1)(1)确定确定确定确定(qudng)(qudng)(qudng)(qudng)决策变量：我们需要作出决策或者选决策变量：我们需要作出决策或者选决策变量：我们需要作出决策或者选决策变量：我们需要作出决策或者选择的量，一般情况下，题目问什么就设什么为决策变择的量，一般情况下，题目问什么就设什么为决策变择的量，一般情况下，题目问什么就设什么为决策变择的量，一般情况下，题目问什么就设什么为决策变量。量。量。量。(2)(2)(2)(2)找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决策变量受到的所有的约束。找出约束条件：即决策变量受到的所有的约束。(3)(3)(3)(3)写出目标函数：即问题所要达到的目标，并明确是写出目标函数：即问题所要达到的目标，并明确是写出目标函数：即问题所要达到的目标，并明确是写出目标函数：即问题所要达到的目标，并明确是求求求求maxmaxmaxmax还是还是还是还是minminminmin。线性规划(xin xn u hu)第4页/共83页第四页，共83页。例例例例 混合配料问题混合配料问题混合配料问题混合配料问题 某糖果厂用原料某糖果厂用原料某糖果厂用原料某糖果厂用原料1 1 1 1、2 2 2 2、3 3 3 3加工三种加工三种加工三种加工三种(sn(sn(sn(sn zhn)zhn)zhn)zhn)不同牌号的糖果甲、乙、丙。已知各种牌号糖果不同牌号的糖果甲、乙、丙。已知各种牌号糖果不同牌号的糖果甲、乙、丙。已知各种牌号糖果不同牌号的糖果甲、乙、丙。已知各种牌号糖果中原料中原料中原料中原料1 1 1 1、2 2 2 2、3 3 3 3的含量、原料每月限用量、三种的含量、原料每月限用量、三种的含量、原料每月限用量、三种的含量、原料每月限用量、三种(sn(sn(sn(sn zhn)zhn)zhn)zhn)牌号糖果的加工费及售价，如下表所示。该厂每牌号糖果的加工费及售价，如下表所示。该厂每牌号糖果的加工费及售价，如下表所示。该厂每牌号糖果的加工费及售价，如下表所示。该厂每月如何生产才能获利最大？月如何生产才能获利最大？月如何生产才能获利最大？月如何生产才能获利最大？线性规划(xin xn u hu)第5页/共83页第五页，共83页。解：用解：用解：用解：用i=1,2,3i=1,2,3i=1,2,3i=1,2,3代表原料代表原料代表原料代表原料1,2,3,j=1,2,31,2,3,j=1,2,31,2,3,j=1,2,31,2,3,j=1,2,3代表糖果甲、乙、丙。代表糖果甲、乙、丙。代表糖果甲、乙、丙。代表糖果甲、乙、丙。XijXijXijXij表表表表示示示示(biosh)(biosh)(biosh)(biosh)第第第第j j j j中产品中原料中产品中原料中产品中原料中产品中原料i i i i的含量，则的含量，则的含量，则的含量，则 对于原料对于原料对于原料对于原料1 1 1 1：x11,x12,x13;x11,x12,x13;x11,x12,x13;x11,x12,x13;对于原料对于原料对于原料对于原料2 2 2 2：x21,x22,x23;x21,x22,x23;x21,x22,x23;x21,x22,x23;对于原料对于原料对于原料对于原料3 3 3 3：x31,x32,x33;x31,x32,x33;x31,x32,x33;x31,x32,x33;对于甲：对于甲：对于甲：对于甲：x11,x21,x31;x11,x21,x31;x11,x21,x31;x11,x21,x31;对于乙：对于乙：对于乙：对于乙：x12,x22,x32;x12,x22,x32;x12,x22,x32;x12,x22,x32;对于丙：对于丙：对于丙：对于丙：x13,x23,x33;x13,x23,x33;x13,x23,x33;x13,x23,x33;目标函数：利润最大，利润目标函数：利润最大，利润目标函数：利润最大，利润目标函数：利润最大，利润=收入收入收入收入-原料成本原料成本原料成本原料成本-加工费加工费加工费加工费 约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制约束条件：原料用量限制，含量限制线性规划(xin xn u hu)第6页/共83页第六页，共83页。线性规划(xin xn u hu)第7页/共83页第七页，共83页。求解求解求解求解(qi ji)(qi ji)(qi ji)(qi ji)方法：方法：方法：方法：1.1.1.1.图解法图解法图解法图解法 适合含有两个决策变量的模型；适合含有两个决策变量的模型；适合含有两个决策变量的模型；适合含有两个决策变量的模型；maxmaxmaxmax z=x1+3x2 z=x1+3x2 z=x1+3x2 z=x1+3x2s.t.s.t.s.t.s.t.x1+x26 x1+x26 x1+x26 x1+x26-x1+2x28-x1+2x28-x1+2x28-x1+2x28x1 0,x20 x1 0,x20 x1 0,x20 x1 0,x20可行(kxng)域目标(mbio)函数等值线最优解64-860 x1x2线性规划第8页/共83页第八页，共83页。2.2.2.2.单纯形法单纯形法单纯形法单纯形法(人工人工人工人工(rngng)(rngng)(rngng)(rngng)变量法、对偶单纯形法变量法、对偶单纯形法变量法、对偶单纯形法变量法、对偶单纯形法)软件求解：软件求解：软件求解：软件求解：lingolingolingolingo，lindolindolindolindo，MatlabMatlabMatlabMatlabMin f=0.4x1+1.5x2+x3+1.3x4 Min f=0.4x1+1.5x2+x3+1.3x4 Min f=0.4x1+1.5x2+x3+1.3x4 Min f=0.4x1+1.5x2+x3+1.3x4 S.t.0.3x1+3x2+1.5x4=320S.t.0.3x1+3x2+1.5x4=320S.t.0.3x1+3x2+1.5x4=320S.t.0.3x1+3x2+1.5x4=320 0.5x1+2x3+x4=240 0.5x1+2x3+x4=240 0.5x1+2x3+x4=240 0.5x1+2x3+x4=240 1.4x1+0.7x4=420 1.4x1+0.7x4=420 1.4x1+0.7x4=420 1.4x1+0.7x4=420 线性规划(xin xn u hu)第9页/共83页第九页，共83页。将某种物资从将某种物资从将某种物资从将某种物资从m m m m个产地遇到个产地遇到个产地遇到个产地遇到(y do)n(y do)n(y do)n(y do)n个销地，个销地，个销地，个销地，每个产地都有一定的产量每个产地都有一定的产量每个产地都有一定的产量每个产地都有一定的产量aiaiaiai，i=1,2,mi=1,2,mi=1,2,mi=1,2,m，每个，每个，每个，每个销地都对物资有一定的需求量销地都对物资有一定的需求量销地都对物资有一定的需求量销地都对物资有一定的需求量bj,j=1,2,nbj,j=1,2,nbj,j=1,2,nbj,j=1,2,n。已知从第已知从第已知从第已知从第i i i i个产地向第个产地向第个产地向第个产地向第j j j j个销地运送单位物资的运价个销地运送单位物资的运价个销地运送单位物资的运价个销地运送单位物资的运价为为为为cijcijcijcij，总产量等于总需求量，总产量等于总需求量，总产量等于总需求量，总产量等于总需求量()()()()。如何。如何。如何。如何调运物资，才能使总运费最小？调运物资，才能使总运费最小？调运物资，才能使总运费最小？调运物资，才能使总运费最小？设设设设xijxijxijxij为从产地为从产地为从产地为从产地AiAiAiAi运往销地运往销地运往销地运往销地BjBjBjBj的运输量，的运输量，的运输量，的运输量，运输(ynsh)问题第10页/共83页第十页，共83页。运输表：运输表：(产销平衡的运输问题产销平衡的运输问题)求解方法：求解方法：1.1.确定初始基本可行解（西北角确定初始基本可行解（西北角法、最小元素法、最小元素(yun s)(yun s)法、法、vogalvogal法）法）2.2.最优性检验；最优性检验；3.3.迭代求新的基本可行解。迭代求新的基本可行解。运输(ynsh)问题第11页/共83页第十一页，共83页。例例例例 某食品公司下属的三个食品厂某食品公司下属的三个食品厂某食品公司下属的三个食品厂某食品公司下属的三个食品厂A1A1A1A1、A2A2A2A2、A3A3A3A3生产食品，生产食品，生产食品，生产食品，3 3 3 3个厂每月的生产个厂每月的生产个厂每月的生产个厂每月的生产能力分别为能力分别为能力分别为能力分别为7 7 7 7吨、吨、吨、吨、4 4 4 4吨、吨、吨、吨、9 9 9 9吨，食品被运到吨，食品被运到吨，食品被运到吨，食品被运到B1B1B1B1、B2B2B2B2、B3B3B3B3、B4B4B4B4四个销售点，四个销售点，四个销售点，四个销售点，它们对方便食品的月需求量分别为它们对方便食品的月需求量分别为它们对方便食品的月需求量分别为它们对方便食品的月需求量分别为3 3 3 3吨、吨、吨、吨、6 6 6 6吨、吨、吨、吨、5 5 5 5吨、吨、吨、吨、6 6 6 6吨，运输吨，运输吨，运输吨，运输(ynsh)(ynsh)(ynsh)(ynsh)表如下表，试制定最优运送方案。表如下表，试制定最优运送方案。表如下表，试制定最优运送方案。表如下表，试制定最优运送方案。运输(ynsh)问题第12页/共83页第十二页，共83页。解：解：解：解：1.1.1.1.确定确定确定确定(qudng)(qudng)(qudng)(qudng)初始基可行解初始基可行解初始基可行解初始基可行解 最小元素法：最小元素法：最小元素法：最小元素法：运输(ynsh)问题第13页/共83页第十三页，共83页。解：解：解：解：1.1.1.1.确定初始确定初始确定初始确定初始(ch sh)(ch sh)(ch sh)(ch sh)基可行解基可行解基可行解基可行解(最小元素法最小元素法最小元素法最小元素法)初始初始初始初始(ch sh)(ch sh)(ch sh)(ch sh)基本可行解对应的目标函数值：基本可行解对应的目标函数值：基本可行解对应的目标函数值：基本可行解对应的目标函数值：f=3*4+10*3+1*3+2*1+4*6+5*3=86 f=3*4+10*3+1*3+2*1+4*6+5*3=86 f=3*4+10*3+1*3+2*1+4*6+5*3=86 f=3*4+10*3+1*3+2*1+4*6+5*3=86运输(ynsh)问题第14页/共83页第十四页，共83页。解：解：解：解：2.2.2.2.最优性检验最优性检验最优性检验最优性检验 (1)(1)(1)(1)位势位势位势位势(wi sh)(wi sh)(wi sh)(wi sh)：ui+vj=cij (i=1,2,m,j=1,2,n)ui+vj=cij (i=1,2,m,j=1,2,n)ui+vj=cij (i=1,2,m,j=1,2,n)ui+vj=cij (i=1,2,m,j=1,2,n)其中其中其中其中cij cij cij cij 为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应的单位运价。为基本可行解中基变量对应的单位运价。注：注：注：注：m+n-1m+n-1m+n-1m+n-1个方程，个方程，个方程，个方程，m+nm+nm+nm+n个变量。个变量。个变量。个变量。(2)(2)(2)(2)利用位势利用位势利用位势利用位势(wi sh)(wi sh)(wi sh)(wi sh)求非基变量检验数求非基变量检验数求非基变量检验数求非基变量检验数 检验数计算公式：检验数计算公式：检验数计算公式：检验数计算公式：cij-ui-vj cij-ui-vj cij-ui-vj cij-ui-vj (3)(3)(3)(3)检验数全都大于等于零时对应的解为最优检验数全都大于等于零时对应的解为最优检验数全都大于等于零时对应的解为最优检验数全都大于等于零时对应的解为最优解。解。解。解。运输(ynsh)问题第15页/共83页第十五页，共83页。位势位势位势位势(wi sh)(wi sh)(wi sh)(wi sh)：检验数：检验数：检验数：检验数：运输(ynsh)问题第16页/共83页第十六页，共83页。3.3.3.3.迭代迭代迭代迭代(di di)(di di)(di di)(di di)求新基本可行解求新基本可行解求新基本可行解求新基本可行解(1)(1)(1)(1)负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；负检验数中最小者对应的变量进基；(2)(2)(2)(2)在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点在运输表中找一个包含进基变量的闭回路，这个回路上其他顶点均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格均为基变量。依次对闭回路的四个顶点标号，将顶点分为奇点格和偶点格；和偶点格；和偶点格；和偶点格；(3)(3)(3)(3)偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格偶点格的最小值作为调整量，所有奇点格+调整量；偶点格调整量；偶点格调整量；偶点格调整量；偶点格-调整调整调整调整量，即一次迭代量，即一次迭代量，即一次迭代量，即一次迭代(di di)(di di)(di di)(di di)。(4)(4)(4)(4)按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。按位势方程求新解对应的位势及检验数，判别最优性。运输(ynsh)问题第17页/共83页第十七页，共83页。闭回路闭回路闭回路闭回路(hul)(hul)(hul)(hul)：运输(ynsh)问题第18页/共83页第十八页，共83页。迭代及新基本可行迭代及新基本可行迭代及新基本可行迭代及新基本可行(kxng)(kxng)(kxng)(kxng)解的检验数计算：解的检验数计算：解的检验数计算：解的检验数计算：运输(ynsh)问题第19页/共83页第十九页，共83页。产销不平衡运输问题：产销不平衡运输问题：产销不平衡运输问题：产销不平衡运输问题：1.1.1.1.供大于求，引入虚拟销售点，并假设它的需求量供大于求，引入虚拟销售点，并假设它的需求量供大于求，引入虚拟销售点，并假设它的需求量供大于求，引入虚拟销售点，并假设它的需求量为为为为 供不应求，引入虚拟的产地，并假设它的产量为供不应求，引入虚拟的产地，并假设它的产量为供不应求，引入虚拟的产地，并假设它的产量为供不应求，引入虚拟的产地，并假设它的产量为 由于虚拟销地是不存在的，实际上这个差值是在产地由于虚拟销地是不存在的，实际上这个差值是在产地由于虚拟销地是不存在的，实际上这个差值是在产地由于虚拟销地是不存在的，实际上这个差值是在产地贮存的，故从产地到虚拟销地的单位运价为贮存的，故从产地到虚拟销地的单位运价为贮存的，故从产地到虚拟销地的单位运价为贮存的，故从产地到虚拟销地的单位运价为0 0 0 0；同理，由于虚拟产地是不存在的，所以同理，由于虚拟产地是不存在的，所以同理，由于虚拟产地是不存在的，所以同理，由于虚拟产地是不存在的，所以(suy)(suy)(suy)(suy)虚设的虚设的虚设的虚设的产地到各个销地的单位运价也为产地到各个销地的单位运价也为产地到各个销地的单位运价也为产地到各个销地的单位运价也为0.0.0.0.运输(ynsh)问题第20页/共83页第二十页，共83页。例例例例 2 2 2 2个化肥厂供应个化肥厂供应个化肥厂供应个化肥厂供应3 3 3 3个地区的化肥，试决定运费最小的调运方案。个地区的化肥，试决定运费最小的调运方案。个地区的化肥，试决定运费最小的调运方案。个地区的化肥，试决定运费最小的调运方案。解：增加虚设的销地解：增加虚设的销地解：增加虚设的销地解：增加虚设的销地B4B4B4B4，销量，销量，销量，销量(xio lin)(xio lin)(xio lin)(xio lin)为为为为10101010，构造产销平衡，构造产销平衡，构造产销平衡，构造产销平衡的运输表。的运输表。的运输表。的运输表。运输(ynsh)问题第21页/共83页第二十一页，共83页。初始基可行解及其检验初始基可行解及其检验初始基可行解及其检验初始基可行解及其检验(jinyn)(jinyn)(jinyn)(jinyn)数：数：数：数：迭代求新基本可行解：迭代求新基本可行解：迭代求新基本可行解：迭代求新基本可行解：运输(ynsh)问题第22页/共83页第二十二页，共83页。n n n n项任务，恰好有项任务，恰好有项任务，恰好有项任务，恰好有n n n n个人承担，由于每个人的专长不同，个人承担，由于每个人的专长不同，个人承担，由于每个人的专长不同，个人承担，由于每个人的专长不同，完成各工作的效率不同，于是产生了应指派哪个人去完完成各工作的效率不同，于是产生了应指派哪个人去完完成各工作的效率不同，于是产生了应指派哪个人去完完成各工作的效率不同，于是产生了应指派哪个人去完成哪项，使得完成成哪项，使得完成成哪项，使得完成成哪项，使得完成n n n n项任务的总效率最高的问题，这类问项任务的总效率最高的问题，这类问项任务的总效率最高的问题，这类问项任务的总效率最高的问题，这类问题称为指派问题。题称为指派问题。题称为指派问题。题称为指派问题。例例例例 有一份说明书，需要有一份说明书，需要有一份说明书，需要有一份说明书，需要(xyo)(xyo)(xyo)(xyo)译成英、日、德、俄四种译成英、日、德、俄四种译成英、日、德、俄四种译成英、日、德、俄四种文字，现有甲乙丙丁四个人，他们将说明书译成不同文文字，现有甲乙丙丁四个人，他们将说明书译成不同文文字，现有甲乙丙丁四个人，他们将说明书译成不同文文字，现有甲乙丙丁四个人，他们将说明书译成不同文字所需要字所需要字所需要字所需要(xyo)(xyo)(xyo)(xyo)的时间如下表所示，问应指派哪个人完的时间如下表所示，问应指派哪个人完的时间如下表所示，问应指派哪个人完的时间如下表所示，问应指派哪个人完成哪项工作，耗用的总时间最少？成哪项工作，耗用的总时间最少？成哪项工作，耗用的总时间最少？成哪项工作，耗用的总时间最少？指派(zhpi)问题第23页/共83页第二十三页，共83页。一般地，有一般地，有一般地，有一般地，有n n n n项任务、项任务、项任务、项任务、n n n n个完成人，第个完成人，第个完成人，第个完成人，第i i i i人完成第人完成第人完成第人完成第j j j j项任务的项任务的项任务的项任务的代价为代价为代价为代价为cij(i,j=1,2,n),cij(i,j=1,2,n),cij(i,j=1,2,n),cij(i,j=1,2,n),为了求得总代价最小的指派方为了求得总代价最小的指派方为了求得总代价最小的指派方为了求得总代价最小的指派方案案案案(fng n)(fng n)(fng n)(fng n)，引入，引入，引入，引入0-10-10-10-1型变量型变量型变量型变量xij,xij,xij,xij,令令令令 数学模型为数学模型为数学模型为数学模型为 注：指派问题是注：指派问题是注：指派问题是注：指派问题是0-10-10-10-1整数规划的特例，也是运输问题的特例，整数规划的特例，也是运输问题的特例，整数规划的特例，也是运输问题的特例，整数规划的特例，也是运输问题的特例，其产地和销地数均为其产地和销地数均为其产地和销地数均为其产地和销地数均为1 1 1 1，各产地产量和各销地销量均为，各产地产量和各销地销量均为，各产地产量和各销地销量均为，各产地产量和各销地销量均为1.1.1.1.指派(zhpi)问题第24页/共83页第二十四页，共83页。n n指派问题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。指派问题的求解方法：匈牙利法。n n匈牙利法基于下面的事实：如果系数矩阵的所有元素满足匈牙利法基于下面的事实：如果系数矩阵的所有元素满足匈牙利法基于下面的事实：如果系数矩阵的所有元素满足匈牙利法基于下面的事实：如果系数矩阵的所有元素满足(mnz)(mnz)(mnz)(mnz)：cij=0cij=0cij=0cij=0，而其中有，而其中有，而其中有，而其中有n n n n个位于不同行不同列的一组个位于不同行不同列的一组个位于不同行不同列的一组个位于不同行不同列的一组0 0 0 0元元元元素，则只要令对应于这些素，则只要令对应于这些素，则只要令对应于这些素，则只要令对应于这些0 0 0 0元素位置的元素位置的元素位置的元素位置的xij=1xij=1xij=1xij=1，其余的，其余的，其余的，其余的xij=0 xij=0 xij=0 xij=0，就得到最优解。就得到最优解。就得到最优解。就得到最优解。n n n n 如如如如 则则则则n n n n 指派(zhpi)问题第25页/共83页第二十五页，共83页。n n求解上例：求解上例：求解上例：求解上例：n n n n 行变换得行变换得行变换得行变换得 列变换得列变换得列变换得列变换得n n n n 画出最少覆盖画出最少覆盖画出最少覆盖画出最少覆盖0 0 0 0元素元素元素元素(yun s)(yun s)(yun s)(yun s)的直线，的直线，的直线，的直线，r=4=r=4=r=4=r=4=矩阵阶数，矩阵阶数，矩阵阶数，矩阵阶数，n n 则可以找到最优解则可以找到最优解则可以找到最优解则可以找到最优解,所需最少时间所需最少时间所需最少时间所需最少时间=4+4+9+11=28=4+4+9+11=28=4+4+9+11=28=4+4+9+11=28 n n 甲甲甲甲-俄语俄语俄语俄语n n 从而得到最优指派：乙从而得到最优指派：乙从而得到最优指派：乙从而得到最优指派：乙-日语日语日语日语n n 丙丙丙丙-英语英语英语英语n n 丁丁丁丁-德语德语德语德语 指派(zhpi)问题第26页/共83页第二十六页，共83页。例例例例 分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成分配甲、乙、丙、丁四个人去完成A A A A、B B B B、C C C C、D D D D、E E E E五项任务，每人完成各五项任务，每人完成各五项任务，每人完成各五项任务，每人完成各项任务的时间项任务的时间项任务的时间项任务的时间(shjin)(shjin)(shjin)(shjin)如下表所示，由于任务重，人手少，考虑以下如下表所示，由于任务重，人手少，考虑以下如下表所示，由于任务重，人手少，考虑以下如下表所示，由于任务重，人手少，考虑以下两种情况下的最优分配方案，使得完成任务的总时间两种情况下的最优分配方案，使得完成任务的总时间两种情况下的最优分配方案，使得完成任务的总时间两种情况下的最优分配方案，使得完成任务的总时间(shjin)(shjin)(shjin)(shjin)最少。最少。最少。最少。(1)(1)(1)(1)任务任务任务任务E E E E必须完成，其他必须完成，其他必须完成，其他必须完成，其他4 4 4 4项任务可选项任务可选项任务可选项任务可选3 3 3 3项完成，但甲不能做项完成，但甲不能做项完成，但甲不能做项完成，但甲不能做A A A A项工作；项工作；项工作；项工作；(2)(2)(2)(2)其中有一人完成其中有一人完成其中有一人完成其中有一人完成2 2 2 2项，其他人每人完成项，其他人每人完成项，其他人每人完成项，其他人每人完成1 1 1 1项。项。项。项。解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处解：这是一人数与任务数不等的指派问题，若用匈牙利法求解，需作以下处理。理。理。理。指派(zhpi)问题第27页/共83页第二十七页，共83页。(1)(1)(1)(1)由于任务数大于人数，所以需要有一个由于任务数大于人数，所以需要有一个由于任务数大于人数，所以需要有一个由于任务数大于人数，所以需要有一个(y)(y)(y)(y)虚拟的人，设虚拟的人，设虚拟的人，设虚拟的人，设为戊。因为工作为戊。因为工作为戊。因为工作为戊。因为工作E E E E必须完成，故设戊完成必须完成，故设戊完成必须完成，故设戊完成必须完成，故设戊完成E E E E的时间为的时间为的时间为的时间为M(MM(MM(MM(M为非常为非常为非常为非常大的正数大的正数大的正数大的正数)，即戊不能做工作，即戊不能做工作，即戊不能做工作，即戊不能做工作E E E E，其余的假想时间为，其余的假想时间为，其余的假想时间为，其余的假想时间为0 0 0 0，建立，建立，建立，建立的效率矩阵为：的效率矩阵为：的效率矩阵为：的效率矩阵为：采用匈牙利解法求解过程如下：采用匈牙利解法求解过程如下：采用匈牙利解法求解过程如下：采用匈牙利解法求解过程如下：指派(zhpi)问题第28页/共83页第二十八页，共83页。(1)(1)(1)(1)由于由于由于由于r=4r=4r=4r=4矩阵阶数矩阵阶数矩阵阶数矩阵阶数=5=5=5=5，需要调整，需要调整，需要调整，需要调整0 0 0 0元素元素元素元素(yun s)(yun s)(yun s)(yun s)的分布。的分布。的分布。的分布。从该矩阵可看出，从该矩阵可看出，从该矩阵可看出，从该矩阵可看出，r=5=r=5=r=5=r=5=矩阵阶数，因此能找到最优指派方案。矩阵阶数，因此能找到最优指派方案。矩阵阶数，因此能找到最优指派方案。矩阵阶数，因此能找到最优指派方案。甲甲甲甲-B-B-B-B 乙乙乙乙-D-D-D-D 丙丙丙丙-E-E-E-E 丁丁丁丁-A-A-A-A 戊戊戊戊-C-C-C-C（戊（戊（戊（戊 为虚拟人，即任务为虚拟人，即任务为虚拟人，即任务为虚拟人，即任务C C C C无人完成）无人完成）无人完成）无人完成）最少的耗时数最少的耗时数最少的耗时数最少的耗时数 z=29+20+32+24=105 z=29+20+32+24=105 z=29+20+32+24=105 z=29+20+32+24=105 指派(zhpi)问题第29页/共83页第二十九页，共83页。(2)(2)(2)(2)思路：思路：思路：思路：方案方案方案方案1 1 1 1：甲，【甲】，乙，丙，丁：甲，【甲】，乙，丙，丁：甲，【甲】，乙，丙，丁：甲，【甲】，乙，丙，丁方案方案方案方案2 2 2 2：甲，乙，【乙】，丙，丁：甲，乙，【乙】，丙，丁：甲，乙，【乙】，丙，丁：甲，乙，【乙】，丙，丁方案方案方案方案3 3 3 3：甲，乙，丙，【丙】，丁：甲，乙，丙，【丙】，丁：甲，乙，丙，【丙】，丁：甲，乙，丙，【丙】，丁方案方案方案方案4 4 4 4：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】：甲，乙，丙，丁，【丁】方案方案方案方案5 5 5 5：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作：甲，【甲】，乙，【乙】，丙，【丙】，丁，【丁】，工作(gngzu)A(gngzu)A(gngzu)A(gngzu)A，B B B B，C C C C，D D D D，E E E E，虚拟工作，虚拟工作，虚拟工作，虚拟工作(gngzu)F(gngzu)F(gngzu)F(gngzu)F，G G G G，H H H H。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。这些方案较烦琐，采用以下思路更为简便。设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做设有虚拟人戊，他集五人的优势为一身，即戊的费用是每人的最低，戊所做的工作的工作的工作的工作(gngzu)(gngzu)(gngzu)(gngzu)即为此项工作即为此项工作即为此项工作即为此项工作(gngzu)(gngzu)(gngzu)(gngzu)的费用最低者的工作的费用最低者的工作的费用最低者的工作的费用最低者的工作(gngzu)(gngzu)(gngzu)(gngzu)，效率矩阵分配表为：，效率矩阵分配表为：，效率矩阵分配表为：，效率矩阵分配表为：指派(zhpi)问题第30页/共83页第三十页，共83页。采用匈牙利解法求解：采用匈牙利解法求解：采用匈牙利解法求解：采用匈牙利解法求解：对对对对C3C3C3C3做做做做0 0 0 0元素的最小直线元素的最小直线元素的最小直线元素的最小直线(zhxin)(zhxin)(zhxin)(zhxin)覆盖，得覆盖，得覆盖，得覆盖，得r=5=nr=5=nr=5=nr=5=n。结果为。结果为。结果为。结果为 甲甲甲甲-B-B-B-B 乙乙乙乙-D-D-D-D 丙丙丙丙-E-E-E-E 丁丁丁丁-A-A-A-A 戊戊戊戊-C-C-C-C 但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做但戊为虚拟人，不能真做，它做C C C C工作是借乙工作是借乙工作是借乙工作是借乙(此列最小时数此列最小时数此列最小时数此列最小时数26262626是是是是C C C C所创业所创业所创业所创业绩绩绩绩)的优势，应由乙来做，即乙做两件工作：的优势，应由乙来做，即乙做两件工作：的优势，应由乙来做，即乙做两件工作：的优势，应由乙来做，即乙做两件工作：D D D D、C C C C。指派(zhpi)问题第31页/共83页第三十一页，共83页。例例例例 最大收益的最优分配问题：有最大收益的最优分配问题：有最大收益的最优分配问题：有最大收益的最优分配问题：有5 5 5 5名工人完成名工人完成名工人完成名工人完成5 5 5 5项不同的任务收项不同的任务收项不同的任务收项不同的任务收 益如表所示：益如表所示：益如表所示：益如表所示：求使总收益达到最高的任务分配方案。求使总收益达到最高的任务分配方案。求使总收益达到最高的任务分配方案。求使总收益达到最高的任务分配方案。解：这是一个解：这是一个解：这是一个解：这是一个(y)(y)(y)(y)寻求总收益为最大值的极大化问题，需要转化为极小寻求总收益为最大值的极大化问题，需要转化为极小寻求总收益为最大值的极大化问题，需要转化为极小寻求总收益为最大值的极大化问题，需要转化为极小化问题才能用匈牙利解法。化问题才能用匈牙利解法。化问题才能用匈牙利解法。化问题才能用匈牙利解法。收益矩阵收益矩阵收益矩阵收益矩阵B=B=B=B=（bijbijbijbij），设），设），设），设b=maxbijb=maxbijb=maxbijb=maxbij，令，令，令，令cij=b-bij cij=b-bij cij=b-bij cij=b-bij，C=C=C=C=（cijcijcijcij），以），以），以），以C C C C为为为为效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。效率矩阵的极小化问题即是原最大收益的极大化问题转化而来。指派(zhpi)问题第32页/共83页第三十二页，共83页。b=maxbij=19b=maxbij=19b=maxbij=19b=maxbij=19，令，令，令，令cij=19-bij cij=19-bij cij=19-bij cij=19-bij，C=C=C=C=（cijcijcijcij），），），），继续对继续对继续对继续对C C C C矩阵采用匈牙利法求解，得到矩阵采用匈牙利法求解，得到矩阵采用匈牙利法求解，得到矩阵采用匈牙利法求解，得到C C C C的最优分配方案的最优分配方案的最优分配方案的最优分配方案(fng n)(fng n)(fng n)(fng n)为为为为即即即即 甲甲甲甲-D-D-D-D 乙乙乙乙-B-B-B-B 丙丙丙丙-E-E-E-E 丁丁丁丁-A-A-A-A 戊戊戊戊-C-C-C-C，求得的最大总收益为，求得的最大总收益为，求得的最大总收益为，求得的最大总收益为74.74.74.74.指派(zhpi)问题第33页/共83页第三十三页，共83页。237184566134105275934682网络(wnglu)优化最短路径问题：有一批货物要从节点1运送到节点8，这两点间的通路如下图，每条弧旁边(pngbin)的数字表明该弧的长度。总路径越短，运费越低，为节省运输费用，应该选择怎样的运输路线？求从1到8的最短路径(ljng)。第34页/共83页第三十四页，共83页。237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,w4=1w1=0w1=0第35页/共83页第三十五页，共83页。237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,w2=2w1=0w4=1w2=2第36页/共83页第三十六页，共83页。237184566134105275934682X=1,2,4min c16,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,w6=3w2=2w4=1w1=0w6=3第37页/共83页第三十七页，共83页。237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,w7=3w2=2w4=1w1=0w6=3w7=3第38页/共8