1、2.6 运输问题及其解法 2.6.1 运输问题模型及其特征2.6.2 产销平衡 (TP)的表上作业法 2.6.3 产销不平衡 TP问题的平衡转换1. 模型(各 Ai运往 Bj之和 )(Ai运往各 Bj之和 )2.6.1 运输问题模型及其特征2.(TP)的特征记 (TP)的系数矩阵： Pij=ei+em+j,rank(A)=m+n-1,从而 A不是行 满 秩的，且 A的任何 m+n-1行线性无关，故 (TP)的基解中有 n+m-1个基变量； (TP)恒有可行解和最 优 解证： 令 则 为 (TP)可行解，又 故 (TP)的可行集是非空有界 集，于是连续目标函数 z 取到最小值。(TP)是一个线性
2、规划问题，但用单纯法求解，存贮量大和 计算量大，利用 A的特殊结构，研究特殊解法。思想：在运输表上给出一个调运方案 (基可行解 )，用最优准则判断：是最优，则停，否则修正，产生新的调运方案。一、初始调运方案的求法 :最小元素法 ,西北角法 ,伏格尔法0. 各种不同方法的基本做法： 用具体方法在表中没划掉格子中 选 出待填格子 (i,j); 然后在格子 (i,j)的右下角尽可能多地安排 调 运量； 划行或列：将安排完 产 量的 产 地行或安排完 销 量的销地列用虚线划掉，并注意修改列销量或行产量。 右下角填数 格子个数 应 等于 m+n-1；2.6.2 产销平衡 (TP)的表上作业法302060
3、0200401. 最小元素法(1)做法：在运输表中选尚未划掉的运价 cij最小的格子 (i,j)(2)示例：某运输问题的运输表及初始调运方案：600202. 西北角法：选在没划掉格子中西北角 (左上角 )格子为待 填的 格子。3.伏格尔法 ：和最下行。每次填数时，在行差额和列差额中选最大差额，各列中最小运费与次最小运费之差，并填于表中最右列然后在其所在行 (列 )中选运费最小格子为待填格子。首先在运输表中计算出没被划掉的各行和伏格尔法 示例：列 差额销地产 地行差额7 10 8 6 4 405 9 7 12 6 403 6 5 8 11 9030 40 60 20 202 3 2 2 2 2
4、- 2 2 2 - - 2 2 2 - - 1 6 2 - - 1 - 2 - - 7 - 6 2 1 22 1 22 1 32 1 |4 1 | | 1 | 40 5030 202020 2020040 040 0二、最优检验数的计算对于当前基 B， 记 JB=(i,j)： 格子 (i,j)为基变量 ，JN=(i,j)： 格子 (i,j)为非基变量 ，检验数：于是：位势 方程该 方程有无穷多解，可取其中某个 ui=0,求解之。先将 ui， vi填于表的最右列和最下行，在表上计算非基 变量的检验数 ，并将其填于格子 (i,j)的左下角 (基变量格子不填 )如表中各非基格子 (i,j)左下角全小
5、于等于零，则 当前解为最优。例 . 由最小元素法求得的可行调运方案为：最优判别：75330107056062012084206118940606 46134-1-80-7 -741 2 -3三、用闭回路改进调运方案1. 形成闭回路将非基 变量中检验数为 “坏 ”(左下角数 0)的一个格子(r,s)加入基变量，连同基变量一起形成一条由水平和垂线组成的，在这些点处转角的闭回路。2. 在闭回路上调整，选一个出基， (r,s)进基：(i,j)： (i,j)为闭回路上奇点 ，(i,j)： (i,j)为闭回路上偶点 ， (r,s)为第一个奇点 )调整： 上的 格子运量增加 上 格子运量减少(p,q)出基，右下角不填。
