运输与指派问题.pptx

运筹学运筹学OperationsResearch第三讲第三讲运输与指派问题运输与指派问题实际工作中常碰到很多线性规划问题，由于他们约束实际工作中常碰到很多线性规划问题，由于他们约束条件变量的系数矩阵具有特殊的结构，很可能找到比单纯条件变量的系数矩阵具有特殊的结构，很可能找到比单纯形法更为简便的方法进行求解，从而可节约时间和费用形法更为简便的方法进行求解，从而可节约时间和费用,运输问题就是其中之一。运输问题的一般提法是运输问题就是其中之一。运输问题的一般提法是:某种物资某种物资有若干个产地和销地，若已知各产地地产量、各销地的销有若干个产地和销地，若已知各产地地产量、各销地的销量，以及各产地到各销地的单位运价量，以及各产地到各销地的单位运价(或运输距离或运输距离)，问应，问应如何组织调运才能使总运费如何组织调运才能使总运费(或总运输量或总运输量)最省？最省？【例例1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应粮食分别为粮食分别为10，8，5(万吨万吨)，现将粮食运往，现将粮食运往B1，B2，B3，B4四个地区，其需要量四个地区，其需要量分别为分别为5，7，8，3(万吨万吨)。产粮地到需求地的运价。产粮地到需求地的运价(元元/吨吨)如表如表1所示，问如何安排一个运输计划，使总的运输费用最少。所示，问如何安排一个运输计划，使总的运输费用最少。地区地区产粮区产粮区B1B2B3B4产量产量A1326310A253828A341295需要量需要量578323运价表运价表(元元/吨吨)表表1运输模型运输模型ModelofTransportationProblems设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运个需求地的运量，这样得到下列运输问题的数学模型：量，这样得到下列运输问题的数学模型：【解解】运输模型运输模型ModelofTransportationProblems【例例2】有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务为台的生产任务为a i(i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i 台机床台机床加工第加工第j 种零件需要的时间为种零件需要的时间为cij，如表，如表2所示。问如何安排生产所示。问如何安排生产任务使总的加工时间最少？任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表2运输模型运输模型ModelofTransportationProblems【解解】设设xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的数种零件的数量，则此问题的数学模型为量，则此问题的数学模型为运输模型运输模型ModelofTransportationProblems运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地生产某种物资个产地生产某种物资,记作记作A1,A2,A3,Am，其产量分别，其产量分别为为a1,a2,am；有；有n个销地个销地,记作记作B1，B2，Bn，其需要量分，其需要量分别为别为b1,b2,bn；且；且产销平衡产销平衡，即，即。从第。从第i个产地个产地到第到第j 个销地的单位运价为个销地的单位运价为cij，在满足各地需要的前提下，求总，在满足各地需要的前提下，求总运输费用最小的调运方案。运输费用最小的调运方案。设设xij(i=1,2,m；j=1,2,n)为第为第i 个产地到第个产地到第j个销地的运量，则数学模型为：个销地的运量，则数学模型为：运输模型运输模型ModelofTransportationProblems设平衡运输问题设平衡运输问题的数学模型为：的数学模型为：模型特征模型特征:1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解;2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解;3.有有m+n个约束个约束，mn个变量个变量;4.有有m+n1个基变量个基变量;运输模型运输模型ModelofTransportationProblems为为一一个个闭闭回回路路，集集合合中中的的变变量量称称为为回回路路的的顶顶点点，相相邻邻两两个个变变量量的连线为闭回路的边。的连线为闭回路的边。x25x23B1B2B3B4B5A1A2A3x35A4 x43x11 x12x31x42表表3表表3中闭回路的变量集合是中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有共有8个顶点，个顶点，这这8个顶点间用水平或垂直个顶点间用水平或垂直线段连接起来，组成一条线段连接起来，组成一条封闭的回路。封闭的回路。闭回路闭回路:运输模型运输模型ModelofTransportationProblemsx11x12x32x33x41B1B2B3A1A2A3A4x43表表4表表4中闭回路是中闭回路是注：注：(1)(1)一条回路中的顶点数一定是偶数，回路遇到顶点必须一条回路中的顶点数一定是偶数，回路遇到顶点必须转转9090度与另一顶点连接。度与另一顶点连接。(2)有些变量组本身不构成回路，但其可能包含回路，例如：有些变量组本身不构成回路，但其可能包含回路，例如：表表3中变量组中变量组不能组成一条闭不能组成一条闭回路，但回路，但A中包含有中包含有 闭回路闭回路运输模型运输模型ModelofTransportationProblems设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：运输单纯形法运输单纯形法TransportationSimplexMethod运输单纯形法基本思路：运输单纯形法基本思路：是是基可行解基可行解最优否最优否否否停停运运输输单单纯纯形形法法也也称称为为表表上上作作业业法法，是是直直接接在在运运价价表表上上求求最最优解的一种方法，它的步骤是：优解的一种方法，它的步骤是：Step1：求求初初始始基基可可行行解解(初初始始调调运运方方案案)。常常用用的的方方法法 有有最小元素法、元素差额法最小元素法、元素差额法(Vogel近似法近似法)、左上角法等。、左上角法等。Step2：求求检检验验数数并并判判断断是是否否得得到到最最优优解解。常常用用于于求求检检验验数数的的方方法法有有闭闭回回路路法法和和位位势势法法，当当非非基基变变量量的的检检验验数数ij全全都都非非负负时时得得到到最最优优解解，若若存存在在检检验验数数lk0，说说明明还还没没有有达达到到最最优优，转第三步。转第三步。Step3：调调整整运运量量，即即换换基基。选选一一个个变变量量出出基基，对对原原运运量量进行调整得到新的基可行解，转入第二步。进行调整得到新的基可行解，转入第二步。注注:表上作业法的条件是表上作业法的条件是产销平衡和运价非负。产销平衡和运价非负。运输单纯形法运输单纯形法TransportationSimplexMethod初始基可行解的确定初始基可行解的确定最最小小元元素素法法：最最小小元元素素法法的的思思想想是是就就近近优优先先运运送送，即即最最小小运运价价cij 对应的变量对应的变量xij 优先赋值优先赋值然然后后再再在在剩剩下下的的运运价价中中取取最最小小运运价价对对应应的的变变量量赋赋值值并并满满足足约约束束，依次下去，直到最后得到一个初始基可行解。依次下去，直到最后得到一个初始基可行解。【例例3】求表求表5所示的运输问题的初始基可行解。所示的运输问题的初始基可行解。表表5销销地地产地产地B1B2B3产产量量A1A2A3847634758304525销销量量603010100运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3产产量量A186730A243545A374825销销量量603010100表表6【解解】3015102520运输单纯形法运输单纯形法TransportationSimplexMethod【例例4】求表求表7给出的运输问题的初始基本可行解给出的运输问题的初始基本可行解B1B2B3B4aiA14104420A2773815A31210615bj510251050表表7运输单纯形法运输单纯形法TransportationSimplexMethod表表8BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解解】5100151010运输单纯形法运输单纯形法TransportationSimplexMethod初始基本可行解可用下列矩阵表示初始基本可行解可用下列矩阵表示表表8中，基变量恰好是中，基变量恰好是3+41=6个且不包含闭回路，个且不包含闭回路，是一组基变量，其余标有符号是一组基变量，其余标有符号的变量是非基变量的变量是非基变量运输单纯形法运输单纯形法TransportationSimplexMethod求求出出一一组组基基可可行行解解后后，判判断断其其是是否否最最优优，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij，由由第第一一章章知知，求求最最小小值值的的运运输输问问题题的的最最优优判判别准则是：别准则是：所有非基变量的检验数都非负，则运输方案最优所有非基变量的检验数都非负，则运输方案最优(即为最优解即为最优解)。求检验数的方法有两种，求检验数的方法有两种，闭回路法和位势法。闭回路法和位势法。1 1闭闭回回路路法法求求某某一一非非基基变变量量的的检检验验数数的的方方法法是是：在在基基本本可可行行解解矩矩阵阵中中，以以该该非非基基变变量量为为起起点点，以以基基变变量量为为其其它它顶顶点点，找找一一条条闭闭回回路路，由由起起点点开开始始，分分别别在在顶顶点点上上交交替替标标上上代代数数符符号号+、-、+、-、，以以这这些些符符号号分分别别乘乘以以相相应应的的运运价价，其其代代数数和和就就是是这这个个非非基基变量的检验数。变量的检验数。求检验数求检验数运输单纯形法运输单纯形法TransportationSimplexMethod【解解】用最小元素法得到下列一组基本可行解用最小元素法得到下列一组基本可行解【例例5】求求下下列列运运输输问问题题的的一一个个初初始始基基本本可可行行解解及及其其检检验验数数。矩矩阵阵中中的的元元素素为为运运价价Cij，矩矩阵阵右右边边的的元元素素为为产产量量ai，下下方方的的元元素为销量素为销量bj。运输单纯形法运输单纯形法TransportationSimplexMethod只求非基变量的检验数：只求非基变量的检验数：求求11，先找出，先找出x11的闭回路的闭回路，对应的运价为，对应的运价为再用正负号分别交替乘以运价有再用正负号分别交替乘以运价有直接求代数和得直接求代数和得运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA19384706010A27651502030A321092201010bj1060403080966-32 2位位势势法法求求检检验验数数:位位势势法法求求检检验验数数是是根根据据对对偶偶理理论论推推导导出出来来的的一种方法。一种方法。设平衡运输问题为设平衡运输问题为设设前前m个个约约束束对对应应的的对对偶偶变变量量为为ui(i=1,2,m)，后后n个个约约束束对对应的对偶变量为应的对偶变量为vj(j=1,2,n),则运输问题的对偶问题是则运输问题的对偶问题是运输单纯形法运输单纯形法TransportationSimplexMethod加入松驰变量加入松驰变量ij将约束化为等式将约束化为等式:ui+vj+ij=cij记记原原问问题题基基变变量量XB的的下下标标集集为为I，由由第第二二章章对对偶偶性性质质知知，原原问问题题xij的的检检验验数数的的相相反反数数是是对对偶偶问问题题的的松松弛弛变变量量ij，当当（i，j）I时时ij=0，因而有，因而有解上面第一个方程，将解上面第一个方程，将ui、vj 代入第二个方程求出代入第二个方程求出ij运输单纯形法运输单纯形法TransportationSimplexMethod【例例6】用位势法求例用位势法求例7给出的初始基本可行解的检验数。给出的初始基本可行解的检验数。【解解】第一步求位势第一步求位势u1、u2、u3及及v1、v2、v3、v4。10604030令令u1=0得到位势的解为得到位势的解为运输单纯形法运输单纯形法TransportationSimplexMethod再再由由公公式式求求出出检检验验数数，其其中中cij是是非非基变量对应的运价。基变量对应的运价。计算结果与例计算结果与例7结果相同。结果相同。运输单纯形法运输单纯形法TransportationSimplexMethod用位势法求检验数通常可直接在表上进行计算：例如用位势法求检验数通常可直接在表上进行计算：例如BjAiB1B2B3B4uiA193846010A276512030A3210921010vj308-341189660-3运输单纯形法运输单纯形法TransportationSimplexMethod调整运量调整运量当当某某个个检检验验数数小小于于零零时时，基基可可行行解解不不是是最最优优解解，总总运运费费还还可可以以下下降降，这这时时需需调调整整运运输输量量，改改进进原原运运输输方方案案，使使总总运运费费减减少少，改进运输方案的改进运输方案的步骤步骤是：是：第一步：确定进基变量第一步：确定进基变量:第第二二步步：确确定定出出基基变变量量:在在进进基基变变量量xik的的闭闭回回路路中中，标标有有负负号号的的最最小小运运量量作作为为调调整整量量，对对应应的的基基变变量量为为出出基基变变量量，并并打打上上“”以示作为非基变量。以示作为非基变量。第第三三步步：调调整整运运量量:在在进进基基变变量量的的闭闭回回路路中中标标有有正正号号的的变变量量加加上上调调整整量量，标标有有负负号号的的变变量量减减去去调调整整量量，其其余余变变量量不不变变，得得到到一一组新的基可行解，然后求所有非基变量的检验数重新检验。组新的基可行解，然后求所有非基变量的检验数重新检验。运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190【例例7】求下列运输问题的最优解求下列运输问题的最优解表表95.2运输单纯形法运输单纯形法TransportationSimplexMethod【解解】用最小元素法求得初始基本可行解如表用最小元素法求得初始基本可行解如表9用用 闭闭 回回 路路法法 求求 非非 基基变变 量量 的的 检检验数验数得：得：BjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190+_+_+_运输单纯形法运输单纯形法TransportationSimplexMethod因因为为有有4个个检检验验数数小小于于零零，所所以以这这组组基基本本可可行行解解不不是是最最优优解解。对对应应的的非非 基基 变变 量量 x11进基进基.对应的非基变量对应的非基变量x11进基进基.x11的闭回路是的闭回路是x33最小，最小，x33是出基量，调整量是出基量，调整量=15BjAiB1B2B3B4aiA15892704030A23647804535A31012145402515bj45655030190+_+_+_BjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190在在x11的的闭闭回回路路上上x11、x32、x23分分别别加加上上15，x12、x33、x21分分别别减减去去15，并并且且在在x33处处打打上上记记号号“”作作为为非非基基变变量量，其其余余变变量量不不变，调整后得到一组新的基可行解：变，调整后得到一组新的基可行解：运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA1589270152530A23647803050A310121454040bj45655030190重新求所有非基变量的检验数得重新求所有非基变量的检验数得13=3，22=0，24=7，31=1，33=4，34=134=10,说明还没有得到最优解，说明还没有得到最优解，x34进基，在进基，在x34的闭回路中，的闭回路中，标负号的变量标负号的变量x14和和x32，调整量为，调整量为运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA15892701555A23647803050A31012145401030bj45655030190 x14出基，调整运量得到：出基，调整运量得到：再求非基变量的检验数：再求非基变量的检验数：13=3，14=1，22=0，24=8，31=1，33=4运输单纯形法运输单纯形法TransportationSimplexMethod再求非基变量的检验数：再求非基变量的检验数：13=3，14=1，22=0，24=8，31=1，33=4所有检验数所有检验数ij0因而得到最优解因而得到最优解最小运费最小运费运输单纯形法运输单纯形法TransportationSimplexMethod设数学模型为设数学模型为最大值问题最大值问题运输单纯形法运输单纯形法TransportationSimplexMethod方法一：方法一：将极大化问题转化为极小化问题。设极大化问题的运将极大化问题转化为极小化问题。设极大化问题的运价表为价表为C=（Cij）mn，用一个较大的数，用一个较大的数M（MmaxCij）去减每）去减每一个一个Cij得到矩阵得到矩阵C=（Cij）mn，其中，其中Cij=MCij0,将将C作为极作为极小化问题的运价表，用表上用业法求出最优解，目标函数值为小化问题的运价表，用表上用业法求出最优解，目标函数值为例例如如，下下列列矩矩阵阵C是是Ai（i=1，2，3）到到Bj的的吨吨公公里里利利润润,运运输输部部门如何安排运输方案使总利润最大门如何安排运输方案使总利润最大.8149运输单纯形法运输单纯形法TransportationSimplexMethod用最小元素法求初始方案得用最小元素法求初始方案得11=8,12=4,21=2,23=2全全部部非非负负,得得到到最最 优优 运运 输输 方方 案案 X,最最 大大 利利 润润Z=89+1010+68+54=240方方法法二二:所所有有非非基基变变量量的的检检验验数数ij0时时最最优优.求求初初始始运运输输方方案案可可采采用最大元素法用最大元素法.如上例如上例,用最大元素得到用最大元素得到的初始运输方案的初始运输方案:8149求求检检验验数数:11=8,12=4,21=2,23=2,全全部部非非正正,得得到到最最优优解解运输方案运输方案,结果与第一种方法相同结果与第一种方法相同.运输单纯形法运输单纯形法TransportationSimplexMethod当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问这类运输问题在实际中常常碰到题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。按平衡问题求解。1.1.当产大于销时当产大于销时,即即数学模型为数学模型为不平衡运输问题不平衡运输问题运输单纯形法运输单纯形法TransportationSimplexMethod由于总产量大于总销量，必有部分产地的产量不能全部运送由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量为完，必须就地库存，即每个产地设一个仓库，库存量为xi，n+1（i=1，2，m），总的库存量为），总的库存量为运输单纯形法运输单纯形法TransportationSimplexMethodbn+1作为一个虚设的销地作为一个虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，的运价为零，即即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：具体求解时具体求解时,只在只在运价表右端增加一列运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可运输单纯形法运输单纯形法TransportationSimplexMethod2.2.当销大于产时当销大于产时,即即数学模型为数学模型为运输单纯形法运输单纯形法TransportationSimplexMethod由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量为，产量为xm+1,j是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2,n)运输单纯形法运输单纯形法TransportationSimplexMethod销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。运输单纯形法运输单纯形法TransportationSimplexMethod指派问题指派问题assignmentproblem【例例8】人事部门欲安排四人到四个不同的岗位工作，每个岗位人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如下表所示，一个人经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。如何安排他们的工作使总成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088【解解】设设指派问题的数学模型指派问题的数学模型数学模型为：数学模型为：甲乙丙丁ABCD图图5.3指派问题指派问题assignmentproblem假设假设m个人恰好做个人恰好做m项工作，第项工作，第i个人做第个人做第j项工作的效率为项工作的效率为cij0，效率矩阵为效率矩阵为cij，如何分配工作使效率最佳，如何分配工作使效率最佳(min或或max)的数学模的数学模型为型为指派问题指派问题assignmentproblem解指派问题的匈牙利算法解指派问题的匈牙利算法匈牙利法的条件匈牙利法的条件：问题求：问题求最小值、人数与工作数相等及效率非负最小值、人数与工作数相等及效率非负【定理定理5.4】如果从分配问题效率矩阵如果从分配问题效率矩阵cij的每一行元素中分别减的每一行元素中分别减去去(或加上或加上)一个常数一个常数ui(被称为该行的位势被称为该行的位势)，从每一列分别减去，从每一列分别减去(或加上或加上)一个常数一个常数vj(称为该列的位势称为该列的位势)，得到一个新的效率矩阵，得到一个新的效率矩阵bij，其中，其中bij=cij ui vj,则则bij的最优解等价于的最优解等价于cij的最优解，这的最优解，这里里cij、bij均非负均非负【定理定理5.5】若矩阵若矩阵A的元素可分成的元素可分成“0”与非与非“0”两部分，则覆两部分，则覆盖盖“0”元素的元素的最少直线数等于位于不同行不同列的最少直线数等于位于不同行不同列的“0”元素元素(称称为独立元素为独立元素)的最大个数的最大个数如果最少直线数等于如果最少直线数等于m，则存在，则存在m个独立的个独立的“0”元素，令这些零元素，令这些零元素对应的元素对应的xij等于等于1，其余变量等于，其余变量等于0，这时目标函数值等于零，这时目标函数值等于零，得到最优解得到最优解指派问题指派问题assignmentproblem【例例9】某汽车公司拟将四种新产品配置到四个工厂生产，四个某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本工厂的单位产品成本(元元/件件)如下表所示求最优生产配置方案如下表所示求最优生产配置方案产品产品1产品产品2产品产品3产品产品4工厂工厂15869180260工厂工厂27550150230工厂工厂36570170250工厂工厂48255200280【解解】问题求最小值。问题求最小值。第一步：第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有小元素，有指派问题指派问题assignmentproblem第二步第二步：找出矩阵每列的最小元素，再分别从每列中减去，有：找出矩阵每列的最小元素，再分别从每列中减去，有指派问题指派问题assignmentproblem第三步第三步：用最少的直线覆盖所有：用最少的直线覆盖所有“0”，得，得第四步：第四步：这里直线数等于这里直线数等于3(等于等于4时停止时停止运算运算)，要进行下一轮计算从矩阵未被，要进行下一轮计算从矩阵未被直线覆盖的数字中找出一个最小数直线覆盖的数字中找出一个最小数k并且并且减去减去k，矩阵中，矩阵中k5直线相交处的元素直线相交处的元素加上加上k，被直线覆盖而没有相交的元素不，被直线覆盖而没有相交的元素不变，得到下列矩阵变，得到下列矩阵第四步等价于第第四步等价于第1、3行减去行减去5，同时第，同时第1列加上列加上5得到的结果得到的结果指派问题指派问题assignmentproblem第五步第五步：覆盖所有零最少需要：覆盖所有零最少需要4条直线，表明矩阵中存在条直线，表明矩阵中存在4个个不同行不同列的零元素容易看出不同行不同列的零元素容易看出4个个“0”的位置的位置()()()()或或()()()()指派问题指派问题assignmentproblem得到两个最优解得到两个最优解有两个最优方案有两个最优方案第一种方案第一种方案：第一个工厂加工产品：第一个工厂加工产品1，第二工厂加工产品，第二工厂加工产品3，第三个工厂加工产品第三个工厂加工产品4，第四个工厂加工产品，第四个工厂加工产品2；第二种方案第二种方案：第一个工厂加工产品：第一个工厂加工产品1，第二工厂加工产品，第二工厂加工产品4，第三个工厂加工产品第三个工厂加工产品3，第四个工厂加工产品，第四个工厂加工产品2；单件产品总成本单件产品总成本Z5815025055513指派问题指派问题assignmentproblem其它变异问题其它变异问题【例例10】求例求例8的最优分配方案的最优分配方案【解解】则求此问题的最小值求解过程如下求此问题的最小值求解过程如下最优分配方案是最优分配方案是：甲：甲分配到分配到B岗位；乙分配岗位；乙分配到到A岗位；丙分配到岗位；丙分配到D岗位；丁分配到岗位；丁分配到C岗位；岗位；总成绩为总成绩为357工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁86908088指派问题指派问题assignmentproblem