运筹学运输问题.ppt

《运筹学运输问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运输问题简介运输问题是线性规划问题的特例。产地：货物发出的地点。销地：货物接收的地点。产量：各产地的可供货量。销量：各销地的需求数量。运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。一、运输模型引例：某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448(

2、1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数minZ=4x11+12x12+4x13+11x14+2x21+10x22+3x23+9x24+8x31+5x32+11x33+6x34(3)约束条件。产量之和等于销量之和,故要满足：运输问题的LP模型供应平衡条件产地A1：x11+x12+x13+x14=16产地A2：x21+x22+x23+x24=10产地A3：x31+x32+x33+x34=22销售平衡条件销地B1：x11+x21+x31=8销地B2：x12+x22+x32=14销地B3：x13+x23+x33=12销地B4：x14+x24+x3

3、4=14非负性约束xij≥0(i=1,2,3；j=1,2,3,4)二、表式运输模型销地产地A1A2…Am产量a1a2…amB1B2…Bn销地b1b2…bnc11c12…c1nc21c22…c2n…………cm1cm2…cmnx11x12x1nx21x22x2nxm1xm2xmn三、运输问题的三种类型产销平衡产大于销产小于销四、运输模型的特点决策变量mn约束方程m+n系数矩阵的结构如下：x11x12…x1nx21x22…x2n…………xm1xm2…xmnm行n列例题的系数矩阵约束1约束2约束3约束4约束5约束6约束7运输问题求解思路先找到一个初始基可行解，判断其

4、是否最优？如果是，计算结束，得到最佳运输方案。如果不是，则迭代到相邻的基可行解（向目标函数减少的方向），直到求得最优解！为了能按上述思路求解运输问题，要求每一步都必须是基可行解：（1）解必须满足模型中的所有约束条件（2）基变量对应的约束方程组的系数列向量线性无关（3）解中非零变量xij的个数不能大于（m+n-1)个，原因是运输问题中虽有(m+n)个结构约束条件，但由于总产量等于总销量，故只有(m+n-1)个结构约束条件是线性独立的，所以一般我们在迭代过程中都保持基变量的个数为(m+n-1)个。表上作业法表上作业法适合于产销平衡的运输问题求解步骤：找出初始方案（

5、初始基可行解）：产销平衡表上给出m+n-1个数字。最优性检验：计算各非基变量的检验数，当ij0最优（因为现在是求最小化问题）。方案调整与改进：确定进基变量和离基变量，找出新的基可行解。一、确定初始方案西北角法最小元素法“就近运给”，从单位运价表中最小运价开始确定供销关系，逐次挑选最小元素，安排运量min{ai,bj}。最大差额法（沃格尔法）不能按最小运费就近供应，就考虑次小运费。各行(各列)的最小运费与次小运费之差称为行差(列查)。差额越大，说明不能按最小运费调运时，运费增加最多。对最大差额处就采用最小运费调运。★★西北角法西北角法按照运输表格中的位置，安

6、排最西北角（也就是左上角的位置），优先运输。销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448初始基可行解：x11=8,x12=8,x22=6,x23=4,x33=8,x34=14，Z=3728864814（8）★★最小元素法人们容易直观想到，为了减少运费，应优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量，即对所有的i和j，从单位运价表中逐次挑选最小元素，安排运量min{ai,bj}，若xij=ai,则产地Ai的可供物品已用完，以后不再继续考虑这个产地，且Bj的需求量由bj减少为bj

7、-ai，即当产小于销，划去该元素所在行；如果xij=bj，则销地Bj的需求已全部得到满足，以后不再考虑这个销地，且Ai的可供量由ai减少为ai-bj，即当产大于销，划去该元素所在列；然后在余下的继续进行，直到安排完所有供销任务。销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448初始基可行解：x13=10,x14=6,x21=8,x23=2,x32=14,x34=8，Z=24682101486★★最大差额法（沃格尔法）初看起来，最小元素法十分合理，但是，有时按某一最小单位运价优先安排物品调运时，却可能导致不

8、得不采用运费很高的其它供销点对，从而使