运筹学运输问题.pptx

运筹学运筹学OperationsResearchChapter5运输问题运输问题TransportationProblem5.1运输问题的数学模型运输问题的数学模型及其特征及其特征5.2运输单纯形法运输单纯形法5.3运输模型的应用运输模型的应用5.1运输问题的数学模型及其特征运输问题的数学模型及其特征MathematicalModelofTransportationProblems人们在从事生产活动中，不人们在从事生产活动中，不可避免地要进行物资调运工可避免地要进行物资调运工作。如某时期内将生产基地作。如某时期内将生产基地的煤、钢铁、粮食等各类物的煤、钢铁、粮食等各类物资，分别运到需要这些物资资，分别运到需要这些物资的地区，根据各地的的地区，根据各地的生产量生产量和和需要量需要量及各地之间的及各地之间的运输运输费用费用，如何制定一个运输方，如何制定一个运输方案，使总的运输费用最小。案，使总的运输费用最小。这样的问题称为这样的问题称为运输问题运输问题。5.1运输模型运输模型ModelofTransportationProblems5.1.1数学模型数学模型产地销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5354231682329图图5.1【例例5-1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应粮食分别为粮食分别为10，8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/吨）如表吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用所示，问如何安排一个运输计划，使总的运输费用最少。最少。需求地需求地产粮地产粮地B1B2B3B4供给量供给量A1326310A253828A341295需求量需求量578323运价表（元运价表（元/吨）吨）表表5-15.1运输模型运输模型ModelofTransportationProblems设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运量，个需求地的运量，这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即5.1运输模型运输模型ModelofTransportationProblems5.1运输模型运输模型ModelofTransportationProblems有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型看一个例子：看一个例子：【例例5-2】有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务台的生产任务为为a i(i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i台台机床加工第机床加工第j种零件需要的时间为种零件需要的时间为cij，如表，如表52所示。问如何安所示。问如何安排生产任务使总的加工时间最少？排生产任务使总的加工时间最少？零件零件机床机床B1B2B3生产任务生产任务A152350A264160A373440需要量需要量703050150表表525.1运输模型运输模型ModelofTransportationProblems【解解】设设xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的种零件的数量，则此问题的数学模型为数量，则此问题的数学模型为5.1运输模型运输模型ModelofTransportationProblems5.1.2模型特征模型特征运输问题的一般数学模型运输问题的一般数学模型设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其产量分别为量分别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且产销平衡，即；且产销平衡，即。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij，在满足各地需要的前提，在满足各地需要的前提下，求总运输费用最小的调运方案。下，求总运输费用最小的调运方案。5.1运输模型运输模型ModelofTransportationProblems 销地产地产量销量设设xij(i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运量，个销地的运量，则数学模型为：则数学模型为：5.1运输模型运输模型ModelofTransportationProblemsm 行行n 行行5.1运输模型运输模型ModelofTransportationProblems运输问题具有如下特点运输问题具有如下特点:1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解3.有有m+n个约束，个约束，mn个变量个变量4.约束条件系数矩阵的元素等于约束条件系数矩阵的元素等于0或或15.约束条件系数矩阵的每一列有两个非零元素约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前这对应于每一个变量在前m个约束方程中出现一次个约束方程中出现一次,在后在后n个约束方程中也出现一次个约束方程中也出现一次6.所有约束方程都是等式方程所有约束方程都是等式方程7.各产地产量之和等于各销地销量之和各产地产量之和等于各销地销量之和8.有有m+n1个基变量个基变量,因为产销平衡因为产销平衡,所以模型最多只有所以模型最多只有m+n-1个独立约个独立约束方程束方程,即系数矩阵的秩最多为即系数矩阵的秩最多为m+n-1.5.2运输单纯形法运输单纯形法TransportationSimplexMethod设平衡运输问题的数学模型为：设平衡运输问题的数学模型为：5.2运输单纯形法运输单纯形法TransportationSimplexMethod运运输输单单纯纯形形法法也也称称为为表表上上作作业业法法，是是直直接接在在运运价价表表上上求求最最优优解解的的一种方法，它的步骤是：一种方法，它的步骤是：第第一一步步：求求初初始始基基本本可可行行解解（初初始始调调运运方方案案）。常常用用的的方方法法有有最小元素法、元素差额法（最小元素法、元素差额法（Vogel近似法）、左上角法。近似法）、左上角法。第第二二步步：求求检检验验数数并并判判断断是是否否得得到到最最优优解解。常常用用求求检检验验的的方方法法有有闭闭回回路路法法和和位位势势法法，当当非非基基变变量量的的检检验验数数ij全全都都非非负负时时得得到到最最优解，若存在检验数优解，若存在检验数lk0，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。第第三三步步：调调整整运运量量，即即换换基基。选选一一个个变变量量出出基基，对对原原运运量量进进行行调整得到新的基可行解，转入第二步。调整得到新的基可行解，转入第二步。5.2运输单纯形法运输单纯形法TransportationSimplexMethod5.2.1初始基可行解初始基可行解1.最最小小元元素素法法最最小小元元素素法法的的思思想想是是就就近近优优先先运运送送，即即最最小小运运价价Cij对应的变量对应的变量xij优先赋值优先赋值然然后后再再在在剩剩下下的的运运价价中中取取最最小小运运价价对对应应的的变变量量赋赋值值并并满满足足约约束束，依次下去，直到最后得到一个初始基可行解。依次下去，直到最后得到一个初始基可行解。5.2运输单纯形法运输单纯形法TransportationSimplexMethod【例例5-3】求表求表56所示的运输问题的初始基可行解。所示的运输问题的初始基可行解。表表56销销地地产地产地B1B2B3B4产量产量A1A2A39723610859412705020销销量量106040301405.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4产产量量A1938470A2765 150A32109 220销销量量10604030140表表5759【解解】301010605.2运输单纯形法运输单纯形法TransportationSimplexMethod2010到一组基可行解可用矩阵到一组基可行解可用矩阵表示，矩阵表示，矩阵X 中空白处对应的变量是非基变量，运量等于零，中空白处对应的变量是非基变量，运量等于零，这组解就是初始调运方案总运费这组解就是初始调运方案总运费Z=360+810+520+130+210+910=5005.1运输模型运输模型ModelofTransportationProblems【例例5-4】求表求表5-10给出的运输问题的初始基本可行解给出的运输问题的初始基本可行解B1B2B3B4aiA14104420A2773815A31210615bj510251050表表5-105.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-11BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解解】51001510105.2运输单纯形法运输单纯形法TransportationSimplexMethod初始基本可行解可用下列矩阵表示初始基本可行解可用下列矩阵表示5.2运输单纯形法运输单纯形法TransportationSimplexMethod2元元素素差差额额法法（Vogel近近似似法法）最最小小元元素素法法只只考考虑虑了了局局部部运运输输费费用用最最小小。有有时时为为了了节节省省某某一一处处的的运运费费，而而在在其其它它处处可可能能运运费费很很大大。元元素素差差额额法法对对最最小小元元素素法法进进行行了了改改进进，考考虑虑到到产产地地到到销销地地的的最最小小运运价价和和次次小小运运价价之之间间的的差差额额，如如果果差差额额很很大大，就就选选最最小小运运价价先先调调运，否则会增加总运费。例如下面两种运输方案运，否则会增加总运费。例如下面两种运输方案前一种按最小元素法求得，总运费是前一种按最小元素法求得，总运费是Z1=108+52+151=105后后一一种种方方案案考考虑虑到到C11与与C21之之间间的的差差额额是是82=6，先先调调运运x21，再是再是x22，其次是，其次是x12这时总运费这时总运费Z2=105+152+51=85Z1。5.2运输单纯形法运输单纯形法TransportationSimplexMethod基于以上思路，元素差额法求初始基本可行解的步骤是：基于以上思路，元素差额法求初始基本可行解的步骤是：第第一一步步：求求出出每每行行次次小小运运价价与与最最小小运运价价之之差差，记记为为ui，i=1,2,m；同同时时求求出出每每列列次次小小运运价价与与最最小小运运价价之之差差，记记为为vj，j=1，2，n；第第二二步步：找找出出所所有有行行、列列差差额额的的最最大大值值，即即L=maxui，vi，差差额额L对应行或列的最小运价处优先调运；对应行或列的最小运价处优先调运；第第三三步步：这这时时必必有有一一列列或或一一行行调调运运完完毕毕，在在剩剩下下的的运运价价中中再再求求最最大大差差额额，进进行行第第二二次次调调运运，依依次次进进行行下下去去，直直到到最最后后全全部部调调运运完毕，就得到一个初始调运方案。完毕，就得到一个初始调运方案。用用元元素素差差额额法法求求得得的的基基本本可可行行解解更更接接近近最最优优解解，所所以以也也称称为为近近似方案。似方案。5.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-6【例例5-5】用元素差额法求表用元素差额法求表56运输问题的初始基本可行解。运输问题的初始基本可行解。【解解】求行差额求行差额ui,i=1,2,3及列差额及列差额vj,j=1,2,3,4.计算公式为计算公式为ui=i行次小运价行次小运价i行最小运价行最小运价vj=j列次小运价列次小运价j例最小运价例最小运价5.2运输单纯形法运输单纯形法TransportationSimplexMethod销销地地产地产地B1B2B3B4产量产量A1A2A39723610859412705020销销量量10604030140表表512BjAiB1B2B3B4aiuiA19384701A27651504A321092207bj10604030140vj5331【0】105.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-13105.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiuiA19384701A27651504A32109220710bj10604030140vj331【】5.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiuiA19384701A27651504A321092201010bj10604030140vj333表表5-14【】20表表5-15【】6030105.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiuiA19384705A2765150120A321092201010bj10604030140vj33基本可行解为基本可行解为总运费总运费Z=360+810530+120+210+210=470比最小元素法的总运费（比最小元素法的总运费（500）要小）要小305.2运输单纯形法运输单纯形法TransportationSimplexMethod3.左上角法左上角法。左上角法。左上角法(亦称西北角法亦称西北角法)是优先从运价表的左上角的是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同时分配完一值，依次类推，直到右下角元素分配完毕当出现同时分配完一行和一列时，仍然应在打行和一列时，仍然应在打“”的位置上选一个变量作基变量，的位置上选一个变量作基变量，以保证最后的基变量数等于以保证最后的基变量数等于m+n1【例例5-6】用左上角法求例用左上角法求例5-3中表中表5-6的初始基本可行解的初始基本可行解表表5-161060010205.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4产产量量A1938470A2765 150A32109 220销销量量1060403040基本可行解为基本可行解为用左上角法求得的基本可行解对应的目标函数值（总运费）是用左上角法求得的基本可行解对应的目标函数值（总运费）是Z91036080540110+220=520求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输输问问题题的的最最优优判别准则是：判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。求检验数的方法有两种，闭回路法和位势法。1闭闭回回路路法法求求检检验验数数求求某某一一非非基基变变量量的的检检验验数数的的方方法法是是：在在单单位位运运价价表表中中，以以该该非非基基变变量量为为起起点点，以以基基变变量量为为其其它它顶顶点点，找找一一条条闭闭回回路路，由由起起点点开开始始，分分别别在在顶顶点点上上交交替替标标上上+1、-1、+1、-1、，分分别别乘乘以以相相应应的的运运价价，其其代代数数和和就就是是这这个个非非基基变变量量的的检检验验数。数。5.2运输单纯形法运输单纯形法TransportationSimplexMethod5.2.2求检验数求检验数【解解】用最小元素法用最小元素法求得的初始基可行解求得的初始基可行解【例例5-7】用闭回路法求例用闭回路法求例53表表59的检验数。的检验数。5.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4产产量量A1938470A2765 150A32109 220销销量量10604030140301010602010矩矩阵阵中中打打“”的的位位置置是是非非基基变变量量，其其余余是是基基变变量量，这这里里只只求求非基变量的检验数。非基变量的检验数。求求11，先找出，先找出x11的闭回路的闭回路，对应的运价为，对应的运价为再用正负再用正负1分别交替乘以运价有分别交替乘以运价有直接求代数和得直接求代数和得5.2运输单纯形法运输单纯形法TransportationSimplexMethodBjAiB1B2B3B4aiA19384708(+1)6010(-1)0A2765150962030A3210922010(-1)610(+1)-3bj106040305.2运输单纯形法运输单纯形法TransportationSimplexMethod同理可求出其它非基变量的检验数：同理可求出其它非基变量的检验数：这里这里340，说明这组基本可行解不是最优解。，说明这组基本可行解不是最优解。只只要要求求得得的的基基变变量量是是正正确确的的且且数数目目为为m+n1，则则某某个个非非基基变变量量的的闭回路存在且唯一，因而检验数唯一。闭回路存在且唯一，因而检验数唯一。5.2运输单纯形法运输单纯形法TransportationSimplexMethod2位位势势法法求求检检验验位位势势法法求求检检验验数数是是根根据据对对偶偶理理论论推推导导出出来来的的一一种方法。种方法。设平衡运输问题为设平衡运输问题为设设前前m个个约约束束对对应应的的对对偶偶变变量量为为ui,i=1,2,m，后后n个个约约束束对对应应的的对对偶变量为偶变量为vj,j=1,2,n则运输问题的对偶问题是则运输问题的对偶问题是5.2运输单纯形法运输单纯形法TransportationSimplexMethodm 行行n 行行5.1运输模型运输模型ModelofTransportationProblemsu1umv1vn加入松驰变量加入松驰变量ij将约束化为等式将约束化为等式ui+vj+ij=cij记记原原问问题题基基变变量量XB的的下下标标集集合合为为I，由由第第二二章章对对偶偶性性质质知知，原原问问题题xij的的检检验验数数是是对对偶偶问问题题的的松松弛弛变变量量ij，当当（i，j）I时时ij=0，因因而而有有解上面第一个方程，将解上面第一个方程，将ui、vj代入第二个方程求出代入第二个方程求出ij5.2运输单纯形法运输单纯形法TransportationSimplexMethod【例例5-8】用位势法求例用位势法求例5-3表表59给出的初始基本可行解的检验数。给出的初始基本可行解的检验数。【解解】第一步求位势第一步求位势u1、u2、u3及及v1、v2、v3、v4。10604030令令u1=0得到位势的解为得到位势的解为5.2运输单纯形法运输单纯形法TransportationSimplexMethod再再由由公公式式求求出出检检验验数数，其其中中Cij是是非非基变量对应的运价。基变量对应的运价。计算结果与例计算结果与例5-7结果相同。结果相同。5.2运输单纯形法运输单纯形法TransportationSimplexMethod 销地产地B1B2B3B4产量uiA19 83 608 1040 700A279665 201 3050-3A32 101069 102-3 91销量10604030140(产销平衡vj13845.2.3调整运量调整运量前前面面讲讲过过，当当某某个个检检验验数数小小于于零零时时，基基可可行行解解不不是是最最优优解解，总总运运费费还还可可以以下下降降，这这时时需需调调整整运运输输量量，改改进进原原运运输输方方案案，使使总总运费减少，改进运输方案的步骤是：运费减少，改进运输方案的步骤是：第一步：确定进基变量第一步：确定进基变量第第二二步步：确确定定出出基基变变量量在在进进基基变变量量xik的的闭闭回回路路中中，标标有有负负号号的的最最小小运运量量作作为为调调整整量量，对对应应的的基基变变量量为为出出基基变变量量，并并打打上上“”以示作为非基变量。以示作为非基变量。第第三三步步：调调整整运运量量在在进进基基变变量量的的闭闭回回路路中中标标有有正正号号的的变变量量加加上上调调整整量量，标标有有负负号号的的变变量量减减去去调调整整量量，其其余余变变量量不不变变，得得到到一一组新的基可行解，然后求所有非基变量的检验数重新检验。组新的基可行解，然后求所有非基变量的检验数重新检验。5.2运输单纯形法运输单纯形法TransportationSimplexMethod 销地产地B1B2B3B4产量uiA19 83 608 1040 700A2796 65 20([phone]A32 101069 10(-1)2-3(+1)91销量10604030140(产销平衡vj13845.2运输单纯形法运输单纯形法TransportationSimplexMethod因因为为有有一一个个检检验验数数小小于于零零，所所以以这这组组基基本本可可行行解解不不是是最最优解。对应的非基变量优解。对应的非基变量x34进基进基.x34的闭回路是的闭回路是x33最小，最小，x33是出基量，调整量是出基量，调整量=105.2运输单纯形法运输单纯形法TransportationSimplexMethod在在x34的闭回路上的闭回路上x34、x23分别加上分别加上10，x33、x24分别减分别减去去10，其余变量不变，调整后得到一组新的基可行解：，其余变量不变，调整后得到一组新的基可行解：销地产地B1B2B3B4产量uiA1953 608 1040 700A2766 65 301 2050-3A32 101099 32109-2销量10604030140(产销平衡vj4384非基变量的检验数：非基变量的检验数：11=5，14=0，21=6，22=6，32=9，33=3所有检验数所有检验数ij0因而得到最优解因而得到最优解最小运费最小运费5.2运输单纯形法运输单纯形法TransportationSimplexMethod 销地产地B1B2B3B4产量uiA1953 608 10(-1)40(+1)700A2766 6530([phone]A32 101099 32109-2销量10604030140(产销平衡vj43845.2运输单纯形法运输单纯形法TransportationSimplexMethod 销地产地B1B2B3B4产量uiA1953 608 0410 700A2766 65401 1050-3A32 101099 32109-2销量10604030140(产销平衡vj43845.2运输单纯形法运输单纯形法TransportationSimplexMethod5.2运输单纯形法运输单纯形法TransportationSimplexMethod当总产量与总销量不相等时当总产量与总销量不相等时,称为不平衡运输问题称为不平衡运输问题.这类运输问题在这类运输问题在实际中常常碰到实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。衡问题求解。1.当产大于销时当产大于销时,即即数学模型为数学模型为5.2.5不平衡运输问题不平衡运输问题5.2运输单纯形法运输单纯形法TransportationSimplexMethod由于总产量大于总销量，必有部分产地的产量不能全部由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，库存量运送完，必须就地库存，即每个产地设一个仓库，库存量为为xi，n+1（i=1，2，m），总的库存量为），总的库存量为5.2运输单纯形法运输单纯形法TransportationSimplexMethodbn+1作为一个虚设的销地作为一个虚设的销地Bn+1的销量。各产地的销量。各产地Ai到到Bn+1的运价为零，的运价为零，即即Ci，n+1=0,（i=1，m）。则平衡问题的数学模型为：）。则平衡问题的数学模型为：具体求解时具体求解时,只在运价表右端增加一列只在运价表右端增加一列Bn+1，运价为零，运价为零,销量为销量为bn+1即可即可5.2运输单纯形法运输单纯形法TransportationSimplexMethod2.当销大于产时当销大于产时,即即数学模型为数学模型为5.2运输单纯形法运输单纯形法TransportationSimplexMethod由于总销量大于总产量由于总销量大于总产量,故一定有些需求地不完全满足故一定有些需求地不完全满足,这时虚设这时虚设一个产地一个产地Am+1，产量为，产量为xm+1,j是是Am+1运到运到Bj的运量，也是的运量，也是Bj不能满足需要的数量。不能满足需要的数量。Am+1到到Bj的运价为零的运价为零,即即Cm+1,j=0(j=1,2,n)5.2运输单纯形法运输单纯形法TransportationSimplexMethod销大于产平衡问题的数学模型为销大于产平衡问题的数学模型为：具体计算时，在运价表的下方增加一行具体计算时，在运价表的下方增加一行Am+1，运价为零。产，运价为零。产量为量为am+1即可。即可。5.2运输单纯形法运输单纯形法TransportationSimplexMethodB1B2B3B4aiA1592360A2-47840A3364230A448101150bj20603545180160因为有因为有：【例例5-11】求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。所以是一个产大于销的运输问题。所以是一个产大于销的运输问题。5.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-21表中表中A2不可达不可达B1，用一个很大的正数，用一个很大的正数M表示运价表示运价C21。虚设一个。虚设一个销量为销量为b5=180160=20的销地的销地B5，Ci5=0，i=1，2，3，4。表的。表的右边增添一列右边增添一列这样可得新的运价表：这样可得新的运价表：B1B2B3B4B5aiA15923060A2M478040A33642030A4481011050bj20603545201805.2运输单纯形法运输单纯形法TransportationSimplexMethodB1B2B3B4B5AiA1352560A24040A3102030A420102050Bj2060354520180下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没有运个单位没有运出。出。5.2运输单纯形法运输单纯形法TransportationSimplexMethod【例例5-12】在例在例5-11中，假定中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需的需要量是要量是50到到70，试求极小化问题的最优解。，试求极小化问题的最优解。B1B2B3B4aiA1592360A2-47840A3364230A448101150bj2060507035451801502105.2.6需求量不确定的运输问题需求量不确定的运输问题5.2运输单纯形法运输单纯形法TransportationSimplexMethod先作如下分析：先作如下分析：（1）总产量为）总产量为180，B1，B4的最低需求量的最低需求量20+50+35+45=150，这时属产大于销；，这时属产大于销；（2）B1，B4的最高需求是的最高需求是60+70+35+45=210，这时属销大于产，这时属销大于产（3）虚设一个产地）虚设一个产地A5，产量是，产量是210180=30，A5的产量只能供的产量只能供应应B1或或B2。（4）将）将B1与与B2各分成两部分各分成两部分的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此必须由必须由A1，A4供应，供应，可由可由A1、A5供应。供应。（5）上述）上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到、的的运价为零。得到下表的产销平衡表。运价为零。得到下表的产销平衡表。5.2运输单纯形法运输单纯形法TransportationSimplexMethodB3B4aiA155992360A2MM447840A333664230A44488101150A5M0M0MM30bj204050203545210得到这样的平衡表后，计算得到最优方案表得到这样的平衡表后，计算得到最优方案表5-23。5.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-22B3B4aiA1352560A24040A30102030A4203050A5102030bj204050203545210表表中中：x131=0是是基基变变量量,说说明明这这组组解解是是退退化化基基本本可可行行解解,空空格格处处的的变变量量是是非非基基变变量量。B1，B2，B3，B4实实际际收收到到产产品品数数量量分分别别是是50，50，35和和45个单位。个单位。5.2运输单纯形法运输单纯形法TransportationSimplexMethod表表5-235.2.7中转问题中转问题产地销地 A1 20 A2 30 A3 50 A9 20 A8 15 A7 20 A6 45354231682329图图5.2 A4 A522715中转地34135.2运输单纯形法运输单纯形法TransportationSimplexMethodA1A2A3A4A5A6A7A8A9aiA10MM2532MM120A2M0142MMMM130A3MM087MMM15150A4M3M03436M100A5MMMM0M129100A6MMMMM02MM100A7MMMMMM0MM100A8MMMMMMM03100A9MMMMMMMM0100bj100 100 100 100 100 145 120 115 1205.2运输单纯形法运输单纯形法TransportationSimplexMethod设设xij为为Ai到到Aj的运量，的运量，i，j=1，2，m+n+r则中转运输问题则中转运输问题的数学模型为的数学模型为产大于销时将式产大于销时将式(5-3a)改为改为“”约束，销大于产时将式约束，销大于产时将式(5-3c)改为改为“”约束约束5.2运输单纯形法运输单纯形法TransportationSimplexMethod5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4.15.4.1问题的提出与数学模型的提出与数学模型 指派指派问题也称分配也称分配问题,是一种特殊的整数是一种特殊的整数规划划问题,是是0-10-1整数整数线性性规划划问题.在生活中在生活中经常会遇到常会遇到这样的的问题,某某单位需要指派位需要指派m m个个人去完成人去完成m m项任任务,每个人只做一工作每个人只做一工作,同同时,每每项工作只由一个人完成工作只由一个人完成.由于各人的由于各人的专长不同不同,每个人完成各每个人完成各项任任务的效率也不同的效率也不同.于是于是产生了生了应指派哪一个人去完成哪一指派哪一个人去完成哪一项任任务,使完成使完成项任任务的的总效率最高效率最高(如所如所用的用的时间为最少最少)的的问题.这类问题为指派指派问题或分配或分配问题.5.4指派问题指派问题assignmentproblem引例引例 人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考人事部门欲安排四人到四个不同的岗位工作，每个岗位一个人经考核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总核四人在不同岗位的成绩（百分制）如下表所示，如何安排他们的工作使总成绩最好。成绩最好。工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁869080885.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem数学模型为：数学模型为：甲甲乙乙丙丙丁丁ABCD图图5.35.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblemB1B2B3B4B5A14871512A279171410A3691287A46714610A569121065.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem第六步第六步:回到第三步回到第三步,反复进行反复进行,一直到找到了最优分配方案一直到找到了最优分配方案.5.4指派问题指派问题assignmentproblem本本题的最的最优解解最最优分配方案分配方案为:让A1A1承建承建B3,A2B3,A2承建承建B2,A3B2,A3承建承建B1,A4B1,A4承建承建B4,A5B4,A5承建承建B5.B5.这样安排能使安排能使总的建造的建造费用最少用最少,为7+9+6+6+6=34(7+9+6+6+6=34(万万)5.4指派问题指派问题assignmentproblem三、非标准形式的指派问题三、非标准形式的指派问题5.4指派问题指派问题assignmentproblem 求引例的最优分配方案求引例的最优分配方案【解解】则则求此问题的最小值求解过程如下求此问题的最小值求解过程如下 最优分配方案是最优分配方案是：甲：甲分配到分配到B岗位；乙分配岗位；乙分配到到A岗位；丙分配到岗位；丙分配到D岗位；丁分配到岗位；丁分配到C岗位；岗位；总成绩为总成绩为357 工作工作人员人员ABCD甲甲85927390乙乙95877895丙丙82837990丁丁869080885.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem5.4指派问题指派问题assignmentproblem练习练习1：某汽车公司拟将四种新产品配置到四个工厂生产，四个：某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元工厂的单位产品成本（元/件）如下表所示求最优生产配置方件）如下表所示求最优生产配置方案案 产品产品1产品产品2产品产品3产品产品4工厂工厂15869180260工厂工厂27550150230工厂工厂36570170250工厂工厂48255200280解：问题求最小值。解：问题求最小值。第一步：找出