运输问题的表上作业法VIP免费

课题：赣南师范学院２００8年9月引例：求下列运输问题的最优调运方案销地产地B1B2B3B4B5Ａ１Ａ２Ａ３产量ai９４８３５５３５销量bj２１B1B2B3B4B51020591021082561157104平衡表运价表3.2运输问题的表上作业法B1…Bj…Bn发量A1c11x11…cijxij…c1nx1na1…………………Ajci1xi1…cijxij…cinxinai…………………Amcm1xm1…cmjxmj…cmnxmnam收量b1…bj…bn3.2运输问题的表上作业法对于小规模的运输问题其求解过程可以在表上进行。一、编制初始调运方案方法一最小元素法（优先安排运价最小的单元格）安排的数量满足下式jiijbax,min（1）若aibj，则取xij=bj,而xsj=0(s=1,2,…,i-1,i+1,…,m),将bj填入(i,j)格内。这时x1j+x2j+…+xij+…+xmj=xij=bj例3.1用最小元素法求下列运输问题的初始调运方案销地产地B1B2B3B4B5Ａ１Ａ２Ａ３产量ai９４８３５５３５销量bj２１B1B2B3B4B51020591021082561157104平衡表运价表3.2运输问题的表上作业法一、编制初始调运方案求解运输问题的表上作业法的步骤：销地产地B1B2B3B4B5Ａ１Ａ２Ａ３产量ai９４８３５５３５销量bj２１B1B2B3B4B51020591021082561157104平衡表运价表初始基本可行解为{x12,x13,x14,x22,x31,x32,x35}={1,5,3,4,3,0,5},相应运价为：{c12,c13,c14,c22,c31,c32,c35}={20,5,9,10,1,15,4},由此表上作业得初始调运方案的总运费为S=1x20+5x5+3x9+4x10+3x1+0x15+5x4=135（元）3.2运输问题的表上作业法一、编制初始调运方案求解运输问题的表上作业法的步骤：1534305解15234415167方法二左上角法(也称西北角法）令1111,minbax（1）若a1b1，则取x11=b1,则取x11=b1，而xs1=0(s=2,3,…,m),将b1填入(1,1)格内。这时x11+x21+…+xm1=b13.2运输问题的表上作业法一、编制初始调运方案求解运输问题的表上作业法的步骤：例2用左上角法求下列运输问题的初始调运方案销地产地B1B2B3B4B5Ａ１Ａ２Ａ３产量ai9４８３５５３５销量bj２１B1B2B3B4B51020591021082561157104平衡表运价表3.2运输问题的表上作业法一、编制初始调运方案求解运输问题的表上作业法的步骤：3.2运输问题的表上作业法一、编制初始调运方案求解运输问题的表上作业法的步骤：解销地产地B1B2B3B4B5Ａ１Ａ２Ａ３产量ai9４８３５５３５销量bj２１B1B2B3B4B51020591021082561157104平衡表运价表136251314445063575初始基本可行解为{x11,x12,x13,x23,x33,x34,x35}={3,5,1,4,0,3,5},相应运价为：{c11,c12,c13,c23,c33,c34,c35}={10,20,5,8,7,10,4},由此表上作业得初始调运方案的总运费为S=S=3x10+5x20+1x5+4x8+0x7+3x10+5x4=217（元）方法3沃格尔法例3用沃格尔法求解如下运输问题：产地销地B1B2B3B4销量行罚数A116A210A322产量814121448列罚数4923106851112114011251314801121386012128276121244221闭回路法销地产地B1B2B2B4产量A110616A2８210Am14822销量8141214484923106811512114二解最优性检验2位势法(1)计算位和势销地产地B1B2B2B4产量A110616u1(1)A2８210u2(0)Am14822u3(-4)销量814121448V1(2)v2(9)v3(3)v4(10)4923106811512114最优性检验(2)计算检验数根据óij=cij-(ui+vj)基变量的检验数为0当存在检验数为负数时要对方案调整对检验数为负数的格进行调整(调整量为奇顶点上的最小者)销地产地B1B2B2B4产量A110616A2８210Am14822销量8141214484923106811512114三解的改进§3.4运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为...