运输问题及解法.pptx

第五章第五章 运输问题运输问题一.运输问题的一般提法 在经济建设中，经常碰到物资调拨中的运输问题。例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？运输问题的一般提法是：运输问题的一般提法是：1.1.1.1.产销平衡问题产销平衡问题产销平衡问题产销平衡问题2.2.产销不平衡问题产销不平衡问题此时分为两种情形来考虑：此时分为两种情形来考虑：供不应求：即产量小于销量时有 供过于求供过于求：即产量大于销量时有：即产量大于销量时有 二二.运输问题的模型运输问题的模型产销平衡问题模型将约束方程式展开可得将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。2.m+n个约束中有一个是多余的（因为其间含个约束中有一个是多余的（因为其间含有一个平衡关系式有一个平衡关系式 ）所以所以R(A)=m+n-1，即解的，即解的mn个变量中基变量个变量中基变量为为m+n-1个。个。三三.运输问题的解法运输问题的解法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯 形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。表上作业法，实质上还是单纯形法。其步表上作业法，实质上还是单纯形法。其步骤如下：骤如下：1.确定一个初始可行调运方案。可以通过最小元素法、Vogel 法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。（）运输问题的常用解法：最小元素法（确定初始方案）闭回路法（检验当前方案）闭回路法（方案调整）以下面例题说明这种方法的具体步骤：例12：某食品公司下设3个加工厂A1 1，A2 2，A3 3，和4个门市部B1 1，B2 2，B3 3，B4 4。各加工厂每天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？运输问题一般用表上作业运输问题一般用表上作业法求解，需建立表格模型：法求解，需建立表格模型：单位运价表单位运价表产销平衡表产销平衡表 用线性规划法处理此问题。用线性规划法处理此问题。设由产地设由产地i到销地到销地j的运量为的运量为xij，模型为：，模型为：min z=3x11+11x12+3x13+10 x14 +x21 +9x22+2x23+8x24 +7x31 +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)给出初始调运方案最常用的方法给出初始调运方案最常用的方法最小元素法最小元素法314633初始方案运费Z0=31+64+43+12+310+35=86(元)表上作业法要求，调运方案的数字格必须为m+n-1个，且所有数字格不构成闭回路。一般，用最小元素法给出的方案符合这一要求。闭回路:从方案中某一始格出发，沿同行或同列前进，当遇到一个数字格时可以可转90度或继续前进，按此方法进行，直到回到始点的一个封闭曲线。同行或同列最多有两个点。最小元素法中的退化情况最小元素法中的退化情况360542 出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。找出任意空格的闭回路找出任意空格的闭回路除此空格外，其余顶点均除此空格外，其余顶点均为有数格。如可找为有数格。如可找（A A1 1 B B1 1 ）（A A1 1 B B3 3 ）（A A2 2 B B3 3）（A A2 2 B B1 1 ）；）；2.2.检验检验（闭回路法（闭回路法:计算空格的检验数）计算空格的检验数）计算出空格的检验数计算出空格的检验数等于闭回路上由此空格起奇等于闭回路上由此空格起奇数顶点运价与偶数顶点运价的数顶点运价与偶数顶点运价的代数和代数和。如。如 1111c1111-c1313+c2323-c2121=1=1314633计算出此空格的检验数计算出此空格的检验数ij ij,若若ij ij，则该方案为最，则该方案为最优方案，否则转；优方案，否则转；注：检验数的经济意义，以注：检验数的经济意义，以 1111为例，空格表示原方案中为例，空格表示原方案中X11=0,即A A1 1 B B1 1 的运输量为的运输量为0 0。若试着运。若试着运1 1单位，则这样所引起的总单位，则这样所引起的总费用的变化恰是费用的变化恰是 1111，可见检验数可见检验数 ij ij的意义是：的意义是：A Ai i B Bj j增运增运单位所引起的总费用的增量。单位所引起的总费用的增量。ij ij ，说明若增运一单位则在，说明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在总运输量不变情况下，总运费会增加。此时不应在 A Ai i B Bj j上上增运。增运。3.调整:从 ij ij 为最大正值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中为该空格闭回路中偶数顶点的最小值。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经再计算新方案的检验数全部大于0。所以，该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）3 3 6 6 1 1 3 3 2 2 5 52.确定初始方案的方法之二伏格尔法（Vogel法）求各行各列运价最小与次小之差额，选其中最大求各行各列运价最小与次小之差额，选其中最大的行或列中最小运价进行供应；的行或列中最小运价进行供应；如果某一行或某一列按照这种方法已被供应满，如果某一行或某一列按照这种方法已被供应满，则划去该行或该列，在剩下的行列中重复这种方法，则划去该行或该列，在剩下的行列中重复这种方法，即得最优方案。即得最优方案。36351227623.求空格检验数的方法之二位势法原理：设有运输问题的对偶问题为 3146333101245仍以例一为例：对偶变量表面上是7个，实际上只有6个。有一个是自由变量。当找出当找出ij ij00的格后，调整方法仍用闭回路法。的格后，调整方法仍用闭回路法。位势法步骤：由有数格cij=ui+vj求得ui和vj（先令u1=0），原有数格原有数格（基变量）的检验数（基变量）的检验数 ij ij=0=0；空格 ij ij=c=cij ij (u(ui i+v+vj j)；由此可得检验数表。由此可得检验数表。（）产销不平衡的运输问题）产销不平衡的运输问题1.1.产大于销的情况：产大于销的情况：添加松弛变量xi,n+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地Ai自己的仓库里，自己往自己的地方运，运费cin+1显然为0。实际上xin+1即Ai的剩余量。A1AmB1Bn Bn+1C1100C1nCm1Cmn产大于销的单位运价表产大于销的产销量表A1Ama1amB1Bn Bn+1b1bn2.销大于产的情况：销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。销大于产的产销量表A1Ama1amB1Bnb1bnAm+1A1AmB1BnC1100C1nCm1Cmn销大于产的单位运价表Am+1四四 应应 用用 举举 例例n n由于在变量个数相等的情况下，表上作业法的计算远比单纯由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。个典型的例子。n n例例3 3 某厂按合同规定须于当年每个季度末分别提供某厂按合同规定须于当年每个季度末分别提供1010，1515，2525，2020台同一规格的柴油机。已知该厂各台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表季度的生产能力及生产每台柴油机的成本如表3-293-29所示。又如果生产出来的柴油机当季不交货的，每所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用台每积压一个季度需储存、维护等费用0.150.15万元。万元。要求在完成合同的情况下，作出使该厂全年生产要求在完成合同的情况下，作出使该厂全年生产(包包括储存、维护括储存、维护)费用最小的决策费用最小的决策。n n解解 由于每个季度生产出来的柴油机不一定当季交货，由于每个季度生产出来的柴油机不一定当季交货，所以设所以设x xij ij为第为第i i季度生产的用于第季度生产的用于第j j季度交货的柴油机季度交货的柴油机数。根据合同要求，必须满足数。根据合同要求，必须满足n n又每季度生产的用于当季和以后各季交货的柴油机又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：数不可能超过该季度的生产能力，故又有：n n第第i i季度生产的用于季度生产的用于j j季度交货的每台柴油机的实际成季度交货的每台柴油机的实际成本本c cij ij应该是该季度单位成本加上储存、维护等费用。应该是该季度单位成本加上储存、维护等费用。c cij ij的具体数值见表的具体数值见表3-303-30。n n设用设用a ai i表示该厂第表示该厂第i i季度的生产能力，季度的生产能力，b bj j表示第表示第i i季度季度的合同供应量，则问题可写成：的合同供应量，则问题可写成：n n显然，这是一个产大于销的运输问题模型。注意到显然，这是一个产大于销的运输问题模型。注意到这个问题中当这个问题中当i ij j时，时，x xij ij=0=0，所以应令对应的，所以应令对应的c cij ij=MM，再加上一个假想的需求，再加上一个假想的需求D D，就可以把这个问题变，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位成产销平衡的运输模型，并写出产销平衡表和单位运价表运价表(合在一起，见表合在一起，见表3-31)3-31)。n n经用表上作业法求解，可得多个最优方案，表经用表上作业法求解，可得多个最优方案，表3-323-32中列出最优方案之一。即第中列出最优方案之一。即第季度生产季度生产2525台，台，1010台台当季交货，当季交货，1515台台季度交货；季度交货；季度生产季度生产5 5台，用于台，用于季度交货；季度交货；季度生产季度生产3030台，其中台，其中2020台于当季交台于当季交货，货，1010台于台于季度交货。季度交货。季度生产季度生产1010台，于当季台，于当季交货。按此方案生产，该厂总的生产交货。按此方案生产，该厂总的生产(包括储存、维包括储存、维护护)的费用为的费用为773773万元。万元。n n例例4 4 某航运公司承担六个港口城市某航运公司承担六个港口城市A A、B B、C C、D D、E E、F F的四条固定航线的物资运输任务。已知各条航线的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数的起点、终点城市及每天航班数见表见表3-333-33。n n假定各条航线使用相同型号的船只，又各城市间的假定各条航线使用相同型号的船只，又各城市间的航程天数见表航程天数见表3-343-34。n n又知每条船只每次装卸货的时间各需又知每条船只每次装卸货的时间各需1 1天，则该航运天，则该航运公司至少应配备多少条船，才能满足所有航线的运公司至少应配备多少条船，才能满足所有航线的运货需求货需求?n n解解解解 该公司所需配备船只分两部分。该公司所需配备船只分两部分。n n(1)(1)载货航程需要的周转船只数。例如航线载货航程需要的周转船只数。例如航线1 1，在港，在港口口E E装货装货1 1天，天，E ED D航程航程1717天，在天，在D D卸货卸货1 1天，总计天，总计1919天。每天天。每天3 3航班，故该航线周转船只需航班，故该航线周转船只需5757条。各条。各条航线周转所需船只数见表条航线周转所需船只数见表3-353-35。以上累计共需周转船只数91条.第第4节节 应应 用用 举举 例例n n(2)(2)各港口间调度所需船只数。有些港口每天到达船数多于各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口需要船数，例如港口D D，每天到达，每天到达3 3条，需求条，需求1 1条；而有些港条；而有些港口到达数少于需求数，例如港口口到达数少于需求数，例如港口B B。各港口每天余缺船只数。各港口每天余缺船只数的计算见表的计算见表3-363-36。第第4节节 应应 用用 举举 例例n n为使配备船只数最少，应做到周转的空船数为最少。因此建为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表立以下运输问题，其产销平衡表见表3-373-37。单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只单位运价表应为相应各港口之间的船只航程天数航程天数航程天数航程天数，见，见，见，见表表表表3-383-383-383-38。第第4节节 应应 用用 举举 例例n n用表上作业法求出空船的最优调度方案见表用表上作业法求出空船的最优调度方案见表3-393-39。由表3-39知最少需周转的空船数为 21+131+51+171+31=40条。这样在不考虑维修、储备等情况下，该公司至少应配备40+91=131条船。