《运输问题》PPT课件

《《运输问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学OPERATIONALRESEARCH第三章运输问题1课件第一节运输问题及其数学模型一、运输问题的典型形式及其数学模型1.引例2课件求最小运费的运输方案销地产地B1B2B3产量A1645300A2655200销量1501502003课件minZ=6x11+4x12+5x13+6x21+5x22+5x23x11+x12+x13=300x21+x22+x23=200x11+x21=150x12+x22=150x13+x23=200xij04课件A1AmB1B2Bna1……cijA2a2ambnb2b1……求最

2、小运费的运输方案2.典型的运输问题：5课件销地产地B1B2…Bn产量A1a1A2a2……Amam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm26课件销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm27课件minZ=6x11+4x12+5x13+6x21+5x22+5x23x11+x12+x13=300x21+x22+x23=200x11+x21=

3、150x12+x22=150x13+x23=200xij03.运输问题的数学模型8课件i=1,2j=1,2,3xij09课件i=1,2,…,mj=1,2,…,nxij0典型运输问题的数学模型10课件二、运输问题数学模型的特点：运输问题一定有最优解；运输问题约束条件的系数矩阵：x11+x12+x13=300x21+x22+x23=200x11+x21=150x12+x22=150x13+x23=200xij011课件x11x12x13x21x22x23111111111112个3个12课件x11+x12+…

4、+x1n=a1x21+x22+…+x2n=a2………………………………xm1+xm2+…+xmn=amx11+x21+xm1=b1x12+x22+xm2=b2………………………………x1n+x2n+xmn=bnxij013课件x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1………………………………11…11…111…1………………………………11…1mn14课件系数矩阵的特点：（1）约束条件的系数矩阵的元素只有两个：0、1。（2）元素xij对应于每一个变量在前m个约束方程中(第i个

5、方程中)出现一次，在后n个约束方程中（第m+j个方程中）也出现一次。（3）产销平衡问题为等式约束。（4）产销平衡问题中各产地产量之和与各销售地点的销量之和相等。15课件3.运输问题基变量的个数：m+n-1个16课件第二节表上作业法一、表上作业法的基本思想和步骤：1.基本思想：同单纯形法的基本思想基本可行解是否为最优解换基结束YN17课件2.表上作业法的步骤（1）寻找初始基可行解；最小元素法、西北角法、沃格尔法（2）求出非基变量检验数（空格检验数），判断是否为最优解；闭回路法、位势法（3）换基改进，找到新的基可行解

6、闭回路调整法（4）重复（2）（3）18课件二、确定初始基可行解（一）最小元素法：19课件销地产地B1B2B3B4产量A116A210A322销量8141214484125210391146811求运费最小的运输方案。例题（P82例1）20课件412521039114681102销地产地B1B2B3B4产量A110616A28210A314822销量81412144800600621课件4125210391146811销地产地B1B2B3B4产量A116A210A322销量814121448（二）西北角法22课件4

7、125210391146811销地产地B1B2B3B4产量A18816A26410A381422销量814121448（二）西北角法23课件（三）沃格尔法伏格尔法思路：一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加越多。因而，对差额最大处，就应当采用最小运费调运24课件罚数=次小费用-最小费用1、在运价表中分别计算出各行、列的行罚数和列罚数，并填入该表的最右列和最下行。2、从行或列差额中选出最大者，选择它所在行或列的最小元素。按类似于最小元素法

8、优先供应，划去相应的行或列。3、对表中未划去的元素重复1，2步，直至所有的行和列被划掉为止。沃格尔法基本步骤：25课件4125210391146811销地产地B1B2B3B4产量行罚数A1124160A282101A3148221销量814121448列罚数251326课件三、最优解的判别(一)闭回路法闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路