沈阳理工大学物流系统规划设计课程设计_运输问题模型和求解方法的研究.doc

沈阳理工大学课程实践（论文）摘 要运输问题是运筹学的一个分支，是线性规划的特殊形式。它研究的是如何在物资调运中，制定出一个由若干个产地将物资根据已知的运输交通网运到各个销售地的方案，使得总运费最小。运输是整个物流活动中的核心，运输管理是物流活动统筹规划和管理的重要部分，对运输环节进行规划和优化，对提高物流活动的效率有着重要意义。物流被称为“第三利润源泉”，而运输成本又在整个物流成本中占得比例最大。合理的设计运输方案，可以降低企业的物流成本，也就意味着增加了企业的利润。本文通过对运输问题模型和求解方法的研究，在产销平衡的条件下，运用不同的方法：表上作业法、vogel法和excel软件对运输问题进行求解。运用表上作业法或vogel法的基本思路是：初始方案的确定最优解的检验调运方案的调整。其求解步骤相对较为繁琐，所以又介绍了excel软件的求解方法，该方法相对简单，而且准确快速，但是转换建模相对困难。总之，各种方法都有其优点和缺点，在解决实际问题中，我们可以根据实际情况选择一种或几种方法进行求解。关键词：线性规划；运输问题；表上作业法；excel；vogel法目 录1 前言11.1 作业背景11.2 选题说明11.2.1 基本思路11.2.2 作业目标21.3 工作业绩21.3.1 个人主要工作21.3.2 主要收获21.3.3 自我评定31.3.4 小组成员任务分工情况32 物流运输概述42.1 物流与运输42.2.1 物流运输的概念42.2.2 运输在物流中的地位42.2 运输合理化42.2.1 不合理运输42.2.2 影响运输合理化的因素53 线性规划与运输问题63.1 线性规划63.2 运输问题74 运输问题的求解方法104.1 单纯形法104.2 表上作业法104.2.1 初始方案的确定114.2.2 最优解的检验144.2.3 调运方案的改进154.3 excel规划求解方法165 某物流企业煤炭运输项目方案求解20结束语22参考文献2323沈阳理工大学课程实践（论文）1 前言1.1 作业背景本文根据物流系统规划与设计课程要求而做。课程作业要求如下：根据物流方案策划与设计原理，根据所学的专业知识对一个具体的物流项目进行规划与设计。1.根据课程实践时间选择适当规模大小的设计课题。针对物流管理的具体特点，体现项目管理的思想，可由指导教师对学生进行分组（每组3-6人），一组一题，分工合作，共同完成（也可以选定某一物流项目或方案，独立完成）。2.根据合理的进度安排，按照所学原理与实际案例，踏实地开展课程实践活动。3.课程实践过程中，根据选题的具体需求，在开发各环节中撰写相关的技术文档，最后要求提交详细的课程实践报告。4.重点放在方案的可行性与操作性上，内容要有逻辑性，测算要准确。5.提供的方案要具有专业性，并经教师和专家的检查。1.2 选题说明运输问题是线性规划的一种特殊形式，运输问题主要是解决这样的问题：在物资进行调运时，有若干个产地，根据已知的交通运输网，如何制定一个运输方案，将这些物资运到各个销售地，使得总运费最小。物流管理的本质要求就是求实效，以最少的成本，实现最优的服务，达到最佳的经济效益。物流被称为“第三利润源泉”，而运输成本又在整个物流成本中占得比例最大。搞好物流管理，可以通过设计合理的运输方案，使中间装卸搬运、储存费用降低、损失减少，在其他条件不变的情况下，降低物流成本，也就意味着扩大了企业的利润空间，所以一个合理的、有效的运输方案有着重要的意义。1.2.1 基本思路首先分析运输与物流的关系及运输在物流活动中的重要地位，引出为什么要研究运输问题。然后探讨运筹学中线性规划方法在物流运输问题的中应用，主要方法是基于单纯形法的表上作业法和vogel法，这两种方法是单纯形法的简化方法，能够帮助我们以图表的形式快速求解出最优的运输方案，另外本文中还介绍了使用excel求解线性规划，它能帮助我们减少计算量，从而更加快速、准确的得到最优解。最后根据上面介绍的方法对实际问题中的运输案例进行算例演示，主要是建立模型，把不平衡问题转化为产销平衡的问题后运用表上作业法进行求解。1.2.2 作业目标通过对运筹学中线性规划方法对物流运输问题的应用，熟练掌握表上作业法和vogel法的计算方法、对给定方案最优性的检验，以及对不是最优方案进行优化；并学会运用excel工具建立模型进行线性规划的求解。能够对实际情况中各种不同的产销不平衡问题进行建模，转化为平衡的问题从而进行求解。1.3 工作业绩1.3.1 个人主要工作本次课程设计是由我独立完成的，主要进行了对运输问题的线性规划方法研究，包括前期的选题，查找和收集资料，根据以前学习过的运筹学基础知识，掌握熟练运用表上作业法和vogel这两种方法，在学习的过程中对大量的运输问题进行了演算；然后又自行学习了excel软件的线性规划求解方法，对算例进行了反复的修改和试验。最后又进行了多次的检查和修改后撰写成文。1.3.2 主要收获最初因为自己对运筹学比较感兴趣，所以选择了运筹学中线性规划在物流运输问题中应用这个选题方向。但在后来的资料查找与收集、整理中才发现运输问题是很复杂的，尤其在实际问题中涉及到很多的约束条件、多个目标函数要考虑。鉴于自习的学习和研究能力有限，并且在老师的指导建议下，最终缩小了范围，只对产销平衡运输问题和简单的不平衡问题进行研究。从构思到开始撰写成文的过程中遇到了很多的困难，因为运用到了运筹学的相关知识，所以文中多次出现很多公式，以前又没有接触过在编写的过程中遇到了许多问题，然后通过上网学习和同学间互相研究讨教，运用mathtype数学公式编辑器最终解决了这个难题。第4章是本文中最重要的部分，以案例为例具体介绍了表上作业法的计算步骤，在进行这部分的编写时，我在以前学习过的运筹学基础上又从新进行了一遍学习，在这一遍复习的过程中对运筹学的知识又有了新的认识，熟练掌握了运用表上作业法和vogel法求解物流运输问题的方法。此外运用excel软件求解线性规划问题对自己来说也是一个全新的学习过程，自己先在网上查找了相关的学习资料进行了学习，然后在计算机上输入算例一点点进行试验，开始因为地方的专业用语或表示方法看不懂和不会运用，在运行的过程中出现了很多错误以致无法运算或者无法得到最优解。不过通过不断的对比资料，一点点的摸索和反复的试验，我最终掌握了excel软件求解线性规划的方法。虽然学习新方法的过程是很费时费力的，但最后能够掌握新的知识并运用它解决了一些问题后，感觉很有成功感。通过这次的课程设计，也使我对物流系统规划和运筹学的理论知识应用到实践有了更多的认识，自己得到了锻炼，加强了自己学习和动手操作的能力，收获很多。最后还要感谢老师和同学在课程设计中给予我的各种帮助和指导。1.3.3 自我评定 r优 良 中 及格 不及格1.3.4 小组成员任务分工情况学号姓名任务备注2 物流运输概述2.1 物流与运输2.2.1 物流运输的概念物流的运输专指“物”的载运及输送。它是在不同地域范围间（如两个城市、两个工厂之间，或一大企业内相距较远的两车之间），以改变“物”的空间位置为目的的活动，是对“物”进行的空间位移。2.2.2 运输在物流中的地位1.运输是物流系统的基础功能之一。物流系统是通过运输来完成对客户所需的原材料、半成品和制成品的地理定位的。2.运输合理化是物流系统合理化的关键。3.便利和可靠的运输服务，是有效组织输入和输出物流的关键。同时，企业的工厂、仓库与其供货厂商和用户之间的地理分布直接影响着物流的运输作用。因此，运输条件是企业选择工厂、仓库、配送中心等物流设施配置地点所要考虑的主要因素之一。4.运输影响着物流的其它构成因素。例如选择的运输方式决定着装运货物的包装要求，使用不同类型的运输工具决定其配套使用的装卸搬运设备以及接收和发运站台的设计等；企业库存储备量的大小，直接受运输状况的影响，发达的运输系统能比较适量、快速和可靠地补充库存，以减少不必要的储备水平。5.运输费用在物流费用中占有很大的比重。组织合理运输，以最小的费用，较快的时间，及时、准确，安全地将货物从其产地送达销地，是降低物流费用和提高经济效益的重要途径之一。2.2 运输合理化2.2.1 不合理运输不合理运输是在现有条件下可以达到的运输水平而末达到，从而造成了运力浪费、运输时间增加、运费超支等问题的运输形式。不合理运输的主要形式有：1.对流运输。是指同一种货物，或彼此间可以互相代用而又不影响管理、技术及效益的货物，在同一线路上或平行线路上作相对方向的运送，而与对方运程的全部或一部分发生重叠交错的运输。2.迂回运输。是舍近取远的一种运输，可以选取短距离进行运输而却选择路程较长路线进行运输的一种不合理形式。3.重复运输。本来可以直接将货物运到目的地，但是在未达目的地之处，或目的地之外的其它场所将货卸下，再重复装运送达目的地。3.倒流运输。是指货物从销地或中转地向产地或起运地回流的一种运输现象。4.过远运输。是指调运物资舍近求远，近处有资源不调而从远处调，这就造成可采取近程运输而未采取，拉长了货物运距的浪费现象。5.运力选择不当。是指没有根据各种运输工具的优势不正确地利用运输工具造成的不合理现象。2.2.2 影响运输合理化的因素影响物流运输合理化的因素很多，起决定性作用的有以下五个方面因素：1.运输距离。运输过程中，运输时间、运费等若干技术经济指标都与运距有一定的关系，运距长短与否是运输是否合理的一个最基本的因素。2.运输环节。每增加一个运输环节，势必要增加运输的附属活动，如装卸，搬运等，各项技术经济指标也会因此发生改变，因此减少运输环节有一定的促进作用。3.运输工具。各种运输工具都有其优势领域，对运输工具进行优化选择最大限度的发挥运输工具的特点和作用，是运输合理化的重要的一环。4.运输时间。在全部物流时间中运输时间占绝大部分，因此，运输时间的缩短对整个流通时间的缩短起着决定性的作用。此外，缩短运输时间，还能加速运输工具的周转，充分发挥运力的效能，不同程度地改善不合理的现象。5.运输费用。运费在全部物流费用中占很大的比例，运费高底在很大程度上决定整个物流系统的竞争能力。实际上，运费的相对高低，无论对货主还是对物流企业都是运输合理化的一个重要的指标。运费的高低也是各种合理化措施是否行之有效的最终判断依据之一。3 线性规划与运输问题3.1 线性规划经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现。这类统筹规划的问题用数学语言表达，先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示，对问题的限制条件用有关变量的等式或不等式表达。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。一般线性规划问题的数学模型可表示为： （3.1）最早提出线性规划想法的是法国数学家傅里叶和瓦莱.普森，分别于1832年和1911年独立提出的，但是那时并未引起注意。直到1939年，前苏联数学家康托洛维奇在生产组织与计划中的数学方法一书中，提出和研究了线性规划问题，但也未引起重视。1947年，美国数学家丹泽格提出了一般的线性规划数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。单纯形法的提出，推动了最优化理论的发展。1979年，前苏联数学家哈奇扬提出了运用求解线性不等式组解线性规划问题的椭球算法，并证明该算法是多项式时间算法。这算法的提出具有重要的意义，但其实际计算收敛速度极慢，实用效果比单纯形法差。1984年，在美国贝尔电话实验室工作的印度数学家卡玛卡提出了求解线性规划问题的投影尺度法，用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。这个多项式时间算法很有实用意义，这一算法的提出引起人们对内点算法的关注，此后相继出现了多种更为简便实用的内点算法。求解线性规划是非常复杂和耗时的一件事，为了省时省力又准确的得出结果，人们把目光转向了计算机求解，1952年，线性规划问题第一次在计算机上获得求解，这开始了人们对计算机求解线性规划的探索，现在已经有很多软件可以进行线性规划求解，如excel、lingo、matlab等。3.2 运输问题运输问题发展于线性规划问题，自从1939年提出了类似线性规划的模型后，人们发现许多问题都属于线性函数在约束条件下的最优化问题，在1940年hitchcock提出运输问题。运输问题属于线性规划问题的特殊情况，既有线性规划问题的共性，也有自身的特点和算法。运输问题提出后，1958年konterovich对运输问题做了早期的研究。运输问题的数学模型如下：已知某类物资有m个资源点（源点），=1，2，；其资源量分别为（=1，2，）；有n个需求点（终点），=1，2，；其需求量分别为（=1，2，）。从到运送单位货物的运费为。若用表示从到运输物资的数量，z为系统总运输费用。在产销平衡，即的条件下，要求得总运费最小的调运方案，可求解的数学模型： （3.2）但在现实生活中往往产销是不平衡的，这就需要把产销不平衡问题转化为产销平衡问题。当产大于销时，即时，运输问题的数学模型变为 （3.3）由于产大于销，所以多余的产品就要考虑在产地就地储存的问题，设是产地的储存量，有令，当，时，当，时，将其代入(3.3)得： （3.4）其中，这就转化成了一个平衡的运输问题。当销大于产时，也可以转化成为一个产销平衡问题，产大于销是假设多增设一个销售点，该销地的销量为，相应的运价变为。同样，当销大于产时也可以用同样的方法进行转换，这时假设多增加一个产地，其产量为，相应的运价为，然后转化成产销平衡问题。4 运输问题的求解方法4.1 单纯形法在运输问题的解法中最好最有效的方法是单纯形法，单纯形法求解线性规划的思路：先找出一个基本可行解，对它进行鉴别，看其是否是最优解；若不是，则按照一定的法则转换到另一改进的基本可行解，再进行鉴别；若仍不是，则再转换，按此重复进行。单纯形法的计算步骤如下：第一步：求出线性规划的初始基可行解，列出初始单纯形表；第二步：进行最优性检验。如果所有检验数都小于等于零，则基可行解就是最优解，否则进行下一步； 第三步：从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表；第四步：重复第二、三步一直到计算终止。4.2 表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质仍是单纯形法，其一般思路是：初始方案的确定最优解的检验调运方案的调整。分析实际问题列出产销平衡表及单位运价表确定初始调运方案（最小元素法或vogel法）求检验数（闭回路法或位势法）得到最优方案算出总的运价是所有检验数=0否找出绝对值最大的负检验数用闭回路调整，得出新的调运方案图4.1 表上作业法计算步骤在用表上作业法求解运输问题时，首先给出一个初始方案，一般来说，这个方案不会是最好的，因此需要给出一个判别准则，并对初始方案进行调整、改进，一直到求得最优方案为止。下面以一个案例对表上作业法的求解进行介绍。案例：某公司经销某种产品，它下设三个加工厂，有四个销售点，各加工厂每日的产量及各销售点每日销量、各加工厂到销售点的单位产品的运价如表4.1所示，问该公司应如何调运产品，在满足各销售点需求量的前提下，使得总运费最少。表4.1 产销平衡表及单位运价表销地产地b1b2b3b4产量（吨）a13113107a219284a3741059销量（吨）3656204.2.1 初始方案的确定初始方案的确定就是初始基可行解的确定。产销平衡的运输问题总是存在可行解。因为所以必存在可行解：0 =1，2， =1，2，又因为0min（，）故产销平衡的运输问题必存在最优解。确定初始基可行解的方法很多，常用的求解方法一般有：最小元素法和vogel法，简单又尽可能接近最优解的方法是vogel法。1.最小元素法最小元素法的基本方法就是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后依次类推，一直到给出全部方案为止。其步骤如下：第一步：在表4.1找出最小运价为1，先将a2的产品供应给b1。因 ，即a2 除满足b1的全部需要外，还多出1吨产品。在表4.2的（a2，b1）的交叉格处填上3，同时把表4.2中的b1列划掉；表4.2销地产地b1b2b3b4产量（吨）a13113107a2319284a3741059销量（吨）365620第二步：在表4.2中找出没有划掉的最小的运价2，把a2多余的1吨供应给b3，并在表4.3（a2，b3）交叉格中填上1，同时把表4.3的a2行划掉；表4.3销地产地b1b2b3b4产量（吨）a13113107a23191284a3741059销量（吨）365620第三步：同样在表4.3中找出没有划掉的最小的运价3，因为a2已经供应1吨给b3，所以a1供应4吨给b3，并在表4.4（a1，b3）交叉格中填上4，同时把表4.4的b3列划掉；表4.4销地产地b1b2b3b4产量（吨）a131143107a23191284a3741059销量（吨）365620第四步：在表4.4中找出没有划掉的最小的运价4，把 a3的6吨供应给b2，并在表4.5（a3，b2）交叉格中填上6，同时把表4.5的b2列划掉；表4.5销地产地b1b2b3b4产量（吨）a131143107a23191284a376410359销量（吨）365620第五步：在表4.5中找出没有划掉的最小的运价5，由于a3一共生产9吨，把 6吨供应给了b2，剩下的3吨全部供应给b4，并在表4.6（a3，b4）交叉格中填上3，同时把表4.6的a3行划掉；表4.6销地产地b1b2b3b4产量（吨）a131143107a23191284a376410359销量（吨）365620第六步：在表4.6中只剩下运价10没有划掉，由于a1一共生产7吨，把 4吨供应给了b3，剩下的3吨全部供应给b4，并在表4.6（a1，b4）交叉格中填上3，同时把表4.6的b4列划掉。到此已经把产地的产品全部分配到各销地，并得出表4.7运输方案，同时得出总运费为86元。表4.7 最小元素法运输方案销地产地b1b2b3b4产量（吨）a1311433107a23191284a376410359销量（吨）365620总运费=43+310+31+12+64+35=86元2.vogel法vogel法的基本思路是：产品如果不能按最小运费就近供应，就考虑次小运费，会产生一个差额，差额越大，说明不能按最小运费调运时，运费增加就越多，因而对差额最大处采用最小运费调运。vogel法的求解步骤是从运价表上分别找出每行与每列的最小的两个元素之差，再从差值最大的行或列中找出最小运价确定供需关系和供应数量。当产地或销地中有一方数量上供应完毕或得到满足时，划去运价表中对应的行或列，在重复上述步骤。求解过程及结果见下表：表4.8 vogel法计算过程销地产地b1b2b3b4两最小元素之差219281116a37410512两最小元素之差251321321212表4.9 vogel法运输方案销地产地b1b2b3b4产量（吨）a1527a2314a3639销量（吨）365620总运费=31+64+53+210+18+35=85元4.2.2 最优解的检验最优解的判别方法是计算空格的检验数。运输问题的目标函数是要求实现最小化，所以当时，为最优解。求空格检验的方法有两种：闭回路法和位势法，本文采用的是闭回路法。闭回路法的步骤是在初始解方案的计算表上，从每一空格出发找一条闭回路，即以某一个空格为起点，水平或垂直向前划，当碰到一个数字格时可以转90后，继续前进，直到回到原点为止。在例题中用最小元素法求出的初始解表4.7中，从任意一个空格出发，如（a1，b1），若让a1调运1吨产品给b1，为了保持产销平衡，则在（a1，b3）处减少1吨，（a2，b3）处增加1吨，（a2，b1）处减少1吨，构成了一个闭回路。这一闭回路增加的运费为：（+1）3+（-1）3+（+1）2+（-1）1=1（元），。这1就是空格（a1，b1）的检验数，同理可以找出所有空格的检验数，结果如下表：表4.10 检验数表空格闭回路检验数（a1，b1）（a1，b1）（a1，b3）（a2，b3）（a2，b1）（a1，b1）1（a1，b2）（a1，b2）（a1，b4）（a3，b4）（a3，b2）（a1，b2）2（a2，b2）（a2，b2）（a2，b3）（a1，b3）（a1，b4）（a3，b4）（a3，b2）（a2，b2）1（a2，b4）（a2，b4）（a2，b3）（a1，b3）（a1，b4）（a2，b4）-1（a3，b1）（a3，b1）（a3，b4）（a1，b4）（a1，b3）（a2，b3）（a2，b1）（a3，b1）10（a3，b3）（a3，b3）（a3，b4）（a1，b4）（a1，b3）（a3，b3）12当检验数存在负数时，说明原方案不是最优解，需要改进。4.2.3 调运方案的改进在进行最优解检验时，若出现负检验数，表明没有得出最优解，方案需要进行改进，本文采用改进的方法是闭回路调整法。闭回路调整法的思路是：以负检验数的空格为调入格，当负检验数为两个或两个以上时，一般选最小的负检验数，以它相对应的非基变量为换入变量。由表4.10可知，空格（a2，b4）的检验数为负，所以以该空格为调入格见表4.11，在该空格中调入量是以闭回路上具有（-1）的数字格中的最小者，即min（1，3）=1，然后按闭回路上的正、负号，进行加减得到调整方案，见表4.12，此时的总运费为85元。表4.11 方案调整销地产地b1b2b3b4产量（吨）a14（+1）3（-1）7a231（-1） (+1)4a3639销量（吨）3656表4.12 改进后的运输方案销地产地b1b2b3b4产量（吨）a1527a2314a3639销量（吨）3656总运费=31+64+53+210+18+35=85（元）对此调整后的方案再次用闭回路法进行检验，得出的检验数如下：表4.13 改进后的检验数表空格闭回路检验数（a1，b1）（a1，b1）（a1，b3）（a2，b3）（a2，b1）（a1，b1）0（a1，b2）（a1，b2）（a1，b4）（a3，b4）（a3，b2）（a1，b2）2（a2，b2）（a2，b2）（a2，b3）（a1，b3）（a1，b4）（a3，b4）（a3，b2）（a2，b2）2（a2，b4）（a2，b4）（a2，b3）（a1，b3）（a1，b4）（a2，b4）1（a3，b1）（a3，b1）（a3，b4）（a1，b4）（a1，b3）（a2，b3）（a2，b1）（a3，b1）9（a3，b3）（a3，b3）（a3，b4）（a1，b4）（a1，b3）（a3，b3）12表中的所有检验数都是非负数，说明表4.12的结果是最优解。同时也说明vogel法给出的初始解比最小元素法给出的初始解更接近最优解。4.3 excel规划求解方法在进行运输问题求解时，传统的解法是表上作业法，虽然表上作业法已经是最简单的，但是在求解过程中还是会消耗大量的时间，特别是大规模的运输问题，表上作业法就显得很复杂。随着计算机的出现，人们开始尝试用计算机对运输问题进行求解，至今已经有很多软件是针对线性规划而设计的，如excel的规划求解，以及专业的求解工具lingo等。excel的“规划求解”功能强大，它可以实现对有多个决策变量的线性规划问题的求解，回避了用线性规划专业软件求解时对操作者的专业要求，同时也克服了笔算的缺点，其操作方法简单、方便、快捷，大大提高了计算的效率与准确性。excel与专业软件相比，有以下特点：1、excel软件方便易学，大部分人都比较熟悉，容易掌握；2、能用表格简单直观地体现数学模型；3、excel具有大量的内建函数，通过设置参数，就能进行复杂的计算，建模过程简单；4、excel软件具有强大的数据分析功能。excel求解的步骤如下（以4.2中案例为例）：1.创建表格图4.1 创建表格2.建立目标函数和约束条件目标函数：c10=sumproduct(b2:e2，b3:e3)+sumproduct(b4:e4，b5:e5)+ sumproduct(b6:e6，b7:e7)约束条件：b8=sum（b3+b5+b7）；c8=sum（c3+c5+c7）；d8=sum（d3+d5+d7）；e8=sum（e3+e5+e7）；f3=sum（b3+c3+d3+e3）；f5=sum（b5+c5+d5+e5）；f7=sum（b7+c7+d7+e7）；b3:e30；b5:e50；b7:e70；b8=b9；c8=c9；d8=d9；e8=e9；f3=g3；f5=g5；f7=g7；图4.2 约束条件和目标函数3.设置规划求解参数图4.3 规划求解参数4. 设置规划求解选项图4.4 规划求解选项图5.规划求解结果图4.5 规划求解6. 计算结果图4.6 excel求解的结果由图4.6计算结果可知，运用excel求解的结果和用表上作业法求得的结果是一致的。5 某物流企业煤炭运输项目方案求解案例：某物流企业承包了一个冬季供暖的煤炭运输项目，有a、b、c三个煤矿为、四个地区供应冬季的用煤。已知各煤矿的年产量及从各煤矿到各地区单位煤炭的运输费用如表5.1所示，设计一个使总运费最节省的煤炭调拨方案。表5.1销地煤矿产量（万吨）a1613221750b1413191560c19202350最低需求（万吨）最高需求（万吨）3050707003010不限分析：实际问题中的运输问题一般都是产销不平衡的问题，根据表5.1中数据，总产量为50+60+50=160万吨，四个地区的最低需求为30+70+10=110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，此时最高需求为50+70+30+60=210万吨110万吨。为了使产销平衡，需要设一个虚拟的煤矿d，并设其年产量为50万吨。由于各地的需求分最低和最高两种，以第个地区为例，最低需求30万吨是必须满足的条件，所以不可以由虚拟煤矿d供应，可令对应的运价为无限大的正数（极为m），而其余的20万吨是可以满足也可以不满足的，所以这部分可以由d供应，对应运价为0。根据上述分析可写出产销平衡表5.2和单位运价表5.3表5.2 产销平衡表销地煤矿*产量（万吨）a50b60c50d50销量（万吨）302070301050210表5.3 单位运价表销地煤矿*产量（万吨）a16161322171750b14141319151560c19192023mm50dm0m0m050销量（万吨）302070301050210按照4.2节中介绍的表上作业法求得案例的最优方案如表5.4所示表5.4 最优方案销地煤矿*产量（万吨）a5050b20103060c3020050d302050销量（