运筹学-第四章-运输与指派问题-第一讲-运输模型与运输单纯形法

运筹学OperationsResearchChapter4运输与指派问题Transportation

andAssignmentProblem4.1运输模型

MathematicalModelofTransportationProblems4.2运输单纯形法TransportationSimplexMethod4.3运输模型的应用

Applicationof

TransportationModel4.4

指派问题AssignmentProblem

4.1运输模型

MathematicalModelofTransportationProblems人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小,这样的问题称为运输问题。4.1运输模型

ModelofTransportationProblems4.1.1数学模型产地销地

A110

A2

8

A35

B43

B38

B27

B15354231682329图4.1【例4.1】现有A1，A2，A3三个产粮区，可供应粮食分别为10，8，5(万吨)，现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3(万吨)。产粮地到需求地的运价(元/吨)如表5－1所示，问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表(元/吨)表5－14.1运输模型

ModelofTransportationProblems4.1运输模型

ModelofTransportationProblems设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：

【解】注：有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型。【例4.2】有三台机床加工三种零件，计划第i台的生产任务为ai(i=1,2,3)个零件，第j种零件的需要量为bj

(j=1,2,3)，第i台机床加工第j种零件需要的时间为cij

，如表4－2所示。问如何安排生产任务使总的加工时间最少？零件机床B1B2B3生产任务A152350A264160A373440需要量703050150表4－24.1运输模型

ModelofTransportationProblems【解】设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为4.1运输模型

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个销地的运量，则数学模型为：4.1运输模型

ModelofTransportationProblems设平衡运输问题的数学模型为：4.1.2模型特征:4.1运输模型

ModelofTransportationProblems1.运输问题存在可行解，也一定存在最优解;

2.当供应量和需求量都是整数时，则一定存在整数最优解;3.有m+n个约束，mn个变量;4.有m+n－1个基变量;4.1运输模型

ModelofTransportationProblems【定理4.1】

设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。分析：由于运输问题的方程总数为m+n个，对于平衡型的运输问题，当确定其中的m+n-1个方程后，剩下的一个方程也就确定了，因而平衡运输问题的基变量共有m+n-1个。详细证明过程见书本P95页，此处略。【证】为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。首先介绍一些概念。为一个闭回路，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。【定理5.2】

若变量组B

包含有闭回路，则B中的变量对应的列向量线性相关。4.1运输模型

ModelofTransportationProblems注：由定理4.2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。孤立点：若变量组中某一变量是它所在行或列中出现的惟一变量，则称这个变量是关于变量组的孤立点。【定理4.3】

m+n－1个变量组构成基变量的充要条件是它不包含任何闭回路。注：定理4.3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。4.2运输单纯形法

TransportationSimplexMethod设平衡运输问题的数学模型为：4.2运输单纯形法

TransportationSimplexMethod运输单纯形法基本思路：是基可行解最优否否停运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：

Step1：求初始基可行解(初始调运方案)。常用的方法有最小元素法、元素差额法(Vogel近似法)、左上角法等。

Step2：求检验数并判断是否得到最优解。常用于求检验数的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。

Step3：调整运量，即换基。选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。4.2运输单纯形法

TransportationSimplexMethod注:

表上作业法的条件是产销平衡和运价非负。4.2.1初始基可行解的确定1.最小元素法：最小元素法的思想是就近优先运送，即最小运价Cij

对应的变量xij

优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后得到一个初始基可行解。4.2运输单纯形法

TransportationSimplexMethod【例4.3】求表4－6所示的运输问题的初始基可行解。表4－6销地产地B1B2B3产量A1A2A3847634758304525销量60301010042888B1121051414B2B311696814B4A1A2A3销量161022产量12销地产地4311210210686最小元素法：

BjAiB1B2B3产量A186730A243545A374825销量603010100表4－7【解】30××15×10×25204.2运输单纯形法

TransportationSimplexMethod【例4.4】求表4-10给出的运输问题的初始基本可行解．

B1B2B3B4aiA14104420A2773815A31210615bj510251050表4-104.2运输单纯形法

TransportationSimplexMethod表4-11

BjAiB1B2B3B4aiA14104420A2773815A31210615bj510251050【解】5××10××××015×10104.2运输单纯形法

TransportationSimplexMethod初始基本可行解可用下列矩阵表示表4－11中，基变量恰好是3+4－1=6个且不包含闭回路，是一组基变量，其余标有符号×的变量是非基变量4.2运输单纯形法

TransportationSimplexMethod2．元素差额法(Vogel近似法):最小元素法只考虑了局部运输费用最小。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105后一种方案考虑到C11与C21之间的差额是8－2=6，先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85<Z1。4.2运输单纯形法

TransportationSimplexMethod

基于以上思路，元素差额法求初始基本可行解的步骤是：

Step1:求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；

Step2:找出所有行、列差额的最大值，即L=max{ui，vj}，差额L对应行或列的最小运价处优先调运；Step3:这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。

用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。4.2运输单纯形法

TransportationSimplexMethod沃格尔法：42812105431111968141214161022B1B2B3B4A1A2A3产量销量销地产地1254301101201760012354251321321212214881224行罚数列罚数所以初始基可行解为x12=12,x14=4,x21=8,x24=2,x32=14,x34=8目标函数值4.2运输单纯形法

TransportationSimplexMethod3.西北角法:(亦称左上角法)是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕．当出现同时分配完一行和一列时，仍然应在打“×”的位置上选一个变量作基变量，以保证最后的基变量数等于m+n－1.42888B112105614B2B311961414B4A1A2A3销量161022产量12销地产地4311484681488求出一组基可行解后，判断其是否最优，仍然是用检验数来判断，记xij的检验数为λij

，由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优(即为最优解)。求检验数的方法有两种，闭回路法和位势法。1．闭回路法求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、…，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。4.2运输单纯形法

TransportationSimplexMethod4.2.2求检验数【解】用最小元素法得到下列一组基本可行解【例4.7】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij

，矩阵右边的元素为产量ai

，下方的元素为销量bj

。4.2运输单纯形法

TransportationSimplexMethod只求非基变量的检验数：求λ11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得4.2运输单纯形法

TransportationSimplexMethod

BjAiB1B2B3B4aiA1938470×6010×A2765150××2030A3210922010×10×bj1060403080966-35.2运输单纯形法

TransportationSimplexMethod这里λ34<0，说明这组基本可行解不是最优解。注：只要求得的基变量是正确的且数目为m+n－1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。42888B1121051414B2B311696814B4A1A2A3161022124311210产量销量销地产地B1B2B3B4A1A2A3销量产量销地产地检验数表闭回路法：(+1)(-1)(-1)(+1)(+1)(+1)(-1)(-1)(-1)1210121-1(+1)2．位势法求检验数:

位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为设前m个约束对应的对偶变量为ui(i=1,2,…,m)，后n个约束对应的对偶变量为vj(j=1,2,…,n),则运输问题的对偶问题是4.2运输单纯形法

TransportationSimplexMethod加入松驰变量λij将约束化为等式:ui+vj+λij=cij记原问题基变量XB的下标集为I，由第二章对偶性质知，原问题xij的检验数的相反数是对偶问题的松弛变量λij

，当（i，j）∈I时λij=0，因而有解上面第一个方程，将ui、vj

代入第二个方程求出λij4.2运输单纯形法

TransportationSimplexMethod【例8】用位势法求例7给出的初始基本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为4.2运输单纯形法

TransportationSimplexMethod再由公式求出检验数，其中Cij是非基变量对应的运价。计算结果与例7结果相同。4.2运输单纯形法

TransportationSimplexMethodB1B2B3B4产量A1A2A31244112103985116销量814102681610228141214uivj0411-5-1310销地产地求位势：B1B2B3B4产量A1A2A31244112103985116销量814102681610228141214销地产地B1B2B3B4产量A1A2A31244112103985116销量1610228141214销地产地0-5-1vj411310ui1200010-1100120求检验数：4.2.3调整运量当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运费减少，改进运输方案的步骤是：第一步：确定进基变量:第二步：确定出基变量:

在进基变量xik的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示作为非基变量。第三步：调整运量:

在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。4.2运输单纯形法

TransportationSimplexMethod

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj45655030190

【例4.9】求下列运输问题的最优解表4-194.2运输单纯形法

TransportationSimplexMethod

【解】用最小元素法求得初始基本可行解如表4-19用闭回路法求非基变量的检验数得：

BjAiB1B2B3B4aiA1589270×40×30A23647span>8045×35×A3101214540×2515×bj456550301905.2运输单纯形法

TransportationSimplexMethod+_+_+_因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.对应的非基变量x11进基.x11的闭回路是x33最小，x33是出基量，调整量θ=15

BjAiB1B2B3B4aiA1589270×40×30A236478045×35×A3101214540×2515×bj456550301904.2运输单纯形法

TransportationSimplexMethod+_+_+_

BjAiB1B2B3B4ai30A236478030×50×A3101214540×40××bj45655030190在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“×”作为基变量，其余变量不变，调整后得到一组新的基可行解：5.2运输单纯形法

TransportationSimplexMethod

BjAiB1B2B3B4ai30A236478030×50×A31012>14540×40××bj45655030190重新求所有非基变量的检验数得λ13=3，λ22=0，λ24=7，λ31=1，λ33=4，λ34=－1λ34=－1<0,说明还没有得到最优解，x34进基，在x34的闭回路中，标负号的变量x14和x32，调整量为4.2运输单纯形法

TransportationSimplexMethod

BjAiB1B2B3B4ai×A236478030×50×A3101214540×10×30bj45655030190x14出基，调整运量得到：再求非基变量的检验数：λ13=3，λ14=1，λ22=0，λ24=8，λ31=1，λ33=44.