运筹学最小元素

给出初始解•给出初始解有西北角法、最小元素法和Vogel法,我们只介绍比较简单的最小元素法.•步骤:在产销平衡的前提下,运价低的优先安排调运.B1B2B3B4产量A1(3)(11)(3)(10)7A2(1)(9)(2)(8)4A3(7)(4)(10)(5)9销量3656314633最小元素法初始方案产销B1B2B3B4产量A1A2A3317119432101085749销量36562020单位运价表解的最优性检验•解的最优性检验主要有闭回路法和位势法,我们只介绍位势法.•位势法:•(1)把产销平衡表中初始方案中有数字格对应的运价写到检验数表中;•(2)对运输表上的每一行(列)赋予一个数值ui(vj),称为位势.各格子的位势等于行位势与列位势之和.u1+v3=3;u1+v4=10;…..•(3)求出检验数:σij=cij-(ui+vj)B1B2B3B4(ui)A1(3)0(10)0A2(1)0(2)0A3(4)0(5)0(vj)2-13010-59B1B2B3B4A1311310A21928A374105单位运价表位势法检验数计算表(3)1(11)2(9)1(8)-1(7)10(10)12运输方案的改进•当所有σij≥0,即为即优.当σij0时,由闭回路法修改方案.•闭回路法:•(1)找到最小的负检验数,其对应的变量为入基变量.•(2)从入基变量对应的格子出发,遇到有数字的格子可以转90°（也可不转）,直到回到出发点,形成闭回路.如24-14-13-23-24调整量=min（奇点处运量：如（14-3、23-1）所以取1），调整（偶加调整量、奇减去调整量）•(3)根据供应量与需求量总量不变的原则,调整供需关系.3A2A136A3B4B3B2B1方案调整-12A231A1位势(vj)119A3位势(ui)B4B3B2B1检验数表0+θ3-θ4+θ1-θ因供给非负,所以θ=1,得新供给方案运输方案的改进(8)0(1)0A2(10)0(3)0A1位势(vj)(5)0(4)0A3位势(ui)B4B3B2B1检验数表B1B2B3B4A1311310A21928A374105单位运价表0310-23-59(3)0(11)2(9)2(2)1(7)9(10)1228A245A136A3B4B3B2B1第1次调整后的方案213至此,检验数全部大于0,调整后的方案为已为最优方案.总运费=3*5+10*2+1*3+8*1+4*6+5+3=85