资源预览内容
第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
第9页 / 共21页
第10页 / 共21页
亲,该文档总共21页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
案例三一产品转运问题(一)、问题的提出某公司下设三家厂,加工同一种产品,有四个销售点,数据见表:B,B2B3b4a:(吨)A:3113107八219284a3741059bj (吨)365620求产销平衡的最佳运输方案。求解:首先,我们按照常规的表上作业法,很容易求得此产销平衡问题 的最优方案。(1)用最大差值法求出&和v/;(2)在最大差值5所在的列中找最小的元素进行分配;Bib2b3b4Aa?1)Aa?3)UiA,3Xllx35102777720007八2l39X2X81444111116A37X4610x539300012bj3656(1) 最大差值在B2处,首先分配min 6, 9 =6给A3B2处;B2列其它元素不再分配,用X表示;(2) 最大差值在B4列,分配min6,3=3给A3B4处;A3行其它元素不再分配,用X表示;(3) 最大差值在B1列,分配min3,4=3给A2B1处;B1列其它元素不再分配,用X表示;(4) 最大差值在A1行,将min5, 7 =5分配给A1B3处,B3列其它元素不再分配,用X表示;(5) 最大差值在B4列,分配min3,l=l给A2B4处,剩余的2分配给A1B4处,全部分配完毕。b,3056b,3053b/2)0053V)0003V/O)2513Vi(l)213v;2)212v/3)12(3)分酉己完后得:/ = 3x5 + 10x2 + lx3 + 8xl + 4x6 + 5x3 = 85;(4)用闭回路法检验是否最优方案A1A2A3BI B2 B3 B4VX102A13X11108lA2l39X2X853A37X4%r 10X53327X 4610BI B2 B3 B4A1A2A3BI B2 B3 B4nx35102A13Xllx 1L3109X_2X8 JA2l39X8v311053A3BI B2 B3 B47X 4610x53BIB2B3B4A13Xnx35102A2l39X2X8A37X4610x53”BIB2B3B4A13Xnx k35102A2l39X2X81A37X4653 ”用闭冋路法得:7| | 二 3-1+8-10 = 0 Gn = 11-4+5-10 = 2 (722 =9-4+5-8 = 2 cr23 =2-3+10-8=1 731 =7-1+8-5 = 9二 10 - 3+10-5 二 12因为:所有的口0,所以该方案是最优方案。根据上面的结果的最优运输方案为A1A2A3B3B4B1B4B2B4这是一般的思路:直接从产地一销地的求解方法。如果给问题再增加一些条件,也是实际操作中经常遇到的一些可能性条件,则问题可以更加一般化来表示。设增加的条件为:(1) 各厂即可直接运到销售点,也可适当集中一起运;(2) 产品可先运到某个销售点,再转运到其它销售点;(3) 途中可设若干个转运站,在厂与厂、点与点、厂与点之间进行 转运。这样,就形成了产品转运问题。关于产品转运问题的右关数据如下表所示。(表中表示不能进行货运的情况;空格表示货不外运的情况。)产地Ai中转站Tk销地BjA1A2A3T1T2T3T4B1B2B3B4产A10132143311310地A2103521928AiA33012374105中T123101322846转T21510114527站T34231021824TkT43232120126B131724110142销B211948581021地B3321042224203BjB4118567462130(二)建模(建表)(1)从上面所给出的条件和数据中可知:产地、中转站、销地均可进出 货物,故既是产地又是销地。因此该问题实际上可看成有11个产 地与11个销地的运输问题;对数据表中的空白与设定处合理运价:空格表示“货不外运”, 运价可设定为零;同理,表示“货不可运”,运价可设定为M(无 穷大正数);中转站Tk与具备中转功能的魟1(1=1,2,3; j, k=l,2,3,4)设定合 理安全上界:Tk一一纯中转站。进出量相等,转运量至多是原总量20,此为产与 销量的上界;A:一有产量兼中转量。作为产地,合之产量上界a:与纯中转上 界20之和;作为销地,起的是中转的功能,故销量上界不能超 过20;B.i一有销售量与中转量。作为产地,只起中转功能,故其上界 不能超过20;作为销地,有销量兼中转量,其上界应为销量上界为比与纯中转上界20之和。根据上面的设定可得下面的单位运价表:产地Ai中转站Tk销地B j产量aiA1A2A3T1T2T3T4B1B2B3B4产A1013214331131027地A210M35M2192824AiA33M01M237410529中T12310132284620转T215M1011452720站T34M23102182420TkT432321201M2620B13172411014220销B21194858M102120地B332104222420320BjB411856746213020销量bj2020202020202023262526240这是一个产销平衡的运输问题。(三)求解1、用最小元素法求出初始方案产地Ai中转站Tk销地Bj行位势A1A2A3T1T2T3T4B1B2B3B4Ui产A1O201321433Xllx341030地A21O30M352l39X218X-1AiA33MO201M237X4610x53-5中T1231O201322846-4转T215M1O20114527-1站T34M231O2021824-1TkT4323212031M26-1销地BjB13172411O20142-2B21194858M1O2021-9B33210422242O203-3B411856746213O20-10列位势VJ015411129310初始方案的运费如表中所示:/。= 4 X 3+10 X 3+1 X 3+2 X 1 +4 X 6+5 X 3 = 862、取wQ=0,对数值格按+ Vy计算行、列位势值如上表所示;(基变景的个数为n+m-l = ll+lHl=21,现有17个,再任选4个,设这 4个变量的数量为0。)3、对空格按=4-七-计算的值如下表所示:A1A2A3T1T2T3T4B1B2B3B4A1X0-2- 203212XXA22XM052MX1X-1A38MX2M6710X12XT1660X465435XT225M-2X113-3X-2T35M-201X200X-5T442-1-112X0MX-3B15240522X-63-6B220178131316M8X80B364834445-4X-4B42017101216131510210X表中有0,所以该初始方案不是最优解。4、选择ct841=-6处用闭回路法进行调整,所得闭回路如下表所示:A1A2A3T1T2T3T4B1B2B3B4HiA120|1(+1).13(-1)0A220S1(-1)-13(+1)A3
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号