《案例3产品中转问题》由会员分享，可在线阅读，更多相关《案例3产品中转问题（21页珍藏版）》请在金锄头文库上搜索。
1、案例三一产品转运问题（一）、问题的提出某公司下设三家厂，加工同一种产品，有四个销售点,数据见表:B,B2B3b4a：（吨）A:3113107八219284a3741059bj （吨）365620求产销平衡的最佳运输方案。求解：首先，我们按照常规的表上作业法，很容易求得此产销平衡问题 的最优方案。（1）用最大差值法求出&和v/;（2）在最大差值5所在的列中找最小的元素进行分配;Bib2b3b4Aa?1)Aa?3)UiA,3Xllx35102777720007八2l39X2X81444111116A37X4610x539300012bj3656(1) 最大差值在B2处,首先分配min 6, 9 =
2、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 +
3、 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
4、+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) 途中可设若干个转运站，在厂与厂、
5、点与点、厂与点之间进行 转运。这样，就形成了产品转运问题。关于产品转运问题的右关数据如下表所示。(表中表示不能进行货运的情况；空格表示货不外运的情况。）产地Ai中转站Tk销地BjA1A2A3T1T2T3T4B1B2B3B4产A10132143311310地A2103521928AiA33012374105中T123101322846转T21510114527站T34231021824TkT43232120126B131724110142销B211948581021地B3321042224203BjB4118567462130（二）建模（建表）（1）从上面所给出的条件和数据中可知：产地、中转站、
6、销地均可进出 货物，故既是产地又是销地。因此该问题实际上可看成有11个产 地与11个销地的运输问题；对数据表中的空白与设定处合理运价：空格表示“货不外运”， 运价可设定为零；同理，表示“货不可运”，运价可设定为M（无 穷大正数）；中转站Tk与具备中转功能的魟1（1=1,2,3; j, k=l，2,3,4）设定合 理安全上界：Tk一一纯中转站。进出量相等，转运量至多是原总量20,此为产与 销量的上界；A：一有产量兼中转量。作为产地，合之产量上界a：与纯中转上 界20之和；作为销地，起的是中转的功能，故销量上界不能超 过20;B.i一有销售量与中转量。作为产地，只起中转功能，故其上界 不能超过20
7、;作为销地，有销量兼中转量，其上界应为销量上界为比与纯中转上界20之和。根据上面的设定可得下面的单位运价表:产地Ai中转站Tk销地B j产量aiA1A2A3T1T2T3T4B1B2B3B4产A1013214331131027地A210M35M2192824AiA33M01M237410529中T12310132284620转T215M1011452720站T34M23102182420TkT432321201M2620B13172411014220销B21194858M102120地B332104222420320BjB411856746213020销量bj202020202020202326
8、2526240这是一个产销平衡的运输问题。（三）求解1、用最小元素法求出初始方案产地Ai中转站Tk销地Bj行位势A1A2A3T1T2T3T4B1B2B3B4Ui产A1O201321433Xllx341030地A21O30M352l39X218X-1AiA33MO201M237X4610x53-5中T1231O201322846-4转T215M1O20114527-1站T34M231O2021824-1TkT4323212031M26-1销地BjB13172411O20142-2B21194858M1O2021-9B33210422242O203-3B411856746213O20-10列位势V
9、J015411129310初始方案的运费如表中所示:/。= 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
