大学精品课件：第四章 运输问题（第3-5节）.ppt

1、第第1页页表上作业法的使用前提：总产量表上作业法的使用前提：总产量=总销量总销量 在许多的实际运输问题中，总产量在许多的实际运输问题中，总产量总销量，该类总销量，该类问题称为产销不平衡的运输问题。问题称为产销不平衡的运输问题。产销不平衡运输问题的解决方法：将产销不平衡产销不平衡运输问题的解决方法：将产销不平衡运输问题转化为产销平衡的运输问题，再利用表运输问题转化为产销平衡的运输问题，再利用表上作业法求解。上作业法求解。第第2页页如果总产量如果总产量 总销量，即总销量，即 njjmiiba11 0,.,1,.,1,min1111ijjmiijinjijminjijijxnjbxmiaxxcz第第

2、3页页为了能够使用表上作业法对问题进行求解，可增加为了能够使用表上作业法对问题进行求解，可增加一个假想销地一个假想销地 Bn+1：（1）Bn+1 地的销量为地的销量为（2）ci,n+1=0，i=1,m。（原因：销地。（原因：销地 Bn+1 实际上实际上并不存在，因而运往销地并不存在，因而运往销地 Bn+1 的物资实际上就是在的物资实际上就是在产地产地 Ai 存储起来。）存储起来。）njjmiinbab111第第4页页从而问题的模型变为：从而问题的模型变为：01,.,1,.,1,min111111ijjmiijinjijminjijijxnjbxmiaxxcz该模型为产销平衡问题模型，从而建立运

3、输表如下该模型为产销平衡问题模型，从而建立运输表如下所示：所示：第第5页页 njjmiiba11 销地销地产地产地B1BnBn+1*（储存）（储存）产量产量A1x11c11x1nc1nx1,n+10a1Amxm1cm1xmncmnxm,n+10am销量销量b1bn第第6页页如果总产量如果总产量 总销量总销量=70故需增加虚拟销地故需增加虚拟销地 D，其销量为，其销量为 90 70=20将产地将产地 2 分为分为 2 和和 2，产量分别为，产量分别为 38 和和 2。将产地将产地 3 分为分为 3 和和 3，产量分别为，产量分别为 27 和和 3。产地产地 2 和和 3 运出的物资不能发给虚拟销

4、地运出的物资不能发给虚拟销地 D。第第13页页销地销地产地产地ABC产量产量销销 量量3020201225145M1454233M23331223320D38227320第第14页页销地销地产地产地ABC产量产量230812153销销 量量3020201225145M1454233M23331223320D38227320182第第15页页运输费用为：运输费用为：22+301+84+123+153+33=156存储费用为：存储费用为：185+24=98总费用总费用=156+98=254第第16页页例例 2 设有三个化肥厂（设有三个化肥厂（A、B、C）供应四个地区（）供应四个地区（I、II、II

5、I、IV）的农用化肥。各化肥厂年产量、各地）的农用化肥。各化肥厂年产量、各地区的需求量、单位化肥的运价如下表所示。求运费区的需求量、单位化肥的运价如下表所示。求运费最省的调拨方案。最省的调拨方案。第第17页页销地销地产地产地IIIIIIIV产量产量A1613221750B1413191560C192023-50最低需求最低需求3070010最高需求最高需求507030不限不限第第18页页解：解：总产量总产量=50+60+50=160 万吨万吨 最低需求量最低需求量=30+70+0+10=110 万吨万吨最高需求量最高需求量=无限无限第第19页页因为：因为：IV 最多能分配到的化肥数量最多能分配

6、到的化肥数量=总产量总产量 I 地区最低需求量地区最低需求量 II 地区最低需求量地区最低需求量 III 地区最低需求量地区最低需求量=160 30 70-0=60 万吨万吨 第第20页页所以：所以：IV 地最多能分配到地最多能分配到 60 万吨化肥。万吨化肥。即即 IV 地的最高需求为地的最高需求为 60 万吨。万吨。从而运输问题变为：从而运输问题变为：销地销地产地产地IIIIIIIV产量产量A1613221750B1413191560C192023-50最高需求最高需求507030不限不限60第第21页页该问题为产销不平衡问题，且需求量该问题为产销不平衡问题，且需求量 产量，故需增加虚产量

7、，故需增加虚拟产地拟产地 D：销地销地产地产地IIIIIIIV产量产量A1613221750B1413191560C192023-50最高需求最高需求50703060D50?第第22页页分析：分析：因为各地区的需求量包括两部分因为各地区的需求量包括两部分最高需求和最高需求和最低需求。最低需求。最低需求是必须被满足：不能由虚拟产地调运。最低需求是必须被满足：不能由虚拟产地调运。最高需求可以不被满足：可以由虚拟产地调运。最高需求可以不被满足：可以由虚拟产地调运。由此可知：必须将需求地分开。由此可知：必须将需求地分开。第第23页页各地区的需求量包括两部分各地区的需求量包括两部分最高需求和最低需最高需

8、求和最低需求：求：地区地区I地区地区II地区地区III地区地区IV30207000301050不能由不能由D 调运调运可以由可以由D 调运调运不能由不能由D 调运调运可以由可以由D 调运调运不能由不能由D 调运调运可以由可以由D 调运调运不能由不能由D 调运调运可以由可以由D 调运调运运价运价 M运价运价 0运价运价 M运价运价 0运价运价 M运价运价 0运价运价 M运价运价 050703060I I II II III III VI VI 第第24页页从而建立新的运输平衡表：从而建立新的运输平衡表：销地销地产地产地产量产量A50B60C50D50最高需求最高需求I I VI VI IIIII

9、163020703010501419M1614190131320M22192301715MM1715M0第第25页页利用表上作业法求得问题的最优解如下：利用表上作业法求得问题的最优解如下：销地销地产地产地产量产量A50B60C50D50最高需求最高需求I I VI VI IIIII163020703010501419M1614190131320M22192301715MM1715M050201030302003020第第26页页例例 3 某玩具公司分别生产三种新玩具，每月可供量分某玩具公司分别生产三种新玩具，每月可供量分别为别为 1000 件，件，2000 件，件，2000 件，它们分别被送到

10、甲、件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为具预期销售量均为 1500 件，由于经营方面原因，各件，由于经营方面原因，各商店销售不同玩具的盈利额不同（如下表）。商店销售不同玩具的盈利额不同（如下表）。第第27页页甲甲乙乙丙丙可供量可供量A54-1000B16892000C121012000销售量销售量150015001500又知丙百货商店拒绝进又知丙百货商店拒绝进 A 种玩具。种玩具。求满足上述条件下使总盈利额为最大的供销分配方求满足上述条件下使总盈利额为最大的供销分配方案。案。第第28页页解：从盈利额中

11、选取最大的数解：从盈利额中选取最大的数 16，用，用 16 减去表中的数据，减去表中的数据，从而将原问题转化为运输问题。从而将原问题转化为运输问题。销地销地供给产品供给产品甲甲乙乙丙丙供给量供给量A1000B2000C2000需求量需求量1500150015005401689121011111216087465第第29页页解：总供给量解：总供给量=1000+2000+2000=5000 总需求量总需求量=1500+1500+1500=4500总供给量总供给量 总需求量总需求量故需增加虚拟销售商店丁，其销售量故需增加虚拟销售商店丁，其销售量=500第第30页页销地销地产地产地甲甲乙乙丙丙供给量供

12、给量A1112161000B0872000C4652000需求量需求量150015001500丁丁50000050050050015005001500转化为平衡问题，并利用表上作业法求解，可得：转化为平衡问题，并利用表上作业法求解，可得：第第31页页例例 4 请证明：一个最大化运输问题等价于用最大运价请证明：一个最大化运输问题等价于用最大运价减去各运价所得到的新运输表所形成的最小化运输问减去各运价所得到的新运输表所形成的最小化运输问题。题。0 .)(max1 XbAXtsXcczn0 .)(minmax1max XbAXtsXcccczn解：上述问题也即证明下面两个线性规划问题最优解：上述问题

13、也即证明下面两个线性规划问题最优解一样。解一样。第第32页页0 .)(minmax1max XbAXt sXcccczn0 .)(max1 XbAXtsXcczn0 .)(min1 XbAXtsXcczn0 .)(min1 XbAXtsXcczn即证明下面两个线性规划问题的最优解一样。即证明下面两个线性规划问题的最优解一样。第第33页页上述两个线性规划问题的差别只存在于目标函数系上述两个线性规划问题的差别只存在于目标函数系统中，根据灵敏度分析中的目标函数系统变化对最统中，根据灵敏度分析中的目标函数系统变化对最优解的影响分析可知：最优解是否改变，只需要判优解的影响分析可知：最优解是否改变，只需要

14、判断最终单纯形表中的检验数即可。断最终单纯形表中的检验数即可。第第34页页利用位势法求模型的检验数利用位势法求模型的检验数0 .)(min1 XbAXtsXcczn0)(jiijijvuc 第第35页页利用位势法求模型的检验数利用位势法求模型的检验数ijijjiijijcccvuc max)(，0 .)(minmax1max XbAXt sXcccczn第第36页页下面来讨论下面来讨论 的符号的符号ij ijijccc max 的符号主要取决于的符号主要取决于 和和 的取值的取值ij iu jv 第第37页页 sssjijsijijicvucvu.1111 sssjijsijijiccvucc

15、vumaxmax.1111jivu，jjiivcvucu maxmax2121第第38页页0 )()22()()(maxmaxmax ijjiijjiijjiijijvucvcucccvuc 仍然为问题的最优解。仍然为问题的最优解。第第39页页物资调运的方式主要包括如下两种：物资调运的方式主要包括如下两种：直接运输方式：将物资由产地直接运送到销地。直接运输方式：将物资由产地直接运送到销地。转运运输方式：将物资由产地运到某个中间转运站，转运运输方式：将物资由产地运到某个中间转运站，然后再转运到销地。然后再转运到销地。第第40页页用数学语言对上述问题进行描述：用数学语言对上述问题进行描述：1.有有

16、 m 个生产地个生产地 Ai：i=1,2,m；供应量分别为：；供应量分别为：ai，i=1,2,m；2.有有 n 个消费地个消费地 Bj：j=1,2,n；需求量分别为：；需求量分别为：bj，j=1,2,n；3.有有 q 个中转站个中转站 Tk：k=1,2,q。第第41页页4.生产地、消费地也可以作为中间转运站使用。从而生产地、消费地也可以作为中间转运站使用。从而物资发送地和接收地都有物资发送地和接收地都有 m+n+q 个，分别为：个，分别为：发送地：发送地：A1，Am；B1，Bn；T1，Tq接收地：接收地：B1，Bn；A1，Am；T1，Tq第第42页页5.从发送地到接收地的运价为：从发送地到接收

17、地的运价为：，其中：，其中：i=1，m；j=1，n。，其中：，其中：i=1，m；j=1，m。，其中：，其中：i=1，m；j=1，q。，其中：，其中：i=1，n；j=1，m。，其中：，其中：i=1，n；j=1，n。，其中：，其中：i=1，n；j=1，q。，其中：，其中：i=1，q；j=1，m。，其中：，其中：i=1，q；j=1，n。，其中：，其中：i=1，q；j=1，q。jiAAcjiBAcjiABcjiBBcjiTAcjiTBcjiATcjiBTcjiTTc第第43页页假定问题为产销平衡问题，存在假定问题为产销平衡问题，存在 njjmiibaQ11第第44页页接受地接受地(产地产地)接受地接受

18、地(中转地中转地)接受地接受地(销地销地)发送量发送量A1AmT1TqB1Bn发送地发送地(产地产地)A1Am发送地发送地(中转地中转地)T1Tq发送地发送地(销地销地)B1BnQ+a1Q+amQQQQQQQQQ+b1Q+bnmAAc111AAcqTAc111TAc11BAcnBAc1mmAAc1AAmcqmTAc1TAmc1BAmcnmBAcmATc111ATcqTTc111TTc11BTcnBTc1mqATc1ATqcqqTTc1TTqc1BTqcnqBTcmABc111ABcqTBc111TBc11BBcnBBc1mnABc1ABncqnTBc1TBnc1BBncnnBBc第第45页页接

19、受地接受地(产地产地)接受地接受地(销地销地)发送量发送量A1AmB1Bn发送地发送地(产地产地)A1Am发送地发送地(销地销地)B1BnQ+a1Q+amQQQ+b1Q+bnQQ11BAcnBAc11BAmcnmBAc11ABcmABc11ABncmnABcnBBc11BBncmAAc11AAmc11AAcmmAAc11BBcnnBBc第第46页页例例 下图为一个运输系统，它包括：下图为一个运输系统，它包括：两个产地（和）：产量分别为两个产地（和）：产量分别为 10 和和 40。二个销地（和）：销量分别为二个销地（和）：销量分别为 30 和和 20。一个中转站（一个中转站（）。）。节点间运价如

20、下图所示。节点间运价如下图所示。试确定最优运输方案。试确定最优运输方案。第第47页页1245356553324第第48页页解：建立运输表如下表所示。解：建立运输表如下表所示。产地产地转运转运销地销地12345产地产地153260252490转运转运3325550销地销地425650545650接收量接收量5050508070MMMM00000第第49页页利用最小元素法求初始调运方案。利用最小元素法求初始调运方案。产地产地转运转运销地销地12345产地产地15322524转运转运3325550销地销地425650545650接收量接收量505050MMMM00000507020506010508

21、0305005090401020202020第第50页页利用表上作业法求出最优方案如下利用表上作业法求出最优方案如下产地产地转运转运销地销地12345产地产地153260252490转运转运3325550销地销地425650545650接收量接收量5050508070MMMM00000501050202030205050第第51页页最优运输方案为：最优运输方案为：由由 运运 10 单位物资到单位物资到 地：地：由由 运运 20 单位物资到单位物资到 地：地：由由 运运 20 单位物资先到单位物资先到 地，再由地，再由 地转运地转运到到 地：地：201021414 xc802042525 xc2

22、0020320520234334342323 xcxcxc总运费为：总运费为：z=300第第52页页由于运输问题的表上作业法远比一般单纯形法计由于运输问题的表上作业法远比一般单纯形法计算简单，因而在解决实际问题时，设法将问题转算简单，因而在解决实际问题时，设法将问题转化为运输问题的数学模型来求解。化为运输问题的数学模型来求解。第第53页页例例 1 已知某企业各季度的生产能力、每季度交货量、已知某企业各季度的生产能力、每季度交货量、每台设备的生产成本如下表。每台设备的生产成本如下表。季度季度生产能力生产能力（台）（台）交货量交货量（台）（台）生产成本生产成本（万元（万元/台）台）I251010.

23、8II351511.1III302511.0IV102011.3第第54页页如果企业生产出来的设备当季不交货，则每台每个如果企业生产出来的设备当季不交货，则每台每个季度的存储维护费用为季度的存储维护费用为 0.15 万元。万元。求在满足合同的条件下，企业如何安排生产计划，求在满足合同的条件下，企业如何安排生产计划，才能使年生产和存储维护的总费用最低？才能使年生产和存储维护的总费用最低？解：设解：设 xij 表示第表示第 i 季度生产第季度生产第 j 季度交货的设备台季度交货的设备台数。数。第第55页页每季度生产的用于当季度和以后各季度交货的每季度生产的用于当季度和以后各季度交货的设备数不可能超

24、过该季度的生产能力：设备数不可能超过该季度的生产能力：10 30 35 25 44343324232214131211xxxxxxxxxx第第56页页根据合同要求，必须满足：根据合同要求，必须满足：20 25 15 10 44341414332313221211xxxxxxxxxx第第57页页设备的存储维护成本设备的存储维护成本443433242322141312113.11 )(11 )(1.11 )(8.10 xxxxxxxxxx 142413342312315.0 )(215.0 )(15.0 xxxxxx 设备的生产成本设备的生产成本第第58页页考虑将其转化为运输问题。考虑将其转化为运

25、输问题。利用单纯形法求解上述问题计算工作量很大。利用单纯形法求解上述问题计算工作量很大。设设 cij 表示第表示第 i 季度生产第季度生产第 j 季度交货的设备的单季度交货的设备的单位总成本（包括生产成本、存储维护成本）。位总成本（包括生产成本、存储维护成本）。第第59页页 jiIIIIIIIVI10.810.8+0.15110.8+0.15210.8+0.153II11.111.1+0.15111.1+0.152III1111+0.151IV11.3cij 值值MMMMMM第第60页页设设 ai 表示第表示第 i 季度的生产能力；季度的生产能力；设设 bj 表示第表示第 j 季度的合同供货量

26、；季度的合同供货量；则问题可表述成运输问题的形式：则问题可表述成运输问题的形式：销地销地产地产地IIIIIIIV产量产量I10.810.9511.011.2525IIM11.111.2511.435IIIMM1111.1530IVMMM11.310销量销量10152520第第61页页问题为产销不平衡运输问题，增加虚拟销地，转问题为产销不平衡运输问题，增加虚拟销地，转变为平衡问题：变为平衡问题：销地销地产地产地IIIIIIIVV产量产量I10.810.9511.011.25025IIM11.111.2511.4035IIIMM1111.15030IVMMM11.3010销量销量101525203

27、0第第62页页 销地销地产地产地IIIIIIIVV产量产量I1015025II53035III201030IV1010销量销量1015252030利用表上作业法求出问题的最优解为：利用表上作业法求出问题的最优解为：第第63页页例例 2 某公司承担某公司承担 4 条航线的运输任务，已知：条航线的运输任务，已知：（1）各条航线的起点城市和终点城市及每天的航班）各条航线的起点城市和终点城市及每天的航班数，如表数，如表 1 所示；所示；（2）各城市间的航行时间，如表）各城市间的航行时间，如表 2 所示；所示；（3）所有航线都使用同一种船只，每次装船和卸船）所有航线都使用同一种船只，每次装船和卸船时间均

28、为时间均为 1 天。天。问该公司至少配备多少条船才能满足所有航线运输的问该公司至少配备多少条船才能满足所有航线运输的需要？需要？第第64页页表表 1航线航线起点城市起点城市终点城市终点城市每天航班数量每天航班数量1ED32BC23AF14DB1第第65页页表表 2 ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030第第66页页解：解：（1）各条航线航行、装船、卸船所需船只数量。）各条航线航行、装船、卸船所需船只数量。航线航线装船时间装船时间卸船时间卸船时间航行时间航行时间总计总计航班数量航班数量所需船只所需船只111171935

29、72113521031179194111315115为满足每天的装卸船和航行需求，共需配备为满足每天的装卸船和航行需求，共需配备 91 艘船。艘船。第第67页页（2）各港口之间调度所需的船只数量。）各港口之间调度所需的船只数量。城市城市ABCDEF每天到达每天到达每天需要每天需要余缺数余缺数0 1 2 3 0 1 1 20 1 3 0-1-1 2 2-3 1 有多余船只，可调拨其它港口。有多余船只，可调拨其它港口。缺少船只，需要从其它港口调拨。缺少船只，需要从其它港口调拨。第第68页页 至至由由有多余船只有多余船只的港口的港口缺少船只的缺少船只的港口港口C空船调度应采取合理的方案以使得总调运时

30、间最短，从而建立空船调度应采取合理的方案以使得总调运时间最短，从而建立运输表如下。运输表如下。DFABE22111323514131778311111z=40天天第第69页页由此可知，为满足每天港口间的空船调度，共需配由此可知，为满足每天港口间的空船调度，共需配备备 40 艘船只。艘船只。由此可知，该公司至少需要配备由此可知，该公司至少需要配备 131 条船才能满足条船才能满足 4 条航线每天的正常运输需要。条航线每天的正常运输需要。第第70页页例例 3：最优调配方案如下表所示。：最优调配方案如下表所示。销地销地产地产地B1B2B3B4产量产量A1105120101115A2012107159

31、2025A3521416185销量销量5151510第第71页页（1）A2 B2 的单位运价的单位运价 c22 在什么范围变化时，在什么范围变化时，最优调运方案不变？最优调运方案不变？（2）A2 B4 的单位运价的单位运价 c24 变为何值时，有无穷变为何值时，有无穷多最优调运方案？至少再写出一个最优调运方案。多最优调运方案？至少再写出一个最优调运方案。第第72页页解解：（：（1）计算最优调配方案下的位势值。计算最优调配方案下的位势值。销地销地产地产地B1B2B3B4产量产量uiA1105120101115A2012101592025A3521416185销量销量5151510vj7 c220

32、111c22-113-c2210-c22c22-11第第73页页 计算最优调配方案下的非基变量检验数。计算最优调配方案下的非基变量检验数。销地销地产地产地B1B2B3B4产量产量uiA11051201011150A201210c221592025c22-1A3521416185c22-11销量销量5151510vj13-c22110-c2211c22-3c22+1024-c2218-c2210-c2217第第74页页 如最优方案不变，则非基变量检验数均应如最优方案不变，则非基变量检验数均应 0。018024010010032222222222ccccc10322 c第第75页页（2）计算最优调

33、配方案下的位势值。计算最优调配方案下的位势值。销地销地产地产地B1B2B3B4产量产量uiA1105120101115A201210715925A3521416185销量销量5151510vj20c240111663-4第第76页页 计算非基变量检验数。计算非基变量检验数。销地销地产地产地B1B2B3B4产量产量uiA11051201011150A2012107159c24256A3521416185-4销量销量5151510vj61311(4)(17)(c24-17)(17)(17)(11)第第77页页 销地销地产地产地B1B2B3B4产量产量uiA11051201011150A2012107159c24256A3521416185-4销量销量5151510vj61311(4)(17)(c24-17)(17)(17)(11)c24 17=0 时，问题有无穷多最优解。时，问题有无穷多最优解。即：即：c24=17(0)+10+10-10-10第第78页页 得到新的最优调运方案。得到新的最优调运方案。销地销地产地产地B1B2B3B4产量产量uiA11015120011150A201271591017256A3521416185-4销量销量5151510vj61311