《管理运筹学》02-7运输问题.ppt

第四节第四节 运输问题运输问题Transportation Model一、运输问题及其数学模型一、运输问题及其数学模型二、表上作业法求解运输问题二、表上作业法求解运输问题三、产销不平衡的运输问题及应用三、产销不平衡的运输问题及应用3问题的提出问题的提出 运输问题：产地、销地、产量、销量运输问题：产地、销地、产量、销量 例例1 有有A1，A2，A3三座铁矿，每天要把生产三座铁矿，每天要把生产的铁矿石运往的铁矿石运往B1，B2，B3，B4四个炼铁厂。各矿的四个炼铁厂。各矿的产量、各厂的销量以及各厂矿间的运价如下表所示。产量、各厂的销量以及各厂矿间的运价如下表所示。问应如何组织调运才能使运费最少？问应如何组织调运才能使运费最少？运输问题及其数学模型运输问题及其数学模型4B1 B2 B3 B4产量产量A1A2A36 3 2 57 5 8 43 2 9 7523销量销量2 3 1 4(百元百元/百吨百吨)xij Ai运给运给Bj的铁矿石数量（百吨）的铁矿石数量（百吨）z 总运费（百元）总运费（百元）运输问题及其数学模型运输问题及其数学模型5B1B2B3B4产量产量A163255A275842A332973销量销量2314(百元百元/百吨百吨)x11x12x13x14x21x22x23x24x31x32x33x34运输问题及其数学模型运输问题及其数学模型6 数学模型为数学模型为:min z=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24 +3x31+2x32+9x33+7x34 x11+x12+x13+x14 =5 x21+x22+x23+x24 =2 x31+x32+x33+x34=3 x11 +x21 +x31 =2 x12 +x22 +x32 =3 x13 +x23 +x33 =1 x14 +x24 +x34=4 xij0 (i=1,2,3;j=1,2,3,4)s.t.运输问题及其数学模型运输问题及其数学模型7 运输模型的特点：运输模型的特点：(1)它有它有mn个变量，个变量，m+n个约束方程个约束方程 (2)其系数阵具有特殊的结构其系数阵具有特殊的结构 m=3行行n=4行行A=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8表式表式模型模型 产销平衡产销平衡的运输问题的运输问题:aai i=bbj j 产大于销产大于销的运输问题的运输问题:aai ibbj j 产小于销产小于销的运输问题的运输问题:aai ibbj jB1B2Bn 产量产量 A1c11 x11c12 x12c1n x1n a1A2c21 x21c22 x22c2n x2na2Amcm1 xm1 cm2 xm2 cmn xmnam销量销量b1b2bn aib bj运输问题及其数学模型运输问题及其数学模型运输问题及其数学模型运输问题及其数学模型1 1、运输问题的网络图、线性规划模型及运输表、运输问题的网络图、线性规划模型及运输表设有同一种货物从设有同一种货物从m m个供应地个供应地1 1，2 2，m m运往运往n n个需个需求地求地1 1，2 2，n n。第。第i i个供应地的供应量个供应地的供应量（SupplySupply）为）为 ，第，第j j个需求地的需求量个需求地的需求量（DemandDemand）为）为 。每单位货物从供应地。每单位货物从供应地i i运运到需求地到需求地j j的运价为的运价为 。求一个使总运费最小的运。求一个使总运费最小的运输方案。如果从任一供应地到任一需求地都有道路输方案。如果从任一供应地到任一需求地都有道路通行，这样的运输问题称为完全的运输问题；如果通行，这样的运输问题称为完全的运输问题；如果总供应量等于总需求量，这样的运输问题称为供求总供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。我们先考虑完全的、供求平衡的平衡的运输问题。我们先考虑完全的、供求平衡的运输问题。运输问题。运输问题及其数学模型运输问题及其数学模型1inj1m右图是运输问题的网络表示形式。运输问题及其数学模型运输问题及其数学模型运输问题也可以用线性规划表示。设 为从供应地i运往需求地j的运量，则总运费最小的线性规划问题如下式所示。运输问题及其数学模型运输问题及其数学模型运输问题线性规划变量个数为nm个，每个变量与运输网络的一条边对应，所有的变量都是非负的。约束个数为m+n个，全部为等式约束。前m个约束是供应地的供应量约束，后n个约束是需求地的需求量约束。运输问题约束的特点是约束左边所有的系数都是0或1，而且每一列中恰有两个系数是1，其他都是0。运输问题及其数学模型运输问题及其数学模型在运输问题线性规划模型中，令 A=则运输问题的线性规划可以写成：运输问题及其数学模型运输问题及其数学模型完全的运输问题系数矩阵A中，列向量 中只有两个元素是1，其他元素都是0。第一个1位于矩阵的第i行，第二个1位于矩阵的第m+j行。这个列向量可以表示为两个单位向量之和，即运输问题及其数学模型运输问题及其数学模型 运输问题除了用网络表示及线性规划表示外，还可以用运输表表示，见右表。运输表是一个m行n列的表格，每一行对应于一个供应地，每一列对应于一个需求地。运输表共有mn个格子，每个格子对应于从一个供应地出发到一个需求地的运输路线。12n12 m运输问题及其数学模型运输问题及其数学模型上页表中，每一格的左上角小方格内的数字表明从相应的供应地i到需求地j的运价 ，每一格右下角表明从相应的供应地i到需求地j的运量 。表右方表明各供应地的供应量 ，表下方表明各需求地的需求量 。每一行运量之和表示从该供应地运往各需求地的运量之和，它应该等于该供应地的供应量；同样，每一列运量之和表示从各供应地运往该需求地的运量之和，它应该等于该需求地的需求量。运输问题及其数学模型运输问题及其数学模型运输问题约束矩阵的性质运输问题约束矩阵的性质A=分别将A的前m行和后n行相加，得到两个相同的mn维向量，其中的元素都是1。即A矩阵的m+n个行向量是线性相关的，因此A矩阵的秩m+n。运输问题分别从供应地1、2、m到需求地n的m条边以及从供应地1分别到需求地1、2、n-1的n-1条边，一共有m+n-1条边。这m+n-1条边组成运输问题约束矩阵A中的m+n-1个列向量，这些列向量在A矩阵中的子矩阵是一个m+n行，m+n-1列的矩阵 B=删除矩阵B的最后一行，得到 B=可以看出，这是一个上三角矩阵，显然，秩Bm+n-1。由m+n-1=秩B秩A0。由于单纯形叠代在每一步都满足互补松弛条件，因此对于基变量xij0，相应的对偶约束条件ui+vj cij的松弛变量一定等于0，即 ui+vj=cij 由于基变量一共有m+n-1个，因此对偶问题一共有m+n-1个等式约束，只要先确定一个对偶变量的值，就可以由m+n-1个等式约束确定其余m+n-1个对偶变量的值。不妨设vn=0，逐个递推求得ui和vj。求出ui、vj的值以后，就可以进一步计算各非基变量的检验数zij-cij=ui+vj-cij。3.解的改进（1）确定进基变量由单纯形法原理可以知道，凡检验数zij-cij0的非基变量都可以进基。通常总是选取检验数中最小的对应变量进基。（2）确定离基变量为保证改进后的解仍为基本可行解，需要保证所有变量的非负性。因此，改进的方法就是从检验数为负数的空格出发，作一条除该空格外其余顶点均为有数字格组成的闭合回路。在这条闭回路上，按对运量作最大可能的调整。表上作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题表上作业法求解运输问题12341101191530151142131216945453118710501931414131213252515203184例 改进表中用最小元素法得到的初始基本可行解。由表可知，x34的检验数是-2，因此可以作为进基变量。选取变量x34作为进基变量，以其所在的空格为出发点作闭合回路。选取变量x34作为进基变量相应的闭合回路 表上作业法求解运输问题表上作业法求解运输问题12341101191530151521312169454531187105053114414131213252515203184将其改进为新的基本可行解。则x34增加的同时，x14减少，x12增加，x32增加。为保证变量的非负性，能够减少的最大数量为14。此时，x14减少到0，是出基变量。得到新的基本可行解见下表 改进后的基本可行解-1210574422表上作业法求解运输问题表上作业法求解运输问题123411011915301515213121694545311871050201614414131213252515203184上表给出的调运方案是否为最优呢？还需要对这个方案的空格处（非基变量）求出检验数。由于表中x13的检验数为-1，因此对上表进行改进。得到下表。计算表中的检验数。最优基本可行解 由于检验数表2-38中的所有检验数大于等于0。因此上表是最优方案。1310563322最优解的目标函数值为z=1015+915+945+820+716+1014+1325=1427。需要指出的是，有时在闭合回路调整中，在需要减小运量的地方有两个以上相等的最小数，这样调整时原先空格处填上了这个最小数，而有两个以上最小数的地方成了空格。为了保证基变量的个数是m+n-1个，就要把最小数的空格之一变为空格，其余均补填0，补填0的格为有数字格，对应的变量是基变量。表上作业法求解运输问题表上作业法求解运输问题1供给大于需求的情况，即 增加一个虚设的需求地n+1，它的需求量为 。新增从各供应地到该需求地的运输路线（1，n+1），（2，n+1），（m，n+1），这些运输路线上的运价全部等于0，即c1，n+1=c2，n+1=cm，n+1=0，这样就将供给大于需求的的问题转化为供求平衡的问题。在新的问题中，从供应地i到新设的需求地n+1的运量，实际上就是存储在供应地i没有运出的数量。新得到的供求平衡的运输问题的最优解，实际上就是各供应地存储多少、运出多少、运往何地，使总运价最低。产销不平衡的运输问题及应用产销不平衡的运输问题及应用例 设一个供求不平衡的运输问题如下左图。相应的供求平衡问题如图1，2。产销不平衡的运输问题及应用产销不平衡的运输问题及应用图1 供求不平衡的运输问题 图2 供求不平衡的运输问题 由于需求地4是虚拟的，因此对应的运价设为0。供求平衡问题的运输表以及最优解如下：产销不平衡的运输问题及应用产销不平衡的运输问题及应用12341856015105271090251051010101010调整后的运输表及最优解及检验数表 342已获得最优解。这个最优解的含义是：从供应地1到需求地2的运量为10，到需求地3的运量为5，供应量没有剩余；从供应地2到需求地1的运量为10，到需求地3的运量为5，供应量剩余10；最小运费为 min z=510+65+710+95=195.产销不平衡的运输问题及应用产销不平衡的运输问题及应用2供给小于需求的情况，即 当市场的总需求量大于总供给量时，可以仿照供给大于需求的情况处理。即增加一个假想的供应地，产量等于供应不足的部分，即 。由于假想的供应地并不存在，相应运价就等于0。59运输模型的应用运输模型的应用短缺资源的分配问题短缺资源的分配问题自来水分配问题自来水分配问题1601601101106 6 0 0210210160160 额额 外外 基基 本本2 02 0 0 0 5 05 060 50C60B50A供供水水量量引水引水 区区 管理费管理费水库水库D D(虚虚)5050210210甲甲 甲甲1甲甲2需需 求求 量量30302020 乙乙 7070 丙丙 3030丁丁 丁丁1丁丁210105050160140190160140190M0 0130130200M2201902300 0170150MM170150M0 0自来水分配问题自来水分配问题的的规范表式运输模型规范表式运输模型规范表式运输模型规范表式运输模型运输模型的应用运输模型的应用61210501030702030需求量需求量502030脱销脱销5002030C60301020B5050A供水量供水量丁丁2 2丁丁1 1丙丙乙乙甲甲2 2甲甲1 1分配量分配量水库水库区区自来水分配问题自来水分配问题自来水分配问题自来水分配问题的的最优方案表最优方案表最优方案表最优方案表运输模型的应用运输模型的应用62转运问题转运问题面粉转运问题面粉转运问题 设有设有A1、A2、A3三个面粉加工厂，每天分别将三个面粉加工厂，每天分别将 3、4、3吨面粉运往吨面粉运往B1、B2两个糕点厂，而两个糕点厂，而B1、B2每每 天分别需要天分别需要4、6吨面粉。在面粉厂与糕点厂之间有吨面粉。在面粉厂与糕点厂之间有T1、T2两个中继站。各地间每吨面粉的运价如下表所示。两个中继站。各地间每吨面粉的运价如下表所示。应如何调运使总运费最低？应如何调运使总运费最低？运输模型的应用运输模型的应用63 9 9 2 3 6 4B1B2糕糕点点厂厂 2 5 2 6 7 3 5 2 3 2T1T2中中继继站站 6 813 711 4 3 5 2 3 2 3 2 4 2 2A1A2A3面面粉粉厂厂 B1 B2 T1 T2 A1 A2 A3 糕点厂糕点厂 中继站中继站 面面 粉粉 厂厂 终点终点 始点始点运输模型的应用运输模型的应用64 1 转运站转运站既是既是始点始点，又是，又是终点终点的运地。的运地。转化成为有转化成为有7 7个假想产地个假想产地Ai、7 7个假想销地个假想销地Bj的的新问题新问题。2 虚设一个统一转运量虚设一个统一转运量t，应有，应有t max(ai，bj)ai+t，Ai 是是转运站转运站 ai，否则否则ai=假想产地假想产地Ai的产量的产量故可取作故可取作t=10=10本例本例 ai=bj运输模型的应用运输模型的应用65bj+t，Bj 是是转运站转运站 bj，否则否则bj=本例取作本例取作ai=ai+10bj=bj+10 3 虚设虚设 xii 也是运量，即假想各也是运量，即假想各转运站转运站可以自产自销，则其可以自产自销，则其 真实运量为真实运量为假想销地假想销地Bj 的销量的销量t -xii。不可能运输（即表中标不可能运输（即表中标“-”）之处：用大）之处：用大 MM 取代；取代；xii 的的运价运价为为0；本例中即本例中即10-xii。4 新问题新问题的的运价运价：其余不变。其余不变。运输模型的应用运输模型的应用66 面粉转运问题的面粉转运问题的初始方案初始方案初始方案初始方案销销 量量B2B1T2T1A3A2A1产产量量 B2B1T2T1A3A2A1产地产地销地销地334461 11 11 11 11 110101010101010101080809 3 4 9 2 6 27 3 3 5 6 2 5 3 4 11 2 3 2 7 13 2 5 2 4 8 6 3 2 3 2 M M M M MMM M M M 0 0 0 0 0 0 0 uivj3 13300 10 10 10 10 10 10 100 06 6-2 24 4-4 4-7 70 00 0-6 62 2-4 44 47 70 0 3 5 M-4 8 M+7 M 15 M+8 4M+10M+13 12 M-8 1 5 8 M-2 9 12 10 167 1 0 -5 5 M-4 -3 -6-1 -3 8 M+2 -1 6 10 +-+-运输模型的应用运输模型的应用67 面粉转运问题的面粉转运问题的最优方案最优方案8016141010101010销销 量量100 9 83 5M M+14 8M M+4M M+4B2-4109 100 M M+32 4M M+5M M+56 11B1-5102M M-30 7 63 53 5M M+2T2-2105 426 70 2 55 83 6T1-313411 62 03 0 2 2M MA30147 313 84 5 22 20 4 4A20138 4 6 1M M-23 2 23 30 A10B2B1T2T1A3A2A1产产量量4523000 vj 销地销地 ui 产地产地36442614 10 10 10 10 10运输模型的应用运输模型的应用68 最优方案及最优路线最优方案及最优路线 最少总运费为最少总运费为 z*=33+24+31+42+24+24=44(元元)A1B1T1A2T2A3B23吨吨4吨吨3吨吨4吨吨6吨吨341244运输模型的应用运输模型的应用69生产调度问题生产调度问题拖拉机生产调度问题拖拉机生产调度问题 前进拖拉机厂与农机供销社签订了一项生产前进拖拉机厂与农机供销社签订了一项生产100台某种台某种小型拖拉机的合同。按合同规定，该厂要在今后四个月的每小型拖拉机的合同。按合同规定，该厂要在今后四个月的每月内交付一定台数的拖拉机。为此，该厂生产计划科根据本月内交付一定台数的拖拉机。为此，该厂生产计划科根据本厂实际情况列出了一个生产调度表（见下表）。根据此表第厂实际情况列出了一个生产调度表（见下表）。根据此表第二栏（生产能力）的数据，该厂能够提前完成合同总台数，二栏（生产能力）的数据，该厂能够提前完成合同总台数，但生产出来的拖拉机若当月不交货，每台存储一个月，由于但生产出来的拖拉机若当月不交货，每台存储一个月，由于维修保养和积压资金等缘故，另需费用维修保养和积压资金等缘故，另需费用100元。问该厂应如何元。问该厂应如何拟订最经济的生产进度？拟订最经济的生产进度？70130100合合 计计 5000 5200 5100 5300 30 35 45 20 15 25 35 25 单台成本单台成本（元）（元）生产能生产能力（台）力（台）合同规合同规定交付定交付台台 数数 月月 份份运输模型的应用运输模型的应用71 解解 设设 xij 为第为第 i 个月生产的、用于第个月生产的、用于第 j 个月交货的拖拉机台数个月交货的拖拉机台数(i，j=1，2，3，4)。若将各。若将各产期产期视为视为“产地产地”，各，各销期销期视为视为 “销地销地”，将，将xij视为视为“运量运量”，就，就能构成一个运输模型。能构成一个运输模型。cij 表示第表示第i月生产的用于第月生产的用于第j月交货的每台拖拉机的实月交货的每台拖拉机的实际费用，它等于第际费用，它等于第 i 月的单台成本加上月的单台成本加上 j i 个月的贮存费用个月的贮存费用(j i).cij=ci+c(j-i)130100 15 25 35 25 销销 量量30354520 c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 产产 量量 销期销期i i 产期产期j j运输模型的应用运输模型的应用72 130100 15 25 35 25 bj30354520 ai cij j i 51525352 50 -52 -51 -53MMMMMM5354cij=ci+c(j-i),j i运输模型的应用运输模型的应用73 130 30 25352515 bj20 0 5353MMM 45 0 525151MM 35 0 54535252M 30 0 5352515050 ai虚虚 销期销期j j 产期产期i i 545355555759cij=c ci i+c(j-i),ijc ci i+b(i-j),i jb=2 2运输模型的应用运输模型的应用