第三章运输问题新.ppt

管 理 运 筹 学 Operations Research 第三章 运输问题本章重点 产销平衡运输问题的数学模型产销平衡运输问题的数学模型 产销平衡运输问题的产销平衡运输问题的表上作业法表上作业法 本章内容运输问题的数学模型运输问题的数学模型表上作业法表上作业法运输问题的扩展运输问题的扩展第三章 运输问题第三章 运输问题 运输问题（运输问题（Transportation Problem，简记为，简记为TP）是一类常见而且极其特殊的线性规划问题是一类常见而且极其特殊的线性规划问题.它最早是从它最早是从物资调运工作中提出来的，是物流优化管理的重要的物资调运工作中提出来的，是物流优化管理的重要的内容之一内容之一 。从理论上讲，运输问题也可用单纯形法来求解，从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法种比单纯形法更简便的计算方法 表上作业法，表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用算时间与计算费用.但表上作业法的实质仍是单纯形法但表上作业法的实质仍是单纯形法 1 运输问题及其数学模型1 1 运输问题及其数学模型运输问题及其数学模型 设某种物资共有设某种物资共有 m 个产地个产地 A1，A2，Am，各各产地的产量分别是产地的产量分别是a1，a2，am；有有n 个销地个销地 B1，B2，Bn，各销地的销量分别为各销地的销量分别为b1，b2，bn.假定从产地假定从产地Ai（i=1，2，m）向销地向销地Bj（j=1，2，n）运输单位物资的运价是运输单位物资的运价是cij，问怎样调运才能，问怎样调运才能使总运费最小？使总运费最小？一、运输问题的数学模型一、运输问题的数学模型 加速物资流转加速物资流转 降低流通费用降低流通费用 第三章 运输问题 销地销地产地产地 B1 B2 Bn产量产量 A1c11c21 c1na1 A2c21c22 c2na2 Amcm1cm2 cmn am销量销量 b1 b2 bn 运价表运价表1 1、产销平衡问题、产销平衡问题即即 设设 xij 表示产地表示产地 Ai 运往销地运往销地 Bj(i=1,2,m;j=1,2,n)的运量的运量.销地销地产地产地 B1 B2 Bn产量产量 A1 x11c11 x12c21 x1n c1na1 A2 x21c21 x22c22 x2nc2na2 Am xm1cm1 xm2cm2 xmncmn am销量销量 b1 b2 bn1 运输问题及其数学模型2 2、产销不平衡问题、产销不平衡问题当当当当 例1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解解:产销平衡问题：总产量产销平衡问题：总产量=总销量总销量 设设 xij 为从产地为从产地Ai运往销地运往销地Bj的运输量，的运输量，得到下列运输量表：得到下列运输量表：min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13 =200 x21+x22+x23=300 x11 +x21 =150 x12 +x22 =150 x13 +x23=200 xij0 (i=1,2；j=1,2,3）1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵由此可知运输问题具有下述特点由此可知运输问题具有下述特点:1.约束条件系数矩阵的元素等于0或1；2.约束条件系数矩阵的每一列有两个非零元素，这说明每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。对产销平衡运输问题，除上述两个特点外，对产销平衡运输问题，除上述两个特点外，还具有以下特点：还具有以下特点：所有约束条件都是等式约束；各产地产量之和等于各销地销量之和。练习：P87 第1题2 运输问题的表上作业法 表上作业法（又称运输单纯形法）是根据单纯形表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法的求解运输问题的简便而有效的方法.主要步骤：主要步骤：1、求一个初始调运方案（初始基可行解）；求一个初始调运方案（初始基可行解）；2、判别当前方案是否为最优，若是则迭代停止，否则判别当前方案是否为最优，若是则迭代停止，否则 转下一步；转下一步；3、改进当前方案，得到新的方案（新的基可行解），改进当前方案，得到新的方案（新的基可行解），再返回再返回 2。2 2 运输问题的表上作业法运输问题的表上作业法第三章 运输问题一、初始方案的确定一、初始方案的确定1、西北角法西北角法BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15Ex.1 50 已知某商品有三个产地已知某商品有三个产地A1、A2、A3和四个销地和四个销地B1、B2、B3、B4 ，产量、销量及单位运价如表，产量、销量及单位运价如表.问应问应如何调运，在满足各销地需要的情况下，使总的运费如何调运，在满足各销地需要的情况下，使总的运费支出为最少？支出为最少？解：解：51010205规则规则:从运输表的西从运输表的西北角开始北角开始,优先安排优先安排编号小的产地和销地编号小的产地和销地的运输任务的运输任务.填了几个数字填了几个数字？Note:在填入一个数时，如果行和列同时饱和，在填入一个数时，如果行和列同时饱和，规定只划去一行或一列规定只划去一行或一列BjAi B1 B2 B3 B4 ai A110 5 2 3 50 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 155002 运输问题的表上作业法2、最小元素法最小元素法BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15规则规则:优先安排单位运价最小的产地与销地之间的运输优先安排单位运价最小的产地与销地之间的运输 任务任务.40102551010Note:1、在某行（或列）填入最后一个数时，如果行在某行（或列）填入最后一个数时，如果行和列同时饱和，规定只划去该行（或列）。和列同时饱和，规定只划去该行（或列）。2、当表中只剩一个元素时，这时在产销平衡表上填这、当表中只剩一个元素时，这时在产销平衡表上填这个数字时，应在运价表上同时去掉一行和一列。个数字时，应在运价表上同时去掉一行和一列。3、若表中有、若表中有m行行n列，则表上填写（列，则表上填写（m+n-1）个数字，）个数字，即为基变量的值。即为基变量的值。BjAi B1 B2 B3 B4 ai A1 1 5 3 2 60 A2 4 1 2 3 20 A3 5 6 1 4 10 bj 50 20 10 100010102050填了几个数字填了几个数字？2 运输问题的表上作业法BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 差额差额 6 2 差额差额 5 1315BjAi B1 B2 ai A1 8 2 5 A2 3 1 4 bj 6 3 按最小元素法按最小元素法3423、Vogel 法法 (元素差额法元素差额法)规则：计算各行各列的最小元素与次小元素的差额，规则：计算各行各列的最小元素与次小元素的差额，优先安排差额最大的所优先安排差额最大的所在行或列的单位运价最在行或列的单位运价最小的产地与销地之间的小的产地与销地之间的运输任务运输任务练习：P74 例3-2考研真题：考研真题：1（10分，同济大学）已知运输问题的产销平衡表和单位运价表如表所示，求该运输模型的最优解。1、闭回路法闭回路法 闭回路：从空格出发顺时针(或逆时针)画水(或垂直)直线，遇到填有运量的方格可转可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 3656二、最优解的判别二、最优解的判别（检验数的求法）（检验数的求法）闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线，遇到填有运量的方格可转可转90，然后继续前进，直到到达出发的空格所形成的闭合回路。调运方案的任意空格存在唯一闭回路。销销产产B1B2B3B4供量供量A1 5 27A23 14A3 6 39销量销量 36561、闭回路法闭回路法二、最优解的判别二、最优解的判别（检验数的求法）（检验数的求法）第三章 运输问题BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 15401025510101、闭回路法闭回路法+-+-检验数检验数BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6二、最优解的判别二、最优解的判别（检验数的求法）（检验数的求法）结论：结论：1、当所有检验数 ，则找到唯一最优方案。2、当所有检验数非负但存在0，则找到最优方案，但不唯一。3、当存在负的检验数即 ，则方案不是最优，需要调整。存在负检验数，非最优解2 运输问题的表上作业法2、位势法位势法B1B2B3B4A1412411A221039A385116B1 B2 B3 B4 产量产量A116A2810A314822销量销量814 12 14B1B2B3B4uiA1(4)(11)A2(2)A3(5)(6)vj例例2 求最小元素法所给方案的检验数求最小元素法所给方案的检验数单位运价表单位运价表初始方案初始方案位势法检验数表位势法检验数表0411-1-5310121-11012(3)2106ui 称为行位势称为行位势，vj 称为列位势称为列位势第三章 运输问题BjAi B1 B2 B3 B4 A1 4010 25 5 2 5 3 A2 4 3 10 1 10 2 A3 10 5 6 3 4BjAi B1 B2 B3 B4 ui A1(10)(5)(3)A2(1)(2)A3(5)vj位势法检验数表位势法检验数表-5-10 6 6 6-223见见 Ex.1 最小元素法得到的初始基可行解最小元素法得到的初始基可行解0-1-5-1027 105322 运输问题的表上作业法三、基可行解的改进三、基可行解的改进BjAi B1 B2 B3 B4 ai A110 5 2 3 70 A2 4 3 1 2 20 A3 5 6 3 4 10 bj 50 25 10 1540102551010BjAi B1 B2 B3 B4 A1 A2 A3检验数表检验数表-5-10 6 6 6选择进基变量选择进基变量则取非基变量则取非基变量 xst 为进基变量为进基变量确定出基变量确定出基变量调整量调整量则基变量则基变量 xkl 出基（运量擦去）出基（运量擦去）调整方法：在该闭回路上，奇点运量加调整方法：在该闭回路上，奇点运量加 ，偶点减去，偶点减去 能转运多少能转运多少？153010 6 5 4 2010 1-5 6 520 6 6 4 5 6 因为因为 ，所以此运输方案为最优方案所以此运输方案为最优方案Note:若在闭回路上有几个偶点处的运量相等，则若在闭回路上有几个偶点处的运量相等，则可任取其中一个作为出基变量（运量擦去），其余几可任取其中一个作为出基变量（运量擦去），其余几个点的值调整后变为个点的值调整后变为0.(0.(但应填入，说明这些变量还但应填入，说明这些变量还在基内，这时就出现了退化在基内，这时就出现了退化)问：问：从从A2到到B4的单位运价的单位运价c24在什么范围变化时，所得在什么范围变化时，所得最优调运方案不变最优调运方案不变.c12在什么范围变化呢？在什么范围变化呢？考研真题：考研真题：1（10分，同济大学）已知运输问题的产销平衡表和单位运价表如表所示，求该运输模型的最优解。第三章 运输问题四、产销不平衡运输问题四、产销不平衡运输问题当当Note:通常建立运输模通常建立运输模型指的是平衡运输模型型指的是平衡运输模型可以虚设一个产地可以虚设一个产地 Am+1,其产量为其产量为 并假设产地并假设产地 Am+1 运运往各销地的单往各销地的单位运价为位运价为 cm+1,j=0(j=1,2,n).则原问题可转则原问题可转化为平衡运输问题：化为平衡运输问题：产大于销，可通产大于销，可通过虚设销地，类似过虚设销地，类似建立平衡运输模型建立平衡运输模型例例 2.某公司从两个产地某公司从两个产地 A1、A2 将物品运往三个将物品运往三个销地销地 B1、B2、B3，各产地的产量、各销地的销，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表量和各产地运往各销地每件物品的运费如表 7-3 所示，所示，问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？一区一区二区二区三区三区产量产量山西盂县1.801.701.554000河北临城1.601.501.751500需要量300010002000例例3.石家庄北方研究院有三个区，即一区，二区，石家庄北方研究院有三个区，即一区，二区，三区，每年分别需要用煤三区，每年分别需要用煤 3 000 t、1 000 t、2 000 t，由河北临城、山西盂县两处煤矿负责供应，价，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为格、质量相同。供应能力分别为 1 500 t、4 000 t，运价如表，运价如表 所示。所示。由于需大于供，经院研究决定一区供应量可减少由于需大于供，经院研究决定一区供应量可减少 0300 t，二区必须满足需求量，三区供应量不少，二区必须满足需求量，三区供应量不少于于 1 500 吨，试求总费用为最低的调运方案。吨，试求总费用为最低的调运方案。一区一区1 一区一区2二区二区三区三区1三区三区2产量产量山西盂县1.801.801.701.551.554000河北临城1.601.601.501.751.751500假想生产点M0MM0500需要量27003001000150050060006000这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0.B1B2B3B4产量A11613221750A21413191560A319202350最低要求3070010最高要求507030不限练习练习.设设有三个化肥厂供有三个化肥厂供应应四个地区的四个地区的农农用化肥。各化肥用化肥。各化肥厂的年厂的年产产量，各地区的需求量，以及各化肥厂到各地区运量，各地区的需求量，以及各化肥厂到各地区运送送单单位化肥的运价如下表所示，位化肥的运价如下表所示，请请写出写出产销产销平衡运平衡运输输表。表。