(5.2.1)--第14讲产销平衡问题的表上作业法.pdf

《(5.2.1)--第14讲产销平衡问题的表上作业法.pdf》由会员分享，可在线阅读，更多相关《(5.2.1)--第14讲产销平衡问题的表上作业法.pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运运 筹筹 学学 第第1414讲讲 产销平衡问题的表上作业法产销平衡问题的表上作业法 计算步骤：计算步骤：(1)找出初始调运方案。即在(mn)产销平衡表上给出m+n-1个数字格。(最小元素法或差值法）(2)求检验数。（闭回路法或位势法）判别是否达到最优解。如已是最优解，则停止计算，否则转到下一步。(3)对方案进行改善，找出新的调运方案。（表上闭回路法调整）确定m+n-1个基变量 (4)重复（2）、（3），直到求得最优调运方案。空格 第二节第二节 产销平衡问题的表上作业法产销平衡问题的表上作业法 初始基可行解初始基可行解最小元素法最小元素法 基本思想：基本思想：为了减少运费，应优先考虑单位运价最

2、小优先考虑单位运价最小(或运距或运距员短员短)的供销业务的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。一一、1、确定初始方案确定初始方案（初始基可行解初始基可行解）：最小元素法最小元素法，伏格尔法伏格尔法 例题1 某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工

3、厂的生产量、各销售点的销售量(单位为吨)以及各工厂到各销售点的单位运价(元吨)示于表中。问:要求产品如何调运才能使总运费最小?1A2A3A产 地销 地销 量1B2B3B4B产 量8141214161022428104311119648运 费512产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B1022164814828104812511963B12431114 用用最小元素法最小元素法产生基本可行解产生基本可行解:基本思想：优先安排单位运输成本最小的运输方式基本思想：优先安排单位运输成本最小的运输方式 2产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B22216

4、4814828104812511963B12431114210产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B222616 4814828104812511963B10431114210产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B2822 64814828104812511963B1043111421014产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B2864814828104812511963B104311614 210148产地产地 销地销地 产量产量 销量销量 1A3A2A4B1B2B2864814828104812511963B10

5、431162101486所以，初始基可行解为：所以，初始基可行解为：目标函数值目标函数值Z246 对每一个供应地或销售地，均可由它到各销售地或到对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出各供应地的单位运价中找出最小最小单位运价和单位运价和次小次小单位运价，单位运价，并称这两个单位运价并称这两个单位运价之差之差为该供应地或销售地的为该供应地或销售地的罚数罚数。沃格尔法基本思想沃格尔法基本思想：在罚数最大处采用最小运费调运。在罚数最大处采用最小运费调运。如果罚数的值不大，当不能按最小单位运价安排运输如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之

6、，如果罚数的值很大，不按时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。位运价安排运输。沃格尔法就是基于这种考虑提出来的。初始基可行解沃格尔法初始基可行解沃格尔法 .步骤：步骤：10 计算未划去行计算未划去行、列的差额；列的差额；20 找出最大差额对应的最小元素找出最大差额对应的最小元素cij进行供需分配；进行供需分配；30 在未被划去的行在未被划去的行、列重新计算差额列重新计算差额。分别计算各行、各列次小、最小运价的差额(罚数)，优先在最大差

7、额处进行供需搭配。沃格尔法计算步骤：沃格尔法计算步骤：销销 产产 B1 B2 B3 B4 供量供量 A1 7 A2 4 A3 9 销量销量 3 6 5 6 6 B1 B2 B3 B4 行差额行差额 A1 3 11 3 10 0 A2 1 9 2 8 1 A3 7 4 10 5 1 列差额列差额 2 5 1 3 销销 产产 B1 B2 B3 B4 供量供量 A1 7 A2 4 A3 9 销量销量 3 6 5 6 6 B1 B2 B3 B4 行差额行差额 A1 3 11 3 10 0 A2 1 9 2 8 1 A3 7 4 10 5 2 列差额列差额 2 1 3 3 销销 产产 B1 B2 B3

8、B4 供量供量 A1 7 A2 4 A3 9 销量销量 3 6 5 6 6 B1 B2 B3 B4 行差额行差额 A1 3 11 3 10 0 A2 1 9 2 8 1 A3 7 4 10 5 列差额列差额 2 1 2 3 3 销销 产产 B1 B2 B3 B4 供量供量 A1 7 A2 4 A3 3 9 销量销量 3 6 5 6 6 B1 B2 B3 B4 差额差额 A1 3 11 3 10 7 A2 1 9 2 8 6 A3 7 4 10 5 差额差额 1 2 3 5 1 2 17 2、最优解的判别最优解的判别（检验数的求法检验数的求法）要判别运输问题的某个解是否为最优解，可仿照一般单纯形

9、法，检验这个解的各非基变量（对应于运输表中的空格空格）的检验数。检验数。若有某空格的检验数为负，说明将其变成基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验所有空格的检验数全为非负数全为非负，则不管怎样变换，解均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解解就是最优解。（1）闭回路法闭回路法 销销 产产 B1 B2 B3 B4 供量供量 A1 5 2 7 A2 3 1 4 A3 6 3 9 销量销量 3 6 5 6 闭回路：闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。可以

10、证明：从每一空格出发一定存在和可以找到唯一的闭回路。销销 产产 B1 B2 B3 B4 产量产量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销量销量 3 6 5 6 3 1 4 6 3 3+-+-例如空格变量 x11的检验数：11=3-1+2-3=1 每一个每一个空格的检验数空格的检验数=奇顶点运费之和奇顶点运费之和 偶顶点运费之和。偶顶点运费之和。闭回路法计算检验数的经济解释闭回路法计算检验数的经济解释 销销 产产 B1 B2 B3 B4 产量产量 3 11 3 10 A1 7 1 9 2 8 A2 4 7 4 10 5 A3 9 销量销量 3 6

11、5 6 3 1 4 6 3 3+-+-若有某空格的检验数为负为负，说明将其变成基变量将使运输费用减少，故当前这个解不是最优解。若所有空格的检验数全为非负所有空格的检验数全为非负，则不管怎样变换，解均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解解就是最优解。例题2 设某产品从产地A1，A2，A3运往销地B1，B2，B3，B4，B5，运量和单位运价如下表所示，问如何调运才能使总的运费最少？销地 运价 产地 B1 B2 B3 B4 B5 产量（万吨）A1 7 10 8 6 4 40 A2 5 9 7 12 6 40 A3 3 6 5 8 11 90 销量（万吨）30 40 60 20

12、 20 位势法判别最优解举例位势法判别最优解举例 22 销地 运价 产地 B1 B2 B3 B4 B5 产量（万吨）A1 7 10 8 6 4 40 A2 5 9 7 12 6 40 A3 3 6 5 8 11 90 销量（万吨）30 40 60 20 20 30 40 60 20 20 0 0 解：用最小元素法得到的初始调运方案如下：23 第一步：将运价表中增加vj和ui列。第二步：利用数字格分别算出ui和vj，即 令u1=0，然后按ui+vj=Cij (i,jJB)，相继确定ui，vj的值。第三步：按ij=Cij (ui+vj)(i,jJN)算出表中各空格（即非基变量）的检验数：由于运输问

13、题的目标函数是求最小化，故判别最优解的准则是所有的非基变量的检验数：ij=CijCBB-1Pij0 即，只要有一个负检验数，所对应的方案就不是最优方案，尚须改进。位势法求检验数步骤位势法求检验数步骤 B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2 位势法举例位势法举例 B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2 8-3 7 位势表位势表)(jiijijvuc检验数检验数 B1B2B3B4ui311310A11928A274105A3vj 0 1 1 2 8-3 7 检验数表检验数表 1 2 1-1 10 12 24=-

14、10，当前方案，当前方案 不是最优方案。不是最优方案。27 i)确定进基变量：ii)作闭回路，确定调整量：从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格；从(p,q)空格开始给闭回路上的点按+1，-1，+1，-1编号，-1格的最小运量为调整量。iii)在闭回路上进行调整：对闭回路上每个对闭回路上每个-1顶点的调运量顶点的调运量，对闭回路上每个对闭回路上每个+1顶点顶点（含起始格含起始格）的调运量的调运量+。调整后，将闭回路中为0的一个数格作为空格（即出基变量）闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解)三三、闭回路调整法改进方案闭回路调整法改进方案 为换入变量pqp

15、qijjix ,)0(min,=min1，3=1 从从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，空格开始画闭回路，其它转角点都是填有运量的方格，并从并从(p,q)空格开始给闭回路上的点按空格开始给闭回路上的点按+1，-1，+1，-1编号，编号，-1格格的最小运量的最小运量为调整量。为调整量。换出变量 销地销地 产地产地 B1 B2 B3 B4 产量产量 A1 A2 A3 3 6 4(+1)1(-1)3(-1)(+1)3 7 4 9 销量销量 3 6 5 6 运量 为换入变量pqpqijjix ,)0(min,8511862401zz新的调运方案为：新的调运方案为：销地销地 产地

16、产地 B1 B2 B3 B4 产量产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量销量 3 6 5 6 销地销地 产地产地 B1 B2 B3 B4 产量产量 A1 A2 A3 3 6 4(+1)1(-1)3(-1)(+1)3 7 4 9 销量销量 3 6 5 6 销地销地 产地产地 B1 B2 B3 B4 产量产量 A1 A2 A3 3 6 5 2 1 3 7 4 9 销量销量 3 6 5 6 得到的一个解得到的一个解 需 供 B1 B2 B3 B4 ui A1 0 2 10 A2 2 1 8 A3 9 12 5 Vj -7-1-7 0 7 1 3 4 9 11 10 2 3

17、10 8 5 对应上述解的非基变量检验数对应上述解的非基变量检验数 3、表上作业法须注意的问题：表上作业法须注意的问题：（1）无穷多最优解）无穷多最优解 在前面提到，产销平衡的运输问题必定存在最优解。那么有唯一最优解还是无穷多最优解？依线性规划单纯性最优解判别标准，即某个非基变量（空格）的检验数为时，该问题有无穷多最优解。用表上作业法求解运输问题当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。有以下两种情况：（1）当确定初始解的各供求关系时，若在（i，j）格填入某数字后，出现i处的余量等于j处的需量，这时在产销平衡表上填一个数，而在单位运价表上相应地要划去一行和一列。为了使在产销

18、平衡表上有（m+n-1）个数字格。这时需要添一个“0”。它的位置可在对应同时划去的那行或那列的任一空格处对应同时划去的那行或那列的任一空格处。（2）在用闭回路法调整时，在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后，得到退化解。这时有一个数字格调必需填入一个0，表明它是基变量，当出现退化解后，并作改进调整时，可能在某闭回路上有标记为(-1)的取值为0的数字格，设应取调整量=0。（2）退化）退化 表上作业法求解步骤如下：所有ij0 Y N 根据问题条件列出产销平衡表和运费表 用最小元素法或差值法确定初始方案 用闭回路法或位势法求非基变量的检验数ij 最优方案，计算总运费，停。以绝对值最大的负检验数对应的非基变量作为起始变量作闭回路，求出调整量，调整的新的运输方案。练习练习1 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 2 9 10 7 1 3 4 2 8 4 2 5 9 5 7 销量 3 8 4 6 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 7 8 1 4 2 6 5 3 1 4 2 7 3 5 8 销量 2 1 7 6 练习练习2