北邮运筹学ch3-3表上作业法课件

设平衡运输问题的数学模型为：2/6/2023课件表上作业法也称为运输单纯形法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。2/6/2023课件3.3.1初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。2/6/2023课件B1B2B3可发量A186730A243545A374825未满足量603010100000【解】301510252015452020000产地销地2/6/2023课件【例4】求表3－7给出的运输问题的初始基本可行解。

B1B2B3B4aiA1311447A277384A3121069bj365620表3－72/6/2023课件【解】

B1B2B3B4aiA1311447A277384A3121069bj3656203××60×××4×16在x12、x22、x33、x34中任选一个变量作为基变量，例如选x12表3－82/6/2023课件2．运费差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。运费差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案，15151515前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105，后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85<Z1。2/6/2023课件基于以上想法，运费差额法求初始基本可行解的步骤是：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,…,m；同时求出每列次小运价与最小运价之差，记为vj，j=1，2，…，n；第二步：找出所有行、列差额的最大值，即L=max{ui，vi}，差额L对应行或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额，进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运方案。用运费差额法求得的基本可行解更接近最优解，所以也称为近似方案。2/6/2023课件【例5】用运费差额法求表3—9运输问题的初始基本可行解。

B1B2B3B4aiA15891215A2672425A311013820bj201052560表3—92/6/2023课件销地产地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××414—332200×××2/6/2023课件销地产地B1B2B3B4aiuiA1

5

8

9

1215A2

1

7

2

425A36

10

13

820bj201052560

vj

5××200×××—2—44—220×1052/6/2023课件基本可行解为总运费Z=10×8+20×1+5×2+20×8=270。求运输问题的初始方案还有很多方法，如左上角法、右上角法等。常用的方法是Vogel近似法、最小元素法。2/6/2023课件【解】用最小元素法得到下列一组基本可行解【例6】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij，矩阵右边的元素为产量ai

，下方的元素为销量bj。106040302/6/2023课件矩阵中打“×”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。求λ11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得2/6/2023课件同理可求出其它非基变量的检验数：这里λ34<0，说明这组基本可行解不是最优解。只要求得的基变量是正确的且数目为m+n－1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。2/6/2023课件加入松驰变量λij将约束化为等式ui+vj+λij=cij记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量λij当（i，j）时λij=0，因而有解上面第一个方程，将ui、vj代入第二个方程求出λij。2/6/2023课件【例7】用位势法求例7给出的初始基本可行解的检验数。【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。10604030令u1=0得到位势的解为2/6/2023课件再由公式求出检验数，其中Cij是非基变量对应的运价。计算结果与例7结果相同。2/6/2023课件3.3.3调整运量前面讲过，当某个检验数小于零时，基可行解不是最优解，总运费还可以下降，这时需调整运输量，改进原运输方案，使总运输减少，改进运输方案的步骤是：第一步：确定进基变量；第二步：确定出基变量，在进基变量xik的闭回路中，标有负号的最小运量作为调整量θ，θ对应的基变量为出基变量，并打上“×”以示作为非基变量。第三步：调整运量。在进基变量的闭回路中标有正号的变量加上调整量θ，标有负号的变量减去调整量θ，其余变量不变，得到一组新的基可行解，然后求所有非基变量的检验数重新检验。2/6/2023课件【例9】求下表所示的运输问题的最优解。表3－6

B1B2B3产量A186730A243545A374825销量603010100产地销地2/6/2023课件B1B2B3产量A186730A243545A374825销量60301010030151020[-1][2]25＋－＋－[-2]产地销地【解】前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：2/6/2023课件B1B2B3产量A186730A243545A374825销量60301010030151020[-1][2]25＋－＋－[-2]产地销地[2]【解】前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：2/6/2023课件B1B2B3A1867A2435A374830151020[-1][2]25[-2]产地销地[０]因为有２个负检验数，所以这组基本可行解不是最优解。取非基变量x32进基,用闭回路法调整如下闭回路如上图，标负号的运量是：x31=25、x22=30，取其最小值25作为调整量，在闭回路上x21、x32分别加上25，x31、x22分别减去25，调整后得到一组新的基可行解。＋－＋25－

405

2/6/2023课件B1B2B3产量A186730A243545A374825销量603010100540102520[-1][2]＋－＋－[2]再检验（表中括号中的数字为检验数）2/6/2023课件B1B2B3产量A186730A243545A374825销量603010100540102520[-1][2][4]＋－＋－[2]＋－再检验（表中括号中的数字为检验数）2/6/2023课件B1B2B3产量A186730A243545A374825销量603010100540102520[-1][2][4]＋－[2]＋－5

4515检验数l12=-1,方案需调整，下面用闭回路法调整2/6/2023课件B1B2B3产量A186730A243545A374825销量60301010025451015再计算一次检验数（表中括号中的数字