3.2 表上作业法.ppt

《3.2 表上作业法.ppt》由会员分享，可在线阅读，更多相关《3.2 表上作业法.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一一.表上作业法的基本思想和基本步骤：表上作业法的基本思想和基本步骤：基本可行解基本可行解是否为最优解是否为最优解换基换基结束结束YN1.1.基本思想基本思想：同：同单纯形法单纯形法的基本思想的基本思想2 2.特点特点1)1)约束条件非常有规律，技术系数非约束条件非常有规律，技术系数非 0 即即 1;2)2)基变量基变量(m+n-1)的个数远小于决策变量的个数远小于决策变量(mn)的个数的个数;3)3)产销平衡的产销平衡的产销平衡的产销平衡的运输问题一定存在最优解运输问题一定存在最优解;4)4)4)4)运算中涉及两个表：单位运价表和产销平衡表运算中涉及两个表：单位运价表和产销平衡表4 4.思路

2、思路首先将问题用首先将问题用表格形式表格形式予以表达予以表达 求求出出一个一个初始初始基基可行解可行解 然后进行然后进行判优判优，迭代迭代以改善解以改善解 直到求出直到求出最优解最优解为止为止1 1 1 1）L.P.L.P.方法只能使用于小、中型问题方法只能使用于小、中型问题（若有（若有 100 100 个起运点和个起运点和 1000 1000 个目的地时，变量个目的地时，变量将有将有100,000 100,000 个）个）2 2 2 2）表上作业法表上作业法可以可以简化计算，对大型问题简化计算，对大型问题更有效率更有效率3.3.方法的比较方法的比较某公司经销一种产品，它下设三个工厂、四个销售

3、部。某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：三个工厂的日产量分别为：A A1 177吨，吨，A A2 244吨，吨，A A3 399吨；吨；各销售部的日销量分别为：各销售部的日销量分别为：B B1 133吨，吨，B B2 266吨，吨，B B3 355吨，吨，B B4 466吨。吨。各厂到各销售部的单位产品的运价如下表。各厂到各销售部的单位产品的运价如下表。问该公司应如何调运产品，才能完成运输任务而使运费最省。问该公司应如何调运产品，才能完成运输任务而使运费最省。例例1:1:x11+x12+x13+x14 =7 x21+x22+x23+x24 =4 x31+x3

4、2+x33+x34=9 x11 +x21 +x31 =3 x12 +x22 +x32 =6 x13 +x23 +x33 =5 x14 +x24 +x34=6 xij0 (i=1,2,3;j=1,2,3,4)(1)(1)(1)(1)先用线性规划法处理此问题。先用线性规划法处理此问题。设由产地设由产地i i到销地到销地j j的运量为的运量为x xij ij,模型为：模型为：3x11+11x12+3x13+10 x14+x21 +9x22+2x23+8x24+7x31+4x32+10 x33+5x34min z=产销平衡表产销平衡表单位运价表单位运价表 (2)(2)(2)(2)运输问题一般用运输问题

5、一般用表上作业法表上作业法求解，求解，需建立表格模型：需建立表格模型：(1)(1)(1)(1)给出初始调运方案给出初始调运方案。初始基可行解：初始基可行解：即在有即在有(mnmn)个空格的产销平衡表上给出个空格的产销平衡表上给出 (m+n-1)(m+n-1)个数字格个数字格。一般用一般用最小元素法，最小元素法，VogelVogel法法，西北角法，西北角法;(2)(2)(2)(2)求各求各非基非基变量的检验数，变量的检验数，即在表上计算空格的检验数。即在表上计算空格的检验数。从而判断检验方案是否达到最优从而判断检验方案是否达到最优,若是最优解若是最优解,则停止计算则停止计算;否则转下一步否则转下

6、一步。用用闭回路法、位势法闭回路法、位势法求检验数；求检验数；表上作业法步骤类似于单纯形法表上作业法步骤类似于单纯形法:表上作业法表上作业法是单纯形法在求解运输问题时的一是单纯形法在求解运输问题时的一种简化方法，种简化方法，其实质是单纯形法。其实质是单纯形法。5.5.步骤步骤:(3)(3)(3)(3)调整调运方案，得新的方案。调整调运方案，得新的方案。即即改进当前的基本可行解改进当前的基本可行解 (确定入基和出基变量确定入基和出基变量)，找出新的基可行解。找出新的基可行解。在表上用在表上用闭回路调整法闭回路调整法；(4)(4)(4)(4)重复重复(2),(3)(2),(3)直到求出最优方案。直

7、到求出最优方案。表表上上作作业业法法计计算算步步骤骤框框图图分析实际问题分析实际问题列出产销平衡表列出产销平衡表及单位运价表及单位运价表确定初始调运方案确定初始调运方案(最小元素法或最小元素法或VogelVogel法法)求检验数求检验数(闭回路法或位势法闭回路法或位势法)所有检验数所有检验数 0 0找出绝对值最大的负检验数，找出绝对值最大的负检验数，用闭回路调整法，得出新的调用闭回路调整法，得出新的调运方案运方案得到最优方案得到最优方案算出总的运价算出总的运价是是否否二二 表上作业法的具体步骤和方法表上作业法的具体步骤和方法1.1.1.1.确定初始基可行解确定初始基可行解确定初始基可行解确定初

8、始基可行解运输问题必存在最优解。运输问题必存在最优解。确定初始基可行解的方法很多，确定初始基可行解的方法很多，有西北角法，有西北角法，最小元素法和伏格尔最小元素法和伏格尔(Vogel)(Vogel)法法。一般希望的方法是既简便，又尽可能接近最优解。一般希望的方法是既简便，又尽可能接近最优解。下面介绍后两种方法：下面介绍后两种方法：初始基可行解的确定初始基可行解的确定初始基可行解的确定初始基可行解的确定 -（1 1）最小元素法）最小元素法）最小元素法）最小元素法基本思想：基本思想：就近优先供应，就近优先供应，即从单位运价表中的即从单位运价表中的最小运价最小运价c cij ij 开始确定调开始确定

9、调运量运量,然后再由然后再由次小运价次小运价确定调运量确定调运量,依次下去，依次下去，直到最后供完为止就给出了初始基可行解直到最后供完为止就给出了初始基可行解。314633最后在最后在(A(A1 1,B,B4 4)的交叉格处填上的交叉格处填上3 3，将将A A1 1行和行和B B4 4列运价同时划列运价同时划去去，得到一个初始调运方案。，得到一个初始调运方案。单单位位运运价价表表产产销销平平衡衡表表3 31 14 46 63 33 3数字格的个数数字格的个数=3+4-1(=3+4-1(即即m+n-1)m+n-1)数字格数字格：基变量基变量空格空格：非基变量非基变量该初始方案的总运费该初始方案的

10、总运费（3 31 1）（6 64 4）（）（4 43 3）（1 12 2）（3 31010）（3 35 5）8686元元 单位运价表单位运价表产销平衡表产销平衡表初始基本可行解为:(x13,x14,x21,x23,x32,x34)=(4,3,3,1,6,3)相应运价为：（c13,c14,c21,c23,c32,c34）=（3,10,1,2,4,5）基本步骤：基本步骤：基本步骤：基本步骤：1).1).1).1).在单位运价表中找出在单位运价表中找出最小的运价最小的运价c cij ij ,其其 对应的变量对应的变量x x ij ij 优先赋值优先赋值x xij ij =min(amin(ai i,

11、b bj j),),2).2).2).2).使该行或列对应的供或求得到满足，在产使该行或列对应的供或求得到满足，在产 销平衡表中填对应的供求数值，销平衡表中填对应的供求数值，3).3).3).3).在单位运价表中划去该行或列，以示不需在单位运价表中划去该行或列，以示不需 再予供应，再予供应，4).4).4).4).在剩余的单位运价表中做同样的操作，直在剩余的单位运价表中做同样的操作，直 到单位运价表中所有的元素都被划去为止。到单位运价表中所有的元素都被划去为止。表上作业法表上作业法要求要求要求要求：调运方案的调运方案的数字格数字格必须为必须为m+n-1m+n-1个，个，且有且有数字格不构成闭回

12、路数字格不构成闭回路。一般用最小元素法给出的方案符合这要求。一般用最小元素法给出的方案符合这要求。用最小元素法给出的初始解是运输问题的基可行解用最小元素法给出的初始解是运输问题的基可行解用最小元素法给出的初始解是运输问题的基可行解用最小元素法给出的初始解是运输问题的基可行解，其理由为：其理由为：(1)数字格给出了数字格给出了(m+n-1)个值。个值。数字格数字格(m+n-1):m+n-1):基变量基变量空格：空格：非基变量非基变量 (2)这这(m+n-1)个数字格个数字格 所对应的系数列向量是所对应的系数列向量是 线性独立的线性独立的。证证:若表中确定的第一个基变量为若表中确定的第一个基变量为

13、x i1 j1 ，它对应的，它对应的系数列向量为系数列向量为:因当给定因当给定x i1 j1的值后，将划去第的值后，将划去第i1行或第行或第j1列列，类似地给出第二个，类似地给出第二个，第，第(m+n-1)个。个。因而因而 P i1 j1不可能用解中的其他向量的线性组合表示不可能用解中的其他向量的线性组合表示即其后的系数列向量中再不出现即其后的系数列向量中再不出现ei1或或em+j1，这这(m+n-1)(m+n-1)个向量都不可能用解中的其他向量的线个向量都不可能用解中的其他向量的线性组合表示。性组合表示。故这故这(m+n-1)(m+n-1)个向量是线性独立的。个向量是线性独立的。用最小元素法

14、给出的初始解是运输问题的基可行解用最小元素法给出的初始解是运输问题的基可行解即即数字格里为基变量的取值数字格里为基变量的取值，空格为非基变量的取值空格为非基变量的取值注意注意注意注意:1 1 1 1）用最小元素法给出初始解时，用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列在单位运价表上同时划去一行和一列(即产地和销地都得到满足即产地和销地都得到满足)。为保证基变量的个数仍是为保证基变量的个数仍是m+n-1,m+n-1,要在该行或列某空格要在该行或列某空格(相应运价未被划掉相应运价未被划掉)处填一个处填一个0,0

15、,该该0 0看作数字格看作数字格,即基变量的取值为即基变量的取值为0,0,这时这时 得到的解为退化解。得到的解为退化解。2 2 2 2）当单位运价表中同时有两个相同的最小值时，任当单位运价表中同时有两个相同的最小值时，任取其一即可。取其一即可。最小元素法中的退化情况最小元素法中的退化情况第一次划去第第一次划去第1 1列列B B1 1，第二次最小运价为第二次最小运价为2 2，对应，对应的销地的销地B B2 2销量和产地销量和产地A A3 3的产量未分配量皆为的产量未分配量皆为6 6，故，故同时划去同时划去B B2 2列和列和A A3 3行。非零的数字格小于行。非零的数字格小于(m+n-1)(m+

16、n-1)个。个。出现退化时，要在同时被划去的行列中任选一个出现退化时，要在同时被划去的行列中任选一个空格填空格填0 0，此格作为数字格。，此格作为数字格。345602基本思想基本思想基本思想基本思想：一产地的产品假如不能按最小运费就近供应，一产地的产品假如不能按最小运费就近供应，一产地的产品假如不能按最小运费就近供应，一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。就应考虑次小运费。就应考虑次小运费。就应考虑次小运费。这就有一个差额，这就有一个差额，这就有一个差额，这就有一个差额，差额越大，说明不能按最小运费调运时，运费差额越大，说明不能按最小运费调运时，运费差额越大，说明不能按最小

17、运费调运时，运费差额越大，说明不能按最小运费调运时，运费增加越多。增加越多。增加越多。增加越多。因而对差额最大处，就应当采用最小运费调运。因而对差额最大处，就应当采用最小运费调运。因而对差额最大处，就应当采用最小运费调运。因而对差额最大处，就应当采用最小运费调运。初始基可行解的确定初始基可行解的确定 -（2 2）伏格尔法）伏格尔法(Vogel)(Vogel)：最小元素法的缺点是：最小元素法的缺点是：最小元素法的缺点是：最小元素法的缺点是：为了节省一处的费用，为了节省一处的费用，有时会造成在其他处要多花几倍的运费。有时会造成在其他处要多花几倍的运费。做法：做法：1 1）.分别计算出各行和各列的罚

18、数。分别计算出各行和各列的罚数。分别计算出各行和各列的罚数。分别计算出各行和各列的罚数。（罚数（罚数（罚数（罚数=次小费用次小费用次小费用次小费用-最小费用）最小费用）最小费用）最小费用）2 2）.找出最大的罚数找出最大的罚数找出最大的罚数找出最大的罚数,选择它所在的行或列所对应的选择它所在的行或列所对应的选择它所在的行或列所对应的选择它所在的行或列所对应的 最小费用最小费用最小费用最小费用,进行优先安排。进行优先安排。进行优先安排。进行优先安排。3 3）.重复计算步骤重复计算步骤重复计算步骤重复计算步骤1 1和和和和2 2。2 5 1 3 2 5 1 3 0 0 1 1 1 1 6 6 2

19、1 3 2 1 3 0 0 1 1 2 2 3 3 2 1 2 2 1 2 0 0 1 1 3 3 1 2 1 2 7 7 6 6 5 52 21 1当产销地的数量不多当产销地的数量不多时，伏格尔法给出的时，伏格尔法给出的初始方案有时就是最初始方案有时就是最优方案，故常优方案，故常用该法用该法求运输问题最优方案求运输问题最优方案的近似解的近似解本题用本题用VogelVogel法确定的初始法确定的初始解即为最优解解即为最优解1).对对单位运价表单位运价表中求出各行中求出各行和和各列的各列的最小运费和最小运费和 次小运费的差额罚数次小运费的差额罚数 从从行罚数和列罚数行罚数和列罚数中中选取选取最大

20、最大者，再在它所在的行者，再在它所在的行或列中或列中选取选取最小最小元素元素2).在在产销平衡表产销平衡表中对应位置，仍按最小元素法的方法，中对应位置，仍按最小元素法的方法，填入可使该行或该列之一得到满足的数值填入可使该行或该列之一得到满足的数值3).在在单位运价表单位运价表中中划去该行或列划去该行或列，以示不需再予供应，以示不需再予供应4).在剩余的在剩余的单位运价表单位运价表中找出中找出各行和各列的最小运费各行和各列的最小运费和次小运费的差额和次小运费的差额，直到单位运价表中，直到单位运价表中所有的元素所有的元素都被划去为止都被划去为止基本步骤：基本步骤：当同时有两个差额最大时，选取运费较

21、小的一个当同时有两个差额最大时，选取运费较小的一个.注意的问题：注意的问题：由以上可见：由以上可见：伏伏格格尔尔法法同同最最小小元元素素法法除除在在确确定定供供求求关关系系的的原则上不同外，其余步骤相同。原则上不同外，其余步骤相同。伏伏格格尔尔法法给给出出的的初初始始解解比比用用最最小小元元素素法法给给出出的初始解更接近最优解。的初始解更接近最优解。表中所示基变量非负，且满足产销平衡约束表中所示基变量非负，且满足产销平衡约束条件，是为可行解条件，是为可行解 表中基变量个数应为表中基变量个数应为m+n-1m+n-1个，即个，即6 6个，但表个，但表 中所示不足，是为非基可行解中所示不足，是为非基

22、可行解例例 、下表给出的调运方案能否作为下表给出的调运方案能否作为 初始基可行解初始基可行解 最优性检验的判别方法最优性检验的判别方法:表格中有调运量的地方（数字格）为基变量，表格中有调运量的地方（数字格）为基变量，空格处为非基变空格处为非基变 量。量。基变量的检验数基变量的检验数ij ij0 0，非基变量非基变量 (空格空格)的检验数的检验数 c cij ij C CB B B B-1-1 P Pij ij。因运输问题的目标函数是要求因运输问题的目标函数是要求实现最小化实现最小化，故当所有的故当所有的 c cij ij C CB B B B-1-1 P Pij ij00时，为最优解。时，为最

23、优解。下面介绍两种求空格下面介绍两种求空格(非基变量非基变量)检验数的方法检验数的方法:1.1.闭回路法；闭回路法；2.2.位势法位势法2.2.最优性的判别最优性的判别最优性检验最优性检验 -（1）闭回路法）闭回路法闭回路：闭回路：闭回路：闭回路：从某一从某一空格出发空格出发，沿水平方向或垂直方向，沿水平方向或垂直方向前进前进,遇到遇到合适合适的的数字格可以旋转数字格可以旋转9090度度，继续前进，继续前进,若最后能回到出发点若最后能回到出发点,则所构成的回路为闭回路。则所构成的回路为闭回路。结论结论结论结论:在任何可行方案中在任何可行方案中,以空格以空格(i,ji,j)为一个顶点为一个顶点,

24、其其余顶点全是数字格的余顶点全是数字格的闭回路存在且唯一闭回路存在且唯一.minmin的非基变量检验数的非基变量检验数ij ij的经济意义的经济意义:在保持产销平衡的条件下在保持产销平衡的条件下,非基变量每增加一个单位运量而成为进基变量时非基变量每增加一个单位运量而成为进基变量时引起目标函数值引起目标函数值(总运费）的增量总运费）的增量.检验原理检验原理：利用检验数的经济意义利用检验数的经济意义 ij ij 0 0 0 表示总运费增加。表示总运费增加。作法作法:先从任意空格先从任意空格(i,j)处出发，作一闭回路处出发，作一闭回路给空格给空格(i,ji,j)一个单位的运量一个单位的运量,调整闭

25、回路上其余数字格的运量调整闭回路上其余数字格的运量,使达到产销平衡使达到产销平衡.则则闭回路上总运费的变化值等于空格闭回路上总运费的变化值等于空格(i,ji,j)的检验数的检验数.当所有的检验数都为正时，则为最优解当所有的检验数都为正时，则为最优解.(+1)(-1)(-1)(+1)3312奇点奇点偶点偶点经调运后，运费的变化值为：经调运后，运费的变化值为：3-3+2-1=13-3+2-1=1，即空格即空格(A(AI I,B,B1 1)的检验数为的检验数为1 1依次求出所有空格（非基变量）的检验数，当检依次求出所有空格（非基变量）的检验数，当检验数还存在负数时，说明原方案还不是最优解。验数还存在

26、负数时，说明原方案还不是最优解。B1B2B3B4产量产量A17A24A39销量销量365631363124111054 调运后总运费的变化值为：调运后总运费的变化值为：11 1110+510+54 4 2 2 空格空格(1,2)(1,2)的检验数为的检验数为2 2。B1B2B3B4产量产量A17A24A39销量销量36563136312149231054调运后总运费的变化值为：调运后总运费的变化值为：9 92+3-10+2+3-10+5-45-41 1空格空格(2,2)(2,2)的检验数为的检验数为1 1。B1B2B3B4产量产量A17A24A39销量销量36563136312-1431082

27、调运后总运费的变化值为：调运后总运费的变化值为：8-2+3-108-2+3-10-1-1空格空格(2,4)(2,4)的检验数为的检验数为-1-1。1B B1 1B B2 2B B3 3B B4 4产量产量产量产量A A1 17A A2 24A A3 39销量销量365631363121-11047123105 调运后总运费的变化值为：调运后总运费的变化值为：7-1+2-3+10-57-1+2-3+10-51010 空格空格(3,1)(3,1)的检验数为的检验数为1010。B B1 1B B2 2B B3 3B B4 4产量产量产量产量A17 7A24 4A3109 9销量销量3 36 65 5

28、6 631363121-1124103105调运后总运费的变化值为：调运后总运费的变化值为：10-3+10-510-3+10-51212 空格空格(3,3)(3,3)的检验数为的检验数为1212。检验数表检验数表1 1101012121 1-1-12 2 检验数中有负数，说明原方案不是最优解。检验数中有负数，说明原方案不是最优解。用闭回路法求检验数时，用闭回路法求检验数时，需给每一空格找一条闭回路。需给每一空格找一条闭回路。当产销点很多时，这种计算很繁。当产销点很多时，这种计算很繁。下面介绍较为简便的方法下面介绍较为简便的方法位势法。位势法。位势法。位势法。设设Y=(uY=(u1 1，u u2

29、 2，u umm;v;v1 1，v v2 2，v vn n)是对应是对应运输问题的运输问题的m+nm+n个约束条件的个约束条件的对偶变量对偶变量。运输问题的约束条件共有运输问题的约束条件共有m+nm+n个，个，其中前其中前mm个是产地产量的限制；个是产地产量的限制；后后n n个是销地销量的限制。个是销地销量的限制。其对偶问题也应有其对偶问题也应有m+nm+n个变量，个变量，其中其中前前mm个计为个计为u ui i（i=1.2i=1.2mm）,后后n n个计为个计为v vj j （j=1.2j=1.2n n）而每个决策变量而每个决策变量x xij ij的系数向量的系数向量P Pij ij=e e

30、i i+e+em+jm+j最优性检验最优性检验(2)位势法（对偶变量法）位势法（对偶变量法）j j =C C j j -C-CB B B B-1-1 P Pj j=C Cj j -Y-Y P Pj j ij ij =C C ij ij -C-CB B B B-1-1 P Pij ij=C Cij ij -Y-Y P Pij ij =C Cij ij -(u -(u1 1,u,u2 2,u,umm,v,v1 1,v,v2 2,v vn n)()(e ei i+e+em+jm+j)=C Cij ij -(-(u ui i+v vj j )当当x xij ij 为基变量为基变量时时 ij ij =C

31、 Cij ij -(-(u ui i+v vj j )=0 )=0 ，即，即C Cij ij =(=(u ui i+v vj j )由此，任选一个对偶变量为由此，任选一个对偶变量为0 0，可求出其余，可求出其余 所有的所有的u ui i，v vj j 。再根据再根据ij ij =C Cij ij -(-(u ui i+v vj j )求出所有求出所有非基变量非基变量 的检验数。的检验数。其中其中u ui i和和v vj j就是就是i i行和列的位势行和列的位势.从线性规划的对偶理论可知所有变量的检验数：从线性规划的对偶理论可知所有变量的检验数：该表是用该表是用最小元素最小元素法给出的法给出的初

32、始运输初始运输方案方案将初始运将初始运输方案输方案（上表）（上表）中有数字中有数字格的地方格的地方换上对应换上对应格的单位格的单位运价得下运价得下表表产销平衡表产销平衡表单位运价表单位运价表令令v v1 1=1=1因为因为v v1 1+u+u2 2=1=1，所以所以u u2 2=0.=0.因为因为u u2 2+v+v3 3=2=2，所以所以v v3 3=2.=2.因为因为v v3 3+u+u1 1=3=3，所以所以u u1 1=1.=1.因为因为u u1 1+v+v4 4=10=10，所以所以v v4 4=9=9因为因为v v4 4+u+u3 3=5 =5 ，所以，所以u u3 3=-4=-4

33、因为因为u u3 3+v+v2 2=4 =4 ，所以，所以v v2 2=8.=8.检验数检验数 3131=c=c3131-(-(u u3 3+v+v1 1)确定确定各行各列各行各列的一组的一组位势位势：使基变量中的：使基变量中的 c cij ij=u ui i+v+vj j其中其中u ui i和和v vj j即即i i行和列的行和列的位势位势单单位位运运价价表表cij10-41829ij=Cij-(Ui+Vj)Ui+VjCij表中还有负数，表中还有负数，说明还未得到说明还未得到最优解，应继最优解，应继续调整。续调整。位势法的原理位势法的原理v共有共有mm+n n 1 1个基变量个基变量x xi

34、j ij ，因此可得因此可得mm+n n 1 1个等式个等式 u ui i +v vj j=c cij ij 而一共有而一共有mm+n n个个 u ui i 和和 v vj j ，但可令任一个但可令任一个u ui i 或或 v vj j=0=0，从而解出其它从而解出其它 mm+n n 1 1个的值，这就是个的值，这就是位势法位势法.v若对所有非基变量有若对所有非基变量有 c cij ij z zij ij 0 0，即即 u ui i +v vj j c cij ij，表明当前表明当前u ui i 和和 v vj j 是对偶问题的可行解，是对偶问题的可行解，当前当前mm+n n 1 1个基变量个

35、基变量x xij ij 是原问题最优解，是原问题最优解，否则否则,从从 c cij ij z zij ij 0 0 中找中找最最小小者者，对应，对应x xij ij 就是就是入基变量入基变量。1.1.根据根据基变量的检验数为零基变量的检验数为零，2.2.确定各行各列的一组位势：使确定各行各列的一组位势：使c cij ij=u ui i+v+vj j，3.3.其中其中u ui i和和v vj j写到写到单位运价表单位运价表中的第中的第i i行右行右侧和第列下侧，侧和第列下侧，4.4.表示其行位势和列位势表示其行位势和列位势.2.2.任一任一空格空格(非基变量）非基变量）的检验数为的检验数为ij

36、ij=c cij ij-(u ui i+v vj j)任一任一有数字格（基变量）有数字格（基变量）的检验数为的检验数为 ij=cij-(ui+vj)=0基本步骤：基本步骤：当表中空格处出现负检验数时，当表中空格处出现负检验数时，表明当前平衡表给出的调运方案不是最优的，表明当前平衡表给出的调运方案不是最优的，需调整调运量，改进原调运方案，使总运费减少。需调整调运量，改进原调运方案，使总运费减少。改进原理同单纯形法一样。改进原理同单纯形法一样。调整方法调整方法调整方法调整方法：1.1.1.1.确定进基变量。确定进基变量。确定进基变量。确定进基变量。为使方案有较大的改进，为使方案有较大的改进，先确定

37、非基变量（空格）中最小的检验数，先确定非基变量（空格）中最小的检验数，即即minminij ij|ij ij 0 0=LK LK ,则则x x LK LK 入基入基;改进的方法闭回路调整法改进的方法闭回路调整法注意：注意：多个空格（非基变量）的检验数为负，多个空格（非基变量）的检验数为负，任一个都可作为进基变量。任一个都可作为进基变量。一般选一般选ij ij00中最小的负检验数所对应变量作为换中最小的负检验数所对应变量作为换入变量，入变量，目的是使运费尽可能的减少。目的是使运费尽可能的减少。6563销量销量9A34A27A1产量产量B4B3B2B1313463以以(2(2，4)4)格为调入格，

38、以此格为出发点，格为调入格，以此格为出发点，作一闭环回路。作一闭环回路。（+1）（1）（+1）（1）2 2。在。在最小负检验数最小负检验数所在的闭回路上，取所在的闭回路上，取偶点中运量最小的偶点中运量最小的，（以保证调整之后各分量仍是正值，即仍是基可行解），它即（以保证调整之后各分量仍是正值，即仍是基可行解），它即为为出基变量出基变量出基变量出基变量3 3。最小运量即为最小运量即为调整量调整量：闭回路上，闭回路上，奇点加调整量，偶点减奇点加调整量，偶点减调整量调整量，得到新的方案，得到新的方案.1 1。最小负检验数最小负检验数所对应的所对应的空格空格（非基变量），即为（非基变量），即为进基变量

39、进基变量进基变量进基变量运量调整后，必然使某个数字格变成零。把一个运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。变成零的数字格抹去，得新的调运方案。B1B2B3B4产量产量A1527A2314A3639销量销量36566563销量销量9A34A27A1产量产量B4B3B2B1313463（+1）（1）（1）（+1）注意：注意：调整后调整后只有三个数字格改变了，（只有三个数字格改变了，（1 1，3 3）、（）、（1 1，4 4）和（）和（2 2，3 3），还有三个数字格没有变，（），还有三个数字格没有变，（2 2，1 1）、（）、（3 3，2 2）和（）和（3 3

40、，4 4）。）。数字格总数数字格总数没有变化，没有变化，仍为仍为m+n-1m+n-12 2 2 2.确定出基变量。确定出基变量。确定出基变量。确定出基变量。在进基变量在进基变量x x LKLK 的闭回路中，取偶点的最小的闭回路中，取偶点的最小运量为调整量运量为调整量），），对应的变量为出基变量；对应的变量为出基变量；3 3 3 3.调整调运量调整调运量调整调运量调整调运量.在进基变量在进基变量x x LKLK 的闭回路中，的闭回路中，奇点对应的变量加上调整量奇点对应的变量加上调整量，偶点对应的变量减去调整量偶点对应的变量减去调整量，其余变量不变，得到一组新的可行解其余变量不变，得到一组新的可行

41、解 然后求此时所有非基变量的检验数重新检验然后求此时所有非基变量的检验数重新检验B1B2B3B4A10200A20210A390120经检验经检验所有所有ij ij00得到最优解，得到最优解，最小运费为最小运费为8585元。元。0v4v3v2v1u351047A3u28291A2u1103113A1B4B3B2B1成本表成本表c cij ij1039355242A328171A2010393A1B4B3B2B1(u ui i+v+vj j)ij ij=C Cij ij-(u-(ui i+v+vj j)B1B2B3B4产量产量A1527A2314A3639销量销量36563 30 07 70 0

42、例例例例 、将下表按闭回路调整法进行调整、将下表按闭回路调整法进行调整在需要减少运量在需要减少运量的地方有的地方有多个相多个相等的最小数，等的最小数，则则调整后原先空格调整后原先空格处填上这个最小处填上这个最小数，而原数，而原最小数最小数的位置都变为的位置都变为空空格格.继续继续计算中，计算中，要把最小数格之要把最小数格之一变为空格，其一变为空格，其余均补添余均补添0 0，并，并看作数字格，使看作数字格，使数字格数数字格数=m+n-=m+n-1 1 已知某运输问题的资料如下表所示已知某运输问题的资料如下表所示B1B2B3B4发量发量A1265315A2132112A3327413收量收量101

43、312540 表中的发量、收量单位为：吨，表中的发量、收量单位为：吨，运价单位为：元运价单位为：元/吨吨 试求出最优运输方案试求出最优运输方案.例：例：解：解：解：解：1 1 1 1、用最小元素法求初始方案用最小元素法求初始方案B1B2B3B4发量发量A112315A210212A313013收量收量1013125B1B2B3B4A153A211A324运费为运费为108108元元/吨吨2 2 2 2、用位势法判断用位势法判断：B1B2B3B4ui A153u1A211u2A324u3vj v1v2v3v4成本表成本表B1B2B3B4ui A1530A2112A3241vj 3153B1B2B

44、3B4ui A131530A211312A342641vj 3153(ui+vj)B1B2B3B4A12653A21321A33274B1B2B3B4A13153A21131A34264cijB1B2B3B4A11500A20410A31010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，调整运输方案。调整运输方案。ij(ui+vj)B1B2B3B4A1123A2102A3130B1B2B3B4A1105A2102A31302222新的运送方案新的运送方案B1B2B3B4A153A212A324新的成本（新的成本（c cij ij )B1B2B3B4ui A141530A

45、212203A352641vj 4153(u(ui i+v+vj j)1 1 总的运费总的运费 105105元元/吨吨B1B2B3B4A11500A20410A31010B1B2B3B4A14153A21220A35264B1B2B3B4A12653A21321A33274B1B2B3B4A12500A20501A32010表中还有负数，说表中还有负数，说明没有得到最优解，明没有得到最优解，继续调整运输方案。继续调整运输方案。cij(ui+vj)1 (ij)1 013A3210A2510A1B4B3B2B13512vj 14623A330221A203512A1ui B4B3B2B1(ui+v

46、j)2 42A32A2352A1B4B3B2B1新的成本表新的成本表cij013A312A25010A1B4B3B2B1新的运送方案新的运送方案总的运费总的运费 85元元/吨吨B1B2B3B4A12500A20501A32010B1B2B3B4A12653A21321A33274cijB1B2B3B4A12153A21 220A33264(ui+vj)2 B1B2B3B4A10500A22501A30010(ij)2 表中没有负数，说表中没有负数，说明已经得到最优解。明已经得到最优解。但有无穷多最优解。但有无穷多最优解。013A312A25010A1B4B3B2B1最终的运送方案最终的运送方案

47、总的运费总的运费 85元元/吨吨1 1 1 1 退化解退化解退化解退化解：有基变量取值为有基变量取值为0 0的解的解(a)(a)(a)(a)确定初始方案时候初始解退化。确定初始方案时候初始解退化。最小元素法取基可行解时：最小元素法取基可行解时：当出现同时划掉一行当出现同时划掉一行一列时，为使一列时，为使数字格的格数数字格的格数(基变量个数基变量个数)仍为仍为m+n-1m+n-1，可在对应的，可在对应的行或列行或列中的中的空格空格部分部分任选一格填任选一格填0 0。补充的原则：尽量先选运费小的实变量；补充的原则：尽量先选运费小的实变量；三三.表上作业法计算中的问题表上作业法计算中的问题-解的判别

48、解的判别3 36 60 0当出现同时划掉一当出现同时划掉一行一列时，为使数行一列时，为使数字格数，即基变量字格数，即基变量个数仍为个数仍为m+n-1，可在对应的行或列可在对应的行或列中的空格部分任选中的空格部分任选一格填一格填0.为使数字格数仍为为使数字格数仍为3+4-1=6,在对应的在对应的4个空格中任选一个空格中任选一格填格填0。这个填。这个填0的的格被当作数字格，格被当作数字格，即基变量看待即基变量看待.0 00 00 0例例例例、按最小元素法确定以下问题的初始基可行解按最小元素法确定以下问题的初始基可行解 （b b b b）闭回路调整中闭回路调整中：闭回路中，在需要减少运量的地方，基变

49、量同闭回路中，在需要减少运量的地方，基变量同时有多个达到最小时有多个达到最小,调整后原先空格处填上这个最小数，而有多个调整后原先空格处填上这个最小数，而有多个原基变量变为原基变量变为 0 0，就要把其中之一变为空格，就要把其中之一变为空格.原则是选运费最大者变为空格，即为出基变量，原则是选运费最大者变为空格，即为出基变量，其余均保留在新的基解中，即均补添其余均保留在新的基解中，即均补添0 0，并看，并看作数字格，使数字格数作数字格，使数字格数=m+n-1=m+n-12 2 2 2、无穷解、无穷解、无穷解、无穷解：运输问题必有最优解，当某个非基运输问题必有最优解，当某个非基变量（空格）的检验数为

50、变量（空格）的检验数为0 0时，该问题有无穷最时，该问题有无穷最优解优解.(max)初始单纯形表：初始单纯形表：通过通过加入加入松驰变量松驰变量，确定，确定初始基可行解初始基可行解最优性检验：当表中最优性检验：当表中所有检验所有检验数数 j j 0 0，则表中的则表中的基可行解基可行解就就是问题的是问题的最优解最优解从一个从一个基可行解基可行解转换到另一个转换到另一个目标函数目标函数值值更更大大的基可行解的基可行解，列出新的单纯形表列出新的单纯形表(1)1)确定确定进基进基变量变量(2)(2)确定确定出基出基变量变量一定是一定是minmin问题问题,应用应用最小元素法最小元素法或或VogelV