运筹学与运输问题.ppt
- 文档编号:18775865
- 上传时间:2023-11-08
- 格式:PPT
- 页数:37
- 大小:491KB
运筹学与运输问题.ppt
《运筹学与运输问题.ppt》由会员分享,可在线阅读,更多相关《运筹学与运输问题.ppt(37页珍藏版)》请在冰点文库上搜索。
Chapter3运输规划(TransportationProblem),1.运输规划问题的数学模型2.表上作业法3.运输问题的应用,本章主要内容:
1.运输规划问题的数学模型,例3.1某公司从两个产地A1、A2将物品运往三个销地B1,B2,B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:
应如何调运可使总运输费用最小?
解:
产销平衡问题:
总产量=总销量500设xij为从产地Ai运往销地Bj的运输量,得到下列运输量表:
MinC=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij0(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)有时目标函数求最大。
如求利润最大或营业额最大等;2)当某些运输线路上的能力有限制时,在模型中直接加入约束条件(等式或不等式约束);3)产销不平衡时,可加入假想的产地(销大于产时)或销地(产大于销时)。
定理:
设有m个产地n个销地且产销平衡的运输问题,则基变量数为m+n-1。
2.表上作业法,表上作业法是一种求解运输问题的特殊方法,其实质是单纯形法。
例3.2某运输资料如下表所示:
问:
应如何调运可使总运输费用最小?
解:
第1步求初始方案,见下表所示。
最小元素法基本思想是就近供应,即从运价最小的地方开始供应(调运),然后次小,直到最后供完为止。
3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,总的运输费(31)+(64)+(43)+(12)+(310)+(35)=86元,第2步最优解的判别(检验数的求法),求出一组基可行解后,判断是否为最优解,仍然是用检验数来判断,记xij的检验数为ij由第一章知,求最小值的运输问题的最优判别准则是:
所有非基变量的检验数都大于等于,则运输方案最优,求检验数的方法有三种:
闭回路法位势法()运价矩阵法,运价矩阵法,当存在非基变量的检验数kl0且kl=minij时,令Xkl进基。
从表中知可选x24进基。
第3步确定换入基的变量,第4步确定换出基的变量,以进基变量xik为起点的闭回路中,所有偶顶点中的最小运量作为调整量,对应的基变量为出基变量。
闭回路的概念,为一个闭回路,集合中的变量称为回路的顶点,相邻两个变量的连线为闭回路的边。
如下表,例下表中闭回路的变量集合是x11,x12,x42,x43,x23,x25,x35,x31共有8个顶点,这8个顶点间用水平或垂直线段连接起来,组成一条封闭的回路。
一条回路中的顶点数一定是偶数,回路遇到顶点必须转90度与另一顶点连接,上表中的变量x32及x33不是闭回路的顶点,只是连线的交点。
闭回路,例如变量组不能构成一条闭回路,但A中包含有闭回路,变量组变量数是奇数,显然不是闭回路,也不含有闭回路;,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),调整步骤为:
在进基变量的闭回路中所有奇顶点对应的变量加上调整量,所有偶顶点对应的变量减去调整量,其余变量不变,得到一组新的基可行解。
1,2,5,过x24的闭回路为:
x24,x14,x13,x23,因为所有非基变量的检验数均非负,故当前调运方案即为最优方案,如表此时最小总运费:
Z=(13)(46)(35)(210)(18)(35)85元,表上作业法的计算步骤:
表上作业法计算中的问题:
(1)若运输问题的某一基可行解有多个非基变量的检验数为负,在继续迭代时,取它们中任一变量为换入变量均可使目标函数值得到改善,但通常取ij0中最小者对应的变量为换入变量。
(2)无穷多最优解产销平衡的运输问题必定存最优解。
如果非基变量的ij0,则该问题有无穷多最优解。
退化解:
表格中一般要有(m+n-1)个数字格。
但有时在分配运量时则需要同时划去一行和一列,这时需要补一个0,以保证有(m+n-1)个数字格作为基变量。
一般可在划去的行和列的任意空格处加一个0即可。
利用进基变量的闭回路对解进行调整时,所有偶顶点中的最小运量(超过2个最小值)作为调整量,选择任意一个最小运量对应的基变量作为出基变量,并打上“”以示作为非基变量,另一个变量仍为基变量且它的值为0。
3.运输问题的应用,求极大值问题目标函数求利润最大或营业额最大等问题。
求解方法:
将极大化问题转化为极小化问题。
设极大化问题的运价表为C,用一个较大的数M(Mmaxcij)去减每一个cij得到矩阵C,其中C=(Mcij)0,将C作为极小化问题的运价表,用表上用业法求出最优解。
例3.3下列矩阵C是Ai(I=1,2,3)到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大.,得到新的最小化运输问题,用表上作业法求解即可。
产销不平衡的运输问题当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。
当产大于销时,即:
数学模型为:
由于总产量大于总销量,必有部分产地的产量不能全部运送完,必须就地库存,即每个产地设一个仓库,假设该仓库为一个虚拟销地Bn+1,bn+1作为一个虚设销地Bn+1的销量(即库存量)。
各产地Ai到Bn+1的运价为零,即Ci,n+1=0,(i=1,m)。
则平衡问题的数学模型为:
具体求解时,只在运价表右端增加一列Bn+1,运价为0,销量为bn+1即可,当销大于产时,即:
数学模型为:
由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1,运价为0,产量为:
销大于产化为平衡问题的数学模型为:
具体计算时,在运价表的下方增加一行Am+1,运价为0。
产量为am+1即可。
例3.4求下列表中极小化运输问题的最优解。
因为有:
所以是一个产大于销的运输问题。
表中A2不可达B1,用一个很大的正数M表示运价C21。
虚设一个销量为b5=180-160=20,Ci5=0,i=1,2,3,4,表的右边增添一列,得到新的运价表。
下表为计算结果。
可看出:
产地A4还有20个单位没有运出。
3.生产与储存问题,例3.5某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。
已知该厂各季度的生产能力及生产每台柴油机的成本如右表。
如果生产出来的柴油机当季不交货,每台每积压一个季度需储存、维护等费用0.15万元。
试求在完成合同的情况下,使该厂全年生产总费用为最小的决策方案。
解:
设xij为第i季度生产的第j季度交货的柴油机数目,那么应满足:
交货:
x11=10x12+x22=15x13+x23+x33=25x14+x24+x34+x44=20生产:
x11+x12+x13+x1425x22+x23+x2435x33+x3430x4410,把第i季度生产的柴油机数目看作第i个生产厂的产量;把第j季度交货的柴油机数目看作第j个销售点的销量;设cij是第i季度生产的第j季度交货的每台柴油机的实际成本,应该等于该季度单位成本加上储存、维护等费用。
可构造下列产销平衡问题:
由于产大于销,加上一个虚拟的销地D,化为平衡问题,即可应用表上作业法求解。
该问题的数学模型:
Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44,最优生产决策如下表,最小费用z773万元。
4.转运问题例3.6某公司有A1、A2、A3三个分厂生产某种物资,分别供应B1、B2、B3、B4四个地区的销售公司销售。
假设质量相同,有关数据如下表:
试求总费用为最少的调运方案。
假设:
1.每个分厂的物资不一定直接发运到销地,可以从其中几个产地集中一起运;2.运往各销地的物资可以先运给其中几个销地,再转运给其他销地;3.除产销地之外,还有几个中转站,在产地之间、销地之间或在产地与销地之间转运。
运价如下表:
解:
把此转运问题转化为一般运输问题:
1、把所有产地、销地、转运站都同时看作产地和销地;2、运输表中不可能方案的运费取作M,自身对自身的运费为0;3、Ai:
产量为20+原产量,销量为20;Ti:
产量、销量均为20;Bi:
产量为20,销量为20+原销量,其中20为各点可能变化的最大流量;4、对于最优方案,其中xii为自身对自身的运量,实际上不进行运作。
扩大的运输问题产销平衡与运价表:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 运输 问题