运输问题表上作业法课件.ppt

上传人:小飞机 文档编号:1797936 上传时间:2022-12-19 格式:PPT 页数:42 大小:1.51MB
返回 下载 相关 举报
运输问题表上作业法课件.ppt_第1页
第1页 / 共42页
运输问题表上作业法课件.ppt_第2页
第2页 / 共42页
运输问题表上作业法课件.ppt_第3页
第3页 / 共42页
运输问题表上作业法课件.ppt_第4页
第4页 / 共42页
运输问题表上作业法课件.ppt_第5页
第5页 / 共42页
点击查看更多>>
资源描述

《运输问题表上作业法课件.ppt》由会员分享,可在线阅读,更多相关《运输问题表上作业法课件.ppt(42页珍藏版)》请在三一办公上搜索。

1、运输问题的表上作业法,1、单纯形法(为什麽?)2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法,一、表上作业法的基本思想 先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案,如图3-1所示。表上作业法和单纯形法的求解思想完全一致,但是具体作法更加简捷。,图1 运输问题求解思路图,二、 初始方案的确定 1、作业表(产销平衡表) 初始方案就是初始基本可行解。 将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”(产销平衡表)。 表2是两个产地、三个销地的运输问题作业表。,表2 运输问题作业表(产销平衡表),其中xij是决策变量,表

2、示待确定的从第i个产地到第j个销地的调运量,cij为从第i个产地到第j个销地的单位运价。2、确定初始方案的步骤:(1)选择一个xij,令xij= minai,bj=,将具体数值填入xij在表中的位置;,(2)调整产销剩余数量:从ai和bj中分别减去xij的值,若ai-xij=0,则划去产地Ai所在的行,即该产地产量已全部运出无剩余,而销地Bj尚有需求缺口bj-ai;若bj-xij =0,则划去销地Bj所在的列,说明该销地需求已得到满足,而产地Ai尚有存余量ai-bj;(3)当作业表中所有的行或列均被划去,说明所有的产量均已运到各个销地,需求全部满足,xij的取值构成初始方案。否则,在作业表剩余

3、的格子中选择下一个决策变量,返回步骤(2)。,按照上述步骤产生的一组变量必定不构成闭回路,其取值非负,且总数是m+n-1个,因此构成运输问题的基本可行解。 对xij的选择采用不同的规则就形成各种不同的方法,比如每次总是在作业表剩余的格子中选择运价(或运距)最小者对应的xij,则构成最小元素法,若每次都选择左上角格子对应的xij就形成西北角法(也称左上角法)。,3、举例,例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤,各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4,求使总运输量最少的调运方案。,表3-4 例3-2有关信息表,例3-2 的数学模型,分别使用最小元素法和西北角法求出

4、初始方案。& 最小元素法的基本思想是“就近供应” ;& 西北角法则不考虑运距(或运价),每次都选剩余表格的左上角(即西北角)元素作为基变量,其它过程与最小元素法相同 ;,用最小元素法确定例3-2初始调运方案,150,100,100,100,100,100,100,得到初始调运方案为: x11=100,x13=100,x22=150,x23=100,最小元素法实施步骤口诀,运价表上找最小,平衡表上定产销; 满足销量划去“列”,修改“行产”要记牢;(满足产量划去“行”,修改“列销”要记牢) 划去列(行)对运价, 修改“行产(列销)”在产销; 余表再来找最小,方案很快就找到。,用西北角法确定例3-2

5、初始调运方案,100,100,100,50,50,200,200,得到初始调运方案为: x11=100,x12=100,x22=50,x23=200,三、最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法:计算非基变量(未填上数值的格,即空格)的检验数(也称为空格的检验数),若全部大于等于零,则该方案就是最优调运方案,否则就应进行调整。,1、闭回路法 以确定了初始调运方案的作业表为基础,以一个非基变量作为起始顶点,寻求闭回路。 该闭回路的特点是:除了起始顶点是非基变量外,其他顶点均为基变量(对应着填上数值的格)。可以证明,如果对闭回路的方向不加区别,对于每一个非基变量而

6、言,以其为起点的闭回路存在且唯一。,约定作为起始顶点的非基变量为偶数次顶点,其它顶点从1开始顺次排列,那麽,该非基变量xij的检验数:,现在,在用最小元素法确定例3-2初始调运方案的基础上,计算非基变量X12的检验数 :,例3-2初始调运方案中以X12(X21)为起点的闭回路,非基变量X12的检验数:,非基变量X21的检验数:,=(c12+c23)-(c13+c22) =70+75-(100+65)=-20,,=(c21+c13)-(c11+c23)=80+100-(90+75)=15。,经济含义:在保持产销平衡的条件下,该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,2、位势法

7、,以例3-2初始调运方案为例,设置位势变量 和 ,在初始调运方案表的基础上增加一行和一列(见下页表格)。 然后构造下面的方程组:,(3-7),例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)

8、结合方程组(3-7),推出计算非基变量xij检验数的公式 ij=cij-(ui+vj) (3-8),在式(3-7)中,令u1=0,则可解得v1=90,v3=100,u2=-25,v2=90,于是12=c12-(u1+v2)=70-(0+90)=-2021=c21-(u2+v1)=80-(-25+90)=15与前面用闭回路法求得的结果相同。,位势法计算非基变量xij检验数的公式 ij=cij-(ui+vj) (3-8),复习比较检验数计算的两种方法,思考:试解释位势变量的含义(提示:写出运输问题的对偶问题),四、方案调整 当至少有一个非基变量的检验数是负值时,说明作业表上当前的调运方案不是最优的

9、,应进行调整。 若检验数ij小于零,则首先在作业表上以xij为起始变量作出闭回路,并求出调整量:,继续上例,因12=-20 ,画出以x12为起始变量的闭回路,计算调整量:=Min(100,150)=100。按照下面的方法调整调运量: 闭回路上,奇数次顶点的调运量减去,偶数次顶点(包括起始顶点)的调运量加上;闭回路之外的变量调运量不变。,得到新的调运方案:,重复上面的步骤,直至求出最优调运方案:,结 果 最优调运方案是: x11=50,x12=150,x21=50,x23=200 相应的最小总运输量为: Zmin=9050+70150+8050+75200 =34000(吨公里),运输问题的计算

10、机求解表上作业法,1、适用软件Transportation/Transshipment Problem(TRP)2、输入数据:Maximize 1 minimize 2 Number of sources? Number of destinations? Number of transshipment point? Use the default names(S1 Sn ,D1 Dn ,T1Tn) ,Press the Space Bar to continue if your entries are correct,Capacities of SourcesS1: 200 S2: 250 D

11、emands of destinationsD1: 100 D2: 150 D3: 200,ENTER THE Cost/Profit Coefficients of the TRP Model,-Minimization-From To S1 D1: 90 D2: 70 D3: 100 S2 D1: 80 D2: 65 D3: 80,(注意:该例的输入数据与前例不同),3、计算过程中的初始表 Initial solution by,4、求解结果报告,3.3运输问题的推广,一、产销不平衡的运输问题,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运距(或运价) ?,二、转运问题特点是所调运的物资不是由产地直接运送到销地,而是经过若干中转站送达。求解思路:转化成一个等价的产销平衡运输问题,再用表上作业法求出最优调运方案。,如何转化 ?,第一步,将产地、转运点、销地重新编排,转运点既作为产地又作为销地;第二步,各地之间的运距(或运价)在原问题运距(运价)表基础上进行扩展:从一地运往自身的单位运距(运价)记为零,不存在运输线路的则记为M(一个足够大的正数);,第三步,由于经过转运点的物资量既是该点作为销地的需求量,又是该点作为产地时的供应量,但事先又无法获取该数量的确切值,因此通常将调运总量作为该数值的上界。对于产地和销地也作类似的处理。,作业,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号