运筹学运输问题.ppt

《运筹学运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学运输问题.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、回回 顾顾w 运输问题的数学模型及其特点；运输问题的数学模型及其特点；w 运输问题解法运输问题解法表上作业法；表上作业法；（两个表格：产销平衡表，单位运价表）（两个表格：产销平衡表，单位运价表）w 表上作业法中初始基可行解的确定方法：表上作业法中初始基可行解的确定方法：最小元素法；最小元素法；Vogel法（最大差额法）法（最大差额法）w 闭回路的建立与闭回路法求解检验数闭回路的建立与闭回路法求解检验数11、运输问题的数学模型、运输问题的数学模型22、最小元素法确定初始基可行解的步骤、最小元素法确定初始基可行解的步骤w步骤一：步骤一：确定第一个基变量确定第一个基变量 方法：（方法：（1）从）从单

2、位运价表单位运价表中，找出中，找出最小运价最小运价；（；（2）对于对于最小运价处最小运价处，用所在用所在行的产量行的产量最大限度最大限度满足销售量满足销售量（所在列）（所在列）的需求的需求。将。将满足之数满足之数填入填入填入填入产销平衡表产销平衡表产销平衡表产销平衡表中中中中相应相应相应相应的位置处的位置处的位置处的位置处；（；（3）观察）观察产和销的关系产和销的关系：1）如果）如果产量产量用完用完，则则划去划去所在所在行行的的单位运价信息单位运价信息；如果如果销量销量得到满足得到满足，则，则划去所在划去所在列列的单位运价的单位运价信息信息。（注意产量和销量的变。（注意产量和销量的变化）化）w

3、步骤二：确定第二个基变量步骤二：确定第二个基变量 方法：在方法：在剩下剩下的单位运价信息中，寻找的单位运价信息中，寻找最小值最小值。按。按照上述方法进行操作。照上述方法进行操作。33、伏格尔方法（、伏格尔方法（Vogel）确定初始基可行解）确定初始基可行解主旨：主旨：最大差额处，优先按最大差额处，优先按最小运价最小运价进行调运。进行调运。第一步第一步：计算：计算单位运价表单位运价表中同行、同列的中同行、同列的最小运费与次小最小运费与次小运费之差运费之差，分别列在，分别列在单位运价表单位运价表的的最右列和最下行最右列和最下行（行（行差和列差差和列差）。）。第二步：对第二步：对行差和列差进行对比行

4、差和列差进行对比，找出，找出最大差额最大差额。以与。以与最最大差额值同行（或同列）大差额值同行（或同列）的的最小运价最小运价为准，为准，倾所在倾所在行的行的产量产量，最大限度最大限度地满足地满足所在列的需求所在列的需求；一旦需求（或库；一旦需求（或库存）被彻底满足（或库存调光），则存）被彻底满足（或库存调光），则随即划去该列（或随即划去该列（或行）的所有运价信息行）的所有运价信息。（注意产量和销量的变化。（注意产量和销量的变化）第三步：重新计算同行同列的第三步：重新计算同行同列的最小运费与次小运费之差最小运费与次小运费之差，并对其它未被确定调拨值的行列，重复第二步的处理，并对其它未被确定调拨值

5、的行列，重复第二步的处理，直至构造出某直至构造出某初始调拨方案初始调拨方案（初始解）。（初始解）。44、最优性检验的核心思想、最优性检验的核心思想w1、最优、最优检验判断思路检验判断思路：确定初始基可行解后，调：确定初始基可行解后，调查非基变量取值变化对总运费的影响。查非基变量取值变化对总运费的影响。w2、实现方法实现方法：在确定的初始基可行解基础上，当：在确定的初始基可行解基础上，当非基变量有取值时非基变量有取值时，考虑，考虑总的运费的变化情况总的运费的变化情况？（1）如果所有情况下）如果所有情况下总费用均增加总费用均增加，证明初始方案为，证明初始方案为最最优优；（2）一旦出现了）一旦出现了

6、总费用降低总费用降低，代表给，代表给该非基变量安该非基变量安排运量排运量可更优，说明最初方案需要优化。可更优，说明最初方案需要优化。w3、需要解决的问题需要解决的问题：当非基变量取值时，为保证：当非基变量取值时，为保证产销平衡表上的产销平衡，会引起已确定的产销平衡表上的产销平衡，会引起已确定的基变基变量的连锁变化，量的连锁变化，导致相应的导致相应的行或列基变量的波动行或列基变量的波动。需要靠需要靠闭回路法闭回路法来确定基变量的变动情况。来确定基变量的变动情况。55、闭回路法的构造、闭回路法的构造w（1）闭回路）闭回路：调运方案调运方案中由中由一个空格一个空格（非基变量）和（非基变量）和若干个有

7、数字格若干个有数字格（基变（基变量）的量）的水平和垂直连线水平和垂直连线所组成的所组成的回路回路。w（3）闭回路的构造方法）闭回路的构造方法：从选中的空格：从选中的空格（非基变量）出发，沿水平或铅垂方向（非基变量）出发，沿水平或铅垂方向前进，确保前进，确保只以途中的有数字格（基变只以途中的有数字格（基变量）为拐点实施转向量）为拐点实施转向，直到，直到返回返回出发的出发的空格（非基变量）空格（非基变量）。6闭闭回路形式回路形式76、利用闭回路法计算非基变量检验数方法、利用闭回路法计算非基变量检验数方法 1）参考产销平衡表，）参考产销平衡表，建立非基变量检验数表建立非基变量检验数表，用于填，用于填

8、写各非基变量的检验数；写各非基变量的检验数；2）以确定的）以确定的初始（或前一可行）调运方案表初始（或前一可行）调运方案表为准，寻为准，寻找每个找每个非基变量的闭回路非基变量的闭回路；3）在每个非基变量的闭回路上，计算当）在每个非基变量的闭回路上，计算当非基变量由非基变量由“0”变为变为“+1”时，时，基变量的取值变化规律（基变量的取值变化规律（+1，还是，还是-1）；4）利用）利用单位运价表单位运价表中与闭回路相对应的运价信息，计中与闭回路相对应的运价信息，计算运费的变化情况（算运费的变化情况（非基变量单位运价非基变量单位运价-处于奇数位置的基变处于奇数位置的基变量的单位运价量的单位运价+处

9、于偶数位置的基变量的单位运价处于偶数位置的基变量的单位运价），即为非基），即为非基变量检验数；变量检验数；5）将非基变量检验数填入检验数表中相应位置。）将非基变量检验数填入检验数表中相应位置。8 销地销地产地产地B1B2B3B4产量产量A1非基变非基变量量1（3）非基变非基变量量2（11）4（3）3（10）7A23（1）非基变非基变量量3（9）1（2）非基变非基变量量4（8）4A3非基变非基变量量5（7）6（4）非基变非基变量量6（10）3（5）9销量销量3656利用闭回路法计算非基变量检验数利用闭回路法计算非基变量检验数方法方法A1B1非基变量：A1B1+1，A1B3-1，A2B3+1，A2

10、B1-1.运费影响：3-3+2-1=10（即为此非基变量的检验数）。A2B2非基变量：A2B2+1，A2B3-1，A1B3+1，A1B4-1，A3B4+1，A3B2-1.运费影响：9-2+3-10+5-4=10。非基变量非基变量4：A2B4-1，A1B4+1,A1B3-1,A2B3+1。运费影响：运费影响：8-10+3-2=-10。9 销地销地产地产地B1B2B3B4A112A21-1A31012非基变量检验数表非基变量检验数表非基变量非基变量A2B4的检验数小于的检验数小于0，表明在，表明在A2B4处安处安排运量可以带来更低的运费排运量可以带来更低的运费如何调整如何调整?107、问、问 题题

11、w 对于每一个非基变量，需要重复寻找闭对于每一个非基变量，需要重复寻找闭回路，并计算回路，并计算“非基变量非基变量+1”时对总运费时对总运费的影响的影响繁琐繁琐。w 当出现检验数当出现检验数0，证明原初始方案或改，证明原初始方案或改进方案还不是最优进方案还不是最优如何进行基变量的如何进行基变量的调入调出？调入调出？采用位势法一次全部计采用位势法一次全部计算出所有检验数算出所有检验数给检验数给检验数0的非基变量赋值，越大的非基变量赋值，越大越好。但要考虑产销平衡问题。越好。但要考虑产销平衡问题。118、运输问题的校验方法、运输问题的校验方法2 位势法位势法利用行位势和列位势两类数据，将检验数与利

12、用行位势和列位势两类数据，将检验数与单位运价联系起来单位运价联系起来12检检 验验 数数 方方 程程ij=cij ui vjui ，vj 行位势行位势 列位势列位势单位运价单位运价m个产地，个产地，n个销地时，则需要确定个销地时，则需要确定m个个行位势，行位势，n个列位势个列位势13一般令基变量的一般令基变量的 ij=0，故确定故确定ui与与vj可借助基变量的位势方程组来确定可借助基变量的位势方程组来确定ui+vj=cij（基变量对应的单位运价）（基变量对应的单位运价）它总共含有它总共含有 m+n 1 个方程，确定个方程，确定m+n个未知个未知数数，一般可以令某一个位势，一般可以令某一个位势为

13、为0或或1或者任何数或者任何数，通过上述关系即可确定所有的位势。通过上述关系即可确定所有的位势。14A、位势法求检验数的步骤、位势法求检验数的步骤w第一步第一步：根据最小元素法或：根据最小元素法或Vogel法确定的法确定的初始运量表初始运量表做做一表格一表格，将基变量（或运量）数据替换成，将基变量（或运量）数据替换成与之对应的单位与之对应的单位运价运价；（或对单位运价表进行修改，只保留与基变量对应的运价信；（或对单位运价表进行修改，只保留与基变量对应的运价信息）息）w第二步第二步：在：在右侧增加一列右侧增加一列，下侧增加一行下侧增加一行，用于填写位势，用于填写位势数据。数据。右侧表示行位势右侧

14、表示行位势ui（i=1，2.m），下侧表示），下侧表示列位势列位势vj（j=1，2.n）；）；w第三步第三步：对于：对于基变量对应的单位运价处基变量对应的单位运价处，ui+vj=cij。随便。随便确定任一个位势确定任一个位势，即可求解全部行和列位势；，即可求解全部行和列位势；w第四步第四步：在：在非基变量对应的空格处非基变量对应的空格处，计算检验数，计算检验数ij=cij-（ui+vj）。）。并将检验数并将检验数填入检验数表填入检验数表中；中；w第五步第五步：判断检验数：判断检验数ij是否大于是否大于0，如是，则表示较优。，如是，则表示较优。如不是，则需要调整基变量。如不是，则需要调整基变量。

15、w第六步：第六步：基变量的调整采用闭回路法进行基变量的调整采用闭回路法进行。15 销地销地产地产地B1B2B3B4A143A23 1 A363 销地销地产地产地B1B2B3B4A1310A212A345初初始始调调运运表表基变量的单位运价表基变量的单位运价表 销地销地产地产地B1B2B3B4A1311310A21928A374105+步骤一：建立基变步骤一：建立基变量的单位运价表量的单位运价表单位运价表单位运价表B、例子、例子 P8816步骤二：确定行位势与列位势取值步骤二：确定行位势与列位势取值 销地销地产地产地B1B2B3B4A1310A212A345基变量的单位运价表基变量的单位运价表u

16、iu1u2u3vjv1v2v3v41）对于基变量）对于基变量处，处，cij=ui+vj；2）任意确定一）任意确定一个位势即可。个位势即可。0103-12-5917步骤三：根据行位势与列步骤三：根据行位势与列位势取值计算非基变量检位势取值计算非基变量检验数验数 销地销地产地产地B1B2B3B4A1310A212A345uivj0103-12-591）对于非基变）对于非基变量处，检验数为量处，检验数为cij-（ui+vj）；）；2）结合非基变）结合非基变量对应的单位运量对应的单位运价，即可计算出价，即可计算出所有非基变量的所有非基变量的检验数。检验数。销地销地产地产地B1B2B3B4A131131

17、0A21928A3741051211012-118收点收点发点发点B1v1B2v2B3v3B4v4发量发量A1u1x119 18x131 109A2u2x2111x226 8 1810A3u3x3114 12 2x34166收量收量4975a=b行行位势位势ui与列位势与列位势vj的确定方法的确定方法初初始始调调运运表表79211509251411例例219 利用已确定好的利用已确定好的ui与与vj值，再结合值，再结合cij值计算非基变量的检验数值计算非基变量的检验数ij=cij(ui+vj)总共总共 (m 1)(n 1)个个20收点收点发点发点B19B24B31B411发量发量A10 x11

18、9 18x131 109A22x2111x226 8 1810A35x3114 12 2x34166收量收量4975a=b用行列位势用行列位势ui与与vj确定非基变量的检验数确定非基变量的检验数初初始始调调运运表表792115 14-1 55 3-421确定非基变量检验数后，如果非基变量检验确定非基变量检验数后，如果非基变量检验数数销销”情形：情形：产量盈余产量盈余，可，可虚拟虚拟一个销售地一个销售地（库存），让多余的产量均运抵此（库存），让多余的产量均运抵此销售地，则其销售地，则其销售量销售量=“产产-销销”，同时令该虚，同时令该虚拟的销售地的拟的销售地的单位运价为单位运价为0；（虚拟的销地

19、）；（虚拟的销地）w（2）对于）对于“销销产产”，可，可虚拟一个产地虚拟一个产地，让，让其其产量产量=“销销-产产”，同时令该虚拟的产地的，同时令该虚拟的产地的单单位运价为位运价为0.33例例 1 产大于销产大于销销地销地产地产地 B1 B2 B3产量产量 A1 A2 A3 5 9 2 3 1 7 6 2 8 151817销量销量 18 12 16504634解法：虚设一销地，令其销量为产销量之差。解法：虚设一销地，令其销量为产销量之差。b4=ai-bj=4 该列单位运价为该列单位运价为0，即可化为产销平，即可化为产销平衡问题衡问题销地销地产地产地 B1 B2 B3 B4产量产量 A1 A2

20、A3 5 9 2 0 3 1 7 0 6 2 8 0 151817销量销量 18 12 16 450=5035例例 2 产小于销产小于销 销销产产B1B2B3aiA141210A234312bj8105222336解法：虚设一销地，令其销量为产销量之解法：虚设一销地，令其销量为产销量之差差 b4=bj-ai=1 令令该列运价为该列运价为0，如此可化为产销平，如此可化为产销平衡问题。衡问题。37 销销产产B1B2B3aiA14 1 210A234312A30 001bj810523233810、运输问题的应用、运输问题的应用w短缺资源的分配问题短缺资源的分配问题 需求产地产量产量A1613221

21、750B1413191560C19202350最低最低需求需求3070010最高最高507030不限不限39 需求产地产量产量A1613221750B1413191560C19202350最低需最低需求求3070010最高需最高需求求507030不限不限必须满足必须满足最高和最低之最高和最低之间差额，不一间差额，不一定全额满足。定全额满足。问题分析问题分析1、产销量问题、产销量问题。产量。产量160，最低需求，最低需求110，最高需求无限，最高需求无限，但根据现有情况，最高总需求为但根据现有情况，最高总需求为210（因为（因为销地最多可销地最多可获得获得60），属于产销不平衡问题；），属于产销

22、不平衡问题；2、如何转换、如何转换成产销平衡成产销平衡问题？增加问题？增加假想产地。假想产地。3、将需求、将需求量化成两部量化成两部分，一部分分，一部分满足最低需满足最低需求，一部分求，一部分满足差额。满足差额。40 需求需求产地产地1212产量产量A16161322171750B14141319151560C19192023MM50D50销量销量302070301050步骤一：转化成产销平衡问题步骤一：转化成产销平衡问题解：增设产地丁，令其供应量为：最大需求量供应量解：增设产地丁，令其供应量为：最大需求量供应量50虚拟产地的运价如何确定？虚拟产地的运价如何确定？最小需求最高与最低需求差41

23、需求需求产地产地1212产量产量A16161322171750B14141319151560C19192023MM50D50销量销量302070301050M表示无穷大正数，表示最低需求不能由表示无穷大正数，表示最低需求不能由D产产地处供给。地处供给。步骤二：虚拟产地的单位运价确定步骤二：虚拟产地的单位运价确定原则原则：销地的最小需求必须得到满足，而最高需求不一定得到满足。：销地的最小需求必须得到满足，而最高需求不一定得到满足。说明最小销售量的满足不能来源于虚拟的产地。说明最小销售量的满足不能来源于虚拟的产地。MMM00042步骤三：采用表上作业法进行求解计算步骤三：采用表上作业法进行求解计算

24、 需求需求产地产地1212产量产量A5050B20103060C3020050D302050销量销量30207030105043w课后请自学课后请自学P92的例的例3.4和例和例3.544作作 业业：P95，3.4题 某厂按合同须于每个季度末分别完成某厂按合同须于每个季度末分别完成10、15、25、20台同一规格柴油机。已知该厂各季度生产能力及生产每台同一规格柴油机。已知该厂各季度生产能力及生产每台柴油机成本如表台柴油机成本如表3.45所示。又如果生产出来的柴油机所示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护费用当季不交货，每台每积压一个季度需储存、维护费用0.15万元。要求在完成合同的条件下，制订使该厂万元。要求在完成合同的条件下，制订使该厂全年全年生产、储存和维护费用为最小生产、储存和维护费用为最小的决策方案。的决策方案。季度季度生生产产能力（台）能力（台）单单台成本（万元）台成本（万元）2510.83511.13011.01011.345The End!46