第五章运输问题及解法优秀课件.ppt

《第五章运输问题及解法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第五章运输问题及解法优秀课件.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章运输问题及解法第五章运输问题及解法第1页，本讲稿共42页运输问题的一般提法是：运输问题的一般提法是：运输问题的一般提法是：运输问题的一般提法是：1.1.1.1.产销平衡问题产销平衡问题产销平衡问题产销平衡问题第2页，本讲稿共42页2.2.产销不平衡问题产销不平衡问题此时分为两种情形来考虑：此时分为两种情形来考虑：供不应求供不应求：即产量小于销量时有：即产量小于销量时有 供过于求供过于求：即产量大于销量时有：即产量大于销量时有 第3页，本讲稿共42页二二.运输问题的模型运输问题的模型产销平衡问题模型第4页，本讲稿共42页将约束方程式展开可得将约束方程式展开可得约束方程式中共mn个变量，m+

2、n个约束。第5页，本讲稿共42页第6页，本讲稿共42页第7页，本讲稿共42页2.m+n个约束中有一个是多余的（因为其间含有一个约束中有一个是多余的（因为其间含有一个平衡关系式个平衡关系式 ）所以所以R(A)=m+n-1R(A)=m+n-1，即解的，即解的mn个变量中基变量个变量中基变量为为为为m+n-1m+n-1个。个。个。个。第8页，本讲稿共42页三三.运输问题的解法运输问题的解法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯 形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问

3、题的特点设计出它的特殊解法表上作业法。第9页，本讲稿共42页表上作业法，实质上还是单纯形法。其步骤表上作业法，实质上还是单纯形法。其步骤如下：如下：1.确定一个初始可行调运方案。可以通过最小元素法、Vogel 法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。第10页，本讲稿共42页（）运输问题的常用解法：最小元素法（确定初始方案）闭回路法（检验当前方案）闭回路法（方案调整）以下面例题说明这种方法的具体步骤：例12：某食品公司下设3个加工厂A1 1，A2 2，A3 3，

4、和4个门市部B1 1，B2 2，B3 3，B4 4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？第11页，本讲稿共42页 运输问题一般用表上作业运输问题一般用表上作业法求解，需建立表格模型：法求解，需建立表格模型：单位运价表单位运价表产销平衡表产销平衡表 用线性规划法处理此问题。用线性规划法处理此问题。设由产地设由产地i到销地到销地j的运量为的运量为xij，模型为：，模型为：min z=3x11+11x12+3x13+10 x14 +x21 +9x22+2x23+8x24 +7x31

5、 +4x32+10 x33+5x34 x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+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)第12页，本讲稿共42页给出初始调运方案最常用的方法给出初始调运方案最常用的方法最小元素法最小元素法314633初始方案运费Z0=31+64+43+12+310+35=86(元)第13页，本讲稿共42页 表上作业法要求，调运方案的数字格必须为m+n-1个，且所有数字格不构成闭回路。一般，用最小

6、元素法给出的方案符合这一要求。闭回路:从方案中某一始格出发，沿同行或同列前进，当遇到一个数字格时可以可转90度或继续前进，按此方法进行，直到回到始点的一个封闭曲线。同行或同列最多有两个点。第14页，本讲稿共42页最小元素法中的退化情况最小元素法中的退化情况360542 出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。第15页，本讲稿共42页找出任意空格的闭回路找出任意空格的闭回路除此空格外，其余顶点均为有除此空格外，其余顶点均为有数格。如可找数格。如可找（A A1 1 B B1 1 ）（A A1 1 B B3 3 ）（A A2 2 B B3 3）（A A2 2 B B1

7、1 ）；）；2.2.检验检验（闭回路法（闭回路法:计算空格的检验数）计算空格的检验数）计算出空格的检验数计算出空格的检验数等于闭回路上由此空格起奇数顶等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的点运价与偶数顶点运价的代数和代数和。如。如 1111c c1111-c1313+c2323-c2121=1=1314633第16页，本讲稿共42页计算出此空格的检验数计算出此空格的检验数ij ij,若若ij ij，则该方案为最优方案，则该方案为最优方案，否则转；否则转；注：检验数的经济意义，以注：检验数的经济意义，以 1111为为例，空格表示原方案中例，空格表示原方案中X11=0,即A A1 1

8、B B1 1 的运输量为的运输量为0 0。若试着运。若试着运1 1单位，则这样所引起的总费用的变单位，则这样所引起的总费用的变化恰是化恰是 1111，可可见检验见检验数数 ij ij的意的意义义是：是：A Ai i B Bj j增运增运单位所引起的总费单位所引起的总费用的增量。用的增量。ij ij ，说明若增运一单位则在总运输量不变情况下，总运，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在费会增加。此时不应在 A Ai i B Bj j上增运。上增运。第17页，本讲稿共42页3.调整:从 ij ij 为最大正值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(

9、这才能保证新的平衡)，其中为该空格闭回路中偶数顶点的最小值。2424=-10=-10，从（从（从（从（A A2 2 B B4 4）出发其闭回路上=1，调整后得到一个新方案（如下表），运量为=1的（A A2 2 B B3 3）变空格，）变空格，得到新方案后再转得到新方案后再转 2。1111=1=1，1212=2=2 2222=1=1，2424=-1=-1 3131=10=10，3333=12=12314633第18页，本讲稿共42页经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。

10、（保证基变量个数不变）3 3 6 6 1 1 3 3 2 2 5 5第19页，本讲稿共42页2.确定初始方案的方法之二伏格尔法（VogelVogel法）求各行各列运价最小与次小之差额，选其中最大的行求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；或列中最小运价进行供应；如果某一行或某一列按照这种方法已被供应满，则划如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，即得最去该行或该列，在剩下的行列中重复这种方法，即得最优方案。优方案。第20页，本讲稿共42页3635122762第21页，本讲稿共42页3.求空格检验数的方法之二位势法原理

11、：设有运输问题的对偶问题为第22页，本讲稿共42页 3146333101245仍以例一为例：对偶变量表面上是7个，实际上只有6个。有一个是自由变量。第23页，本讲稿共42页当找出当找出ij ij00的格后，调整方法仍用闭回路法。的格后，调整方法仍用闭回路法。位势法步骤：由有数格cij=ui+vj求得ui和vj（先令u1=0），原有数格（基原有数格（基变量）的检验数变量）的检验数 ij ij=0=0；空格 ij ij=c=cij ij (u(ui i+v+vj j)；由此可得检验数表。由此可得检验数表。第24页，本讲稿共42页（）产销不平衡的运输问题）产销不平衡的运输问题1.1.产大于销的情况：

12、产大于销的情况：添加松弛变量xi,n+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即Ai的剩余量。第25页，本讲稿共42页A1AmB1Bn Bn+1C1100C1nCm1Cmn产大于销的单位运价表产大于销的产销量表A1Ama1amB1Bn Bn+1b1bn第26页，本讲稿共42页2.2.销大于产的情况：销大于产的情况：销大于产的情况：销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。第27页，本讲稿共42

13、页销大于产的产销量表A1Ama1amB1Bnb1bnAm+1A1AmB1BnC1100C1nCm1Cmn销大于产的单位运价表Am+1第28页，本讲稿共42页四四 应应 用用 举举 例例n n由于在变量个数相等的情况下，表上作业法的计算远比单纯形由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。的例子。第29页，本讲稿共42页n n例例3 3 某厂按合同规定须于当年每个季

14、度末分别提供某厂按合同规定须于当年每个季度末分别提供1010，1515，2525，2020台同一规格的柴油机。已知该厂各季度的生台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表产能力及生产每台柴油机的成本如表3-293-29所示。又如果生所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用存、维护等费用0.150.15万元。要求在完成合同的情况下，作万元。要求在完成合同的情况下，作出使该厂全年生产出使该厂全年生产(包括储存、维护包括储存、维护)费用最小的决策费用最小的决策。第30页，本讲稿共42页

15、n n解解 由于每个季度生由于每个季度生产产出来的柴油机不一定当季交出来的柴油机不一定当季交货货，所以，所以设设x xij ij为为第第i i季度生季度生产产的用于第的用于第j j季度交季度交货货的柴油机数。根据的柴油机数。根据合同要求，必合同要求，必须满须满足足第31页，本讲稿共42页n n又每季度生产的用于当季和以后各季交货的柴油机数不可能又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：超过该季度的生产能力，故又有：第32页，本讲稿共42页n n第第i i季度生季度生产产的用于的用于j j季度交季度交货货的每台柴油机的的每台柴油机的实际实际成本成本c ci

16、j ij应该应该是是该该季度季度单单位成本加上位成本加上储储存、存、维护维护等等费费用。用。c cij ij的的具体数具体数值见值见表表3-303-30。第33页，本讲稿共42页n n设设用用a ai i表示表示该该厂第厂第i i季度的生季度的生产产能力，能力，b bj j表示第表示第i i季度的合同季度的合同供供应应量，量，则问题则问题可写成：可写成：第34页，本讲稿共42页n n显显然，然，这这是一个是一个产产大于大于销销的运的运输问题输问题模型。注意到模型。注意到这这个个问题问题中当中当i ij j时时，x xij ij=0=0，所以，所以应应令令对应对应的的c cij ij=MM，再加

17、，再加上一个假想的需求上一个假想的需求D D，就可以把，就可以把这这个个问题变问题变成成产销产销平衡的运平衡的运输输模型，并写出模型，并写出产销产销平衡表和平衡表和单单位运价表位运价表(合在一起，合在一起，见见表表3-3-31)31)。第35页，本讲稿共42页n n经用表上作业法求解，可得多个最优方案，表经用表上作业法求解，可得多个最优方案，表3-323-32中列出最中列出最优方案之一。即第优方案之一。即第季度生产季度生产2525台，台，1010台当季交货，台当季交货，1515台台季度交货；季度交货；季度生产季度生产5 5台，用于台，用于季度交货；季度交货；季度生产季度生产3030台，其中台，

18、其中2020台于当季交货，台于当季交货，1010台于台于季度交货。季度交货。季度生季度生产产1010台，于当季交货。按此方案生产，该厂总的生产台，于当季交货。按此方案生产，该厂总的生产(包括包括储存、维护储存、维护)的费用为的费用为773773万元。万元。第36页，本讲稿共42页n n例例4 4 某航运公司承担六个港口城市某航运公司承担六个港口城市A A、B B、C C、D D、E E、F F的四的四条固定航线的物资运输任务。已知各条航线的起点、终点城条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数市及每天航班数见表见表3-333-33。第37页，本讲稿共42页n n假定各条

19、航线使用相同型号的船只，又各城市间的航程天假定各条航线使用相同型号的船只，又各城市间的航程天数见表数见表3-343-34。第38页，本讲稿共42页n n又知每条船只每次装卸货的时间各需又知每条船只每次装卸货的时间各需1 1天，则该航运公天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求司至少应配备多少条船，才能满足所有航线的运货需求?n n解解解解 该公司所需配备船只分两部分。该公司所需配备船只分两部分。n n(1)(1)载货航程需要的周转船只数。例如航线载货航程需要的周转船只数。例如航线1 1，在港口，在港口E E装装货货1 1天，天，E ED D航程航程1717天，在天，在D

20、D卸货卸货1 1天，总计天，总计1919天。每天天。每天3 3航班，故该航线周转船只需航班，故该航线周转船只需5757条。各条航线周转所需船条。各条航线周转所需船只数见表只数见表3-353-35。以上累计共需周转船只数91条.第39页，本讲稿共42页第第4节节 应应 用用 举举 例例n n(2)(2)各港口间调度所需船只数。有些港口每天到达船数多于需要船数，各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口例如港口D D，每天到达，每天到达3 3条，需求条，需求1 1条；而有些港口到达数少于需求数，条；而有些港口到达数少于需求数，例如港口例如港口B B。各港口每天余缺船只数的计

21、算见表。各港口每天余缺船只数的计算见表3-363-36。第40页，本讲稿共42页第第4节节 应应 用用 举举 例例n n为使配备船只数最少，应做到周转的空船数为最少。因此建立为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表以下运输问题，其产销平衡表见表3-373-37。单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只航程天数航程天数航程天数航程天数，见表，见表，见表，见表3-383-383-383-38。第41页，本讲稿共42页第第4节节 应应 用用 举举 例例n n用表上作业法求出空船的最优调度方案见表用表上作业法求出空船的最优调度方案见表3-393-39。由表3-39知最少需周转的空船数为 21+131+51+171+31=40条。这样在不考虑维修、储备等情况下，该公司至少应配备40+91=131条船。第42页，本讲稿共42页