运输问题 表上作业法.ppt

《运输问题 表上作业法.ppt》由会员分享，可在线阅读，更多相关《运输问题 表上作业法.ppt（85页珍藏版）》请在三一办公上搜索。

1、4.2 表上作业法,表上作业法表上作业法与单纯形法的关系表上作业法的基本步骤确定初始基可行解最小元素法的基本步骤伏格尔法,三、运输问题的求解,运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。,表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。,1.表上作业法,2.表上作业法与单纯形法的关系,表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；表上作业法中的“位势法”实质上是在求单纯形表中的检验数；调运方案表中数字格的数实质上就是单纯形法中基变量的值；调运方案表上的

2、“闭回路法”实质上是在做单纯形表上的换基迭代。,（1）找出初始基可行解：m+n-1个数字格（基变量）；（2）求各非基变量（空格）的检验数。,那么,选取xij为入基变量；,（3）确定入基变量，若,3.表上作业法的基本步骤,（4）确定出基变量，找出入基变量的闭合回路；（5）在表上用闭合回路法调整运输方案；（6）重复2、3、4、5步骤，直到得到最优解。,4、确定初始基可行解,与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解）。最小元素法（the least cost rule）和伏格尔法（Vogels approximation method）。,最小元素法的基本思想是就

3、近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止.,最小元素法,找出最小运价，确定供求关系，最大量的供应；划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；在剩余的运价表中重复1、2两步，直到得到初始基可行解。,5、最小元素法的基本步骤,最小元素法,最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。,表4-1,最小元素法的应用（以引例4-1为例）,第一步：从表4-1中找出最小运价“1”，最小运价所确定的供应关系为（B，甲），在（B，甲）的交叉格处填上“3”，

4、形成表4-2；将运价表的甲列运价划去得表4-3.,表4-2,表4-3,3,第二步：在表4-3的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（B，丙），即将B余下的1个单位产品供应给丙，表4-2转换成表4-4。划去B行的运价，划去B行表明B所生产的产品已全部运出，表4-3转换成表4-5。,表4-3,表4-4,表4-5,3,1,表4-5,第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。,表4-7,表4-6,3,2,1,3,4,4,6,5,3,3,最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。

5、,最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。,在供需关系格（i，j）处填入一数字，刚好使第 i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。,6.应注意的问题,为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所

6、对应的变量是非基变量。,表4-7,表4-8,3,1,4,7.举例 将例4-1的各工厂的产量做适当调整（调整结果见表4-7），就会出现上述特殊情况。,0,6,6,每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。,8.伏格法尔法,伏格尔法的基本步骤：,8.伏格尔法,1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1

7、4步，直到得到初始基可行解。,表4-1,表4-12,1,3,0,1,1,2,5,4,表4-13,表4-14,6,2,1,3,0,1,2,5,表4-15,6,3,表4-16,2,1,2,0,1,1,表4-17,6,3,3,表4-18,1,2,6,7,3,表4-19,表4-20,6,3,3,5,2,8,1,2,总运费为85由以上可见，伏格尔法同最小元素法除在确定供求关系的原则上不同外，其余步骤是完全相同的。伏格尔法给出的初始解比最小元素法给出的初始解一般来讲会更接近于最优解。,表4-23,6,3,3,5,1,2,4.2.2 基可行解的最优性检验,对初始基可行解的最优性检验有闭合回路法和位势法两种基

8、本方法。闭合回路法具体、直接，并为方案调整指明了方向；而位势法具有批处理的功能，提高了计算效率。所谓闭合回路是在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭合回路。一个空格存在唯一的闭回路。,所谓闭合回路法，就是对于代表非基变量的空格（其调运量为零），把它的调运量调整为1，由于产销平衡的要求,我们必须对这个空格的闭回路的顶点的调运量加上或减少1。最后我们计算出由这些变化给整个运输方案的总运输费带来的变化。如果所有代

9、表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则继续迭代找出最优解。,1.闭合回路,下面就以表4-6中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论闭合回路法。,表4-24,（+3）,（-3）,（+2）,（-1）,从表4-6给定的初始方案的任一空格出发寻找闭合回路，如对于空格（A，甲）在初始方案的基础上将A生产的产品调运一个单位给甲，为了保持新的平衡，就要依次在（A，丙）处减少一个单位、（B，丙）处增加一个单位、（B，甲）处减少一个单位；即要寻找一条除空格（A，甲）之外其余顶点均为有数字格（基变量）组成的闭合回路。表4-24中用虚线画出了这条闭合回路。

10、闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。,对应这样的方案调整，运费会有什么变化呢？可以看出（A，甲）处增加一个单位，运费增加3个单位；在（A，丙）处减少一个单位，运费减少3个单位；在（B，丙）处增加一个单位，运费增加2个单位；在（B，甲）处减少一个单位，运费减少1个单位。增减相抵后，总的运费增加了1个单位。由检验数的经济含义可以知道，（A，甲）处单位运量调整所引起的运费增量就是（A，甲）的检验数，即11=1。,表4-24,（+3）,（-3）,（+2）,（-1）,仿照此步骤可以计算初始方案中所有空格的检验数，表4-25表4-30展示了各检验

11、数的计算过程，表4-30给出了最终结果。可以证明，对初始方案中的每一个空格来说“闭合回路存在且唯一”。,表4-25,表4-26,表4-27,表4-28,表4-29,表4-30,如果检验数表中所有数字均大于等于零，这表明对调运方案做出任何改变都将导致运费的增加，即给定的方案是最优方案。在表4-30中，24=-1,说明方案需要进一步改进。,2.位势法,对于特定的调运方案的每一行给出一个因子 ui（称为行位势），每一列给出一个因子vj（称为列位势），使对于目前解的每一个基变量xij 有cij=ui+vj，这里的ui 和 vj可正、可负也可以为零。那么任一非基变量 xij的检验数就是,这一表达式完全可

12、以通过先前所述的闭合回路法得到。在某一的闭合回路上（如下表所示），由于基变量的运价等于其所对应的行位势与列位势之和，即：,非基变量,基变量,（-cik）基变量,（+clk）基变量,于是,所以,对于一个具有m个产地、n个销地的运输问题，应具有m个行位势、n个列位势，即具有“m+n”个位势。运输问题基变量的个数只有“m+n-1”个，所以利用基变量所对应的“m+n-1”个方程，求出“m+n”个位势，进而计算各非基变量的检验数是不现实的。,通常可以通过在这些方程中对任意一个因子假定一个任意的值（如u1=0等等），再求解其余的“m+n-1”个未知因子，这样就可求得所有空格（非基变量）的检验数。仍以表4-

13、6中给出的初始基可行解（最小元素法所给出的初始方案）为例，讨论位势法求解非基变量检验数的过程。,第一步：把方案表中基变量格填入其相应的运价并令u1=0；让每一个基变量xij都有cij=ui+vj，可求得所有的位势，如表4-32所示。,表4-32,第二步：利用,计算各非基变量xij,的检验数，结果见表4-30。,10,3,-1,-5,9,2,0,4.2.3方案的优化,在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。在入基变量所处的闭合回路上，赋予入基变量最大的增量，即可完成方案的优化。在入基变量有最大增量的同时，一定存在原来的某一基变量减少为“0”，该变量即为出基变量。切记出基变

14、量的“0”运量要用“空格”来表示，而不能留有“0”。,在表4-30中，,，故选择,x24为入基变量。在入基变量x24所处的闭合回路上（如表4-33所示），赋予最大的增量“1”，相应地有x23最大的增量“1”，相应地有x23出基,x13=5,x14=2.,利用闭合回路法或位势法计算各空格（非基变量）的检验数，可得表4-34（同伏格尔法的初始解表4-23）。,表4-30,表4-33,表4-34,由于表4-33中的检验数均大于等于零，所以表4-33（同伏格尔法所给出的初始解表4-23）给出的方案是最优方案，这个最优方案的运费是85个单位。,23=1,31=9,22=2,11=1,12=2,33=12

15、,4.3运输问题的拓展,总产量大于总销量的运输问题即为产大于销的运输问题。在实际问题中，产大于销意味着某些产品被积压在仓库中。可以这样设想，如果把仓库也看成是一个假想的销地，并令其销量刚好等于总产量与总销量的差；那么，产大于销的运输问题就转换成产销平衡的运输问题 假想一个销地，相当于在原产销关系表上增加一列。,4.3.1产大于销的运输问题,假想列所对应的运价,由于假想的销地代表的是仓库，而我们优化的运费是产地与销地间的运输费用，并不包括厂内的运输费用；所以假想列所对应的运价都应取为“0”。,至此，我们已经将产大于销的运输问题转换成产销平衡的运输问题，进一步的求解可利用上节介绍的表上作业法来完成

16、。,例4-2 将表4-35所示的产大于销的运输问题转换成产销平衡的运输问题,表4-35,解 此运输问题的总产量为23、总销量为20，所以假设一个销地戊并令其销量刚好等于总产量与总销量的差“3”。取假想的戊列所对应的运价都为“0”，可得表4-36所示的产销平衡运输问题。,表4-36,4.3.2销大于产的运输问题,总销量大于总产量的运输问题即为销大于产的运输问题。可以这样设想，假想一个产地，并令其产量刚好等于总销量与总产量的差；那么，销大于产的运输问题同样可以转换成产销平衡的运输问题 假想的产地并不存在，于是各销地从假想产地所得到的运量，实际上所表示的是其未满足的需求。由于假想的产地与各销地之间并

17、不存在实际的运输，所以假想的产地行所有的运价都应该是“0”。至此，我们又将销大于产的运输问题转换成了产销平衡的运输问题。,例4-3 将表4-37所示的销大于产的运输问题转换成产销平衡的运输问题,表4-37,解 此运输问题的总产量为20、总销量为28，所以假设一个产地D并令其产量刚好等于总销量与总产量的差“8”。令假想的D行所对应的运价都为“0”，可得表4-37所示的产销平衡运输问题。,表4-38,4.3.3运输问题的应用举例,例4-4 设有三个化肥厂供应四个地区的化肥需求，假定等量化肥在这些地区的使用效果相同。各化肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的单位运价如表4-39

18、所示，试求出总的运费最节省的化肥调拨方案。,表4-39,根据现有产量，除满足地区1、地区2和地区3的最低需求外，地区4每年最多能分配到60万吨，这样其不限的最高需求可等价认为是60万吨。,解 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。,按最高需求分析，总需求为210万吨，大于总产量160万吨，将此问题定义为销大于产的运输问题。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，令其年产量为50万吨。各地区的需要量包含最低和最高两部分：如地区1，其中30万吨是最低需求，故这部分需求不能由假想的化肥厂D来供给，因此相应的运价定义为任意大正数M

19、；而另一部分20万吨满足与否都是可以的，因此可以由假想化肥厂D来供给，按前面讲的，令相应运价为“0”。,凡是需求分两种情况的地区，实际上可按照两个地区来看待，这样可以将表4-39所示的运输问题转换为表4-40所示的运输问题。,表4-40（单位：万吨）,用表上作业法计算，可以求得这个问题的最优方案,如表4-41所示。,19,0,30,2,14,0,2,15,3,1,0,0,2,14,0,2,15,3,1,0,0,0,30,20,2,2,0,2,2,3,1,0,0,0,30,20,13,50,5,5,7,M,M,3,1,0,0,0,30,20,13,50,15,10,5,5,7,M,M,3,1,0

20、,0,0,30,20,13,50,15,10,15,30,5,5,7,M,M,3,0,0,0,0,30,20,13,50,15,10,15,30,13,20,14,5,5,7,M,M,3,1,0,0,0,30,20,13,50,15,10,15,30,13,20,0,30,20,例4-6 在A1、A2、A3、A4、A5和A6六个经济区之间有砖、砂子、炉灰、块石、卵石、木材和钢材七种物资需要运输。具体的运输需求如表4-43所示，各地点间的路程（公里）见表4-44，试确定一个最优的汽车调度方案。,表4-43,表4-44,汽车的最优调度实质上就是空车行驶的公里数最少。先构造如表4-45所示的各地区汽

21、车出入平衡表，表中“十”号表示该点产生空车，“”号表示该点需要调进空车。,表4-44,平衡结果A1、A5、A6除装运自己的货物外，可多出空车21车次；A2、A3、A4缺21车次。按最小空驶调度，可构造表4-46所示的运输问题数据表，进而可得表4-47所示的最优调度方案。,表4-45,表4-46,作 业,课本P62：6、7题课本P63：8题,2023/8/27,第62页习题,6.已知某厂每月可生产甲产品270吨，先运至A1、A2、A3三个仓库，然后在分别供应B1、B2、B3、B4、B5五个用户。已知仓库容量分别为50、100、150吨，各用户的需要量分别为25、105、60、30、70吨。已知从

22、该厂经各仓库然后供应各用户的运费如下表所示，试确定一个使总运费最少的调运方案。,仓库总容量：50+100+150=300（t）各地区需求：25+105+60+30+70=290（t）由于该厂每月最多生产甲产品270t，则仓库有30t不满，各地区有20t不能满足需求可假设存在仓库A4，它的存储量为20t，用户B6 的需求量为30t。这样就转化为产销平衡问题。由于A4 与B6都是假设的，不需要运输，故运价都为0，但是由A4运到B6的运输无法发生，因两者皆为假设的，运价为无穷大，设为M。,此题属于产销不平衡问题,2023/8/27,第62页习题,用伏格尔法求解初始基可行解得：,数字格内填入相应价格，

23、用位势法检验是否为最优解，得：,用位势法检验是否为最优解，得：,因检验数存在负数，故需用闭合回路法调整,用闭合回路法调整得：,用位势法检验得：,因检验数全为正，所以已得最优方案。即A3差30t没有得到满足，B2缺5t，B4缺15t。,7、已知某运输问题的单位运价及最优调运方案如表所示（括号中的数据代表运输数量），由于产地A2至销地B2的道路关闭，故最优调运方案将发生变化，试在原最优调运方案的基础上，寻找新的最优调运方案。,表4-50,解：由于A2 到B2道路关闭，则其运价为M，应令其出基，以实现最优调度。先将M反映进产销平衡表，然后用位势法作检验，有：,要令A2 B2出基，即令其运输量为0，找

24、出负检验数最小的来进行调整，得：,用位势法作检验，有：,检验数已全为非负，故已得最优调度方案。,8、已知某运输问题的单位运价及最优调运方案如表4所示，试回答下述问题：(1)A1到B2、A3到B5、和A4到B1的单位运价，分别在什么范围内变化时上表中给出的最优方案不变；(2)若A1到B2的单位运价由1变为3，最优方案将发生怎样的变化；(3)若A3到B5的单位运价由4变为2，最优方案将发生怎样的变化；,2023/8/27,表4-51,解：（1）设A1 到B2的单位运价为c12，因A1 到B2是基变量，它的运价变化会引起非基变量检验系数的变化，此时，只需对其再进行位势法分析即可。,要令最优方案不变，

25、则非基变量的检验数非负；故有c12 0；3-c12 0；4-c12 0；2-c12 0；2+c120；1+c12 0解上述不等式得0 c12 2。即A1 到B2的单位运价在0，2内变化时，最有方案不变。,(1),A3 到B5的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其检验数非负即可。,先用位势法算出原方案的检验数：,设A3 到B5的单位运价为c35，则其检验数满足c35-（1+2）0，即c35 3。也就是说A3 到B5的单位运价大于等于3时，最有方案不变。,A4 到B1的单位运价属于非基变量，它的变化不会引起其它检验数变化，故只需保证其检验数非负即可。,设A4到B1的单

26、位运价为c41，则其检验数满足c41-（0+2）0，即c35 2。也就是说A4到B1的单位运价大于等于2时，即A4 到B1的单位运价变化范围是2，+)最有方案不变。,先用位势法算出原方案的检验数：,把变化直接反映到表中可得下表：,(2)若A1到B2的单位运价由1变为3，最优方案将发生怎样的变化；,因存在检验数为负数，最优方案发生改变，用闭合回路法调整得：,表4-51,重新计算检验数，得：,非基变量检验数均为非负，故为最优方案。,（3）把A3 到B5的单位运价改为2，然后求检验数得：,表4-51,由于存在负检验数，故最优方案发生变化，此时用闭合回路法调整得：,重新计算检验数，得：,检验数全为非负，故已得最优方案。,65,15,50,20,43=-15,5,15,55,42=-10,5,50,70,