运筹学运输问题

1、第第1页页第三章第三章 运输问题运输问题特殊的线性规划特殊的线性规划第第2页页第三章第三章 运输问题运输问题特殊的线性规划特殊的线性规划第第3页页运输问题的典例运输问题的典例例例1.1.某食品公司经销的主要产品之一是糖果某食品公司经销的主要产品之一是糖果. .它下面设有三个加工厂它下面设有三个加工厂, ,每每天的糖果天的糖果产量分别为产量分别为:A:A1 1-7t,A-7t,A2 2-4t,A-4t,A3 3-9t-9t. .该公司把这些糖果分别运往该公司把这些糖果分别运往四个地区的门市销售四个地区的门市销售, ,各地区每天的各地区每天的销售量分别为：销售量分别为：B B1 1-3t, B-3

2、t, B2 2-6t-6t，B B3 3-5t,B-5t,B3 3-6t-6t. .已知从每个加工厂到各销售门市部每吨的运价如表所示已知从每个加工厂到各销售门市部每吨的运价如表所示，问该食品公司应如何调运问该食品公司应如何调运, ,在满足各门市部销售需要的情况下，使在满足各门市部销售需要的情况下，使得总的运费支出为最少得总的运费支出为最少. .8291A251047A3103113A1B4B3B2B1门市部门市部加工厂加工厂表表 3-1 单位：元单位：元/t第第4页页 现有一批货物现有一批货物, 从从m个供应地个供应地运往运往n个销售地个销售地, Ai ( i=1, ,m )处处有货物有货物a

3、i吨吨，Bj ( j= 1,n)处处需货物需货物bj吨吨, 已知从已知从Ai到到Bj的的运价运价为为cij 元元/吨吨. 问如何安排，既可以满足各销地需要，又使总费用最小？问如何安排，既可以满足各销地需要，又使总费用最小？A1A2AmB1B2Bna1a2amb1b2bm供应量供应量需求地需求地供应地供应地需求量需求量调运量调运量xij运输问题的框图表示运输问题的框图表示第第5页页产销表产销表运输问题的数学模型运输问题的数学模型第第6页页单位运价表单位运价表第第7页页1B2BnB1A1a11x12xnx12A2a21x22xnx2mA2mc11c12cnc121c22cnc21mcmncma1m

4、x2mxmnx1b2bnbnjjbmiia11产销平衡产销平衡条件下条件下第第8页页设设xij为从产地为从产地A Ai运往销地运往销地B Bj的物资数量的物资数量( (i=1,i=1,m;jm;j=1,n=1,n）从从Ai运出的物资总量运出的物资总量应等于应等于Ai的产量的产量ai，xij应满足：应满足： miaxnjiij, 2 , 11运到运到Bj的物资总量的物资总量应该等于应该等于Bj的销量的销量bj，xij还应满足：还应满足：mijijnjbx1, 1第第9页页总运费为：总运费为：11minmnij ijijzc x第第10页页 njmixnjbxmiaxtsxczijmijijnji

5、ijminjijij,1;,1,0,1,1.min1111minjjiba11产销平衡条件第第11页页minjjiba11 njmixnjbxmiaxtsxczijmijijnjiijminjijij,1;,1,0,1,1.min1111第第12页页将将约约束束方方程程组组展展开开约束方程组共包含约束方程组共包含mn个变量个变量，(m+n)个约束条件个约束条件111,. .1,0,1,;1,nijijmijjiijxaims txbjnxim jn第第13页页mnmmnnxxxxxxxxx,;,212222111211111111111111111111m行行n行行矩阵的元素均为矩阵的元素均为

6、1 1或或0 0； 每一列只有两个元素为每一列只有两个元素为1 1，其余元素均为，其余元素均为0 0；将矩阵分块将矩阵分块, ,特点是特点是: :前前m m行构成行构成m m个个m mn n阶矩阵阶矩阵, ,而且而且第第k k个矩阵只有第个矩阵只有第k k行元素全为行元素全为1,1,其余元素全为其余元素全为0 0（k=1,k=1,m,m）; ;后后n n行构成行构成m m个个n n阶单位阵阶单位阵。0110ijimjPee mnmmnnxxxxxxxxx,;,212222111211111111111111111111 m行行 n行行为什么？为什么？第第i行行第第m+j行行 第第15页页第三章

7、第三章 运输问题运输问题特殊的线性规划特殊的线性规划第第16页页第三章第三章 运输问题运输问题特殊的线性规划特殊的线性规划第第17页页表上作业法表上作业法 表上作业法是单纯形法求解运输问题的一表上作业法是单纯形法求解运输问题的一种简化方法，实质是单纯形法。但是具体计种简化方法，实质是单纯形法。但是具体计算和术语有所不同。算和术语有所不同。1B2BnB1A1a11x12xnx12A2a21x22xnx2mA2mc11c12cnc121c22cnc21mcmncma1mx2mxmnx1b2bnbnjjbmiia11第第18页页运输问题中寻找可行解运输问题中寻找可行解1B2B3B4B1A2A3A填有

8、数字的格填有数字的格: :对应运输问题解中的基变量取值，对应运输问题解中的基变量取值，这里为这里为3+4-1=63+4-1=6个个空格：对应解中非基变量空格：对应解中非基变量第第19页页表上作业法表上作业法第第20页页 确定初始确定初始方案方案( (初始基可行解初始基可行解) ) 改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图求解思路图表上作业法表上作业法第第21页页(一一) 初始方案的给定初始方案的给定给定初始方案的方法很多给定初始方案的方法很多(如前例如前例)，一，一般来说，希望方法简便易行，并能给出般来说，希望方法简

9、便易行，并能给出较好的方案。减少迭代次数。这里介绍较好的方案。减少迭代次数。这里介绍即即749365620331B2B3B4B1A2A3A第第23页页7493656201B2B3B4B1A2A3A第第24页页最小元素法的说明最小元素法的说明退化现象退化现象： 部分产量和部分产量和部分销量和部分销量和在迭代在迭代过程中过程中，可能出现一行和一列，可能出现一行和一列同时被划去同时被划去。74936562061B2B3B4B1A2A3A0为使迭代过程中基变量的个数恰好为为使迭代过程中基变量的个数恰好为(m+n-1)(m+n-1)个，应在个，应在同时划去的一行或一列同时划去的一行或一列中的某个格中中的

10、某个格中填入数字填入数字0 0，表示这个格中的变量是取值为，表示这个格中的变量是取值为0 0的的基变量。以便当做有数字的格看待。基变量。以便当做有数字的格看待。第第26页页7493656201B2B3B4B1A2A3A0第第27页页优选考虑优选考虑最大差额（最小运价优势）最大差额（最小运价优势）方案方案罚数罚数次小次小运价系数运价系数- -最小最小运价系数运价系数1B2B3B4B1A2A3A产量产量销地销地产地产地1B2B3B4B1A2A3A0112513( )6220 0 71312121 1 62( )33( )521108( )第第28页页1B2B3B4B1A2A3A产量产量销地销地产地

11、产地1B2B3B4B1A2A3A633521一般当产销地数量不多时，一般当产销地数量不多时，(Vogel)法给出的初始方案法给出的初始方案有时就是最优方案。有时就是最优方案。第第29页页29练习练习. .求下表给出的运输问题的初始基本可行解求下表给出的运输问题的初始基本可行解 B1B2B3B4产量产量A14104420A2773815A31210615销量销量510251050(一一) 初始方案的给定初始方案的给定第第30页页30 销地销地产地产地B1B2B3B4aiA14104420A2773815A31210615销量销量5102510505100151010(一一) 初始方案的给定初始方

12、案的给定第第31页页31 BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一一) 初始方案的给定初始方案的给定第第32页页 确定初始确定初始方案方案( (初始基可行解初始基可行解) ) 改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图求解思路图表上作业法表上作业法第第33页页(一一) 初始方案的给定初始方案的给定给定初始方案的方法很多给定初始方案的方法很多(如前例如前例)，一，一般来说，希望方法简便易行，并能给出般来说，希望方法简便易行，并能给出较好

13、的方案。减少迭代次数。这里介绍较好的方案。减少迭代次数。这里介绍第第34页页最小元素法或最小元素法或VogelVogel法给出的是一个运输问题的基可行法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化当为否时，应进行调整得到优化. .(二二) 最优性检验与方案的调整最优性检验与方案的调整基本思想：基本思想： 计算非基变量计算非基变量（未填上数值的格，即空格）（未填上数值的格，即空格）的的检验数检验数（也称为（也称为空格的检验数空格的检验数），若全部），若全部大于等大于等于零于零，则该

14、方案，则该方案就是最优就是最优调运方案，调运方案，否则否则就应进就应进行调整。行调整。1.闭回路法闭回路法.对偶变量法（对偶变量法（位势法位势法）第第35页页 沿沿水平或垂直水平或垂直方向前，方向前，向左或右转向左或右转9090度度（当然也可以不改变方向）继续前进，这样当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由继续下去，直至回到出发的那个空格，由此形成的此形成的封闭折线封闭折线叫做闭回路。叫做闭回路。闭回路闭回路第第36页页 x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31 x42表中闭回路的变量集合是表中闭回路的变量集

15、合是 x x1111, ,x x1212, ,x x4242, ,x x 43 43, ,x x 23 23, ,x x 25 25, , x x 35 35, ,x x 31 31 共有共有8 8个顶点，个顶点， 这这8 8个顶点间用水平或垂个顶点间用水平或垂直线段连接起来，组成一直线段连接起来，组成一条封闭的回路。条封闭的回路。 运输问题中的闭回路运输问题中的闭回路 3-132222111,jijijijijijisssxxxxxx132222111,jijijijijijisssPPPPPP0132222111jijijijijijisssPPPPPPm+n-1个变量构成个变量构成基变量

16、基变量的充要条件是该变的充要条件是该变量组量组不含闭回路不含闭回路。第第38页页 确定初始确定初始方案方案( (初始基可行解初始基可行解) ) 改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图求解思路图表上作业法表上作业法第第39页页(一一) 初始方案的给定初始方案的给定给定初始方案的方法很多给定初始方案的方法很多(如前例如前例)，一，一般来说，希望方法简便易行，并能给出般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍较好的方案。减少迭代次数。这里介绍第第40页页最小元素法或最小元素法或VogelVoge

17、l法给出的是一个运输问题的基可行法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化当为否时，应进行调整得到优化. .(二二) 最优性检验与方案的调整最优性检验与方案的调整基本思想：基本思想： 计算非基变量计算非基变量（未填上数值的格，即空格）（未填上数值的格，即空格）的的检验数检验数（也称为（也称为空格的检验数空格的检验数），若全部），若全部大于等大于等于零于零，则该方案，则该方案就是最优就是最优调运方案，调运方案，否则否则就应进就应进行调整。行调整。1.闭回路法闭回路法.对偶变量法

18、（对偶变量法（位势法位势法）ijijkkxzz)()1(第第41页页 沿沿水平或垂直水平或垂直方向前，方向前，向左或右转向左或右转9090度度（当然也可以不改变方向）继续前进，这样当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由继续下去，直至回到出发的那个空格，由此形成的此形成的封闭折线封闭折线叫做闭回路。叫做闭回路。闭回路闭回路第第42页页 x25 x23 B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31 x42表中闭回路的变量集合是表中闭回路的变量集合是 x x1111, ,x x1212, ,x x4242, ,x x 43 43, ,

19、x x 23 23, ,x x 25 25, , x x 35 35, ,x x 31 31 共有共有8 8个顶点，个顶点， 这这8 8个顶点间用水平或垂个顶点间用水平或垂直线段连接起来，组成一直线段连接起来，组成一条封闭的回路。条封闭的回路。 运输问题中的闭回路运输问题中的闭回路第第43页页 3-132222111,jijijijijijisssxxxxxx132222111,jijijijijijisssPPPPPP0132222111jijijijijijisssPPPPPPm+n-1个变量构成个变量构成基变量基变量的充要条件是该变的充要条件是该变量组量组不含闭回路不含闭回路。第第44页

20、页 将如下表中将如下表中6 6个顶点间用水平或垂直线段连接起来，个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。组成一条封闭的回路。1B2B3B4B1A2A3A销量销量产产量量销地销地产地产地(A2 ,B1 ), (A3 ,B2)无法连入闭回路中无法连入闭回路中闭回路闭回路孤 立 格孤 立 格 是 指是 指 在 所 在 行在 所 在 行 或或 列 中列 中 唯 一唯 一 出 现 的 变 量 。出 现 的 变 量 。 孤立格一定不会成为闭回路的顶点孤立格一定不会成为闭回路的顶点最小元最小元素法得素法得初始方初始方案案第第45页页运输问题中的闭回路运输问题中的闭回路第第46页页目目 的：的：

21、计算解中各非基变量计算解中各非基变量( (空格空格) )的检验数的检验数基本思路：基本思路：1.1.对于代表对于代表非基变量非基变量的空格（其调运量为零），把它的的空格（其调运量为零），把它的调调运量调整为运量调整为1 1（每次调整一个非基变量每次调整一个非基变量）；2.2.由于产销平衡的要求我们必须对这个空格的闭回路的由于产销平衡的要求我们必须对这个空格的闭回路的顶顶点的调运量加上或减少点的调运量加上或减少1 1 ( (可行条件可行条件) )；3.3.计算出由这些变化给整个运输方案的总运输费带来的变计算出由这些变化给整个运输方案的总运输费带来的变化，这里称之为化，这里称之为检验数检验数。闭回

22、路法求检验数闭回路法求检验数ijijkkxzz)()1(1)( )1,kkijijxzzz 这里则4.4.如果如果所有所有代表非基变量的空格的检验数也即非基变量的代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则进行检验数都大于等于零，则已求得最优解，否则进行方方案调整（后续）案调整（后续）第第47页页1B2B3B4B1A2A3A同理可以找出所有空格（即非基变量）的检验数。同理可以找出所有空格（即非基变量）的检验数。1113 1231 即此新可行解较原来解运费增加即此新可行解较原来解运费增加1元元闭回路法求检验数闭回路法求检验数第第48页页闭回路法求检验数闭回路法

23、求检验数1B2B3B4B1A2A3A3110122224332;1;1;12; 75 1032 110 约定约定奇数次顶点奇数次顶点ij第第49页页- -11A21210A321A1B4B3B2B1销地销地产地产地检验数表检验数表闭回路法求检验数闭回路法求检验数第第50页页闭回路法求调整方案闭回路法求调整方案选一个选一个非基变量非基变量变为变为基变量基变量进基进基选一个选一个基变量基变量变为变为非基变量非基变量离基离基反映在运输表上就是要反映在运输表上就是要选一个空格填上大于选一个空格填上大于0 0的数的数0,minijijkl从绝对值最大的负检验数格(k,l)出发第第51页页闭回路法求调整方

24、案闭回路法求调整方案- -11A21210A321A1B4B3B2B1销地销地产地产地检验数表检验数表在作业表上以在作业表上以（A A2 2 , B , B4 4）为起点作一条除该空为起点作一条除该空格外其余顶点均为有数字格组成的闭回路格外其余顶点均为有数字格组成的闭回路第第52页页闭回路法求调整方案闭回路法求调整方案1B2B3B4B1A2A3A206563941374633调运方案（最小元素法得到）调运方案（最小元素法得到）+ +1- -1调整量=min3,1=1离离 基？基？在作业表上以在作业表上以（A A2 2 , B , B4 4）为起点作一条除该空为起点作一条除该空格外其余顶点均为有

25、数字格组成的闭回路格外其余顶点均为有数字格组成的闭回路 在这条闭回路上，在保持产销平衡的条件下对在这条闭回路上，在保持产销平衡的条件下对偶数偶数顶点格子的运量做最大可能的调整顶点格子的运量做最大可能的调整+1- -1第第53页页闭回路法求调整方案闭回路法求调整方案（A A2 2 , B , B4 4）为起点作一条出该空格外为起点作一条出该空格外其余顶点均为有数字各组成的闭回路其余顶点均为有数字各组成的闭回路1B2B3B4B1A2A3A20656394375632调运方案（最小元素法得到）调运方案（最小元素法得到）1调整量=min3,1=1继续用闭回路检验，直到检验数大于等于零第第54页页在作业

26、表上在作业表上从从绝对值最大的负检验数格绝对值最大的负检验数格(k,l)出发出发,即即x xklkl为起始变为起始变量作出量作出闭回路闭回路。2.2.以空格以空格( (k,lk,l) )为第一个奇数顶点，沿闭回路的顺（或逆）时针方为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点向依次对顶点编号编号。3.3.在闭回路上的在闭回路上的所有偶数顶点所有偶数顶点中，找出中，找出运输量最小运输量最小的格子，以该的格子，以该格对应的变量为格对应的变量为离基变量离基变量。4.4.调整量调整量5.5.将该闭回路上将该闭回路上所有奇数顶点所有奇数顶点处的运输量都处的运输量都增加增加 所有偶数顶点所有偶数

27、顶点处的运输量都处的运输量都减去减去ij闭回路法求调整方案闭回路法求调整方案第第55页页位势法位势法 在闭回路方法当中，要判断一个方案是否在闭回路方法当中，要判断一个方案是否最优，需要通过每一个空格来寻找回路，以及根最优，需要通过每一个空格来寻找回路，以及根据闭回路求出每个空格的检验数，当一个运输问据闭回路求出每个空格的检验数，当一个运输问题的产地和销地很多时，用此方法工作量十分繁题的产地和销地很多时，用此方法工作量十分繁重重. 位势法是根据位势法是根据对偶理论对偶理论推导出来的一种推导出来的一种求求解检验数方法解检验数方法.运输方案的调整同前面的闭回路运输方案的调整同前面的闭回路法法.第第5

28、6页页56minjjiijxcZ11min111,2,1,2,0,1,2,1,2,nijijmijjiijxaimxbjnximjn，；位势法求检验数位势法求检验数minjjjiivbuaw11max,1,2, ;1,2,1,2, ;1,2,ijijijuvC imjnu vimjn无约束jivu原问题原问题对偶问题对偶问题第第57页页57记原问题基变量记原问题基变量X XB B的下标集合为的下标集合为I I，有如下式子成立：，有如下式子成立：( , )( . )ijiji jijijuvCi jICuvi jI（解上面第一个方程，将解上面第一个方程，将u ui i、v vj j代入第二个方程

29、代入第二个方程求出检验数求出检验数, ,称称u ui i(i(i=1,=1, ,m),m),v vj j(j(j=1,=1,n),n)分别成为第分别成为第i i行和第行和第j j列的列的位势位势1ijijBijcC B PTijijcY P)(jiijvuc回忆：这里回忆：这里Pij 有如何特有如何特殊形式殊形式?位势法求检验数位势法求检验数uiu1u2u32123131434321231054uvuvuvuvuvuv1B2B3B4B1A2A3A102353467819131034113产量产量销地销地产地产地1B2B3B4B1A2A3A注意：由于这些位势的数值是相互关联的，所以填写时可注意：

30、由于这些位势的数值是相互关联的，所以填写时可以先任意决定其中的一个，然后推导出其他位势的数值。以先任意决定其中的一个，然后推导出其他位势的数值。(, )(. )ijijijijiju vCi jICu vijI （A2A3A1B4B3B2B1销地销地产地产地检检验验数数表表121-11012uiu1u2u31B2B3B4B1A2A3A102353467819131034113产量产量销地销地产地产地1B2B3B4B1A2A3A(, )(. )ijijijijiju v Ci j ICu vij I （表表上上作作业业法法得到最优方案得到最优方案算出的总运价算出的总运价分析实际问题分析实际问题列

31、出产销平衡表列出产销平衡表及单位运价表及单位运价表求检验数求检验数（闭回路法或位势法闭回路法或位势法） 是是确定初始调运方案确定初始调运方案（最小元素法最小元素法或或Vogel法法） 找出绝对值最大的负找出绝对值最大的负的检验数用的检验数用闭回路闭回路调整调整，得出新的调运方案，得出新的调运方案否否循循环环所有检验数所有检验数0 0求求解解步步骤骤第第61页页第三章第三章 运输问题运输问题特殊的线性规划特殊的线性规划 产销不平衡运输问题产销不平衡运输问题第第62页页第三章第三章 运输问题运输问题特殊的线性规划特殊的线性规划 产销不平衡运输问题产销不平衡运输问题第第63页页产销不平衡运输问题产销

32、不平衡运输问题1 1 产产 销销2 2 销销 产产3.3.扩大的运输问题（中转站）扩大的运输问题（中转站）第第64页页Min z= cij xijni=1j=1mm)1,2,.,(i 1ainjijxn) 1,.,j ; m ., 1,(i 0n) ,., 1,2(j 1xijjmiijbxMin z= cijxij+ + 0 0 x xi i, ,n+1n+1ni=1 j=1mm)1,2,.,(i 11ainjijx1)nn, 1,.,j ; m ., 1,(i 01)nn, ,., 1,2(j 1xijjmiijbxi=1i=1m m相当于：增加一个相当于：增加一个假想销地假想销地产产 销

33、销问题问题 a ai i b bj j第第65页页产地产地销地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 销量销量产量产量b1b2bna1 a2 amaibj相当于：增加一个相当于：增加一个假想销地假想销地产产 销销问题单位运价表问题单位运价表第第66页页Min z= cij xijni=1j=1mm)1,2,.,(i 1ainjijxn) 1,.,j ; m ., 1,(i 0n) ,., 1,2(j 1xijjmiijbxMin z= cijxij + + 0 0 x xm+1m+1, ,j jni=1 j=1m1)mm,1,2,.,

34、(i 1ainjijxn) 1,.,j ; 1mm, ., 1,(i 0n) ,., 1,2(j 11xijjmiijbxj=1j=1n n销销 产产问题问题相当于：增加一个相当于：增加一个假想产地假想产地 a ai i 销销第第70页页数学模型：数学模型：季季度度生产能力生产能力( (台台) )单位成本单位成本( (万元万元/ /台台) )252535353030101010.810.811.111.111.011.011.311.3 每台每积压一个季度需要存储维每台每积压一个季度需要存储维护费用护费用0.15万元。万元。单位运价表：单位运价表：销量销量 D 产量产量10.810.95 11

35、.10 11.25 0 25 M 11.10 11.25 11.40 0 35 M M11.00 11.15 0 30单位：万元单位：万元供应供应需求需求10 15 25 20 30MM M 11.30 0 10当当ij时，必须时，必须xij=0，令，令cij=M(很大的正数很大的正数)，加以惩罚，加以惩罚产产销销第第71页页 例二例二 有有A A、B B、C C三个化肥厂供应四个地区三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为的农用化肥，三个工厂每年各自的产量为A-50A-50万吨，万吨，B-B-60-60万吨，万吨，C-50C-50万吨。四个地区的需求量分别是万吨。四个地区

36、的需求量分别是地区最地区最高高5050万吨，最低万吨，最低3030万吨，万吨，地区为地区为7070万吨，万吨，地区为地区为3030万万吨以下，吨以下，地区不低于地区不低于1010万吨。问：如何调运，可使总的万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。调运费用最小？单位调运费用如下表所示。产地产地销地销地A1A1A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4 产量产量销量销量16 13 22 17 16 13 22 17 14 13 19 15 14 13 19 15 19 20 23 19 20 23 单位运价表单位运价表50 50 60 60 505030

37、-50 70 0-30 10-30-50 70 0-30 10-单位：万元单位：万元/ /万吨万吨设设 x xijij-第第i i工厂工厂调至第调至第j j需求地区需求地区的化肥数量的化肥数量运输问题案例运输问题案例2 2销销 产产上限上限50第第72页页运输问题案例运输问题案例2 2A B C D 161613221717 14141319151519192023 M MM0M0M0供应供应需求需求产量产量销销 量量50 50 60 60 50 50 5050 303020207070303010105050修正运价表修正运价表产地产地销地销地A1A1A2A2A3A3B1 B2 B3 B4B

38、1 B2 B3 B4 产量产量销量销量16 13 22 17 16 13 22 17 14 13 19 15 14 13 19 15 19 20 23 19 20 23 单位运价表单位运价表50 50 60 60 505030-50 70 0-30 10-30-50 70 0-30 10-单位：万元单位：万元/ /万吨万吨设设 x xijij-第第i i工厂工厂调至第调至第j j需求地区需求地区的化肥数量的化肥数量销销 产产第第73页页扩大的运输问题扩大的运输问题例：在前面的糖果例题中，若既例：在前面的糖果例题中，若既可以从可以从AiAi运到运到BjBj，也也可以经过可以经过中间站中间站T1T

39、1、T2T2、T3T3、T4T4或者或者AiAi、BjBj转运转运，称扩大的运输问题。，称扩大的运输问题。几点说明：几点说明：1.1.所有的产地、销地、中间站均视作产地、销地；所有的产地、销地、中间站均视作产地、销地；2.2.所有中转站的转运量等于总的产量之和；所有中转站的转运量等于总的产量之和；3.3.不能出现循环倒运现象，允许自身往自身最多调运一次，不能出现循环倒运现象，允许自身往自身最多调运一次，运价为运价为C Cijij=0=0；4.4.实际产地产量为转运量与该产地实际产量之和，实际销地实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。销量为转运量与实际销

40、量之和。A1 A2 A3A1 A2 A3T1 T2 T3 T4T1 T2 T3 T4 B1 B2 B3 B4B1 B2 B3 B4A1 A1 A2 A2 A3A3T1 T1 T2 T2 T3 T3 T4T4B1 B1 B2 B2 B3 B3 B4B40 1 3 0 1 3 1 0 - 1 0 - 3 - 03 - 02 1 4 3 2 1 4 3 3 5 - 2 3 5 - 2 1 - 2 31 - 2 33 11 3 10 3 11 3 10 1 9 2 8 1 9 2 8 7 4 10 57 4 10 52 3 1 2 3 1 1 5 - 1 5 - 4 - 2 4 - 2 3 2 33

41、2 33 1 7 3 1 7 11 9 4 11 9 4 3 2 10 3 2 10 1010 8 5 8 50 1 3 2 0 1 3 2 1 0 1 1 1 0 1 1 3 1 0 2 3 1 0 2 2 1 2 0 2 1 2 0 2 8 4 6 2 8 4 6 4 5 2 7 4 5 2 7 1 8 2 4 1 8 2 4 1 - 2 6 1 - 2 6 2 4 1 1 2 4 1 1 8 5 8 - 8 5 8 - 4 2 2 2 4 2 2 2 6 7 4 66 7 4 60 1 4 2 0 1 4 2 1 0 2 1 1 0 2 1 4 2 0 3 4 2 0 3 2 1 3 0

42、2 1 3 0产产销销产量产量销量销量27 27 24 24 292920 20 2020 2020 202020 20 2020 2020 202020 20 2020 202020 20 2020 2020 2020 23 26 25 2623 26 25 26产销平衡表产销平衡表第第75页页 某餐馆承办宴会，每晚连续举行，共举行五次。某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天晚的需要量为：第一天10001000条，第二天条，第二天700700条，第三条，第三天天800800条，第四天条，第四天12001200条，第五天条，第五天15001500条，五天之后，条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要条新餐巾需要1 1元的费用，送洗时可选择两种方式：元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为快洗仅需要一天时间，每条洗涤费用为0.20.2元，慢洗元，慢洗需要两天时间，每条洗涤费用需要两天时间，每条洗涤费用0.10.1元。问：如何安排，元。问：如何安排，可