第八章-运输问题课件.ppt

《第八章-运输问题课件.ppt》由会员分享，可在线阅读，更多相关《第八章-运输问题课件.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、运输问题模型及其求解思路一、运输问题模型及其求解思路v1、问题的提出：、问题的提出：v某公司从两个产地某公司从两个产地A1、A2将物品运往三将物品运往三个销地个销地B1、B2、B3。v各产地的产量、各销地的销量和各产地各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示。运往各销地每件物品的运费如下表所示。v问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？一、运输问题模型及其求解思路一、运输问题模型及其求解思路B1B2B3产量产量A1646200A2655300销量销量150150200运价表运价表销量和产量和销量和产量和产销平衡产销平衡一、运输问题模型

2、及其求解思路一、运输问题模型及其求解思路B1B2B3产量产量A1x11x12x13200A2x21x22x23300销量销量150150200v为建立模型，设为建立模型，设 xij 为从产地为从产地Ai运往销地运往销地Bj的的运输量，得到下表：运输量，得到下表：运量表运量表一、运输问题模型及其求解思路v据题意，可建立线性规划模型：据题意，可建立线性规划模型：vMin f=6x11+4x12+6x13+6x21+5x22+5x23vs.t.x11+x12+x13=200v x21+x22+x23=300v x11+x21=150v x12+x22=150v x13+x23=200v xij0(i

3、=1,2；j=1,2,3）一、运输问题模型及其求解思路一、运输问题模型及其求解思路v2、产销平衡运输问题模型的特点、产销平衡运输问题模型的特点v从模型的建立可知：从模型的建立可知：v列数为列数为2（产地数）（产地数）3（销地数）（销地数）6；v行数为行数为2（产地数）（产地数）+3（销地数）（销地数）5；v再观察模型的系数矩阵：再观察模型的系数矩阵：一、运输问题模型及其求解思路一、运输问题模型及其求解思路 1 1 1 0 0 0 200 0 0 0 1 1 1 300 1 0 0 1 0 0 150 0 1 0 0 1 0 150 0 0 1 0 0 1 200前前2行之和后行之和后3行之和行

4、之和一、运输问题模型及其求解思路一、运输问题模型及其求解思路v对于产销平衡的运输问题，若产地为对于产销平衡的运输问题，若产地为m个，销地为个，销地为n个，个，v则变量个数为则变量个数为mn个，线性无关的约束个，线性无关的约束条件个数为条件个数为m+n-1，v故基本解中的基变量个数为故基本解中的基变量个数为m+n-1。一、运输问题模型及其求解思路一、运输问题模型及其求解思路v3、运输问题求解思路、运输问题求解思路表上作业法表上作业法v由于运输规划系数矩阵的特殊性，如果由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。则无

5、法利用这些有利条件。v人们在分析运输规划系数矩阵特征的基人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的础上建立了针对运输问题的表上作业法表上作业法。一、运输问题模型及其求解思路一、运输问题模型及其求解思路B1B2B3产量产量A1 6 x11 4 x12 6 x13200A2 6 x21 5 x22 5 x23300销量销量150150200v我们关心的量均在运价表和运量表中，我们关心的量均在运价表和运量表中，故将两表和为故将两表和为作业表作业表：一、运输问题模型及其求解思路一、运输问题模型及其求解思路v表上作业法的总体思路和单纯形法类似：表上作业法的总体思路和单纯形法类似：基本可行

6、解基本可行解是否最优解是否最优解结束结束换基换基是是否否每个步骤每个步骤都充分利都充分利用运输表用运输表的特点的特点一、运输问题模型及其求解思路一、运输问题模型及其求解思路v例：某食品公司下属的例：某食品公司下属的A1、A2、A3，3个厂个厂生产方便食品，要运输到生产方便食品，要运输到B1、B2、B3、B4，4个销售点，数据如下表，求最优运输方案。个销售点，数据如下表，求最优运输方案。B1B2B3B4产量产量A13113107A219284A3741059销量销量365620二、确定初始基本可行解二、确定初始基本可行解v1、西北（左上）角法、西北（左上）角法v每次找最西北角的元素，让其运输量尽

7、每次找最西北角的元素，让其运输量尽可能的满足一个约束条件。可能的满足一个约束条件。二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113107A219284A3741059销量销量365620342236二、确定初始基本可行解二、确定初始基本可行解这样得到的初始基本可行解为：这样得到的初始基本可行解为：x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其，其余均为余均为0。对应的总运费为：对应的总运费为：33+411+29+22+310+65135二、确定初始基本可行解二、确定初始基本可行解v2、最小元素法、最小元素法v每次找到剩下的最小运价，让

8、其对应的每次找到剩下的最小运价，让其对应的运输量尽可能的满足一个约束条件。运输量尽可能的满足一个约束条件。二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113107A219284A3741059销量销量365620343163二、确定初始基本可行解二、确定初始基本可行解用最小元素法求出的初始基本可行解为：用最小元素法求出的初始基本可行解为：x21=3,x22=1,x13=4,x32=6,x34=3,x14=3,其余均为其余均为0。对应的总运费为：对应的总运费为：31+12+43+64+35+31086二、确定初始基本可行解二、确定初始基本可行解v为保证基变量的个数有

9、为保证基变量的个数有m+n-1个，注意：个，注意：v1、每次填完数，只能划去一行或一列，只有每次填完数，只能划去一行或一列，只有最后一个格子例外。最后一个格子例外。v2、用最小元素法时，可能会出现基变量个数用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩此时不能将剩下行或列按空格划掉，应在剩下的空格中标上下的空格中标上0。（退化的基本可行解）。（退化的基本可行解）二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113108A219283A3741059销量销量3656

10、20353063二、确定初始基本可行解二、确定初始基本可行解B1B2B3B4产量产量A13113104A219284A3741059销量销量365317340163三、最优性检验三、最优性检验v检验数的意义：非基变量增加一个单位，检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。使目标函数值增加的数量。v运输问题中目标函数值要求最小化，因运输问题中目标函数值要求最小化，因此，当所有的检验数都大于或等于零时此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则不是。该调运方案就是最优方案；否则不是。v下面介绍两种计算检验数的方法：下面介绍两种计算检验数的方法：三、最优性检验三、

11、最优性检验v1、闭回路法、闭回路法v闭回路：在已给出基本解的运输表上，从一闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转只有碰到基变量，才能向右或向左转90o(当当然也可以不改变方向）继续前进。然也可以不改变方向）继续前进。v这样继续下去，总能回到出发的那个非基变这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。量，由此路线形成的封闭曲线，叫闭回路。三、最优性检验三、最优性检验v每一个非基变量都有唯一的闭回路每一个非基变量都有唯一的闭回路B1B2B3B4产量产量A131

12、13 410 37A21 392 184A374 6105 39销量销量365620三、最优性检验三、最优性检验v观察观察x24的闭回路：的闭回路：v若让第一个顶点非基变量若让第一个顶点非基变量x24的取值变为的取值变为1，为，为了保持产销平衡，其闭回路上的顶点运量都了保持产销平衡，其闭回路上的顶点运量都要调整，基数顶点要调整，基数顶点+1，偶数顶点，偶数顶点-1。v上述调整使总的运输费用发生的变化为上述调整使总的运输费用发生的变化为 8 10+3 2 -1，这就说明原方案还不是最优，这就说明原方案还不是最优方案，需要进行调整。方案，需要进行调整。三、最优性检验三、最优性检验B1B2B3B4产

13、量产量A13113 410 37A21 392 184A374 6105 39销量销量365620v若让若让x111，则总运费变化：，则总运费变化：33+211。三、最优性检验三、最优性检验v如果规定作为起始顶点的非基变量如果规定作为起始顶点的非基变量xij为第为第 1 个顶点，其闭回路上的其他顶点依次为第个顶点，其闭回路上的其他顶点依次为第 2 个顶点、第个顶点、第 3 个顶点个顶点，那么就有该非基，那么就有该非基变量的检验数：变量的检验数：v ij=(闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和)-(闭回闭回路上的偶数顶点运价之和路上的偶数顶点运价之和)v最优标准：所有检验数最优标

14、准：所有检验数0三、最优性检验三、最优性检验B1B2B3B4产量产量A13 113 410 37A21 39 2 18 4A37 4 610 5 39销量销量365620v检验数计算如下表：检验数计算如下表：（1）（2）（1）（-1）（10）（12）三、最优性检验三、最优性检验v2、位势法、位势法v闭回路法的缺点：当变量个数较多时，寻找闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。闭回路以及计算两方面都容易出错。v位势法：设产地位势法：设产地Ai对应的位势量为对应的位势量为ui，销地，销地Bj对应的位势量为对应的位势量为vj，检验数检验数 ij=cij ui-vj。三、

15、最优性检验三、最优性检验B1B2B3B4产量产量uiA13 11 3 410 37u1A21 39 2 184u2A37 4 6105 39u3销量销量365620vjv1v2v3v4三、最优性检验三、最优性检验v根据基变量根据基变量xij 的检验数的检验数 ij=0，对应基变量，对应基变量的运价的运价cij可以分解为可以分解为ui 和和vj，即，即cij=ui+vj。v因为位势量因为位势量ui,vj的总数为的总数为m+n 个，而限定方个，而限定方程只有程只有m+n-1个（基变量个数），所以位势个（基变量个数），所以位势量（量（ui,vj）有无穷多组解，其中总有一个自）有无穷多组解，其中总有一

16、个自由变量。由变量。v故可以任意取一个位势量赋以定值，从而确故可以任意取一个位势量赋以定值，从而确定其它位势量的值，一般取定其它位势量的值，一般取u1 0。三、最优性检验三、最优性检验10392vj206563销量销量bj-595 310 4 67 A3-148 2 19 1 3A20710 33 411 3 A1ui产量产量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）检验数计算总结检验数计算总结v1、闭回路法计算式：、闭回路法计算式：v ij=(闭回路上的奇数顶点运价之和闭回路上的奇数顶点运价之和)-(闭回闭回路上的偶数顶点运价之和路上的偶数顶点运价之和)v2、位势法计算式

17、：、位势法计算式：v ij=cij-ui vj 四、方案调整四、方案调整B1B2B3B4产量产量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39销量销量365620最小检验数最小检验数原则，确定原则，确定进基变量进基变量最小偶点原则，最小偶点原则，确定出基变量和确定出基变量和调整量调整量+1-1+1-1四、方案调整四、方案调整B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj365620v得到新的基变量：得到新的基变量：x13=5,x14=

18、2,x21=3,x24=1,x32=6,x34=3。重新计算检验数。重新计算检验数。（0）（2）（2）（1）（9）（12）四、方案调整四、方案调整v经过一次基变换，所有经过一次基变换，所有 ij 0，已得到最优解：，已得到最优解：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3，其它为，其它为0。v最优值：最优值：vf*=35+102+13+81+46+53=85四、方案调整四、方案调整闭回路调整法步骤：闭回路调整法步骤：1、入基变量的确定：选负检验数中最小者、入基变量的确定：选负检验数中最小者 rk，那么，那么 xrk 作为进基变量；（使总运费尽作为进基变量；（使总运费

19、尽快减少）快减少）2、出基变量的确定：在进基变量、出基变量的确定：在进基变量xrk 的闭回的闭回路上，选取偶数顶点上调运量最小的值，将路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）基变量出基，其它基变量都为正）四、方案调整四、方案调整即求即求=Minxij 闭回路上的偶数顶点的闭回路上的偶数顶点的xij=xpq。那么确定那么确定xpq为出基变量，为出基变量，为调整量；为调整量；3、换基调整：对闭回路的奇数顶点运量调整、换基调整：对闭回路的奇数顶点运量调整为：为：xij+，对各偶数顶点运量调整为：，

20、对各偶数顶点运量调整为：xij-，特别，特别 xpq-=0，xpq变为非基变量。变为非基变量。重复以上步骤，直到所有检验数均非负，即重复以上步骤，直到所有检验数均非负，即得到最优解。得到最优解。练习题练习题已知如下运价表，用表上作业法求解：已知如下运价表，用表上作业法求解：产销地产销地B1B2B3B4产量产量A165344A244756A376583销量销量243413 初始解对应目标值为初始解对应目标值为33+41+42+44+8361产销地产销地B1B2B3B4产量产量uiA165344A244756A376583销量销量243413vj3421030341334(3)(2)(3)(0)(

21、-1)(-2)产销地产销地B1B2B3B4产量产量uiA165344A244756A376583销量销量243413vj4030240341332(3)(2)(3)(2)(1)(2)已达到最优，最优目标值为已达到最优，最优目标值为44+42+44+5355五、运输问题的几种特殊情况五、运输问题的几种特殊情况v1、多个最优方案的情况：、多个最优方案的情况：v若最优表中有非基变量的检验数为若最优表中有非基变量的检验数为0，则为多，则为多个最优方案的情况。个最优方案的情况。v这种情况下，可将检验数为这种情况下，可将检验数为0的非基变量作为的非基变量作为进基变量，即可得到另一个最优方案。进基变量，即可

22、得到另一个最优方案。五、运输问题的几种特殊情况五、运输问题的几种特殊情况B1B2B3B4产量产量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39销量销量bj365620v如上例中的最优方案就不唯一：如上例中的最优方案就不唯一：（0）（2）（2）（1）（9）（12）检验数为检验数为0者进基者进基最小偶点为出基最小偶点为出基变量和调整量变量和调整量+2-2-2+2五、运输问题的几种特殊情况五、运输问题的几种特殊情况v得到另一个最优方案：得到另一个最优方案：vx11=2,x13=5,x21=1,x24=3,x32=6,x34=3,v其余其余 xij=0；v

23、最优值仍然为最优值仍然为 f*=85五、运输问题的几种特殊情况五、运输问题的几种特殊情况v2、无解情况：、无解情况：v当某个产地当某个产地Ai不能向某个销地不能向某个销地Bj供应产品时，供应产品时，设相应的运费为设相应的运费为M（类似于大（类似于大M法），然后法），然后求最优解。求最优解。v在最优解中，若相应在最优解中，若相应xij的取值为的取值为0，则此最优，则此最优解为原问题的最优解；若解为原问题的最优解；若xij的取值不为的取值不为0，则，则原问题无解。原问题无解。五、运输问题的几种特殊情况五、运输问题的几种特殊情况v3、退化情况、退化情况v一个或多个基变量等于一个或多个基变量等于0。v

24、思考思考：运输问题是否存在无界解情况？：运输问题是否存在无界解情况？六、运输问题的应用六、运输问题的应用v1、产销不平衡的运输问题、产销不平衡的运输问题v例：某公司从两个产地例：某公司从两个产地A1、A2将物品运往三将物品运往三个销地个销地B1、B2、B3，各产地的产量、各销地，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费的销量和各产地运往各销地每件物品的运费如下表所示。如下表所示。v问：应如何调运可使总运输费用最小？问：应如何调运可使总运输费用最小？销量销量产量产量六、运输问题的应用六、运输问题的应用B1B2B3产量产量A1646200A2655300销量销量250150200

25、六、运输问题的应用六、运输问题的应用v办法：增加一行表示缺货量。办法：增加一行表示缺货量。100000缺货量缺货量200150250销量销量300556A2200646A1产量产量B3B2B1六、运输问题的应用六、运输问题的应用v实际应用中，可能出现的其他情况：实际应用中，可能出现的其他情况：v（1）某些运输线路上的运输能力有限制；）某些运输线路上的运输能力有限制；v如范例中，如范例中，A1产地产量为产地产量为7，B4销地销量为销地销量为6，从，从A1到到B4线路上最大运输能力为线路上最大运输能力为4。v处理办法：直接在约束条件中增加该约束，处理办法：直接在约束条件中增加该约束，即保证即保证X

26、14的取值不超过产量、销量和线路最的取值不超过产量、销量和线路最大运输能力。大运输能力。六、运输问题的应用六、运输问题的应用v（2）销量大于产量，但某些销地的销量必须）销量大于产量，但某些销地的销量必须完全满足，不能有缺货；完全满足，不能有缺货；v处理办法：对缺货量到该销地的运价定为一处理办法：对缺货量到该销地的运价定为一个充分大的值个充分大的值M。（类似于大。（类似于大M法）法）六、运输问题的应用六、运输问题的应用v如表中如表中B2销量不能短缺：销量不能短缺：1000M0缺货量缺货量200150250销量销量300556A2200646A1产量产量B3B2B1六、运输问题的应用六、运输问题的

27、应用v（3）销量大于产量时，若某地的销量可以有）销量大于产量时，若某地的销量可以有一定量缺货，但供应量必须不小于某个值一定量缺货，但供应量必须不小于某个值p；v处理办法：将该销地分解为两个销地处理办法：将该销地分解为两个销地Bj1和和Bj2，Bj1对应必须满足的销量对应必须满足的销量p，Bj2对应缺货的对应缺货的销量销量bj-p。v其中，缺货量到其中，缺货量到Bj1的运价为的运价为“大大M”。六、运输问题的应用六、运输问题的应用v如表中如表中B2销量不能低于销量不能低于100：10000缺货量缺货量200150250销量销量300556A2200646A1产量产量B3B2B1B21B22100

28、504455M0六、运输问题的应用六、运输问题的应用v例例1：石家庄北方研究院有一、二、三，三个区。每年分别：石家庄北方研究院有一、二、三，三个区。每年分别需要用煤需要用煤3000、1000、2000t，由河北临城、山西盂县两处，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为煤矿负责供应，价格、质量相同。供应能力分别为1500、4000t，运价如下表。由于需大于求，经院研究决定一区供，运价如下表。由于需大于求，经院研究决定一区供应量可减少应量可减少0300t，二区必须满足需求量，三区供应量不，二区必须满足需求量，三区供应量不少于少于1700t，试求总费用为最低的调运方案。

29、，试求总费用为最低的调运方案。一区一区二区二区三区三区产量产量临城临城1.651.701.754000盂县盂县1.601.651.701500销量销量300010002000六、运输问题的应用六、运输问题的应用一区一区 一区一区二区二区三区三区三区三区产量产量临城临城1.651.651.701.751.754000盂县盂县1.601.601.651.701.701500假想产地假想产地M0MM0500销量销量270030010001700300v解：根据题意，作出产销平衡的运价表，取解：根据题意，作出产销平衡的运价表，取M代表一个很大的正数，其作用是强迫相应代表一个很大的正数，其作用是强迫相应

30、的的x31、x33、x34取值为取值为0。六、运输问题的应用六、运输问题的应用1234产量产量A1613221750B1413191560C19202350最低需要量最低需要量3070010最高需要量最高需要量507030不限不限v例例2：设有：设有A、B、C三个化肥厂供应三个化肥厂供应1、2、3、4四四个地区的农用化肥。假设效果相同，有关数据如下个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。表。试求总费用为最低的化肥调拨方案。六、运输问题的应用六、运输问题的应用112344产量产量A16161322171750B14141319151560C19192023

31、MM50DM0M0M050销量销量302070301050v解：根据题意，作出产销平衡的运价表解：根据题意，作出产销平衡的运价表六、运输问题的应用六、运输问题的应用v2、生产与储存问题、生产与储存问题v例例1：某厂按合同规定须于当年每个季度末分别提：某厂按合同规定须于当年每个季度末分别提供供10、15、25、20台同一规格的柴油机。已知该厂台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用个季度需储存、维护等费用0

32、.15万元。万元。v试求在完成合同的情况下，使该厂全年生产总费用试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。为最小的决策方案。六、运输问题的应用六、运输问题的应用六、运输问题的应用六、运输问题的应用v解：解：设设 xij为第为第 i 季度生产的第季度生产的第 j季度交货的季度交货的柴油机数目，那么应满足：柴油机数目，那么应满足：交货：交货：生产：生产：x11 =10 x11+x12+x13+x14 25x12+x22 =15 x22+x23+x24 35x13+x23+x33 =25 x33+x34 30 x14+x24+x34+x44 =20 x44 10六、运输问题的应用

33、六、运输问题的应用v把第把第 i 季度生产的柴油机数目看作第季度生产的柴油机数目看作第 i 个生产厂的个生产厂的产量；把第产量；把第 j 季度交货的柴油机数目看作第季度交货的柴油机数目看作第 j 个销个销售点的销量；成本加储存、维护等费用看作运费。售点的销量；成本加储存、维护等费用看作运费。v可构造下列产销平衡问题：可构造下列产销平衡问题：v例例2：光明仪器厂生产电脑绣花机是以产定销的。：光明仪器厂生产电脑绣花机是以产定销的。已知已知1至至6月份各月的生产能力、合同销量和单台月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：电脑绣花机平均生产费用见下表：六、运输问题的应用六、运输

34、问题的应用v已知上年末库存已知上年末库存103台绣花机，如果当月生产出台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每来的机器当月不交货，则需要运到分厂库房，每台增加运输成本台增加运输成本0.1万元万元,每台机器每月的平均仓每台机器每月的平均仓储费、维护费为储费、维护费为0.2万元。在万元。在78月份销售淡季，月份销售淡季，全厂停产全厂停产1个月，因此在个月，因此在6月份完成销售合同后还月份完成销售合同后还要留出库存要留出库存80台。加班生产机器每台增加成本台。加班生产机器每台增加成本1万元。万元。v问应如何安排问应如何安排16月份的生产，可使总的生产费月份的生产，可使总的生

35、产费用（包括运输、仓储、维护）最少？用（包括运输、仓储、维护）最少？六、运输问题的应用六、运输问题的应用v解：解：这个生产存储问题可化为运输问题来做。这个生产存储问题可化为运输问题来做。v考虑：各月生产与交货分别视为产地和销地。考虑：各月生产与交货分别视为产地和销地。v1）1-6月份合计生产能力（包括上年末储存量）为月份合计生产能力（包括上年末储存量）为743台，台，销量为销量为707台。设一假想销地销量为台。设一假想销地销量为36；v2）上年末库存）上年末库存103台，只有仓储费和运输费，把它列为的台，只有仓储费和运输费，把它列为的0行；行；v3）6月份的需求除月份的需求除70台销量外，还要

36、台销量外，还要80台库存，其需求应台库存，其需求应为为70+80=150台；台；v4）1-6表示表示1-6月份正常生产情况，月份正常生产情况，1-6表示表示1-6月份加班月份加班生产情况。生产情况。六、运输问题的应用六、运输问题的应用产销平衡的运价表：产销平衡的运价表：六、运输问题的应用六、运输问题的应用v3、转运问题、转运问题v原运输问题上增加若干转运站。原运输问题上增加若干转运站。v运输方式有：产地运输方式有：产地 转运站、转运站转运站、转运站 销销地、产地地、产地 产地、产地产地、产地 销地、销地销地、销地 转转运站、销地运站、销地 产地等产地等。例：某公司有例：某公司有A1、A2、A3

37、三个分厂生产某种物质，三个分厂生产某种物质，分别供应分别供应B1、B2、B3、B4四个地区的销售公司销售。四个地区的销售公司销售。假设质量相同，有关数据如下表：假设质量相同，有关数据如下表：六、运输问题的应用六、运输问题的应用假设：假设：1、每个分厂的物资不一定直接发运到销地、每个分厂的物资不一定直接发运到销地,可以从可以从其中几个产地集中一起运；其中几个产地集中一起运；2、运往各销地的物资可以先运给其中几个销地，、运往各销地的物资可以先运给其中几个销地，再转运给其他销地；再转运给其他销地；3、除产销地之外，还有几个中转站，在产地之间、除产销地之外，还有几个中转站，在产地之间、销地之间或在产地

38、与销地之间转运。运价如下表，销地之间或在产地与销地之间转运。运价如下表，试求总费用为最少的调运方案。试求总费用为最少的调运方案。六、运输问题的应用六、运输问题的应用解：把此转运问题转化为一般运输问题：解：把此转运问题转化为一般运输问题：1、把所有产地、销地、转运站都同时看作产地和销地；、把所有产地、销地、转运站都同时看作产地和销地；2、不可能方案的运费取作、不可能方案的运费取作M，自身对自身的运费为，自身对自身的运费为0；3、产量及销量可定为：、产量及销量可定为：中转站中转站 产量和销量均为产量和销量均为20，产地产地 产量为原产量产量为原产量+20，销量为，销量为20销地销地 产量为产量为20，销量为原销量，销量为原销量+20。其中，其中，20为各点可能变化的最大流量；为各点可能变化的最大流量；4、对于最优方案，其中、对于最优方案，其中 xii为自身对自身的运量，实际上不进为自身对自身的运量，实际上不进行运作。行运作。六、运输问题的应用六、运输问题的应用可得到扩大的产销平衡运输问题表：可得到扩大的产销平衡运输问题表：