5.5 运输问题 进阶

《5.5 运输问题 进阶》由会员分享，可在线阅读，更多相关《5.5 运输问题 进阶（10页珍藏版）》请在金锄头文库上搜索。

1、1运输问题 进阶1、策略 2、运输问题？? 3、指派问题? 4、空车调度问题? 5、运输问题悖论?例例 要在五个不同地区设专卖商店。由于不同地区人们 的消费水平及运输费用不同，财会部门经调查提供了 有关三个工厂根据自己的产量计划建商店的数目、五 个地区的需求量及年利润预算报告如下，应该 如何选 择专卖商店地址，使年利润最大？要在五个不同地区设专卖商店。由于不同地区人们 的消费水平及运输费用不同，财会部门经调查提供了 有关三个工厂根据自己的产量计划建商店的数目、五 个地区的需求量及年利润预算报告如下，应该 如何选 择专卖商店地址，使年利润最大？ 利润利润B1B2B3B4B5 设店数设店数A179

2、5367A2646759A38625711需求量需求量4648527利润利润B1B2B3B4B5 设店数设店数A1-7-9-5-3-67A2-6-4-6-7-59A3-8-6-2-5-711需求量需求量4648527解：解：解：解：将C将Cijij转换成- C转换成- Cijij，问题由求利 润最大变成求最小费用。，问题由求利 润最大变成求最小费用。 利润利润B1B2B3B4B5 设店数设店数A1-7-96-5-3-67A2-6-4-6-7-59A3-8-6-2-5-711需求量需求量4648527最小元素法。最小元素法。最小元素法。最小元素法。利润利润B1B2B3B4B5 设店数设店数A1-

3、7-96-5-3-67A2-6-4-6-7-59A3-84-6-2-5-711需求量需求量4648527最小元素法。最小元素法。最小元素法。最小元素法。利润利润 B1 B2 B3 B4 B5 设店数设店数A1 -7 -96 -5 -3 -6 7 A2 -6 -4 -6 -7 -5 9 A3 -84 -6 -2 -5 -75 11 需求量需求量 4 6 4 8 5 27 最小元素法。最小元素法。最小元素法。最小元素法。2利润利润B1B2B3B4B5 设店数设店数A1-7-96-5-3-67A2-6-4-61-78-59A3-84-6-2-5-7511需求量需求量4648527最小元素法。最小元素

4、法。最小元素法。最小元素法。利润利润 B1 B2 B3 B4 B5 设店数设店数A1 -7 -96 -51 -3 -6 7 A2 -6 -4 -61 -78 -5 9 A3 -84 -6 -2 -5 -75 11 需求量需求量 4 6 4 8 5 27 最小元素法。最小元素法。最小元素法。最小元素法。利润利润B1B2B3B4B5 设店数设店数A1-7-96-51-3-67A2-6-4-61-78-59A3-84-6-22-5-7511需求量需求量4648527最小元素法。最小元素法。最小元素法。最小元素法。利润利润B1B2B3B4B5 设店数设店数A1617A2189A342511需求量需求量

5、4648527最小元素法，得到初始方案。最小元素法，得到初始方案。最小元素法，得到初始方案。最小元素法，得到初始方案。利润利润B1B2B3B4B5uiA1-7-4 -96-51-3-3 -6-40A2-6-6 -4-6 -61-78-5-6-1A3-84-60-22-52-753vj-11-9-5-6-10计算检验数，（A3，B4）为正。计算检验数，（A3，B4）为正。利润利润B1B2B3B4B5uiA1-7-4 -96-51-3-3 -6-40A2-6-6 -4-6 -61-78-5-6-1A3-84-60-22-52-753vj-11-9-5-6-10闭回路闭回路3利润利润B1B2B3B4

6、B5aiA1617A2369A342511bj46485得到新方案。得到新方案。得到新方案。得到新方案。利润利润B1B2B3B4B5uiA1-7-2 -96-51-3-3 -6-20A2-6-4 -4-6 -63-76-5-4-1A3-84-6-2 -2-2 -52-751vj-9-9-5-6-8计算检验数，全为非正。计算检验数，全为非正。计算检验数，全为非正。计算检验数，全为非正。利润利润B1B2B3B4B5aiA1617A2369A342511bj46485得到最优方案。得到最优方案。得到最优方案。得到最优方案。最大利润最大利润最大利润最大利润=196=196=196=196（百万元）（百

7、万元）（百万元）（百万元）当某个发点A当某个发点Ai i由于某种原因 不能向某个收点B由于某种原因 不能向某个收点Bj j供应产品时， 设相应的运费C供应产品时， 设相应的运费Cijij为M（M充分地 大），然后进行求最优解。在最 优解中，若相应的x为M（M充分地 大），然后进行求最优解。在最 优解中，若相应的xijij取0值，则 此最优解为原问题的最优解；否 则，原问题无解。取0值，则 此最优解为原问题的最优解；否 则，原问题无解。生产与储存问题?某机床厂定下一年合同分别于各季度末 交货。各季度生产能力、生产成本、合 同交货量如表。允许存货，存储费0.1万 元/台季。如何安排生产，年费用最低

8、15 20 25 2012 11 11.5 12.525 35 30 201 2 3 4交货台数单位成本（万元）正常生产能力季度分析：?比拟运输问题，得下表销售季度销售季度204 420D3035 25产量产量252015销量销量CBA32132112.11111.51211.112.212.511.611.212.3生产季度生产季度110804建模：?后季度生产的不可能前季度销售，可视为费用无穷大（后季度生产的不可能前季度销售，可视为费用无穷大（M)?增加一虚拟销售季度，销售量总生产能力总需求量增加一虚拟销售季度，销售量总生产能力总需求量30d d204 42041103035 25每季生

9、产量每季生 产量252015每季交货量每季交货量32132132112.111M11.5M1211.1M12.2MMM12.511.611.212.30000?例例某高科技企业生产某种光电通讯产品，现要安排今后某高科技企业生产某种光电通讯产品，现要安排今后4个季度的生产计划。已知今后四个季度的合同签定数，企业各季度 生产能力以及各季度的生产成本如表个季度的生产计划。已知今后四个季度的合同签定数，企业各季度 生产能力以及各季度的生产成本如表315所示。考虑资金的机 会成本，预计每件产品每存储一个季度的费用为所示。考虑资金的机 会成本，预计每件产品每存储一个季度的费用为0.1千元。在完 成合同的条

10、件下，试安排这四个季度的生产计划，使生产成本 与存储费用之和最小。千元。在完 成合同的条件下，试安排这四个季度的生产计划，使生产成本 与存储费用之和最小。季度季度合同签定数 （台）合同签定数 （台）生产能力 （台）生产能力 （台）生产成本 （千元）生产成本 （千元）1 2 3 4230 265 255 245270 260 280 2703.2 3.33 3.31 3.42生产与存储问题生产与存储问题(production and inventory application)解解设设xij表示第表示第i季度生产第季度生产第j季度交货的该种产品的数 量，考虑生产成本与存储费用后，季度交货的该种产

11、品的数 量，考虑生产成本与存储费用后，xij所对应的目标 函数中的价格系数所对应的目标 函数中的价格系数cij如表如表318所示。所示。j i123413.23.33.43.523.333.433.5333.313.4143.42?这样问题的数学模型可以描述为：这样问题的数学模型可以描述为： min f = 3.2x11+3.3x12+3.4x13+3.5x14+3.33x22+3.43x23 +3.53x24+3.31x33+3.41x34+3.42x44 x11+x12+x13+x14270 x22+x23+x24260 x33+x34280 x44270 x11 =230 x12+x22

12、 =265 x13+x23+x33 =255 x14+x24+x34+x44 =245 xij0，i=1，4；j=1，4；ij?观察该模型，若将观察该模型，若将x21、x31、x32、x41、x42、x43等变量补齐， 则模型变为一个标准的运输问题数学模型。为了保证模型的 性质不变，必须使这些补齐的变量为等变量补齐， 则模型变为一个标准的运输问题数学模型。为了保证模型的 性质不变，必须使这些补齐的变量为0。为此，可在目标函数 中令这些变量的系数为。为此，可在目标函数 中令这些变量的系数为M，这样就得到一个产销不平衡的运 输问题。此时，可假设一个销地，变成产销平衡问题。产销 表及运价表如表，这样

13、就得到一个产销不平衡的运 输问题。此时，可假设一个销地，变成产销平衡问题。产销 表及运价表如表319所示。所示。销地 产地销地 产地12345产量产量13.23.33.43.502702M3.333.433.5302803MM3.313.4102604MMM3.420270销量销量230265255245851080 1080?从最优调运表中可以看出，第从最优调运表中可以看出，第1季度生产季度生产270台，其中台，其中40台用 于满足第季度需要，第台用 于满足第季度需要，第2季度生产季度生产225台，第台，第3季度生产季度生产260 台，其中台，其中5台用于满足第台用于满足第4季度的需要，第季

14、度的需要，第4季度则生产季度则生产240台。 总费用为台。 总费用为3299.15千元。千元。用表上作业法，可求得四个季度的生产计划如表所示。用表上作业法，可求得四个季度的生产计划如表所示。销地 产地销地 产地12345产量产量12304027022255528032555260424030270销量销量230265255245851080 10805案例案例-康托斯毛毯厂生产与存储问题康托斯毛毯厂生产与存储问题0.25 0.25 0.25 0.252 5 3 3400 500 400 400600 300 500 4001 2 3 4库存成本库存成本 (美元美元/平方码平方码)生产成本生产成

15、本 (美元美元/平方码平方码)需求需求 (平方码平方码)生产能力生产能力 (平方码平方码)季 度康托斯毛毯的产量、市场需求和预期开支季 度康托斯毛毯的产量、市场需求和预期开支(1)运输问题解法运输问题解法 设设xij表示第表示第i季度生产第季度生产第j季度交货的毛毯的数量，考 虑生产成本与存储费用后，季度交货的毛毯的数量，考 虑生产成本与存储费用后，xij所对应的目标函数中的 价格系数所对应的目标函数中的 价格系数cij如下表所示。如下表所示。343.5335.55.25522.752.52.25214321i j?我们有与上例同样形式的数学模型我们有与上例同样形式的数学模型 min f = 2x11+2.25x12+2.5x13+2.75x14+5x22+5.25x23 +5.5x24+3x33+3.25x34+3x44 x11+x12+x13+x14600 x22+x23+x24300 x33+x34500 x44400 x11 =400 x12+x22 =500 x13+x23+x33 =400 x14+x24+x34+x44 =400 xij0，i=1，4；j=1，4；ij?化为运输问题化为运输问题400400500400销量销量400500300600产量产量3MMM43.53MM35.55.255M22.752.52.25214321产