运筹学与运输问题.ppt
《运筹学与运输问题.ppt》由会员分享,可在线阅读,更多相关《运筹学与运输问题.ppt(37页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学与运输问题运筹学与运输问题1.运输规划问题的数学模型例3.1 某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?B1B2B3产量A1646200A2655300销量150150200解:产销平衡问题:总产量=总销量500 设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:B1B2B3产量A1x11x12x13200A2x21x22x23300销量150150200Min C=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x
2、13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1、2;j=1、2、3)运输问题的一般形式:产销平衡 A1、A2、Am 表示某物资的m个产地;B1、B2、Bn 表示某物质的n个销地;ai 表示产地Ai的产量;bj 表示销地Bj 的销量;cij 表示把物资从产地Ai运往销地Bj的单位运价。设 xij 为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型:变化:变化:1 1)有时目标函数求最大。如求利润最大或营业额最大等;)有时目标函数求最大。如求利润最大或营业额最大等;2 2)当某些运输线路上的能力
3、有限制时,在模型中直接加入)当某些运输线路上的能力有限制时,在模型中直接加入约束条件(等式或不等式约束约束条件(等式或不等式约束);3 3)产销不平衡时,可加入假想的产地(销大于产时)或销)产销不平衡时,可加入假想的产地(销大于产时)或销地(产大于销时)。地(产大于销时)。定理:设有m个产地n个销地且产销平衡的运输问题,则基变量数为m+n-1。2.表上作业法 表上作业法是一种求解运输问题的特殊方法,其实质是单纯形法。步骤描述方法第一步求初始基行可行解(初始调运方案)西北角法、最小元素法、元素差额法第二步求检验数并判断是否得到最优解当非基变量的检验数ij全都非负时得到最优解,若存在检验数ij 0
4、,说明还没有达到最优,转第三步。闭回路法、位势法运价矩阵法第三步调整运量,即换基,选一个变量出基,对原运量进行调整得到新的基可行解,转入第二步闭回路调整法例例3.23.2 某运输资料如下表所示:某运输资料如下表所示:单位 销地 运价 产地产量311310719284741059销量3656问:应如何调运可使总运输费用最小?问:应如何调运可使总运输费用最小?解:第1步 求初始方案,见下表所示。最小元素法最小元素法 基本思想是就近供应,即从运价最小的地方开始供应(调运)基本思想是就近供应,即从运价最小的地方开始供应(调运),然后次小,直到最后供完为止。,然后次小,直到最后供完为止。B1B2B3B4
5、产量A17A2 4A39销量3656311310192741058341633总的运输费总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元元第第第第2 2步步步步 最优解的判别(检验数的求法)最优解的判别(检验数的求法)最优解的判别(检验数的求法)最优解的判别(检验数的求法)求求出出一一组组基基可可行行解解后后,判判断断是是否否为为最最优优解解,仍仍然然是是用用检检验验数数来来判判断断,记记xij的的检检验验数数为为ij由由第第一一章章知知,求求最最小小值值的的运运输问题的最优判别准则是:输问题的最优判别准则是:所所有有非非基基变变量量的的检检验验数数都都大大于于等
6、等于于,则则运运输输方方案案最优最优求检验数的方法有三种:求检验数的方法有三种:闭回路法闭回路法 位势法(位势法()运价矩阵法运价矩阵法运价矩阵法运价矩阵法 当存在非基变量的检验数kl 0 且kl=minij时,令Xkl 进基。从表中知可选x24进基。第3步 确定换入基的变量第第4步步 确定换出基的变量确定换出基的变量 以进基变量以进基变量xik为起点的闭回路中,所有偶顶点中的最小为起点的闭回路中,所有偶顶点中的最小运量作为调整量运量作为调整量,对应的基变量为出基变量。对应的基变量为出基变量。闭回路的概念为一个闭回路为一个闭回路,集合中的变量称为回路的顶点,相邻两个变,集合中的变量称为回路的顶
7、点,相邻两个变量的连线为闭回路的边。如下表量的连线为闭回路的边。如下表例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点,这8个顶点间用水平或垂直线段连接起来,组成一条封闭的回路。B1B2B3B4B5A1X11X12A2X23X25A3X31X35A4X42X43 一条回路中的顶点数一定是偶数,回路遇到顶点必须转90度与另一顶点连接,上表中的变量x 32及x33不是闭回路的顶点,只是连线的交点。闭回路B1B2B3A1X11X12A2A3X32X33A4X41X43例如变量组 不能构成一条闭回路,但A中包含有闭回路 变量组 变量数是奇数,显然不是
8、闭回路,也不含有闭回路;B1B2B3B4UiA1A2A3Vj3113 31010192 27410105 58 84 4363 31 13 3()()()()调整步骤为:调整步骤为:在进基变量的在进基变量的闭回路中闭回路中所有所有奇顶点奇顶点对应的变量对应的变量加加上上调整量调整量,所有所有偶顶点偶顶点对应的对应的变量变量减减去调整量去调整量,其余变量不变,其余变量不变,得到一组新的基可行解。得到一组新的基可行解。1 12 25 5过x24的闭回路为:x24,x14,x13,x23 因为所有非基变量的检验数均非负,故当前调运方案即因为所有非基变量的检验数均非负,故当前调运方案即为最优方案,如表
9、此时最小总运费:为最优方案,如表此时最小总运费:Z=(13)(46)(35)(210)(18)(35)85元元表上作业法的计算步骤:分析实际问题列出产销平分析实际问题列出产销平衡表及单位运价表衡表及单位运价表确定初始调运方案(最小确定初始调运方案(最小元素法或元素法或Vogel法)法)求检验数(位势法)求检验数(位势法)所有检验数所有检验数0找出绝对值最大的负检验数,用闭合找出绝对值最大的负检验数,用闭合回路调整,得到新的调运方案回路调整,得到新的调运方案得到最优方案,得到最优方案,算出总运价算出总运价表上作业法计算中的问题:表上作业法计算中的问题:表上作业法计算中的问题:表上作业法计算中的问
10、题:(1)若运输问题的某一基可行解有多个非基变量的检验数为)若运输问题的某一基可行解有多个非基变量的检验数为负,在继续迭代时,取它们中任一变量为换入变量均可使目标负,在继续迭代时,取它们中任一变量为换入变量均可使目标函数值得到改善,但通常取函数值得到改善,但通常取ij0中最小者对应的变量为换入变中最小者对应的变量为换入变量。量。(2)无穷多最优解)无穷多最优解 产销平衡的运输问题必定存最优解。如果非基变量的产销平衡的运输问题必定存最优解。如果非基变量的ij0,则该问题有无穷多最优解。,则该问题有无穷多最优解。退化解:退化解:表格中一般要有表格中一般要有(m+n-1)个数字格。但有时在分配运量个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运输 问题
限制150内