3.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage1of31设设平衡运输问题的数学模型为：9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage2of31运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最优解，若存在检验数lk0，说明还没有达到最优，转第三步。第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage3of31初始基可行解初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage4of31【例例3.3】求表】求表36所示的运输问题的初始基可行解。表36销地产地B1B2B3产量A186730A243545A374825销量6030101009/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage5of31销地产地B1B2B3产量A186730A243545A374825销量603010100【解】30151025209/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage6of31【例例3.4】求表37给出的运输问题的初始基本可行解。B1B2B3B4aiA1311447A277384A3121069bj365620表379/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage7of31【解】B1B2B3B4aiA1311447A277384A3121069bj365620360416在x12、x22、x33、x34中任选一个变量作为基变量，例如选x12表表389/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage8of31初始基本可行解可用下列矩阵表示表38中，标有符号的变量恰好是3+41=6个且不包含闭回路，是一组基变量，其余标有符号的变量是非基变量，9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage9of311.最小元素法的优势与劣势各是什么？参考书：熊伟，运筹学，机械工业出版社2.用最小元素法求出的调运方案是否接近最优？思考题：思考题：9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage10of312元元素素差差额额法法（Vogel近近似似法法）最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案，15151515前一种按最小元素法求得，总运费是Z1=108+52+151=105，后一种方案考虑到C11与C21之间的差额是82=6，如果不先调运x21，到后来就有可能x110，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12这时总运费Z2=105+152+51=85Z1。基于以上想法，元素差额法求初始基本可行解的步骤是：9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage11of31基于以上想法，元素差额法求初始基本可行解的步骤是：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n；第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage12of31【例例5】用元素差额法求表】用元素差额法求表39运输问题的初始基本可行解。B1B2B3B4aiA15891215A2672425A311013820bj201052560表表399/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage13of31销地产地B1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【解】解】求行差额ui,i=1,2,3及列差额vj,j=1,2,3,4.计算公式为ui=i行次小运价i行最小运价vj= j列次小运价j例最小运价59/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage14of31销地产地B1B2B3B4aiuiA15891215A2172425A361013820bj201052560vj54143322009/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage15of31销地产地B1B2B3B4aiuiA15891215A2172425A361013820bj201052560vj52002442201059/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage16of31基本可行解为总运费Z=108+201+52+208=270。求运输问题的初始方案还有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage17of31求检验数求检验数求出一组基可行解后，判断是否为最优解，仍然是用检验数来判断，记xij的检验数为ij由第一章知，求最小值的运输问题的最优判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。1闭闭回回路路法法求求检检验验数数求某一非基变量的检验数的方法是：在基本可行解矩阵中，以该非基变量为起点，以基变量为其它顶点，找一条闭回路，由起点开始，分别在顶点上交替标上代数符号+、-、+、-、，以这些符号分别乘以相应的运价，其代数和就是这个非基变量的检验数。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage18of31【解】用最小元素法得到下列一组基本可行解【例7】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij，矩阵右边的元素为产量ai ，下方的元素为销量bj。106040309/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage19of31矩阵中打“”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。求11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage20of31同理可求出其它非基变量的检验数：这里340，说明这组基本可行解不是最优解。只要求得的基变量是正确的且数目为m+n1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage21of312位位势势法法求求检检验验位势法求检验数是根据对偶理论推导出来的一种方法。设平衡运输问题为设前m个约束对应的对偶变量为ui,i=1,2,m，后n个约束对应的对偶变量为vj,j=1,2,n则运输问题的对偶问题是9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage22of31加入松驰变量ij将约束化为等式ui+vj+ij=cij记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量ij当（i，j）时ij=0，因而有解上面第一个方程，将ui、vj代入第二个方程求出ij。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage23of31【例8】用位势法求例7给出的初始基本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage24of31再由公式求出检验数，其中Cij是非基变量对应的运价。计算结果与例7结果相同。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage25of31调整运量前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运输减少，改进运输方案的步骤是：第一步：确定进基变量；第二步：确定出基变量，在进基变量xik的闭回路中，标有负号的最小运量作为调整量，对应的基变量为出基变量，并打上“”以示作为非基变量。第三步：调整运量。在进基变量的闭回路中标有正号的变量加上调整量，标有负号的变量减去调整量，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage26of31【例9】求下列运输问题的最优解。45655030销地产地B1B2B3B4aiA1589270A2364780A3101214540bj45655030190【解】用最小元素法求得初始基本可行解如下：3045354025159/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage27of31销地产地B1B2B3B4aiA1589270A2364780A3101214540bj45655030190304535402515求非基变量的检验数,用闭回路法得：9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage28of31销地产地B1B2B3B4aiA1589270A2364780A3101214540bj45655030190304535402515因为有4个检验数小于零，所以这组基本可行解不是最优解。对应的非基变量x11进基.对应的非基变量x11进基.x11的闭回路是标负号的变量是x12、x33、x21，取运量最小值x33最小，x33是出基量，调整量=159/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage29of31销地产地B1B2B3B4aiA1589270A2364780A3101214540bj45655030190在x11的闭回路上x11、x32、x23分别加上15，x12、x33、x21分别减去15，并且在x33处打上记号“”作为基变量，其余变量不变，调整后得到一组新的基可行解：3030502540159/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage30of31销地产地B1B2B3B4aiA1589270A2364780A3101214540bj45655030190303050254015重新求所有非基变量的检验数得：13=3，22=0，24=7，31=1，33=4，34=1x34进基、x14出基。调整运量得到下表：9/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage31of31再求非基变量的检验数：13=3，14=1，22=0，24=8，31=1，33=4所有检验数ij0因而得到最优解最小运费销地产地B1B2B3B4aiA1589270A2364780A3101214540bj456550301903030505510159/17/20243.2运输单纯形法运输单纯形法TransportationSimplexMethodCh3TransportationProblemPage32of31作业：作业：P99T3.3(1)(2)3.4本节讲解了平衡运输问题的求解方法：运输单纯形法运输单纯形法主要分三个步骤：1.求初始运输方案，用最小元素法、元素差额法（Vogel近似法）2.求检验数，用闭回路法和位势法3.调整运量，用闭回路法Exit运输问题的变体运输问题的变体9/17/2024