- 1、本文档共41页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
3.2 运输问题的表上作业法
一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案,如图3-1所示。
表上作业法和单纯形法的求解思想完全一致,但是具体作法更加简捷。
; 确定初始方案
( 初 始
基本可行解); 二、 初始方案的确定
1、作业表(产销平衡表)
初始方案就是初始基本可行解。
将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”(产销平衡表)。
表3-3是两个产地、三个销地的运输问题作业表。 ;调 销地
运
量
产地;其中xij是决策变量,表示待确定的从第i个产地到第j个销地的调运量,cij为从第i个产地到第j个销地的单位运价或运距。
2、确定初始方案的步骤:
(1)选择一个xij,令xij= min{ai,bj}= ;(2)调整产销剩余数量??从ai和bj中分别减去xij的值,若ai-xij=0,则划去产地Ai所在的行,即该产地产量已全部运出无剩余,而销地Bj尚有需求缺口bj-ai;若bj-xij =0,则划去销地Bj所在的列,说明该销地需求已得到满足,而产地Ai尚有存余量ai-bj;
(3)当作业表中所有的行或列均被划去,说明所有的产量均已运到各个销地,需求全部满足,xij的取值构成初始方案。否则,在作业表剩余的格子中选择下一个决策变量,返回步骤(2)。; 按照上述步骤产生的一组变量必定不构成闭回路,其取值非负,且总数是m+n-1个,因此构成运输问题的基本可行解。
对xij的选择采用不同的规则就形成各种不同的方法,比如每次总是在作业表剩余的格子中选择运价(或运距)最小者对应的xij,则构成最小元素法,若每次都选择左上角格子对应的xij就形成西北角法(也称左上角法)。;3、举例 ;表3-4 例3-2有关信息表;例3-2 的数学模型; 分别使用最小元素法和西北角法求出初始方案。
最小元素法的基本思想是“就近供应” ;
西北角法则不考虑运距(或运价),每次都选剩余表格的左上角(即西北角)元素作为基变量,其它过程与最小元素法相同 ;;调 销地
运
量
产地; 得到初始调运方案为:
x11=100,x13=100,x22=150,x23=100 ;最小元素法实施步骤口诀;调 销地
运
量
产地; 得到初始调运方案为:
x11=100,x12=100,x22=50,x23=200 ;1、闭回路法
以确定了初始调运方案的作业表为基础,以一个非基变量作为起始顶点,寻求闭回路。
该闭回路的特点是:除了起始顶点是非基变量外,其他顶点均为基变量(对应着填上数值的格)。
可以证明,如果对闭回路的方向不加区别,对于每一个非基变量而言,以其为起点的闭回路存在且唯一。; 约定作为起始顶点的非基变量为偶数次顶点,其它顶点从1开始顺次排列,那麽,该非基变量xij的检验数:;调 销地
运
量
产地;非基变量X12的检验数:;2、位势法 ;例3-2初始调运方案位势变量对应表 ;方程组的特点:
? 方程个数是m+n-1=2+3-1=4个,位势变量共有m+n=2+3=5个,通常称ui为第i行的位势,称vj为第j列的位势;
? 初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的位势变量之和等于该基变量对应的运距(或运价):ui+vj=cij;
?方程组恰有一个自由变量,可以证明方程组中任意一个变量均可取作自由变量。 ; 给定自由变量一个值,解方程组式(3-7),即可求得位势变量的一组值,根据式(3-6)结合方程组(3-7),推出计算非基变量xij检验数的公式 σij=cij-(ui+vj) (3-8);位势法计算非基变量xij检验数的公式 σij=cij-(ui+vj) (3-8); 四、方案调整
当至少有一个非基变量的检验数是负值时,说明作业表上当前的调运方案不是最优的,应进行调整。
若检验数σij小于零,则首先在作业表上以xij为起始变量作出闭回路,并求出调整量ε:;调 销地
运
量
产地; ?计算调整量:ε=Min(100,150)=10
您可能关注的文档
- 3.5.2生态系统的能量流动讲解.ppt
- 机械设计_蜗杆传动习题分析.doc
- 3.6什么样的土地容易被侵蚀讲解.ppt
- 3.7对分查找算法及程序实现讲解.pptx
- 3.4升华和凝华课件讲解.ppt
- 3.4升华和凝华25p讲解.ppt
- 3.4实际问题与一元一次方程5方程讲解.ppt
- 3.4实际问题与一元一次方程(第1课时)讲解.ppt
- 3.4实际问题与一元一次方程电话计费问题讲解.ppt
- 3.4实际问题与一元一次方程--行程问题讲解.ppt
- 《GB/Z 44363-2024致热性 医疗器械热原试验的原理和方法》.pdf
- GB/T 16716.6-2024包装与环境 第6部分:有机循环.pdf
- 中国国家标准 GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 《GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统》.pdf
- GB/T 44376.1-2024微细气泡技术 水处理应用 第1 部分:亚甲基蓝脱色法评价臭氧微细气泡水发生系统.pdf
- 中国国家标准 GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 44305.2-2024塑料 增塑聚氯乙烯(PVC-P)模塑和挤塑材料 第2部分:试样制备和性能测定.pdf
- 《GB/T 44315-2024科技馆展品设计通用要求》.pdf
- GB/T 44315-2024科技馆展品设计通用要求.pdf
- GB/T 39560.9-2024电子电气产品中某些物质的测定 第9 部分:气相色谱-质谱法(GC-MS)测定聚合物中的六溴环十二烷.pdf
文档评论(0)