法学运输问题PPT学习教案

1、会计学1 法学运输问题法学运输问题 第1页/共91页 第2页/共91页 第3页/共91页 第4页/共91页 第5页/共91页 第6页/共91页 第7页/共91页 第8页/共91页 第9页/共91页 第10页/共91页 第11页/共91页 第12页/共91页 第13页/共91页 第14页/共91页 第15页/共91页 第16页/共91页 第17页/共91页 销地销地 产地产地 B1B2Bn产量产量 A1c11c12c1na1 A2c21c22c2na2 Amcm1cm2cmnam 销量销量b1b2bn 根据所给的数据可以列如下的运输表根据所给的数据可以列如下的运输表 第18页/共91页 设从产地

2、设从产地Ai，运往销地，运往销地Bj的运量为的运量为Xij，则运输问题的数学模型如下：，则运输问题的数学模型如下： 产地约束条件产地约束条件 ji ijij xcZ , min miax n j iij 1 1 销地约束条件销地约束条件 njbx m i jij 1 1 非负约束非负约束 njmixij110 第19页/共91页 ji ijij xcZ , min njmix njbx miax ts ij m i jij n j iij 1,1, 0 1 1 . . 1 1 即即 第20页/共91页 二、产量平衡的运输问题的模型二、产量平衡的运输问题的模型 第21页/共91页 ji ijij

3、 xcZ , min njmix njbx miax ts ij m i jij n j iij 1,1, 0 1 1 . . 1 1 n j j m i i ba 11 产销平衡的运输问题产销平衡的运输问题 第22页/共91页 运输问题是一种特殊的线性规划问题，其约束方程系数矩阵结构如下运输问题是一种特殊的线性规划问题，其约束方程系数矩阵结构如下 111 111 111 111 111 111 行 行 n m mnmmnn xxxxxxxxx 212222111211 n j iij ax 1 m i jij bx 1 第23页/共91页 该矩阵的元素全部是该矩阵的元素全部是0或或1。每一列

4、只有两个元素为。每一列只有两个元素为1，其余为，其余为0。若用。若用Pij表示表示xij的系数列向量，则在的系数列向量，则在Pij中第中第i个和第个和第m+j个元素为个元素为1，其余为，其余为0。即。即 行 行 jm i pij 0 1 0 1 0 行iei 0 0 1 0 0 jmiij eep 第24页/共91页 1 1 1111 1 1 1 1 行 行 n m 1312111211mn xxxxxx A 的增广矩阵的前的增广矩阵的前m个行向量之和减去后个行向量之和减去后n个行向量之和为零向量，但可取如下的一个不等于零的个行向量之和为零向量，但可取如下的一个不等于零的m+n-1阶子式，故阶

5、子式，故A 的增广矩阵的秩等于的增广矩阵的秩等于m+n-1 第25页/共91页 第二节第二节 表上作业法表上作业法 表上作业法是求解运输问题的一种简便而有效的方法，其求解工作是在运输表上进行的。表上作业法是求解运输问题的一种简便而有效的方法，其求解工作是在运输表上进行的。 运输问题也是一个线性规划问题，当用单纯形法进行求解时，我们首先应当知道它的基变量的个数；其次，要知道这样一组基变量应当是由哪些变量来组成。由运输问题系数矩阵的形式并结合第一章单纯形算法的讨论可以知道：运输问题的每一组基变量应由运输问题也是一个线性规划问题，当用单纯形法进行求解时，我们首先应当知道它的基变量的个数；其次，要知道

6、这样一组基变量应当是由哪些变量来组成。由运输问题系数矩阵的形式并结合第一章单纯形算法的讨论可以知道：运输问题的每一组基变量应由 m+n-1个变量组成个变量组成 (即基变量的个数即基变量的个数 = 产地个数产地个数 + 销售地个数销售地个数 1) 。 第26页/共91页 进一步我们想知道进一步我们想知道, 怎样的怎样的 m+n-1个变量会构个变量会构 成一组基变量？计算步骤：成一组基变量？计算步骤： （1）找出初始基可行解，即在）找出初始基可行解，即在 (mn) 产销平衡表产销平衡表 上给出上给出m+n-1个有数字的格，其相应的调运量就是个有数字的格，其相应的调运量就是 基变量，格子中所填写的值

7、即为基变量的值。这些基变量，格子中所填写的值即为基变量的值。这些 有数字的格不能构成闭回路，且行和等于产量，列有数字的格不能构成闭回路，且行和等于产量，列 和等于销售量；和等于销售量； （2）求各非基变量的检验数，即在表上求空格的）求各非基变量的检验数，即在表上求空格的 检验数，判别是否达到最优解。如果达到最优解，检验数，判别是否达到最优解。如果达到最优解， 则停止计算，否则转入下一步；则停止计算，否则转入下一步； （3）确定换入变量和换出变量，找出新的基可行）确定换入变量和换出变量，找出新的基可行 解，在表上用闭回路法进行调整。解，在表上用闭回路法进行调整。 （4）重复（）重复（2）、（）、

8、（3）步，直到求得最优解为）步，直到求得最优解为 止。止。 以下我们就具体给出求解运输问题表上作业法以下我们就具体给出求解运输问题表上作业法 。 第27页/共91页 一、求初始基可行解的方法一、求初始基可行解的方法 1、最小元素法、最小元素法 这种方法的基本思想就是就近供应，在单位运价表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。这种方法的基本思想就是就近供应，在单位运价表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。 逐次寻找最小元素，直至分配完毕逐次寻找最小元素，直至分配完毕 注意：如填写一个数字同时满足了一

9、厂一商，则需在同行或同列中填写一个数字注意：如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字0，以保证恰好有，以保证恰好有m+n-1个数字。个数字。 下面结合例子给出最小元素法的具体步骤下面结合例子给出最小元素法的具体步骤 第28页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 24 0 3 第29页/共91页 最小元素法是以就近供应为原则，确定初始最小元素法是以就近供应为原则，确定初始 基可行解，。这可造成整体的不合理。因为可能基可行解，。这可造成整体的不合理。因为可能 有这样的情况，某单位运

10、价在整个单位运价表中有这样的情况，某单位运价在整个单位运价表中 可能不是最低，但他在所在的行或所在的列中是可能不是最低，但他在所在的行或所在的列中是 最低的，而同行或同列中的次最低运价与其相差最低的，而同行或同列中的次最低运价与其相差 很大，对这行或列而言，如果不按这行或列最低很大，对这行或列而言，如果不按这行或列最低 运价安排运输，而采用次最低运价安排运输，则运价安排运输，而采用次最低运价安排运输，则 总运费增加很多。因此应优先考虑行或列次最低总运费增加很多。因此应优先考虑行或列次最低 运价与最低运价的差最大行或列，取其最低运价运价与最低运价的差最大行或列，取其最低运价 安排运输。这就是安排

11、运输。这就是 第30页/共91页 次最低运价与最低运价的差，次最低运价与最低运价的差，最低运价最低运价 第31页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 2 1 0 1 2121 第32页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 3 2 1 1 1 121 第33页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 3 2 3 1 1 2 11 第34页/

12、共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 3 21 3 1 1 11 第35页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 21 3 3 第36页/共91页 第37页/共91页 二、最优性检验二、最优性检验 检验解的最优性的方法有两种，闭回路法和位势法。检验解的最优性的方法有两种，闭回路法和位势法。 1、闭回路法、闭回路法 闭回路法闭回路法是通过寻找闭回路来找到非基变量的检验数。是通过寻找闭回路来找到非基变量的检验数。 可以证明

13、，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。 第38页/共91页 如果规定作为起始顶点的非基变量为第一个顶点，闭回路的其他顶点依次为第二个顶点、第三个顶点如果规定作为起始顶点的非基变量为第一个顶点，闭回路的其他顶点依次为第二个顶点、第三个顶点，那么就有，那么就有 检验数检验数=奇数点单位运费之和偶数点单位运费之和奇数点单位运费之和偶数点单位运费之和 若所有非基变量检验数若所有非基变量检验数0，则最优。，则最优。 现结合上例中

14、最小元素法给出的初始基可行解说明闭回路法。现结合上例中最小元素法给出的初始基可行解说明闭回路法。 第39页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 24 03 x11检验数为检验数为 6-4+8-6+4-4=4 第40页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 24 03 x12检验数为检验数为 5-4+8-6=3 第41页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 6

15、5 44 7658 75 43 31 24 03 x23检验数为检验数为 7-3+4-8+6-4=2 第42页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 24 03 x24检验数为检验数为 5-8+6-4=-1 第43页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 21 3 3 x11检验数为检验数为 6-4+5-4=3 第44页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 6

16、5 44 7658 75 43 31 21 3 3 x12检验数为检验数为 5-4+5-4=2 第45页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 21 3 3 x23检验数为检验数为 7-3+4-5=3 第46页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 21 3 3 x31检验数为检验数为 7-4+4-5=1 第47页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 4

17、4 7658 75 43 31 21 3 3 x33检验数为检验数为 5-3+4-5+4-6=-1 第48页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 x11检验数为检验数为 6-4+5-4=3 第49页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 x12检验数为检验数为 5-4+5-4=2 第50页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65

18、 44 7658 75 43 04 24 3 0 x23检验数为检验数为 7-3+4-5=3 第51页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 x31检验数为检验数为 7-4+5-4+3-5=2 第52页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 x33检验数为检验数为 6-5+3-4+5-4=1 第53页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量2434

19、13 65 44 7658 75 43 04 24 3 0 x34检验数为检验数为 8-5+3-4=2 第54页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 此解为最优解，最低运费为此解为最优解，最低运费为55（元）（元） 第55页/共91页 2、位势法、位势法 当运输问题变量的格数较多时，用闭回路法计算检验数比较麻烦，而位势法比较简便。当运输问题变量的格数较多时，用闭回路法计算检验数比较麻烦，而位势法比较简便。 对于运输问题对于运输问题 minf=CX AX=b X0 设设B为其一个可行基，则

20、为其一个可行基，则xij的的检验数为检验数为 ijij=C=CB BB B-1-1P Pijij-C-Cijij 第56页/共91页 对于运输问题的对偶问题对于运输问题的对偶问题 maxf=Yb YA C Y无限制无限制 其中，其中，Y =(u1, um,v1, ,vn)为为对偶变量，根据对偶理论有对偶变量，根据对偶理论有Y=C CB BB B-1-1, ,因此有因此有 ijij=YP=YPijij-C-Cijij 又因为又因为P Pijij的第个的第个i元素和第个元素和第个m+j元素为元素为1 1，其它元素为，其它元素为0 0，所以有，所以有 ijij=(u1, um,v1, ,vn)P P

21、ijij-C-Cijij =u =ui i+v+vj j-c-cijij 第57页/共91页 因为所有基变量的检验数为因为所有基变量的检验数为0 0，因此有，因此有 ijij = u = ui i+v+vj j-c-cijij=0=0 即即u ui i+v+vj j=c=cijij 由此可得含有由此可得含有m+ +n-1-1个方程的方程组，其中含有个方程的方程组，其中含有m+ +n个未知量，可令某一个变量等于零，解得方程组的解，然后可根据个未知量，可令某一个变量等于零，解得方程组的解，然后可根据 ijij = u = ui i+v+vj j-c-cijij 计算非基变量的检验数。这种计算检验数

22、的方法称为计算非基变量的检验数。这种计算检验数的方法称为位势法。下面以上面利用伏格尔法求得的初始基可行解为例说明位势法。位势法。下面以上面利用伏格尔法求得的初始基可行解为例说明位势法。 第58页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 31 21 3 3 u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6 第59页/共91页 u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v2=6 令令u1=0 由由 u1+v

23、3=3 得得 v3=3 由由 u1+v4=4 得得 v4=4 由由 u2+v4=5 得得 u2=1 由由 u2+v1=4 得得 v1=3 由由 u2+v2=4 得得 v2=3 由由 u3+v2=6 得得 u3=3 11=u1+v1-c11=0+3-6=-3, 12=u1+v2-c12=0+3-5=-2 23=u2+v3-c23=1+3-7=-4, 31=u3+v1-c31=3+3-7=-1 33=u3+v3-c33=3+3-5=1, 34=u3+v4-c34=3+4-8=-1 第60页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 765

24、8 75 43 31 21 3 3 11=-3, 12=-2,23=-4, 31=-1,33=1, 34=-1 第61页/共91页 销地 产地B1B2B3B4产量 A1 4 A2 6 A3 3 销量243413 65 44 7658 75 43 04 24 3 0 第62页/共91页 u1+v3=3, u1+v4=4, u2+v1=4, u2+v2=4, u2+v4=5, u3+v3=5 令令u1=0 由由 u1+v3=3 得得 v3=3 由由 u1+v4=4 得得 v4=4 由由 u2+v4=5 得得 u2=1 由由 u2+v1=4 得得 v1=3 由由 u2+v2=4 得得 v2=3 由由

25、 u3+v3=5 得得 u3=2 11=u1+v1-c11=0+3-6=-3, 12=u1+v2-c12=0+3-5=-2 23=u2+v3-c23=1+3-7=-4, 31=u3+v1-c31=2+3-7=-5 32=u3+v2-c32=2+3-6=-1, 34=u3+v4-c34=2+4-8=-2 第63页/共91页 三、求出新的基可行解三、求出新的基可行解 如果某如果某ij 0, ,当前的解不是最优解当前的解不是最优解, ,还需要调整还需要调整 运量。运量。调整运量的步骤：调整运量的步骤： 寻找以寻找以xij为第一个顶点其它顶点为基变量的闭为第一个顶点其它顶点为基变量的闭 回路；回路；

26、取闭回路上的偶数次顶点的最小运量记为取闭回路上的偶数次顶点的最小运量记为； 闭回路上的奇数次顶点（包括起始变量）的运闭回路上的奇数次顶点（包括起始变量）的运 量加上量加上；闭回路上的偶数次顶点的运量减去；闭回路上的偶数次顶点的运量减去 ；非闭回路顶点的其他变量调运量不变；非闭回路顶点的其他变量调运量不变； 奇数点上被修改为奇数点上被修改为0的变量为出基变量，在新的变量为出基变量，在新 的方案中不再标出其值。但若有两个为零的变量的方案中不再标出其值。但若有两个为零的变量 ，则只取其一作为出基变量。，则只取其一作为出基变量。 第64页/共91页 求解运输问题的表上作业法只适用产销平衡的运输问题。产

27、销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。求解运输问题的表上作业法只适用产销平衡的运输问题。产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。 解决的办法是：增加一个虚拟的产地或销地，从而变成产销平衡的运输问题。解决的办法是：增加一个虚拟的产地或销地，从而变成产销平衡的运输问题。 第65页/共91页 销地 产地B1B2B3B4产量 A140 A2 60 A350 销量25204045 56 94 10753 85 49 这是一个产大于销的不平衡运输问题。可以虚设一个销地这是一个产大于销的不平衡运输问题。可以虚设一个销地B5,其销量取其销量取20，此

28、问题转化为如下的产销平衡的运输问题，而后求解。，此问题转化为如下的产销平衡的运输问题，而后求解。 第66页/共91页 销地 产地B1B2B3B4B5产量 A140 A2 60 A350 销量2520404520 56 94 10753 85 49 销地 产地B1B2B3B4B5产量 A140 A2 60 A350 销量2520404520 3 5 4 销地 产地B1B2B3B4B5产量 A140 A2 60 A350 销量2520404520 3 5 4 销地 产地B1B2B3B4B5产量 A140 A2 60 A350 销量2520404520 40 0 0 第67页/共91页 销地 产地B

29、1B2B3B4B5产量 A110 A2 9 A310 销量46958 1013 812 6983 105 411 3 5 4 11 15 4 97 9 14 这是一个销大于产的不平衡运输问题。可以虚设一个产地这是一个销大于产的不平衡运输问题。可以虚设一个产地A4,其产量取其产量取3，此问题转化为如下的产销平衡的运输问题，而后求解。，此问题转化为如下的产销平衡的运输问题，而后求解。 第68页/共91页 销地 产地B1B2B3B4B5产量 A110 A2 9 A310 A43 销量46958 1013 812 6983 105 411 3 5 4 11 15 4 97 9 14 00000 第69

30、页/共91页 例：弹性需求问题例：弹性需求问题 设有三煤矿供应四地区，资料如下：设有三煤矿供应四地区，资料如下： 10 不不 限限 0 30 70 70 30 50 最低需求最低需求 最高需求最高需求 50 60 50 17 15 25 22 19 23 13 13 20 16 14 19 A B C 产产 量量 丁丁丙丙乙乙甲甲 运价运价 地区地区 煤矿煤矿 第70页/共91页 解题思路：解题思路： (1)设法转化为产销平衡的运输问题的标准型设法转化为产销平衡的运输问题的标准型 (2)本题产量本题产量160万吨，最低需求万吨，最低需求110万吨，最高万吨，最高 需求无限。实质上比较现实的最高

31、需求需求无限。实质上比较现实的最高需求210万万 吨（产量吨（产量160万吨减去甲乙丙的最低需求万吨减去甲乙丙的最低需求100 万吨为万吨为60万吨，即最多可以给丁万吨，即最多可以给丁60万吨，）万吨，） 。 (3)产量大于最小需求；小于最大需求。而标准产量大于最小需求；小于最大需求。而标准 型是：产量型是：产量=销量。销量。 (4)处理办法：设想一个虚拟煤矿处理办法：设想一个虚拟煤矿D，生产，生产50万吨万吨 ，但这个产量只能供应可有可无的最高需求，但这个产量只能供应可有可无的最高需求 部分，于是各地的需求也应分为两个部分：部分，于是各地的需求也应分为两个部分： 基本需求、机动需求基本需求、

32、机动需求 (5)虚拟产量的运输费用为零，但它对于基本需虚拟产量的运输费用为零，但它对于基本需 求来讲，运费为无穷大。求来讲，运费为无穷大。 第71页/共91页 产量产量 丁丁 2 丁丁 1 丙丙乙乙甲甲 2 甲甲1 运价运价 地区地区 煤矿煤矿 210 210 501030702030需求量需求量 50 60 50 50 17 12 25 0 17 12 25 M 22 19 23 0 13 13 20 M 16 14 19 0 16 14 19 M A B C D 第72页/共91页 210 210 501030702030 需求量需求量 50 60 50 50 30 20 10 30 50

33、 20 02030 A B C D 产量产量 丁丁 2 丁丁1丙丙乙乙甲甲2甲甲1 运价运价 地地 区区 煤矿煤矿 求得最优解见下表：求得最优解见下表： 第73页/共91页 例：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费例：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元万元/台季，三、四季度可以加班生产，加班生产能力台季，三、四季度可以加班生产，加班生产能力8台台/季，加班费用季，加班费用3万元万元/台台 季度季度 正常生产能力正常生产能力单位成本（万元）单位成本（万元）交货台数交货台数 1 2 3 4 30

34、32 20 28 10.55 10.8 11 11.1 25 30 15 45 第74页/共91页 分析：分析： 可用线性规划，但用运输问题更简单可用线性规划，但用运输问题更简单 要决策的问题是各季度生产量和交货量设要决策的问题是各季度生产量和交货量设xij表示第表示第i季度生产第季度生产第j季度交货的台数季度交货的台数 因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度 需求量合计需求量合计115台，生产能力合计台，生产能力合计126台，供需不平衡，因此，增加一项闲置能力。台，供需不平衡，因此，增加一项

35、闲置能力。 第75页/共91页 126 126 25 30 15 45 11 需求量需求量 30 32 20 8 28 8 10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 0 1季度正常生季度正常生 产产 2季度正常生季度正常生 产产 3季度正常生季度正常生 产产 3季度加班生季度加班生 产产 4季度正常生季度正常生 产产 4季度加班生季度加班生 产产 产产 量量 闲闲 置置 1 2 3 4 能能 力力 成本成本 交交 货货 生产生产 建模建

36、模 第76页/共91页 126 126 25 30 15 45 11 需求量需求量 30 32 20 8 28 8 25 5 30 2 10 10 8 28 5 3 1季度正常生产季度正常生产 2季度正常生产季度正常生产 3季度正常生产季度正常生产 3季度加班生产季度加班生产 4季度正常生产季度正常生产 4季度加班生产季度加班生产 产产 量量 闲闲 置置 1 2 3 4 能能 力力 生产生产 交交 货货 生产生产 结果结果 第77页/共91页 例：例： 航运调度问题航运调度问题 某航运公司承担六个城市某航运公司承担六个城市A、B、C、D、E、F之间的四条航线，已知各航线的起点、终点及每天所需的

37、航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？ 航线航线 起点起点 终点终点 每天航班数每天航班数 1 2 3 4 E B A D D C F B 3 2 1 1 第78页/共91页 城市之间航行天数表城市之间航行天数表 Cij A B C D E F A B C D E F 0 1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 5 14 1

38、3 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 第79页/共91页 问题分析：问题分析： 问题要求的是在保证需要的前提下，至少需要多少船只。问题要求的是在保证需要的前提下，至少需要多少船只。 所需船只包括两个部分：载货船、空驶船所需船只包括两个部分：载货船、空驶船 。 航线航线航行航行 天数天数 装卸装卸 天数天数 合计合计航班航班 数数 载货载货 船数船数 1 2 3 4 17 3 7 13 2 2 2 2 19 5 9 15 3 2 1 1 57 10 9 15 第80页/共91页 问题分析（续问题分析（续1） 上表显示：载货船共需上表显示：载货船共需91条，

39、此船何来？条，此船何来？ -1 -1 2 2 -3 1 1 2 0 1 3 0 0 1 2 3 0 1 A B C D E F 余 缺 开 出 到 达 港 口 AB DE F 1 2 1 3 若无空驶，则若无空驶，则91条船刚好够条船刚好够 用，但虚线箭头都是空驶用，但虚线箭头都是空驶 C 第81页/共91页 问题分析（续问题分析（续2） 所需所需91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从E到到D后再起程赴后再起程赴B）。若港口没有空船，则要从其它港口调度而来。（规模效益）。若港口没有空船，则要从其它港口调度而来。（规模效益） 由上表可知：由上表可知：C、D、F港口有多余船只可供调出，而港口有多余船只可供调出，而A、B、E