1、产销不平衡的运输问题产销不平衡的运输问题内内 容容运运 输输 问问 题题表上作业法表上作业法123运输问题的应用运输问题的应用4 运筹学运筹学 第三章第三章 运输问题运输问题Slide 3一、运输模型（产销平衡）一、运输模型（产销平衡）例例1 1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？销地销地运费单价运费单价产地产地A1646200A2655300销量销量150150200B1B2B3产量产量（件）（件）设Xij表示从产地Ai调运到Bj的运输量(i1，2；j1，2，3
2、)，现将安排的运输量列表如下：运筹学运筹学 第三章第三章 运输问题运输问题Slide 4产销平衡表产销平衡表满足产地产量的约束条件为：X11+X12+X13=200 X21+X22+X23=300满足销地销量的约束条件为：X11+X21150 X12+X22150 X13+X23200 运筹学运筹学 第三章第三章 运输问题运输问题Slide 5使运输费最小的目标函数为：minz6X11+4X12+6X13+6X21+5X22+5X23Xij=0一般运输问题的线性规划的模型一般运输问题的线性规划的模型：有m个产地生产某种物资，有n个地区需要该类物资。Al，A2，Am表示某种物资的m个产地；Bl，
3、B2，Bn表示某种物资的n个销地；令a1,a2,am表示各产地产量，b1,b2,bn表示各销地的销量，ai=bj 称为产销平衡。Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。运筹学运筹学 第三章第三章 运输问题运输问题Slide 6则产销平衡的运输问题的线性规划模型如下所示：0 21 211111ijjmiijnjiijminjijijxnjbxmiaxxcz销量约束产量约束,min运输问题有mn个决策变量，m+n 个约束条件。由于产销平衡条件，只有m+n1个相互独立，因此，运输问题的基变量只有m+n1 个。运筹学运筹学 第三章第三章 运输问
4、题运输问题Slide 7共有2个产地和3个销地，产销平衡。基变量的个数为2+3-1=4销地销地运输量运输量产地产地A1501500200A21000200300销量销量150150200500B1B2B3产量产量（件）（件）Objective value:2500 运筹学运筹学 第三章第三章 运输问题运输问题Slide 8二、表上作业法二、表上作业法表上作业法表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。其实质是单纯形法。(1)给出初始调运方案给出初始调运方案初始基可行解：即在(mn)产销平衡表上给出m+n-1个数字格个数字格。用最小元素法或伏格尔法最小元素法或伏格尔法
5、。(2)检验检验方案是否最优，若是最优解，则停止计算；否则转下一步。求各非基变量的检验数，即在表上计算空格的计算空格的检验数检验数。在表上用闭环回路法或乘数法闭环回路法或乘数法。(3)调整调整调运方案，得新的方案。确定入基和出基变量，找出新的基可行解。在表上用闭环回路法闭环回路法。(4)重复(2),(3)直到求出最优方案。【定理】：产销平衡的运输问题一定有可行解，且一定【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。有最优解。运筹学运筹学 第三章第三章 运输问题运输问题Slide 9证：记ai=bj=QXij=aibj/Q就是一个可行解，因为Xij0，且满足Xij=ai,Xij=bj
6、又因为Cij0,Xij0,所以目标函数有下界零。因而运输问题一定有最优解。1、确定初始基可行解、确定初始基可行解最常用的方法是最小元素法最小元素法。既简便，又尽可能接近最优解。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。运筹学运筹学 第三章第三章 运输问题运输问题Slide 10P83例例2.1：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A17吨，A24吨，A39吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B13吨，B26吨，B35吨，B46吨。已知从各工厂到各销售点的单位产品
7、的运价如下表所示。产销平衡表产销平衡表1）找出最小运价为1，先将A2的产品供应给B1，因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。2）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。最后在最后在(A1,B4)的交叉格处填上的交叉格处填上3，将，将A1行和行和B4列运价同时列运价同时划去，得到一个初始调运方案。划去，得到一个初始调运方案。这方案的总运费为这方案的总运费为86
8、元。元。销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 71 11 19 94 43 32 21 10 01 10 08 85 5314633 运筹学运筹学 第三章第三章 运输问题运输问题Slide 12最小元素法中的退化情况最小元素法中的退化情况第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6
9、，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。出现退化时，要在同时被划去的行列中选一个空格填出现退化时，要在同时被划去的行列中选一个空格填0，此格作为有数字格。此格作为有数字格。销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 A A1 1 A A2 2 A A3 3 3 3 3 3 1 1 1 11 1 9 9 2 2 3 3 4 4 1 10 0 1 10
10、0 8 8 5 5 345602伏格尔法伏格尔法(Vogel)差额法：差额法：最小元素法的缺点最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。伏格尔法考虑到：伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 315632 运筹学运筹学 第三章第三
11、章 运输问题运输问题Slide 151）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。3）对未划去的元素再分别计算出各行、各列的最小运对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为总运费为85元元。伏格尔法给出的初始解比用最小元素法给出的更接近伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出
12、的初始解就是最优解。最优解。本例用伏格尔法给出的初始解就是最优解。运筹学运筹学 第三章第三章 运输问题运输问题Slide 162、调运方案的检验、调运方案的检验判别的方法是计算空格（非基变量）的检验数，若所有的检验数都大于等于0，为最优解。1）闭环回路法：）闭环回路法：在给出的初始调运方案表上，从每一空格出发找一条闭环回路，它是以某空格为起点，用水平或垂直线向前划，每碰到一数字格转90后（回路的转角点必须是一个基变量回路的转角点必须是一个基变量），继续前进，直到回到起始空格为止。从每一空格出发一定存在且只有唯一的从每一空格出发一定存在且只有唯一的闭环回路。闭环回路。从空格开始加减闭环各个顶点的
13、运输单价，可得每个空格对应的检验数。销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 314633 销销地地产产地地B B1 1B B2 2B B3 3B B4 4A A1 1A A2 2A A3 33 31 17 71 11 19 94 43 32 21 10 01 10 08 85 5空格空格闭环回路闭环回路检验数检验数(11)(11)(21)(23)(13)(11)1(12)(12)(32)(34)(14)(12)2(22)(22)(32)(34
14、)(14)(13)(23)(22)1(24)(24)(14)(13)(23)(24)-1(31)(31)(34)(14)(13)(23)(21)(31)10(33)(33)(34)(14)(13)(33)12 运筹学运筹学 第三章第三章 运输问题运输问题Slide 18闭环回路计算检验数的经济解释为：闭环回路计算检验数的经济解释为：从任一空格出发，如(A1,B1)，若让A1的产品调运1吨给B1，为了保持产销平衡，就要依次作调整：在(A2,B1)处减少1吨，在(A2,B3)处增加1吨，在(A1,B3)处减少1吨，即构成了以空格(A1,B1)为起点的闭环回路。调整后的方案使运费变成(+1)3(1)
15、1(+1)2(1)31（元）这就是(A1,B1)的检验数。当检验数还存在当检验数还存在负数负数时，说明原方案还不是最优解。时，说明原方案还不是最优解。用闭环回路求检验数用闭环回路求检验数,当产销点很多时当产销点很多时,这种计算很繁琐。这种计算很繁琐。2）乘数法（位势法）：）乘数法（位势法）：乘数法的原理是对偶理论。乘数法的原理是对偶理论。运输问题运输问题()0ijijijijijjiijMin Zc xxapxbx()(),iijjijijijMax Waub vuvc mndu v个约束为自由变量对偶问题对偶问题(),(*)ijijijijdu vc对加松弛变量则+与原问题有什么关系？与原问
16、题有什么关系？由对偶性质，由对偶性质，ijijuvcP93-94基变量：基变量：X13 U1+V3=C13=3X14 U1+V4=C14=10X21 U2+V1=C21=1X23 U2+V3=C23=2X32 U3+V2=C32=4X34 U3+V4=C34=5设U10，则V3=3,U2=-1,V1=2,V4=10,U3=-5,V2=9非基变量：非基变量：C11U1V1=3021C12U1V211092C22U2V2=9191C24U2V481101C31U3V1=7+5210C33U3V3=105312310U1=012U2=-145U3=-5V1=2 V2=9 V3=3 V4=103-0-
17、2=111-0-9=2U1=09+1-9=18+1-10=-1U2=-17+5-2=1010+5-3=12U3=-5V1=2V2=9V3=3V4=103、调整改进的闭环回路方法、调整改进的闭环回路方法迭代迭代若有两个或两个以上的负检验数时，一般选其中最小的负检验数。以(24)格为调入格，以此格为出发点，作一闭环回路。在闭回路上进行运量调整，使选定空格处的运量尽可能运量尽可能地增加（即取相邻两数字格中较小的）地增加（即取相邻两数字格中较小的）。销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 4 4 1 1
18、 3 3 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6 销销地地产产地地 B B1 1 B B2 2 B B3 3 B B4 4产产量量 A A1 1 A A2 2 A A3 3 3 3 6 6 5 5 0 0 2 2 1 1 3 3 7 7 4 4 9 9 销销量量 3 3 6 6 5 5 6 6运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。经检验，经检验，所有检验数都所有检验数都非负非负，故达到最优，最优方案总运费最小是，故达到最优，最优方案总运费最小是85元。元。运筹学运筹学 第三章第三章 运输问题运输问题Slide 22 课堂
19、作业：课堂作业：1、用表上作业法求出最优解。（最小元素法）、用表上作业法求出最优解。（最小元素法）销售点销售点产量产量加工厂加工厂A1327650A2752360A3254525销量销量6060404020201515135135B1B2B3B4销售点销售点产量产量加工厂加工厂A18637520A25M84730A36396830销量销量25252525202010102020B1B2B3B5B42、用伏格尔法直接给出近似最优解。、用伏格尔法直接给出近似最优解。运筹学运筹学 第三章第三章 运输问题运输问题Slide 231、这是一个产销平衡的问题。、这是一个产销平衡的问题。1）初始调运方案（最
20、小元素法）初始调运方案（最小元素法）销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 5 50 0 6 60 0 2 25 5 销销量量 6 60 0 4 40 0 2 20 0 1 15 5 1 13 35 5 销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 A A1 1 A A2 2 A A3 3 3 3 7 7 2 2 2 2 5 5 5 5 7 7 2 2 4 4 6 6 3 3 5 5 401520251025初始调运方案的总运费为420元。2）最优解的判别（闭环回路法）最优解的
21、判别（闭环回路法）销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 A A1 1 A A2 2 A A3 3 3 3 7 7 2 2 2 2 5 5 5 5 7 7 2 2 4 4 6 6 3 3 5 5 销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 5 50 0 6 60 0 2 25 5 销销量量 6 60 0 4 40 0 2 20 0 1 15 5 1 13 35 5 401520251025空格空格闭环回路闭环回路检验数检验数(13)(13)(23)(21)(11)(13)9(
22、14)(14)(24)(21)(11)(14)7(22)(22)(12)(11)(21)(22)1(32)(32)(12)(11)(31)(32)4(33)(33)(23)(21)(31)(33)7(34)(34)(24)(21)(31)(34)7（乘数法）：（乘数法）：基变量：基变量：X11 U1+V1=C11=3X12 U1+V2=C12=2X21 U2+V1=C21=7X23 U2+V3=C23=2X24 U2+V4=C24=3X31 U3+V1=C31=2设U10，则V1=3,V2=2,U2=4,V3=-2,V4=-1,U3=-1非基变量：非基变量：C13U1V3=70+29C14U1
23、V460+17C22U2V2=542-C32U3V25124C33U3V3=4+1+27C34U3V4=5+1+1732U1=0723U2=42U3=-1V1=3V2=2V3=-2V4=-17-0+2=96-0+1=7U1=05-4-2=-1U2=45+1-2=44+1+2=75+1+1=7U3=-1V1=3V2=2V3=-2V4=-1 运筹学运筹学 第三章第三章 运输问题运输问题Slide 263)调整调运方案，得新的方案。调整调运方案，得新的方案。以(22)格为调入格，以此格为出发点，作一闭环回路。经检验，所有检验数都大于0，该调运方案是最优的方案。总运费为395元。销销地地 产产地地 B
24、 B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 5 50 0 6 60 0 2 25 5 销销量量 6 60 0 4 40 0 2 20 0 1 15 5 1 13 35 5 401520251025 销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 产产量量 A A1 1 A A2 2 A A3 3 5 50 0 6 60 0 2 25 5 销销量量 6 60 0 4 40 0 2 20 0 1 15 5 1 13 35 5 1515202535252、用伏格尔法直接给出近似最优解。用伏格尔法直接给出近似最优
25、解。销售点销售点产量产量加工厂加工厂A18637520A25M84730A36396830假想假想D0000020销量销量25252525202010102020100100B1B2B3B5B45202025201000 运筹学运筹学 第三章第三章 运输问题运输问题Slide 29销售点销售点产量产量加工厂加工厂A120020A2201030A352530假想假想D02020销量销量25252525202010102020100100B1B2B3B5B4销销地地 产产地地 B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 行行 差差额额 A A1 1 A A2 2 A A3
26、 3 假假想想地地 D D 8 8 5 5 6 6 0 0 6 6 M M 3 3 0 0 3 3 8 8 9 9 0 0 7 7 4 4 6 6 0 0 5 5 7 7 8 8 0 0 2 2 0 0 0 0 0 0 列列差差额额 0 0 M M 5 5 2 2 8 8 用伏格尔法直接找到了近似最优用伏格尔法直接找到了近似最优方案，总运价为方案，总运价为305元。元。运筹学运筹学 第三章第三章 运输问题运输问题Slide 30第二种算法：第二种算法：销售点销售点产量产量加工厂加工厂A12020A25101530A325530假想假想D20020销量销量25252525202010102020
27、100100B1B2B3B5B4用伏格尔法直接找到了近似最优方案，总运价为345元。用伏格尔法求解，是否一定要转化为产销平衡用伏格尔法求解，是否一定要转化为产销平衡表？表？三、三、产销不平衡的运输问题产销不平衡的运输问题 产销平衡表产销平衡表 P96例例2.3：假设产地A1的产品必须全部调运出去,产地A2、A3的商品调运不出的单位存储费为2百元和1百元产大于销产大于销运输费用：运输费用：22+54+33+41+12=39(百元百元)存储费用：存储费用：22+21=6(百元百元)总成本：总成本：39+6=45(百元百元)P98例例2.4销大销大于产于产销地B1、B2的需求必须全部满足，销地B3、
28、B4每短缺1吨，发生损失费1百元、0。总成本是52百元，其中2百元是销地B3发生缺货的损失费。运筹学运筹学 第三章第三章 运输问题运输问题Slide 34例例3石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北临城，山西孟县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同。两处煤矿能供应北方研究院的煤的数量，山西盂县为4000吨，河北临城为l500吨，由煤矿至北方研究院的单位运价(百元吨)见下表。由于需求大于供给，经院研究平衡决定一区供应量可减少0200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费最低
29、的调运方案。销地销地运费单价运费单价产地产地山西孟县山西孟县1.651.71.75河北临城河北临城1.61.651.7一区一区二区二区三区三区 运筹学运筹学 第三章第三章 运输问题运输问题Slide 35河北临城，山西孟县两处煤矿可以供应煤5500吨。一区、二区、三区至少需要煤5500吨。至多需要煤6000吨。一区和三区必须供应的煤分别为2800吨和1700吨。可以不供应的煤分别为200吨和300吨。产销平衡表产销平衡表销地销地供应量供应量运费单价运费单价（吨）（吨）产地产地山西孟县山西孟县1.651.651.71.751.754000河北临城河北临城1.61.61.651.71.71500假
30、想生产点假想生产点M0MM0500需求量需求量6000（吨）（吨）6000三区三区2280020010001700300一区一区1一区2二区三区三区1 运筹学运筹学 第三章第三章 运输问题运输问题Slide 36例例4设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。需求地区需求地区化肥厂化肥厂A1613221750B1413191560C19202350最低需求最低需求（万吨）（万吨）3070010最高需求最高需求（万吨）（万吨）507030不限不限产
31、量产量（万吨）（万吨）IIIIIIIV 运筹学运筹学 第三章第三章 运输问题运输问题Slide 37三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量，问：根据现有三个化肥厂的产量，地区IV 最高需求是否可以不限？最高需求是多少？160 3070060吨四个地区对化肥的最高需求为50703060 210吨 运筹学运筹学 第三章第三章 运输问题运输问题Slide 38四、运输问题的应用四、运输问题的应用（一）生产与储存的问题（一）生产与储存的问题 P109习题习题2-16 某厂按合同规定须于当年每个季度末分别提供10,15,25,20台同一规格的柴油机。已知该厂各季度的生产能力及市场每
32、台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护费用0.2万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。季度季度生产能力生产能力（台）（台）单位成本单位成本（万元）（万元）12510.823511.13301141011.3 运筹学运筹学 第三章第三章 运输问题运输问题Slide 39设Xij为第i季度生产的用于第j季度交货的柴油机数实际的成本为该季度生产成本加上储存和维护费用。四个季度的生产能力为100台。而四个季度末共须提供柴油机70台。运筹学运筹学 第三章第三章 运输问题运输问题Slide 40例例6光明仪器
33、厂生产电脑绣花机是以销定产的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表。又已知上年末库存103台绣花机。加班生产机器每台增加成本1万元。月份月份16010104152501075143902011513.54100401601351004010313680407013.5正常生产正常生产能力能力（台）（台）加班生产加班生产能力能力（台）（台）销量销量（台）（台）单台费用单台费用（万元）（万元）运筹学运筹学 第三章第三章 运输问题运输问题Slide 41又如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元，每台机器每月的平均仓储费、维
34、护费为0.2万元。在7、8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。问应如何安排16月份的生产使总的生产(包括运输、仓储、维护)费用最少?设Xij为第i个月生产的用于第j个月交货的机器数实际的成本为该月生产成本加上运输、储存和维护费用将正常生产和加班生产分成两种不同的生产月来进行安排。六个月的生产能力为743台。而六个月末共须提供机器707台。上年末库存的103台绣花机，作为第0个月的生产供给。销售月销售月单价单价生产月生产月正常正常00.30.50.70.91.11.3011515.315.515.715.916.1011616.316.516.716.91
35、7.10102M1414.314.514.714.902M1515.315.515.715.90103MM13.513.81414.203MM14.514.81515.20204MMM1313.313.504MMM1414.314.50405MMMM1313.305MMMM1414.30406MMMMM13.506MMMMM14.5040销量销量（万吨）（万吨）1047511516010315036743743100809010010360505月月6月月假想假想销地销地产量（台）产量（台）加班加班1月月2月月3月月4月月 运筹学运筹学 第三章第三章 运输问题运输问题Slide 43（二）调度
36、问题（二）调度问题例例7：某航运公司承担六个港口初始A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见下表71。假定各条航线使用相同型号的船只，又各城市间的航程天数见表72。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？表表71 航线航线起点城市起点城市终点城市终点城市每天航班每天航班数数1ED32BC23AF14DB1表表72(1)(1)载货航程需要的周转船只数：载货航程需要的周转船只数：航线航线装货天数装货天数航程天数航程天数卸货天数卸货天数小计小计航班数航班数周转船只数周转船只数1117119
37、3572131521031719194113115115 运筹学运筹学 第三章第三章 运输问题运输问题Slide 45 例如：航线1，在港口E装货1天，ED航程17天，在D卸货1天，总计19天。每天3航班。故该航线需周转船57条以上共需周转船只数91条。(2)各港口间调度所需船只数各港口间调度所需船只数。有些港口每天到达船数多于需要船数。例如，港口D，每天到达3条，需求1条。港口城市港口城市每天到达每天到达每天需求每天需求余缺数余缺数A01-1B12-1C202D312E03-3F101 运筹学运筹学 第三章第三章 运输问题运输问题Slide 46 为使各港口间调度周转所需的空船空船数最少，其
38、产销平衡表如下。单位运价应为相应各港口之间的船只航程天数。可求出空船的最优调度空船的最优调度方案如下：运筹学运筹学 第三章第三章 运输问题运输问题Slide 47 由上表可计算得知最少周转的空船数为40条。所以，在不考虑维修、储备等情况下，该公司至少应配备131条船。（三）转运问题（三）转运问题例例8腾飞电子仪器公司在大连和广州有两个分厂，大连分厂每月生产400台某种仪器，广州分厂每月生产600台某种仪器。该公司在上海与天津有两个销售公司负责对南京、济南、南昌与青岛四个城市的仪器供应，又因为大连与青岛相距较近，公司同意大连分厂也可以向青岛直接供货。这些城市间的每台仪器的运输费用我们标在两个城市
39、间的弧上，单位为百元。问应该如何调运仪器，使得总的运输费最低。运筹学运筹学 第三章第三章 运输问题运输问题Slide 48思路思路:将转运问题化为无转运问题。将转运问题化为无转运问题。中转地中转地3 3、4 4既可作为产地，也可作为销地。既可作为产地，也可作为销地。例例9：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A17吨，A24吨，A39吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B13吨，B26吨，B35吨，B46吨。已知从各工厂到各销售点的单位产品的运价如下表所示。课本课本P100例例2.5 运筹学运筹学 第三章第三章 运输问题运输问题Slide 50如果假定1）
40、每个工厂生产的产品不一定直接发运到销售点，可以其中几个产地集中一起运；2）运往各销售点的产品可以先运给其中几个销售点，再转运给其它销售点；3）除产地、销售点之外，中间还可以有几个转运站，在产地之间、销售点之间或产地与销售点之间转运。已知各产地、销售点、中间转运站及相互之间每吨产品的运价如下表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往各个销售点，使总的运费最少。销售点销售点加工厂加工厂A1311310A21928A374105B1B2B3B4 运筹学运筹学 第三章第三章 运输问题运输问题Slide 52从A1到B2的单位运价为11元，如从
41、A1经A3运往B2，运价为347元，从A1经T2运往B2，运价为156元。运费最少的路经是从A1经A2、B1运往B2，运价为1+1+13元1)所有的产地、中转地和销地都可以看作产地，也可以看作销地。因此整个问题被当作有11个产地和个产地和11个销地个销地的扩大运输问题。2)中转站中转站的产量等于销量。每个中转站的转运量不大于不大于20吨吨。可以规定四个中转站的产量和销量均为20吨。实际的转运量小于20吨，可以加入一个松弛量Xii，对应的运价为0。(20 Xii)为实际的转运量。3)原来的产地和销地原来的产地和销地也有转运站的作用，故三个厂产量为27、24、29吨，销量均为20吨，四个销售点的销
42、量为23、26、25、26吨，产量均为20吨。同时引进Xii作为松弛变量。运筹学运筹学 第三章第三章 运输问题运输问题Slide 54例例10：某厂在A、B、C三处设仓库供应点的各零售商，详见下图。图中各边数字为沿该线路运送一单位物资所需的费用（元）。已知A、B、C三仓库内现库存物资数分别为200、170、160单位。点各零售商所需物资数列于下表。且对零售商供应短缺一单位时的罚款也列于表中。应如何确立各仓库对各零售点的分配量，使总的运输费和罚款之和最小。ABC 运筹学运筹学 第三章第三章 运输问题运输问题Slide 56总供给量530，总需求量550。零售点零售点费用费用仓库仓库A488191162220200B14771612162317170C20191114615510160假想假想D1085101085820550产量产量销量销量7560357010040908056781234
