运输问题TransportationProblem.ppt
《运输问题TransportationProblem.ppt》由会员分享,可在线阅读,更多相关《运输问题TransportationProblem.ppt(64页珍藏版)》请在三一文库上搜索。
1、运 输 问 题 (Transportation Problem),运输问题的数学模型,表上作业法,产销不平衡的运输问题,例:某运输问题的资料如下:,一、运输问题的数学模型,数学模型的一般形式 已知资料如下:,当产销平衡时,其模型如下:,当产大于销时,其模型是:,当产小于销时,其模型是:,运输问题特征: 1、m个供应地,n个需求地的运输问题; 2、决策变量个数为 m*n 个,约束条件个数为 m+n个; 3、系数矩阵中元素为0或1; 4、每个决策变量在 m 个供应量约束和 n 个需求量约束中各出现一次; 5、系数矩阵的秩等于( m+n-1 )个; 6、基本解中基变量个数等于(m+n-1)个; 7、
2、平衡运输问题必有可行解,也必有最优解。,.重复. ,直到找到最优解为止。,步骤:,.找出初始基本可行解(初始调运方案,一般m+n-1个数字格),用最小元素法、西北角法、伏格尔法;,.求出各非基变量的检验数,判别是否达到最优解。如果是停止计算,否则转入下一步,用位势法计算;,.改进当前的基本可行解(确定换入、换出变量),用闭合回路法调整;,二、表上作业法,例一、某运输资料如下表所示:,1、求初始方案:,.西北角法(或左上角法): 此法是纯粹的人为的规定,没有理论依据和实际背景,但它易操作,特别适合在计算机上编程计算,因而受欢迎。方法如下:,3 6 5 6,7 4 9,3,4 4 9,0 6 5
3、6,4,0 4 9,0 2 5 6,2,0 2 9,0 0 5 6,2,0 0 9,0 0 3 6,3 6,0 0 0 0,0 0 0,3 4 0 0 0 2 2 0 0 0 3 6,总的运费(33)(411)(29)(22)(310)(65)135元,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元,(3)伏格尔法 考虑到最小运费与次小运费及相互差额问题。差额最大处应用最小运费调运。,5 2
4、3 1 6 3,用伏格尔法 得初始调运方案如下: 表1,ij0 (因为目标函数要求最小化) 表格中有调运量的地方为基变量,空格处为非基变 量。基变量的检验数ij0,非基变量的检验数 ij0。,ij 0 表示运费增加。,2、最优解的判别(检验数的求法): .闭合回路法:,3,1,3,4,6,3,(1),(1),(1),(1),计算如下:空格处( A1 B1 ) 3-3+2-11 此数即为该空格处的检验数。,1,3,1,3,6,3,1,2,4,3,1,3,6,3,1,2,-1,4,3,1,3,6,3,1,2,1,-1,4,3,1,3,6,3,1,2,1,-1,12,4,3,1,3,6,3,1,2,
5、1,-1,12,10,4,检验数中有负数,说明原方案不是最优解。,0,0,0,0,0,1,2,1,-1,12,10,0,运输问题的约束条件共有m+n个,其中:m是产地产量的限制;n是销地销量的限制。 其对偶问题也应有m+n个变量,据此: ij=cij(ui+vj) ,其中前m个计为ui(i=1.2m),前n个计为vj (j=1.2n) 由单纯形法可知,基变量的ij 0 cij(ui+vj) 0 因此ui ,vj可以求出。,.位势法,接上例:,成本表,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令: u10,u10 v12 u2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运输 问题 TransportationProblem
链接地址:https://www.31doc.com/p-2831669.html