欢迎来到天天文库
浏览记录
ID:51020681
大小:593.00 KB
页数:43页
时间:2020-03-17
《运筹学-表 上作 业法.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、运输问题求解——表上作业法运输问题求解之表上作业法1.运输问题模型及其求解思路2.确定初始基本可行解3.最优性检验4.方案调整1.运输问题模型及其求解思路运输问题:研究把某种商品从若干个产地运至若干个销售地而使总运费最小的一类问题。目标:1总运费最小1.运输问题模型及其求解思路销地产地B1B2…Bn产量A1A2::Amc11c21::cm1c12c22::cm2……::…c1nc2n::cmna1a2::am销量b1b2…bn已知有m个产地Ai(i=1,2,…,m)可供应某种物资,其供应量(产量)分别为ai,有n个销地Bj(
2、j=1,2,…,n)其销量(需求量)分别为bj,从A到B的单位物资运价为cij。若设代表从第Ai个产地到第Bj个销售地的调运量,在产销平衡的条件下(),要确定总运输费用最小的调运方案,可表示为如下的数学模型s.t.(i=1,2,…,m;j=1,2,…,n)矩阵形式:s.t.1.运输问题模型及其求解思路11···111···111···1111111111············A=m行n行1.运输问题模型及其求解思路系数矩阵A21.运输问题模型及其求解思路对于产销平衡的运输问题,若产地为m个,销地为n个,则变量个数为m×n个
3、,约束条件个数为m+n,其中包含:总产量=总销售故线性无关的约束条件个数为m+n-1,基本解中的基变量个数为m+n-1。运输问题求解思路——表上作业法由于运输规划系数矩阵的特殊性,如果直接使用线性规划单纯形法求解计算,则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。1.运输问题模型及其求解思路表上作业法是单纯形法在求解产销平衡的运输问题时的一种简化方法,其实质仍是单纯形法,所不同的只是完成各步采用的具体形式。具体操作步骤如下:(1)确定一个初始基本可行解:即在m×n阶产销平衡表上
4、给出m+n-1个数字格(基变量);(2)求各非基变量(空格)的检验数,即在表上 计算空格的检验数。判别式否达到最优解。如果是最优解,则停止计算,否则进入下一步。(3)确定换入变量和换出变量,找出新的基可行解。(4)重复(2)、(3)直至得到最优解为止。1.运输问题模型及其求解思路2.确定初始基本可行解1)最小元素法基本思想:就近供应,按运价最小的优先调运原则确定初始方案,即从单位运价表中选择运价最小的开始确定调运关系,然后次小。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,一直到给出初始
5、基可行解为止。例如,某公司经营某种产品,该公司下设A、B、C三个生产厂,有甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点,各工厂到各销售点的路程不同,单位产品的运费不同。各工厂每日的产量、各销售点每日的销量,以及从各工厂到各销售点单位产品的运价如下表。问该公司如何调运产品,在满足各销售点需要的前提下,使总运费最小。甲乙丙丁产量A3113107B19284C741059销量36562.确定初始基本可行解s.t2.确定初始基本可行解若设代表从第i个产地到第j个销售地的运输量(i=1,2,3;j=1,2,
6、3,4)B1B2B3B4产量A13113107A219284A3741059销量36563431632.确定初始基本可行解Z=4×3+3×10+3×1+1×2+6×4+3×5=86为保证基变量的个数有m+n-1个,1、每次填完数,只能划去一行或一列,只有最后一个格子例外。2、用最小元素法时,可能会出现基变量个数还差两个以上但只剩下一行或一列的情况,此时不能将剩下行或列按空格划掉,应在剩下的空格中标上0。(退化的基本可行解)2.确定初始基本可行解注意:B1B2B3B4产量A13113108A219283A3741059销量36
7、563530632.确定初始基本可行解2)伏格尔法伏格尔法的基本思想:如果某一地的产品不能按最小运费就近供应,就考虑次小运费,两者间就有一个差额。差额越大,说明费用增量越大。因而对差额最大处,优先采用最小运费调运。步骤:①分别计算表中各行和各列中最小运费和次小运费的差额,并填入表中的最右列和最下行。②从行和列的差额中选出最大者,选择其所在行或列中的最小元素,按类似于最小元素法优先供应,划去相应的行或列。③对表中未划去的元素,重复①②,直到所有的行和列都划完为止。2.确定初始基本可行解B1B2B3B4两最小元素之差A13113
8、10A21928A374105两最小元素之差2.确定初始基本可行解0112513B1B2B3B4两最小元素之差A13113100A219281A3741052两最小元素之差2132.确定初始基本可行解B1B2B3B4两最小元素之差A13113100A219281A374105两最小元素之差
此文档下载收益归作者所有