电子第三章.ppt

《电子第三章.ppt》由会员分享，可在线阅读，更多相关《电子第三章.ppt（173页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、电子课件第三章现在学习的是第1页，共173页 第2章中讨论了有关物资调运的问题，即运输问题。有时候为了书写简便，运输问题也被写做TP（Transportation Problem）。现在学习的是第2页，共173页 对某种物资，设有m个产地A1,A2,Am，称它们为发点，其对应产量为a1,a2,am，称它们为产量；另有n个销地B1,B2,Bn，称它们为收点，其对应销量为b1,b2,bn，称它们为销量。又知，从产地（发点）Ai运至销地（收点）Bj，该种物资每单位的运价为ci j（ci j0）。试问：应如何安排调运方案，在满足一定要求的前提下，使总运费最低？现在学习的是第3页，共173页根据上述参量

2、的意义列出产销运价，如表3.1所示。表表3.1 产销运价表产销运价表 销地销地 产地产地 B1 B2 Bn 产量产量 A1 c11 c12 c1n a1 A2 c21 c22 c2n a2 Am cm1 cm2 cmn am 销量销量 b1 b2 bn ai bj 现在学习的是第4页，共173页 表中：ai的单位为吨、公斤、件等；bj的单位为吨、公斤、件等；cij的单位为元/吨等。ai,bj,cij的单位应该一致（i1,2,m；j1,2,n）。现在学习的是第5页，共173页 表的右下角 ai表示各产地产量的总和，即总产量或总发量；bj表示各销地销量的总和，即总销量或总收量。这里有两种可能：（1

3、）ai bj（总产量总销量），即产销平衡问题。（2）ai bj（总产量总销量），即产销不平衡问题。它又可分为两种情况：产大于销，即 ai bj；销大于产，即 ai bj。下面先讨论产销平衡问题，再讨论产销不平衡问题。现在学习的是第6页，共173页令xij表示某物资从发点Ai到收点Bj的调拨量（运输量），可以列出产销平衡表如表3.2所示。表表3.2 产销平衡表产销平衡表 销 地产 地 B1 B2 Bn 产 量 A1 x11 x12 x1n a1 A2 x21 x22 x2n a2 Am xm1 xm2 xmn am 销量 b1 b2 bn ai bj 现在学习的是第7页，共173页 将表3.1和

4、表3.2两个表合在一起，得到的一个新表，被称为运输表（或称为产销矩阵表），如表3.3所示。表表3.3 运输表（产销矩阵表）运输表（产销矩阵表）销地产地 B1 B2 Bn 产量 A1 X11 c11 x12 c12 x1n c1n a1 A2 x21 c21 x22 c22 x2n c2n a2 Am xm1 cm1 xm2 cm2 xmn cmn am 销量 b1 b2 bn ai bj 现在学习的是第8页，共173页根据产销矩阵表，求上述问题的解等于求下面数学模型的解，即求：xij（i1,2,m；j1,2,n）),2,1;,2,1(0),2,1(),2,1(11njmixnjbxmiaxij

5、mijijnjiij（3-1）现在学习的是第9页，共173页11minmnijijijzc x（3-2）现在学习的是第10页，共173页 从上述这一特殊的线性规划（LP）问题，可以得到下列三条结论。（1）该问题的基变量有）该问题的基变量有m n 1个。个。（2）该问题一定有最优解。）该问题一定有最优解。（3）如果）如果ai，bj全是整数，则该问题一定有整数最优全是整数，则该问题一定有整数最优解。解。由于对这类问题的研究最早从运输问题开始，故这类问题统称为运输问题。现在学习的是第11页，共173页 3.2.1 产销平衡运输问题的表上作业法产销平衡运输问题的表上作业法 从上面的运输问题的数学模型中

6、可以看到，它包含mn个变量，mn个约束条件。如果用单纯形法求解，应先在每个约束方程中引进一个人工变量。这样一来，即使是m3，n4这样简单的运输问题，变量数就有12个，显然计算起来非常繁杂；而用表上作业法来求解运输问题则比较简便。现在学习的是第12页，共173页 用表上作业法求解运输问题时，同单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。现在学习的是第13页，共173页 每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值

7、比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。现在学习的是第14页，共173页 下面以煤的调运问题为例介绍表上作业法的计算过程。例3.1 设有三个产煤基地A1、A2、A3，四个销煤基地B1、B2、B3、B4，产地的产量，销地的销量和从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。现在学习的是第15页，共173页 表表3.4 产销运价表产销运价表 万吨，万元万吨，万元 销地销地产地产地 B1 B2 B3 B4 产产 量量 A1 3113107A2 192

8、84A3 741059 销销 量量 3656 20 20 现在学习的是第16页，共173页（1）列出运输问题的产销矩阵表。根据表3.4，可列出产销矩阵表（也称为运输表），如表3.5所示。现在学习的是第17页，共173页 表表3.5 产销矩阵表产销矩阵表 万吨，万元万吨，万元 销地销地产地产地 B1 B2 B3 B4 产产 量量 A1x11 3 x12 11 x13 3 x14 10 7A2x21 1 x22 9 x23 2 x24 8 4A3x31 7 x32 4 x33 10 x34 5 9销销 量量3656 2020 现在学习的是第18页，共173页 其中：xij为产地Ai到销地Bj的运量

9、（i1,2,3；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法最小元素法。现在学习的是第19页，共173页在应用最小元素法确定初始方案时，必须注在应用最小元素法确定初始方案时，必须注意以下两点。意以下两点。（1）当选定最小元素（不妨假定为）当选定最小元素（不妨假定为cst）后，如果发现该）后，如果发现该元素所在行的产地的产量元素所在行的产地的产量as恰好等于它所在列的销地的销恰好等于它所在列的销地的销量量bt（即（即as bt），这时，可在产销矩

10、阵表上），这时，可在产销矩阵表上xst处填上处填上一个数一个数as，并画上圈。为了保证调运方案中画圈的数字，并画上圈。为了保证调运方案中画圈的数字为为m n 1个，只能在个，只能在s行的其他格上都打上行的其他格上都打上“”（或在（或在t列的其他格上都打上列的其他格上都打上“”），不可以同时把），不可以同时把s行和行和t列列的其他格子都打上的其他格子都打上“”。现在学习的是第20页，共173页（2）当最后只剩下一行（或一列）还存在没有填数和打）当最后只剩下一行（或一列）还存在没有填数和打“”的格子时，规定只允许填数，不允许打的格子时，规定只允许填数，不允许打“”，其目的也是为保证画圈数字的个数恰

11、为其目的也是为保证画圈数字的个数恰为m n现在学习的是第21页，共173页 所谓闭回路，就是从调运方案的某一个打所谓闭回路，就是从调运方案的某一个打“”处（处（xij）处作为一个起点出发，在表格里向）处作为一个起点出发，在表格里向纵的或横的方向一直走，碰到有圈数字的格才可以纵的或横的方向一直走，碰到有圈数字的格才可以拐弯，这样拐了几个弯以后，再回到起点处，就画拐弯，这样拐了几个弯以后，再回到起点处，就画出一条封闭的折线（由水平和铅直的直线所组成）出一条封闭的折线（由水平和铅直的直线所组成）现在学习的是第22页，共173页 它所有的转角处（通常称为闭回路的顶点或转它所有的转角处（通常称为闭回路的

12、顶点或转角点）除该打角点）除该打“”处以外，其余的都必须是画圈处以外，其余的都必须是画圈的数字，这样的一条封闭折线成为过的数字，这样的一条封闭折线成为过xij处的闭回处的闭回路（简称回路）。路（简称回路）。例如，表例如，表3.9中的直线表示的闭折线分别是过中的直线表示的闭折线分别是过x11处和过处和过x24处的闭回路。处的闭回路。现在学习的是第23页，共173页 可以证明，过可以证明，过xij处的闭回路一定存在，而且是处的闭回路一定存在，而且是唯一的（证明略）。唯一的（证明略）。下面我们简单说明用闭回路法来检验调运方案的下面我们简单说明用闭回路法来检验调运方案的原理。表原理。表3.9中中x11

13、的打的打“”处表示处表示A1生产的煤不调运给生产的煤不调运给B1。现在学习的是第24页，共173页 我们假定把调运方案改变一下，让我们假定把调运方案改变一下，让A1生产的生产的煤调运煤调运1（万吨）给（万吨）给B1，观察过，观察过x11处的回路，为了处的回路，为了保持新的平衡，就要依次在保持新的平衡，就要依次在x13处减少处减少1（万吨），（万吨），x23处增加处增加2（万吨），（万吨），x21处减少处减少1（万吨），即总运（万吨），即总运费增加费增加3 3 2 1 1（万元）。（万元）。现在学习的是第25页，共173页 这说明把这说明把A1生产的煤调运给生产的煤调运给B1 1（万吨），总运费

14、（万吨），总运费比原方案增加比原方案增加1万元，是不合算的。我们把通过万元，是不合算的。我们把通过x11处的处的回路改变的运费数回路改变的运费数1（万元）称为（万元）称为x11处的检验数，记处的检验数，记为为 11 1。如果所有的打。如果所有的打“”处检验数都大于或等于处检验数都大于或等于0，表明对调运方案作任何改变都将导致总的运费增加，表明对调运方案作任何改变都将导致总的运费增加，没有比已给定方案更好的方案了，即给定的方案就没有比已给定方案更好的方案了，即给定的方案就是最优方案。是最优方案。现在学习的是第26页，共173页 否则，如某一打否则，如某一打“”处的检验数为负，则表明对处的检验数为

15、负，则表明对调运方案做出调整后，运费就会减少，即给定方案不调运方案做出调整后，运费就会减少，即给定方案不是最优方案。因此，利用闭回路求得检验数的正或负是最优方案。因此，利用闭回路求得检验数的正或负可以判别调运方案是否最优。可以判别调运方案是否最优。现在学习的是第27页，共173页 这样，用闭回路法检验某调运方案是否最优，可这样，用闭回路法检验某调运方案是否最优，可按下面两步进行。按下面两步进行。求检验数。从某求检验数。从某xij的打的打“”处出发，沿着它的闭处出发，沿着它的闭回路前进（顺时针或逆时针都可以）。将这个打回路前进（顺时针或逆时针都可以）。将这个打“”处对应的单位运价加上正号，而下面

16、首先遇到处对应的单位运价加上正号，而下面首先遇到的一个顶点作为第一个顶点的对应的单位运价加上的一个顶点作为第一个顶点的对应的单位运价加上负号，再将第二个遇到的顶点处对应的单位运价加负号，再将第二个遇到的顶点处对应的单位运价加上正号，正负交错，依次类推。上正号，正负交错，依次类推。现在学习的是第28页，共173页 最后将这些带有正负号的运费相加而得到的总和称为xij处的检验数ij。例如，表3.9中x24处的检验数2 4沿它的闭回路（按顺时针）计算如下：24 c24c23c13c14823101 因为过xij的回路是唯一的，所以它的检验数ij也是唯一的。现在学习的是第29页，共173页 根据检验数

17、进行判别。判别准则是：若所有的检验数都是非负的，即ij0，则所检查的调运方案为最优方案；否则，若存在负的检验数则所检查的调运方案不是最优的。现在学习的是第30页，共173页下面给出对表3.9调运方案检验的全过程。解解 求检验数。求检验数。11 c11 c13 c23 c21 3 3 2 1 1 12 c12 c14 c34 c32 11 10 5 4 2 22 c22 c23 c13 c14 c34 c32 9 2 3 10 5 4 1 24 c24 c23 c13 c14 8 2 3 101 31 c31 c21 c23 c13 c14 c34 7 1 2 3 10 5 10 33 c33

18、c13 c14 c34 10 3 10 5 12将所有打将所有打“”处的检验数填入表中，得到检验数表，如表处的检验数填入表中，得到检验数表，如表3.12所示。所示。现在学习的是第31页，共173页 根据检验数进行判别。因为根据检验数进行判别。因为 2410，所以调运方，所以调运方案案不是最优的。不是最优的。表表3.12 检验数表检验数表 销地销地 产地产地 B1B2B2B2A11B3B3B3A2 B4B4B4A310222现在学习的是第32页，共173页（4）调运方案的调整闭回路法。如果所得到的调运方案不是最优的，就必须调整。根据前面讲过的闭回路的原理，表3.6调运方案中2410，因此设法使x

19、24不为零，就能使总运费减少，所以应对它作最大可能的调整。现在学习的是第33页，共173页 观察过x24的闭回路如表3.9所示，为了把A2生产的煤调运给B4，就要相应减少A2调运给B3的煤运量和A1调运给B4的煤运量，只有这样才能得到新的平衡，这两个格内较小的运量是1，即min（1，3）1，因此A2最多只能将1（万吨）煤调运给B4，经这样调整后可得到一个新的调运方案，如表3.13所示。现在学习的是第34页，共173页 方案的总运费z85万元，显然8586（万元）。对方案进行检验，经计算所有打“”处的检验数都是非负数（请同学自己作为练习），所以它是最优方案。可见，用闭回路法来调整调运方案是行之有

20、效的。现在学习的是第35页，共173页 表表3.13 调运方案调运方案 万吨，万元万吨，万元 销销 地地 产产 地地 B1 B2 B3 B4 产量产量 A1 3 11 3 10 7A2 1 9 2 8 4A3 7 4 10 5 9销销 量量3 6 5 6 20 20现在学习的是第36页，共173页一般地，调运方案的调整可分三步进行。在检验数表中确定一个绝对值最大的负检验数在检验数表中确定一个绝对值最大的负检验数 st，作，作出过出过xst处的闭回路。处的闭回路。从从xst所在的格出发，沿着它的闭回路前进，在各奇所在的格出发，沿着它的闭回路前进，在各奇数次顶点（画圈的数字）中选出最小的一个数（运

21、数次顶点（画圈的数字）中选出最小的一个数（运量）记为量）记为d。将将d填在填在xst处，并画上圈，同时将闭回路上其他奇数次处，并画上圈，同时将闭回路上其他奇数次顶点的运量都减去顶点的运量都减去d，在偶数次顶点的运量都加上，在偶数次顶点的运量都加上d，这样就得到一个新的调运方案。这样就得到一个新的调运方案。现在学习的是第37页，共173页 一般说来，经过一次调整后，对新方案进行检验，可能还会出现负的检验数，那就需要再进行调整，直至所有检验数st0为止。这里还需指出，有时在闭回路的调整过程中，奇数次顶点的画圈数字中有两个或两个以上相等的最小运量，这样在调整时，为了产销矩阵表上画圈数字的个数仍然保持

22、mn1个，以便用表上作业法继续进行计算，规定在奇数次顶点最小运量处只打上一个“”，其余的地方都填上“0”，并画上圈。画圈的0仍当做有圈的数字看待。现在学习的是第38页，共173页 第一步，第一步，求初始调运方案（用最小元素法）。求初始调运方案（用最小元素法）。它保证有调运量的格子个数（基变量个数）等于它保证有调运量的格子个数（基变量个数）等于m n 1。现在学习的是第39页，共173页最小元素法的步骤如下。最小元素法的步骤如下。（1）从没有）从没有“”的运价格子中，找出最小运价（若同的运价格子中，找出最小运价（若同时有若干个相同最小运价则可任选一个），在它的左时有若干个相同最小运价则可任选一个

23、），在它的左下角填入最大可能调运量（能够供应的数量和尚需数下角填入最大可能调运量（能够供应的数量和尚需数量的最小值），转步（量的最小值），转步（2）。）。现在学习的是第40页，共173页（2）若无）若无“”的格子只剩一行或一列，的格子只剩一行或一列，转（转（1）；）；否则，否则，“”去调运量已满足的行或列中其运价处去调运量已满足的行或列中其运价处没有填数和没有划没有填数和没有划“”的格中的左下角填的格中的左下角填“”，（只能在一行或一列中填（只能在一行或一列中填“”），），转步骤（转步骤（1）。）。现在学习的是第41页，共173页第二步，求检验数。第二步，求检验数。若所有若所有 ij0，则最优

24、解已求得，计算终止。填有调，则最优解已求得，计算终止。填有调运量的格子为最优调运方案（未填调运量的格子，运量的格子为最优调运方案（未填调运量的格子，调运量为调运量为0），计算各调运量与对应格子运价之积，），计算各调运量与对应格子运价之积，再求它们的和就是最低总运费。若至少有某个再求它们的和就是最低总运费。若至少有某个 ij0，转第三步。转第三步。现在学习的是第42页，共173页第三步，调整。第三步，调整。（1）从最小负检验数的对应格子出发画直线，碰到有调）从最小负检验数的对应格子出发画直线，碰到有调运量的适当格子转角，做出惟一的一条闭回路（理论运量的适当格子转角，做出惟一的一条闭回路（理论证明

25、的结果）。证明的结果）。（2）在这个闭回路上，令画）在这个闭回路上，令画“”处格子为偶数转角处格子为偶数转角点，依次（无论沿顺时针方向还是沿逆时针方向）排出点，依次（无论沿顺时针方向还是沿逆时针方向）排出各转角点的奇偶性，再求调整量各转角点的奇偶性，再求调整量 min（各奇数转角点（各奇数转角点调运量）。调运量）。现在学习的是第43页，共173页（3）按）按“偶点处加调整量，奇点处减调整量偶点处加调整量，奇点处减调整量”的方法，的方法，重新安排回路上转角点处的调运量，将奇数转角点处重新安排回路上转角点处的调运量，将奇数转角点处调运量变为调运量变为0的一个（仅能一个）格子右上角打的一个（仅能一个

26、）格子右上角打“”，回到第二步。，回到第二步。现在学习的是第44页，共173页 注意：注意：如遇到发量已发完，且收量已满足的格子还如遇到发量已发完，且收量已满足的格子还需要填入调运量时，就填入数字需要填入调运量时，就填入数字0；在最优解中若在最优解中若非基变量（画非基变量（画“”处）的检验数为处）的检验数为0，仍可从该格，仍可从该格子处出发作唯一的闭回路，再按第三步调整可得另一子处出发作唯一的闭回路，再按第三步调整可得另一最优解，此时目标函数最小值不改变。最优解，此时目标函数最小值不改变。现在学习的是第45页，共173页 例例3.2 工地有工地有3个高地个高地A1、A2、A3和和4个洼地个洼地

27、B1、B2、B3、B4，我们想把高地土方有计划地去填洼地。，我们想把高地土方有计划地去填洼地。设各个高地的出土量和各个洼地的填土量如表设各个高地的出土量和各个洼地的填土量如表3.14所所示，各个高地与各个洼地之间的距离如表示，各个高地与各个洼地之间的距离如表3.15所示。所示。试用表上作业法制定最合理的调运方案。试用表上作业法制定最合理的调运方案。现在学习的是第46页，共173页解（解（1）将运量表与距离表合并为产销矩）将运量表与距离表合并为产销矩 阵表，如表阵表，如表3.16所示。所示。（2）用最小元素法求出初始调运方案）用最小元素法求出初始调运方案，如表，如表3.17所示。所示。（3）利用

28、闭回路法求得检验数表）利用闭回路法求得检验数表，如表，如表3.18所示。所示。因为检验数表中的检验数有负数，必须进行调整。因为检验数表中的检验数有负数，必须进行调整。现在学习的是第47页，共173页 洼地洼地高地高地 B1B2B3B4出出 土土A1 70A2 20A3 10填土填土50251015 100 100 表表3.14 3.14 运运 量量 表表 10 10土方土方 现在学习的是第48页，共173页 表表3.15 距距 离离 表表 100米米 洼地洼地高地高地 B1B2B3B4A110523A24312A35634现在学习的是第49页，共173页 表表3.16 产销矩阵表产销矩阵表 1

29、0土方，土方，100米米 洼地洼地高地高地 B1B2B3B4出出 土土A11052370A2431220A3563410 填土填土50251015 100100现在学习的是第50页，共173页 表表3.17 调运方案调运方案 10土方，土方，100米米 洼地洼地高地高地 B1B2B3B4出出 土土A1 10 5 2 370A2 4 3 1 220A3 5 6 3 410填土填土50251015 100100 40 25 现在学习的是第51页，共173页表表3.18 检验数表检验数表 洼洼地地高地高地 B1B2B3B4A1 0 A2 5 1 A3 666现在学习的是第52页，共173页（4）在检

30、验数表）在检验数表中，中，较大，所以过调运方案较大，所以过调运方案（表（表3.17）中）中x21处做出它的闭回路，进行调整得到调运方案处做出它的闭回路，进行调整得到调运方案，如表如表3.19所示。所示。（5）求调运方案）求调运方案的检验数表，如表的检验数表，如表3.20所示。因为所示。因为调运方案调运方案检验数表中的检验数有负数，必须进行调整。检验数表中的检验数有负数，必须进行调整。21现在学习的是第53页，共173页（6）因为）因为 1350，所以过调运方案（，所以过调运方案（）（表）（表3.19）中中x13处做出它的闭回路，进行调整得到调运方案处做出它的闭回路，进行调整得到调运方案，如，如

31、表表3.21所示。所示。（7）再求出方案（）再求出方案（）的检验数表）的检验数表，如表，如表3.22所示。所示。由于检验数全部为正数，所以调运方案由于检验数全部为正数，所以调运方案为最优方案。为最优方案。（8）目标函数值为：）目标函数值为：min z 20 10 25 5 10 2 15 3 20 4 10 5 520（土方公（土方公里）里）现在学习的是第54页，共173页表表3.19 调运方案调运方案 10土方，土方，100米米 洼洼地地高地高地 B1B2B3B4出出 土土A1 10 5 2 370A2 4 3 1 220A3 5 6 3 410填土填土50251015 10010030 1

32、0 10 25 10 15 现在学习的是第55页，共173页表表3.20 检验数表检验数表 洼地洼地高地高地 B1 B2B3B4A1 5 A24 5A3616现在学习的是第56页，共173页表表3.21 调运方案调运方案 10土方，土方，100米米 洼地洼地高地高地 B1B2B3B4出出 土土A1 10 5 2 370A2 4 3 1 220A3 5 6 3 410填土填土50251015 100100 20 20 10 25 10 15 现在学习的是第57页，共173页表表3.22 检验数表检验数表 洼地洼地高地高地 B1 B2B3B4A1 A2455A3666现在学习的是第58页，共173

33、页 上面看到，要判别一个方案是否最优，需要过每一个打“”处做出它的闭回路，再根据回路求出所有的检验数。当一个运输问题的产地和销地个数很多时，用这个方法计算检验数的工作量十分繁重。下面介绍一种更为简便的求检验数的方法位势法。我们仍用煤的调运问题作为例子来介绍这种方法。现在学习的是第59页，共173页 表3.23给出了这个例子用最小元素法确定的初始调运方案。我们用位势法求检验数时，第一步先在表3.23中添加新的一列ui列（i的个数等于产地的个数）和新的一行vj行（j的个数等于销地的个数），如表3.24所示。现在学习的是第60页，共173页 销地销地产地产地 B1B2B3B4产产 量量A1 3 11

34、 3 107 3A2 1 9 2 84 1A3 7 4 10 59 3销量销量3656 2020现在学习的是第61页，共173页表表3.24 初始调运方案（第一步）初始调运方案（第一步）万吨，万元万吨，万元 销地销地产地产地 B1B2B3B4产量产量uiA1 3 11 3 107u1A2 1 9 2 84u2A3 7 4 10 59u3销销 量量365620 vjv1v2v3v4 现在学习的是第62页，共173页 这里的ui和vj分别称为第i行和第j列的位势（i1,2,m；j列的位势（i1,2,m；j1,2,n），并规定它们与表中画圈数字所在的格对应的单位运价有如下关系：13131414212

35、12323323234343101245uvcuvcuvcuvcuvcuvc（3-3）现在学习的是第63页，共173页 第二步是确定ui和vj的数值，由于这些ui和vj的数值相互是有关联的，所以只要任意给定其中的一个；根据关系式（3-3），很容易将其他所有的位势的数值求出。例如，在表3.24中，先令v11，则可由 现在学习的是第64页，共173页u2 v1 1 u2 0u2 v3 2 v3 2u1 v3 3 u1 1u1 v4 10 v4 9u9 v4 5 u34u3 v2 4 v2 8 把这些数分别填入表3.24的ui列和vj行，得到表3.25。现在学习的是第65页，共173页表表3.25

36、初始调运方案（第二步）初始调运方案（第二步）万吨，万元万吨，万元 销地销地产地产地 B1B2B3B4产产 量量uiA1 3 11 3 1071A2 1 9 2 840A3 7 4 10 59 4销量销量365620 vj1829 现在学习的是第66页，共173页 第三步，求出位势后可以根据下面的原理求“”处格子的检验数（即非基变量的检验数）。令ij表示xij处的检验数。例如，31可由闭回路法计算得到：31c31c34c14c13c23c21c31（u3v4）（u1v4）（u1v3）（u2v3）（u2v1）c31（u3v1）现在学习的是第67页，共173页 其中c31是x31处对应的单位运价，（

37、u3v1）恰好就是该打“”处所在行和列的位势之和。类似地，可以得出任一打“”处（xij处）的检验数，即 ij cij(uivj)（3-4）现在学习的是第68页，共173页 根据式（3-4），很容易求出表3.25中所有打“”处的检验数，即1131111211182229081248091317(4)1103310(4)212现在学习的是第69页，共173页 显然，求得的6个检验数与用闭回路求得的检验数（见表3.12）完全一致。如果检验数中出现了负数，对方案进行调整的方法同前面闭回路法一样。最后再指出一点，有无可能在计算位势时出现中断或某一行或某一列可能得出两个不同的位势值的情况。答案是否定的，对

38、给定的初始方案，只要首先给出一个位势，则其他行与其他列的位势存在且惟一。现在学习的是第70页，共173页例例3.3 对表对表3.19调运方案调运方案，用位势法求检验数。，用位势法求检验数。解解 （1）在表）在表3.19中添加新的中添加新的ui列和列和vj行得表行得表3.26。（2）令）令u1 5，用各有圈数字所在格的单位运价，按，用各有圈数字所在格的单位运价，按关系式关系式cij(ui vj)依次求出各位势值填入表依次求出各位势值填入表3.26。现在学习的是第71页，共173页 洼地洼地高地高地 B1B2B3B4出出 土土uiA1 10 5 2 3705A2 4 3 1 220 1A3 5 6

39、 3 4100填土填土50251015 vj502 2 30 10 10 25 10 15 现在学习的是第72页，共173页（3）利用打）利用打“”处的单位运价，按式（处的单位运价，按式（3-4），即可间），即可间接求得相应的检验数表接求得相应的检验数表，如表如表3.27所示。所示。现在学习的是第73页，共173页表表3.27 检验数表检验数表 洼地洼地高地高地 B1B2B3B4A1 5 A2 4 5A3 616现在学习的是第74页，共173页 对于运输问题的初始方案的确定，除了可用最小元素法之外，还可以用其他的方法。例如，西北角法和沃格尔法（Vogel法，也称为元素差额法）等，下面介绍这两种

40、方法。现在学习的是第75页，共173页 1西北角法 西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足产销矩阵表中西北角（即左上角）上空格的供销需求，优先满足供应。下面讨论表3.28所表示的例子。现在学习的是第76页，共173页 销地销地产地产地 B1B2B3B4产产 量量A1 4 12 4 1116 8A2 2 10 3 910 4A3 8 5 11 622 14销量销量814612148 484814 现在学习的是第77页，共173页 由表3.28可知，该表左上角的空格是（A1，B1），在使用西北角法时先在（A1，B1）格中填入数字xijmin（a1，b1）m

41、in（16，8）8。因为B1的销量已经满足，所以B1所在列的格内x21、x31处打“”，A1的可供量变为1688。在产销矩阵表尚未填数和打“”的部分中，左上角格子变为（A1，B2）。由于min（a18，6）min（8，14）8，故在（A1，B2）格子中填入8。现在学习的是第78页，共173页 因为A1的可供量已经用完，所以A1所在行的格内x13、x14处打“”，B2的需求量由b214变为1486。这时（A2，B2）是产销矩阵表剩下部分的左上角格子。因min（a2，b8）6，在（A2，B2）中填入数字6，并在B2所在列的格内x32处打“”，A2的可供量变为1064。如此继续下去，在（A2，B3）

42、格中填入4，在（A3，B3）格中填入8，最后在（A3，B4）格中填入14，同时在A3行和B4列中的其他格中填“”。寻求初始调运方案的过程示于表3.28中。现在学习的是第79页，共173页至此得到初始方案解为x118，x128，x226，x234，x338，x3414其他变量均等于0。它所对应的目标函数z值为：z8481261043811146372现在学习的是第80页，共173页2沃格尔法沃格尔法 沃格尔法（Vogel法）也称为元素差额法。初看起来，最小元素法十分合理；但是，有时按某一最小单位运价优先安排物品调运时却可能导致不得不采用运费很高的其他供销点对，从而使整个运输费用增加。对每一个供应

43、地（或销售地），均可由它到各销售地（或各供应地）的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地（或销售地）的罚数（也称为差额）。现在学习的是第81页，共173页 如果罚数的值不大，当不能按最小单位运价安排如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。法就是基于这种考虑提出来的。现在学习的是第8

44、2页，共173页 下面结合表3.28所表示的例子说明这种方法。首先计算产销矩阵表中每一行和每一列的次小单位运价和最小单位运价之间的差值，并分别称之为行罚数和列罚数。将算出的行罚数填入位于表右侧行罚数栏的左边第一列的相应格子中，列罚数填入位于表下边列罚数栏的第一行的相应格子中，如表3.29所示。现在学习的是第83页，共173页表表3.29 3.29 沃格尔法例子数据沃格尔法例子数据 销地销地产地产地B1 B2 B3 B4 产产 量量 行罚数行罚数 12345A1 4 12 4 1116000 A2 2 10 3 91011160A3 8 5 11 62212销量销量8141214列列罚罚 数数

45、1213221312412512 14 现在学习的是第84页，共173页 例如，A1行中的次小和最小单位运价均为4，故其行罚数等于0；A2行中的次小和最小单位运价分别为3和2，其行罚数等于321；B1列中的次小单位运价和最小单位运价分别为4和2，其列罚数等于2。如此进行，计算出本A1、A2和A3行的行罚数分别为0、1和1、B1、B2、B3和B4列的列罚数分别为2、5、1和3。现在学习的是第85页，共173页 在这些罚数中，最大者为5（在表3.29中用小圆圈示出），它位于B2列。由于B2列中的最小单位运价是位于（A3，B2）格中的5，故在（A3，B2）格中填入尽可能大的运量14，此时B2的需要量

46、得到满足，在B2列的其他格中填“”。现在学习的是第86页，共173页 在尚未填数和填入“”的各行和各列中，按上述方法重新计算各行罚数和列罚数，并分别填入行罚数栏的第2列和列罚数栏的第2行。例如，在A3行中剩下的次小单位运价和最小单位运价分别为8和6，故其罚数等于2。由表3.29中填入这一轮计算出的各罚数可知，最大者等于3位于B4列，由于B4列中的最小单位运价为6，故在其相应的格中填入这时可能的最大调运量8，在A3行的其他格中填“”。现在学习的是第87页，共173页 用上述方法继续做下去，依次算出每次迭代的行罚数和列罚数，根据其最大罚数值的位置在表中的适当格中填入一个尽可能大的运输量，并在对应的

47、一行或一列的其他格中填“”。在本例中，依次在表中填入运输量x3214，x348，x218，x1312，x242，并相应地依次在B2列、A3行、B1列、B3列、A2行中填“”。最后未画“”的格仅为（A1，B4），在这个格中填入数字4，并同时在A1行和B4列中填“”。现在学习的是第88页，共173页用这种方法得到的初始方案的解为x1312，x144，x218，x242，x3214，x348其他变量的值等于零。这个解的目标函数值为z124411822914586244现在学习的是第89页，共173页 比较上述最小元素法、西北角法和沃格尔法三种方法给出的初始方案的解，以沃格尔法给出的解的目标函数值最小

48、，最小元素法次之，西北角法解的目标函数值最大。一般说来，沃格尔法得出的初始解的质量较好，常用来作为运输问题最优解的近似解。现在学习的是第90页，共173页 对于产销不平衡的运输问题，可分为总供给量（总产量）总需求量（总销量）（即 ai bj）或总需求量（总销量）超过总供给量（总产量）（即 ai bj）两种情形，关键是按具体情况虚设收点或虚设发点，其收量或发量是两类总量的差数，并按实际意义决定各新增格子上的单位运价，这样就把它们转化为产销平衡的运输问题。现在学习的是第91页，共173页下面举例说明上述方法。下面举例说明上述方法。例3.4 求下面运输问题的最优调拨方案，其产销运价表如表3.30所示

49、。现在学习的是第92页，共173页表3.30 例3.4产销运价表销地销地 产地产地 B1B2B3B4产产 量量A1211347A2103595A378127 销量销量234619 15 现在学习的是第93页，共173页 解 通过对右下角总供给、总需求的计算，发现 ai bj，产量有剩余，应虚设一收点，叫做库存。任何发点到库存的单位运价设为0，收点“库存”的收量等于：总发量总收量19154，这就建立了一个平衡的运输问题，如表3.31所示。现在学习的是第94页，共173页表表3.31 例例3.4产销运价表（平衡方案）产销运价表（平衡方案）销地销地 产地产地 B1B2B3B4B0产产 量量A1211

50、 3 407A2103 59 0 5A3781207销量销量2346419 19 现在学习的是第95页，共173页 但是，在用最小元素法寻找初始调运方案时，每次不要考虑（新增）库存这一列的单位运价，否则一开始就去满足库存而不是实际的需要，会使初始方案离最优方案距离更远，会增加以后调整的工作量。按最小元素法做出的初始调运方案（请读者重新做一遍并与此题结果核对）如上表所示。经检验，它就是最优调拨方案。由于130，还可有另外的最优调拨方案但总运费不会再下降。现在学习的是第96页，共173页例3.5 设有3个化肥厂供应4个地区的化肥，并设等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地年需求量，