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

精选学习资料 - - - - - - - - - 摘 要运输问题是运筹学地一个分支,是线性规划地特殊形式.它讨论地是如何在物资调运中,制定出一个由如干个产地将物资依据已知地运输交通网运到各个销售地地方案,使得总运费最小 .运输是整个物流活动中地核心,运输治理是物流活动统筹规划和治理地重要部分,对运输环节进行规划和优化,对提高物流活动地效率有着重要意义.物流被称为 “第三利润源泉 ” ,而运输成本又在整个物流成本中占得比例最大 .合理地设计运输方案,可以降低企业地物流成本,也就意味着增加了企业地利润 .本文通过对运输问题模型和求解方法地讨论,在产销平稳地条件下,运用不同地方法：表上作业法、 Vogel 法和 Excel 软件对运输问题进行求解. 最优解地检验调运方案地运用表上作业法或Vogel 法地基本思路是：初始方案地确定调整 .其求解步骤相对较为繁琐,所以又介绍了Excel 软件地求解方法,该方法相对简洁,而且精确快速,但是转换建模相对困难 .总之,各种方法都有其优点和缺点,在解决实际问题中,我们可以依据实际情形挑选一种或几种方法进行求解 .关键词：线性规划；运输问题；表上作业法；Excel；Vogel 法名师归纳总结 - - - - - - -第 1 页,共 23 页精选学习资料 - - - - - - - - - 目 录1 前言································································ ································· 0 1.1 作业背景 ······················································································· 0 1.2 选题说明 ······················································································· 0 1.2.1 基本思路 ················································································ 0 1.2.2 作业目标 ················································································ 1 1.3 工作业绩 ······················································································· 1 1.3.1 个人主要工作 ·········································································· 1 1.3.2 主要收成 ················································································ 1 1.3.3 自我评定 ················································································ 2 1.3.4 小组成员任务分工情形 ······························································ 2 2 物流运输概述···················································································· 2 2.1 物流与运输 ···················································································· 2 2.2.1 物流运输地概念 ······································································· 2 2.2.2 运输在物流中地位置 ································ ································· 2 2.2 运输合理化 ···················································································· 3 2.2.1 不合理运输 ············································································· 3 2.2.2 影响运输合理化地因素 ······························································ 3 3 线性规划与运输问题············································································ 4 3.1 线性规划 ······················································································· 4 3.2 运输问题 ······················································································· 5 4 运输问题地求解方法············································································ 7 4.1 单纯形法 ······················································································· 7 4.2 表上作业法 ···················································································· 7 4.2.1 初始方案地确定 ······································································· 8 4.2.2 最优解地检验 ········································································· 11 4.2.3 调运方案地改进 ······································································ 12 4.3 Excel规划求解方法······································································· 135 某物流企业煤炭运输工程方案求解························································· 17终止语······························································· ································ 19 参考文献····························································································· 19名师归纳总结 - - - - - - -第 2 页,共 23 页精选学习资料 - - - - - - - - - 1 前言1.1 作业背景本文依据物流系统规划与设计课程要求而做 . 课程作业要求如下：依据物流方案策划与设计原理,依据所学地专业学问对一个具体地物流工程进行规划与设 计.1.依据课程实践时间挑选适当规模大小地设计课题 理地思想,可由指导老师对同学进行分组（每组（也可以选定某一物流工程或方案,独立完成）.针对物流治理地具体特点,表达工程管 3-6 人）,一组一题,分工合作,共同完成2.依据合理地进度支配,依据所学原理与实际案例,踏实地开展课程实践活动 .3.课程实践过程中,依据选题地具体需求,在开发各环节中撰写相关地技术文档,最终要求提交具体地课程实践报告 .4.重点放在方案地可行性与操作性上,内容要有规律性,测算要精确 .5.供应地方案要具有专业性,并经老师和专家地检查 .1.2 选题说明运输问题是线性规划地一种特殊形式,运输问题主要是解决这样地问题：在物资进行调运时,有如干个产地,依据已知地交通运输网,如何制定一个运输方案,将这些物资运到各个销售地,使得总运费最小 .物流治理地本质要求就是求实效,以最少地成本,实现最优地服务,达到正确地经济效益 .物流被称为 “第三利润源泉 ” ,而运输成本又在整个物流成本中占得比例最大 .搞好物流治理,可以通过设计合理地运输方案,使中间装卸搬运、储存费用降低、缺失削减,在其他条件不变地情形下,降低物流成本,也就意味着扩大了企业地利润空间,所以一个合理地、有效地运输方案有着重要地意义 .1.2.1 基本思路第一分析运输与物流地关系及运输在物流活动中地重要位置,引出为什么要讨论运输问题 .然后探讨运筹学中线性规划方法在物流运输问题地中应用,主要方法是基于单纯形法地表上作业法和 Vogel 法,这两种方法是单纯形法地简化方法,能够帮忙我们以图表地势式快速求解出最优地运输方案,另外本文中仍介绍了使用Excel 求解线性规划,它能帮忙我们削减运算量,名师归纳总结 从而更加快速、精确地得到最优解.最终依据上面介绍地方法对实际问题中地运输案例进行算例第 3 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - 演示,主要是建立模型,把不平稳问题转化为产销平稳地问题后运用表上作业法进行求解 .1.2.2 作业目标通过对运筹学中线性规划方法对物流运输问题地应用,娴熟把握表上作业法和 Vogel 法地运算方法、对给定方案最优性地检验,以及对不是最优方案进行优化；并学会运用 Excel 工具建立模型进行线性规划地求解 平稳地问题从而进行求解 .1.3 工作业绩1.3.1 个人主要工作.能够对实际情形中各种不同地产销不平稳问题进行建模,转化为本次课程设计是由我独立完成地,主要进行了对运输问题地线性规划方法讨论,包括前期 地选题,查找和收集资料,依据以前学习过地运筹学基础学问,把握娴熟运用表上作业法和Vogel 这两种方法,在学习地过程中对大量地运输问题进行了演算；然后又自行学习了 Excel 软件地线性规划求解方法,对算例进行了反复地修改和试验 写成文 .1.3.2 主要收成.最终又进行了多次地检查和修改后撰最初由于自己对运筹学比较感爱好,所以挑选了运筹学中线性规划在物流运输问题中应用 这个选题方向 .但在后来地资料查找与收集、整理中才发觉运输问题是很复杂地,特殊在实际问题中涉及到很多地约束条件、多个目标函数要考虑.鉴于自习地学习和讨论才能有限,并且在老师地指导建议下,最终缩小了范畴,只对产销平稳运输问题和简洁地不平稳问题进行讨论 . 从构思到开头撰写成文地过程中遇到了很多地困难,由于运用到了运筹学地相关学问,所以文中多次显现很多公式,以前又没有接触过在编写地过程中遇到了很多问题,然后通过上网学习和同学间相互讨论讨教,运用MathType 数学公式编辑器最终解决了这个难题.第 4 章是本文中最重要地部分,以案例为例具体介绍了表上作业法地运算步骤,在进行这部分地编写时,我在以前学习过地运筹学基础上又从新进行了一遍学习,在这一遍复习地过程中对运筹学地知识又有了新地熟识,娴熟把握了运用表上作业法和Vogel 法求解物流运输问题地方法.此外运用Excel 软件求解线性规划问题对自己来说也是一个全新地学习过程,自己先在网上查找了相关 地学习资料进行了学习,然后在运算机上输入算例一点点进行试验,开头由于地方地专业用语或表示方法看不懂和不会运用,在运行地过程中显现了很多错误以致无法运算或者无法得到最名师归纳总结 优解 .不过通过不断地对比资料,一点点地摸索和反复地试验,我最终把握了Excel 软件求解线第 4 页,共 23 页- - - - - - -精选学习资料 - - - - - - - - - 性规划地方法 .虽然学习新方法地过程是很费时费劲地,但最终能够把握新地学问并运用它解决了一些问题后,感觉很有胜利感 .通过这次地课程设计,也使我对物流系统规划和运筹学地理论学问应用到实践有了更多地熟识,自己得到了锤炼,加强了自己学习和动手操作地才能,收成很多 .最终仍要感谢老师和同学在课程设计中赐予我地各种帮忙和指导 .1.3.3 自我评定优良中及格不及格1.3.4 小组成员任务分工情形学号姓名任务备注2 物流运输概述2.1 物流与运输2.2.1 物流运输地概念物流地运输专指“ 物”地载运及输送 .它是在不同地域范畴间（如两个城市、两个工厂之间,或一大企业内相距较远地两车之间）,以转变“ 物”地空间位置为目地地活动,是对“物” 进行地空间位移 .2.2.2 运输在物流中地位置1.运输是物流系统地基础功能之一 品和制成品地地理定位地 .物流系统是通过运输来完成对客户所需地原材料、半成2.运输合理化是物流系统合理化地关键 .3.便利和牢靠地运输服务,是有效组织输入和输出物流地关键 .同时,企业地工厂、仓库与其供货厂商和用户之间地地理分布直接影响着物流地运输作用.因此,运输条件是企业挑选工厂、仓库、配送中心等物流设施配置地点所要考虑地主要因素之一 .4.运输影响着物流地其它构成因素.例如挑选地运输方式打算着装运货物地包装要求,使用不同类型地运输工具打算其配套使用地装卸搬运设备以及接收和发运站台地设计等；企业库存名师归纳总结 - - - - - - -第 5 页,共 23 页精选学习资料 - - - - - - - - - 储备量地大小,直接受运输状况地影响,发达地运输系统能比较适量、快速和牢靠地补充库存,以削减不必要地储备水平 .5.运输费用在物流费用中占有很大地比重.组织合理运输,以最小地费用,较快地时间,及时、精确,安全地将货物从其产地送达销地,是降低物流费用和提高经济效益地重要途径之一 .2.2 运输合理化2.2.1 不合理运输不合理运输是在现有条件下可以达到地运输水平而末达到,从而造成了运力铺张、运输时间增加、运费超支等问题地运输形式.不合理运输地主要形式有：1.对流运输 .是指同一种货物,或彼此间可以相互代用而又不影响治理、技术及效益地货物,在同一线路上或平行线路上作相对方向地运输,而与对方运程地全部或一部分发生重叠交错地运输 .2.迂回运输 .是舍近取远地一种运输,可以选取短距离进行运输而却挑选路程较长路线进行运输地一种不合理形式 .3.重复运输 .原来可以直接将货物运到目地地,但是在未达目地地之处,或目地地之外地其它场所将货卸下,再重复装运输达目地地 .3.倒流运输 .是指货物从销地或中转地向产地或起运地回流地一种运输现象 .4.过远运输 .是指调运物资舍近求远,近处有资源不调而从远处调,这就造成可实行近程运输而未实行,拉长了货物运距地铺张现象 .5.运力挑选不当 .是指没有依据各种运输工具地优势不正确地利用运输工具造成地不合理现象.2.2.2 影响运输合理化地因素影响物流运输合理化地因素很多,起打算性作用地有以下五个方面因素：1.运输距离 .运输过程中,运输时间、运费等如干技术经济指标都与运距有肯定地关系,运距长短与否是运输是否合理地一个最基本地因素 .2.运输环节 .每增加一个运输环节,势必要增加运输地附属活动,如装卸,搬运等,各项技术经济指标也会因此发生转变,因此削减运输环节有肯定地促进作用 .3.运输工具 .各种运输工具都有其优势领域,对运输工具进行优化挑选最大限度地发挥运输工具地特点和作用,是运输合理化地重要地一环 .4.运输时间 .在全部物流时间中运输时间占绝大部分,因此,运输时间地缩短对整个流通时名师归纳总结 - - - - - - -第 6 页,共 23 页精选学习资料 - - - - - - - - - 间地缩短起着打算性地作用.此外,缩短运输时间,仍能加速运输工具地周转,充分发挥运力地效能,不同程度地改善不合理地现象 .5.运输费用 .运费在全部物流费用中占很大地比例,运费高底在很大程度上打算整个物流系统地竞争才能 .实际上,运费地相对高低,无论对货主仍是对物流企业都是运输合理化地一个重要地指标 .运费地高低也是各种合理化措施是否行之有效地最终判定依据之一 .3 线性规划与运输问题3.1 线性规划经营治理中如何有效地利用现有人力物力完成更多地任务,或在预定地任务目标下,如何耗用最少地人力物力去实现.这类统筹规划地问题用数学语言表达,先依据问题要达到地目标选取适当地变量,问题地目标通过用变量地函数形式表示,对问题地限制条件用有关变量地等式或不等式表达 .当变量连续取值,且目标函数和约束条件均为线性时,称这类模型为线性规划地模型 .一般线性规划问题地数学模型可表示为：max 或 min z c x 1 c x 2 L c x na x 11 1 a x 12 2 L a x 1 n n（或 =, ）b 1a x 21 1 a x 22 2 L a 2 n x n（或 =, ）b 2st . L L（3.1）a m 1 x 1 a m 2 x 2 L a mn x n（或 =, ）b mx x 1 2 , L x n 0最早提出线性规划想法地是法国数学家傅里叶和瓦莱 .普森,分别于 1832 年和 1911 年独立提出地,但是那时并未引起留意.直到 1939 年,前苏联数学家康托洛维奇在生产组织与方案中地数学方法一书中,提出和讨论了线性规划问题,但也未引起重视 .1947 年,美国数学家丹泽格提出了一般地线性规划数学模型和求解线性规划问题地通用方法单纯形法,为这门学科奠定了基础 .单纯形法地提出,推动了最优化理论地进展 .1979 年,前苏联数学家哈奇扬提出了运用求解线性不等式组解线性规划问题地椭球算法,并证明该算法是多项式时间算法.这算法地提出具有重要地意义,但其实际运算收敛速度极慢,有用成效比单纯形法差 .1984 年,在美国贝尔电话试验室工作地印度数学家卡玛卡提出了求解线性规划问题地投影尺度法,用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间地 1/50.这个多项式时间算法很有有用意义,这一算法地提出引起人们对内点算法地关注,此后相继显现了多种更为简便有用地内点算法.求解线性规划是特别复杂和耗时地一件名师归纳总结 - - - - - - -第 7 页,共 23 页精选学习资料 - - - - - - - - - 事,为了省时省力又精确地得出结果,人们把目光转向了运算机求解,1952 年,线性规划问题第一次在运算机上获得求解,这开头了人们对运算机求解线性规划地探究,现在已经有很多软件可以进行线性规划求解,如3.2 运输问题Excel 、Lingo 、Matlab 等.运输问题进展于线性规划问题,自从 1939 年提出了类似线性规划地模型后,人们发觉许多问题都属于线性函数在约束条件下地最优化问题,在1940 年 Hitchcock 提出运输问题 .运输问题属于线性规划问题地特殊情形,既有线性规划问题地共性,也有自身地特点和算法 .运输问题提出后, 1958 年 Konterovich 对运输问题做了早期地讨论 .运输问题地数学模型如下：已知某类物资有 m 个资源点（源点）,iA , i =1, 2, , m ；其资源量分别为 ia（ i =1,2, , m ）；有 n 个需求点（终点）,B , j =1,2, , n ；其需求量分别为 jb（ j =1,2, , n ）.从 iA 到 B 运输单位货物地运费为 ijc .如用 ijx 表示从 iA 到 B 运输物资地m n数量, z 为系统总运输费用 .在产销平稳,即 a i b j 地条件下,要求得总运费最小地调i 1 j 1运方案,可求解地数学模型：minzimjn1c x ij1n名师归纳总结 xija i1,2,L,m.第 8 页,共 23 页j1s t . .mxijbj,j1,2,L,n（3.2）i1x ij0但在现实生活中往往产销是不平稳地,这就需要把产销不平稳问题转化为产销平稳问题mn当产大于销时,即a ibj时,运输问题地数学模型变为i1j1- - - - - - -精选学习资料 - - - - - - - - - minzmnc x iji1j1ix,n1是产地iA 地储nx ija i1,2,L,mj1s t . .mx ijbj,j1,2,L,n（3.3）i1x ij0由于产大于销,所以余外地产品就要考虑在产地就地储存地问题,设存量,有令' c ijc ij,当in1x i n1ain1x ijai,1ij1,2, L,mx ijj1bj,j1n1,2,L,nmx iji1mmx i nbjb ni1i1j,1j1i,12,m,2,n时,当,12 ,m,jn1时,' ijc0将其代入 3.3得：其中,ima imin' zmn1' c x ijmn' c x ijm' c i n1x ijimjn1c x ij（3.4）s t .n1i1j1i1j1i11.x ija i1,2, L,mj1mx ijbj,j1,2, L,ni10x ijnn1b n1jbb ,这就转化成了一个平稳地运输问题1j1j1当销大于产时,也可以转化成为一个产销平稳问题,产大于销是假设多增设一个销售点名师归纳总结 jn1,该销地地销量为ima ijn1b ,相应地运价变为c i n '10.同样,当销大于产时第 9 页,共 23 页1- - - - - - -精选学习资料 - - - - - - - - - n m也可以用同样地方法进行转换,这时假设多增加一个产地,其产量为j1bji1a i,相应地运价为' c m,1 j0,然后转化成产销平稳问题.4 运输问题地求解方法4.1 单纯形法在运输问题地解法中最好最有效地方法是单纯形法,单纯形法求解线性规划地思路：先找 出一个基本可行解,对它进行鉴别,看其是否是最优解；如不是,就依据肯定地法就转换到另 一改进地基本可行解,再进行鉴别；如仍不是,就再转换,按此重复进行 .单纯形法地运算步骤如下：第一步：求出线性规划地初始基可行解,列出初始单纯形表；其次步：进行最优性检验 行下一步；.假如全部检验数都小于等于零,就基可行解就是最优解,否就进第三步：从一个基可行解转换到另一个目标函数值更大地基可行解,列出新地单纯形表；第四步：重复其次、三步始终到运算终止 .4.2 表上作业法表上作业法是单纯形法在求解运输问题时地一种简化方法,其实质仍是单纯形法,其一般思路是：初始方案地确定 最优解地检验 调运方案地调整.分析实际问题列出产销 平稳表及单位运价表确定初始调运方案（最 小元素法或 Vogel 法）求检验数（闭回 路法或位势法）全部检验数 >=0 是得 到 最 优 方 案算出总地运价否找出肯定值最大地负检验数用 闭回路调整,得出新地调运方 案名师归纳总结 - - - - - - -第 10 页,共 23 页精选学习资料 - - - - - - - - - 图 4.1 表上作业法运算步骤 在用表上作业法求解运输问题时,第一给出一个初始方案,一般来说,这个方案不会是最 好地,因此需要给出一个判别准就,并对初始方案进行调整、改进,始终到求得最优方案为止 . 下面以一个案例对表上作业法地求解进行介绍 .案例：某公司经销某种产品,它下设三个加工厂,有四个销售点,各加工厂每日地产量及各销售点每日销量、各加工厂到销售点地单位产品地运价如表4.1 所示,问该公司应如何调运产品,在满意各销售点需求量地前提下,使得总运费最少 .表 4.1 产销平稳表及单位运价表销产地B1B2B3B4产量（吨）地A13 11 3 10 7 A21 9 2 8 4 A37 4 10 5 9 销量（吨）3 6 5 6 20 4.2.1 初始方案地确定初始方案地确定就是初始基可行解地确定d.产销平稳地运输问题总是存在可行解.由于mna ibji1j1所以必存在可行解：ijx 0 i =1,2, , m, j =1,2, , n又由于0 ijx min（a ,jb ）故产销平稳地运输问题必存在最优解 .确定初始基可行解地方法很多,常用地求解方法一般有：最小元素法和 Vogel 法,简洁又尽可能接近最优解地方法是 Vogel 法.1.最小元素法最小元素法地基本方法就是就近供应,即从单位运价表中最小地运价开头确定供销关系,名师归纳总结 - - - - - - -然后依次类推,始终到给出全部方案为止.其步骤如下：第一步：在表4.1 找出最小运价为1,先将 A2 地产品供应给B1.因a > b ,即 A2 除满意B1 地全部需要外,仍多出1 吨产品 .在表 4.2 地（ A2 ,B1）地交叉格处填上3,同时把表4.2 中第 11 页,共 23 页精选学习资料 - - - - - - - - - 地 B1 列划掉；表 4.2 销产 地 B1 B2 B3 B4 产量（吨）地A1 3 11 3 10 7 A2 3 1 9 2 8 4 A3 7 4 10 5 9 销量（吨）3 6 5 6 20 其次步：在表 4.2 中找出没有划掉地最小地运价 2,把 A2 余外地 1 吨供应给 B3 ,并在表4.3（A2 ,B3）交叉格中填上 1,同时把表 4.3 地 A2 行划掉；表 4.3 销产 地 B1 B2 B3 B4 产量（吨）地A1 3 11 3 10 7 A2 3 1 9 1 2 8 4 A3 7 4 10 5 9 销量（吨）3 6 5 6 20 第三步：同样在表 4.3 中找出没有划掉地最小地运价 3,由于 A2 已经供应 1 吨给 B3,所以 A1 供应 4 吨给 B3,并在表 4.4（A1 ,B3）交叉格中填上 4,同时把表 4.4 地 B3 列划掉；表 4.4 销产地地B1B2B3B4产量（吨）4.5A13 11 4 3 10 7 A23 1 9 1 2 8 4 A37 4 10 5 9 销量（吨）3 6 5 6 20 第四步：在表4.4 中找出没有划掉地最小地运价4,把 A3 地 6 吨供应给B2,并在表（A3 ,B2 ）交叉格中填上6,同时把表4.5地 B2 列划掉；表 4.5 名师归纳总结 - - - - - - -第 12 页,共 23 页精选学习资料 - - - - - - - - - 销产地地B1B2B3B4产量（吨）7 4 9 20 A13 11 4 3 10 A23 1 9 1 2 8 A37 6 4 10 3 5 销量（吨）3 6 5 6 第五步：在表4.5 中找出没有划掉地最小地运价5,由于 A3 一共生产9 吨,把6 吨供应给了 B2,剩下地3 吨全部供应给B4 ,并在表4.6（A3 ,B4）交叉格中填上3,同时把表4.6 地A3 行划掉；表 4.6 销产地地B1B2B3B4产量（吨）A13 11 4 3 10 7 A23 1 9 1 2 8 4 A37 6 4 10 3 5 9 销量（吨）3 6 5 6 20 7 吨,把 4 吨供应给了第六步：在表4.6 中只剩下运价10 没有划掉,由于A1 一共生产B3,剩下地3 吨全部供应给B4,并在表4.6（A1 ,B4）交叉格中填上3,同时把表4.6 地 B4列划掉 .到此已经把产地地产品全部安排到各销地,并得出表 86 元.表 4.7 最小元素法 运输方案 销4.7 运输方案,同时得出总运费为产地3 B13 6 B211 4 B33 3 B410 产量（吨）地7 A1A23 1 6 9 1 5 2 3 6 8 4 A37 4 10 5 9 销量（吨）20 总运费 =4× 3+3× 10+3× 1+1× 2+6× 4+3× 5=86 元2.Vogel 法 Vogel 法地基本思路是：产品假如不能按最小运费就近供应,就考虑次小运费,会产生一 个差额,差额越大,说明不能按最小运费调运时,运费增加就越多,因而对差额最大处采纳最名师归纳总结 - - - - - - -第 13 页,共 23 页精选学习资料 - - - - - - - - - 小运费调运 .Vogel 法地求解步骤是从运价表上分别找出每行与每列地最小地两个元素之差,再从差值最大地行或列中找出最小运价确定供需关系和供应数量 或得到满意时,划去运价表中对应地行或列,在重复上述步骤表 4.8 Vogel 法运算过程.当产地或销地中有一方数量上供应完毕 .求解过程及结果见下表：产销地B1B2B3B4两最小元素之差地两最A13 11 3 10 0 0 0 7 A21 9 2 8 1 1 1 6 A37 4 10 5 1 2 2 5 1 3 小元2 1 3 素之2 1 2 差1 2 表 4.9 Vogel 法运输方案销产地B1B2B3B4产量（吨）地A13 6 5 2 7 A21