数学建模运输问题.ppt

1、运输问题模型 Transportation,一问题的提出,公司把这些糖果分别运往四个地区的门市部销售， 各地区每天的销售量分别为：,B13吨，B26吨，B35吨，B46吨。,A17 吨，A24吨，A39吨。,某食品公司主要经营糖果。 它下面设有三个加工厂， 每天的糖果生产量分别为：,已知从每个加工厂到各销售门市部每吨糖果的运价如上表所示，,该食品公司应如何调运，在满足各门市部销售需要的情况下， 使总的运费支出为最少。,二问题的概述,在线性规划中研究这样一类问题： 有某种物资需要调运，这种物资的计量单位可以是重量， 包装单位或其他。,已知: 有m 个地点可以供应该种物资（统称产地，用 i =1,

2、m 表示）；,有 n 个地点需要该种物资（统称销地，用 j =1,n 表示）。,n 个销地的需要量（统称销量）为b1 , b2, , bn（统写为 b j ）。,从第 i 个产地到第 j 个销地的单位物资运价为c i j 。,又知 m 个产地的可供量（统称产量）为a1 , a2, , am（统写为a i ）；,上面这些数据通常用产销平衡表和单位运价表来表示。,有时候把两个表写在一起:,三运输问题模型,设 xij 代表从第 i 个产地调运给 第 j 个销地的物资数量。,在产销平衡的条件下，要求解 运输问题使总的运费支出最小， 则有如下的运输问题数学模型：,如果用单纯形法求解， 先要在每个约束条件

3、左端加上一个人工变量， 因此即使象食品公司调运糖果这样简单的数学问题， 变量数就有 34+3+4=19个之多，计算起来非常繁杂。,运输问题的数学模型结构比较特殊， 它的约束条件变量的系数矩阵具有如下的形式：,运输问题的数学模型包含 mn个变量， (m+n)个约束条件。,说明：,产销不平衡的运输问题,1产大于销,1）数学模型,s.t.,产大于销时，增加一个假想的销地 j = n+1（库存），,2）求解方法: 转化为产销平衡问题,该销地的总需求量为,而在单位运价表中从各产地到假想销地的单位运价为,就转化为一个产销平衡的运输问题。,具体做法如下：,2.销大于产,1）数学模型,销大于产时，在产销平衡表

4、中增加一个假想的产地 i = m+1， 该地产量为,在单位运价表中， 从假想产地到各销地的单位运价为,就转化为产销平衡的运输问题。,具体做法如下：,m+1 0 0 0 短缺,2）求解方法: 转化为产销平衡问题,应用实例,设有A1、A2、A3三个产地生产某种物资，产量分别为7、5、7吨， B1、B2、B3、B4四个销地需要该物资，销量分别为2、3、4、6吨。 又知各产销地之间的单位运价见下表， 试决定总运费最少的调运方案。,解： 产地总产量为19吨， 销地总销量为15吨， 这是一个产大于销的运输问题。 首先转化为产销平衡的运输问题， 其产销平衡表和单位运价表分别见下两表。,A17吨，A25吨，A

5、37吨。 B12吨，B23吨，B34吨，B46吨。,用表上作业法计算， 求得最优调运方案为：,LINGO求解,Global optimal solution found at iteration: 8 Objective value: 35.00000,设有三个电视机厂供应四个地区某种型号的电视机。 各厂家的年产量、 各地区的年销售量以及 各地区的单位运价 如右表， 试求出总的运费最省的 电视机调拨方案。,12,M,M,M,0,0,0,M M,总运价:172元,Lingo求解,Global optimal solution found at iteration: 8 Objective val

6、ue: 172.0000,Lingo求解,Global optimal solution found at iteration: 16 Objective value: 172.0000,中转调运问题,1.已知甲、乙两处分别有100吨和85吨同种物资外运， A、B、C三处各需要物资55，60，70吨。 物资可以直接运到目的地，也可以经某些中转点转运。 已知各处之间的单位运价如下表，试确定一个最优的调运方案。,185 185 130 125 115,85 100 185185 185,用Lingo求解,Global optimal solution found at iteration: 10

7、Objective value: 2210.000,进一步讨论：不考虑中转调运。,用Lingo求解,Global optimal solution found at iteration: 3 Objective value: 2235.000,公司把这些糖果分别运往四个地区 的门市部销售，各地区每天的销售量分别为：,B13吨，B26吨，B35吨，B46吨。,A17 吨，A24吨，A39吨。,2.某食品公司主要经营糖果。 它下面设有三个加工厂， 每天的糖果生产量分别为：,假设有四个中转站, 每个加工厂生产的糖果在运往销地的过程中 可以在产地、中转站和销地之间转运。 已知各产地、销地和中转站之间的

8、单位运价如表所示， 试确定总运费最少的调运方案。,B13吨，B26吨，B35吨，B46吨 总销量：20吨,A17 吨，A24吨，A39吨 总产量：20吨,20 20 20,20 20 20 20,17 14 15 14,13 16 11,20 20 20 20,20 20 20 20,用Lingo求解,Global optimal solution found at iteration: 41 Objective value: 68.00000 Variable Value Reduced Cost VOLUME( WH1, C1) 13.00000 0.000000 VOLUME( WH1,

9、 C2) 7.000000 0.000000 VOLUME( WH2, C2) 9.000000 0.000000 VOLUME( WH2, C8) 11.00000 0.000000 VOLUME( WH3, C3) 11.00000 0.000000 VOLUME( WH3, C6) 9.000000 0.000000 VOLUME( WH4, C4) 20.00000 0.000000 VOLUME( WH5, C5) 20.00000 0.000000 VOLUME( WH6, C6) 11.00000 0.000000 VOLUME( WH6, C8) 4.000000 0.0000

10、00 VOLUME( WH6, C10) 5.000000 0.000000 VOLUME( WH7, C7) 20.00000 0.000000 VOLUME( WH8, C8) 5.000000 0.000000 VOLUME( WH8, C9) 6.000000 0.000000 VOLUME( WH8, C11) 6.000000 0.000000 VOLUME( WH9, C9) 14.00000 0.000000 VOLUME( WH10, C10) 15.00000 0.000000 VOLUME( WH11, C11) 14.00000 0.000000,20 20 20,20

11、 20 20 20,17 14 15 14,13 16 11,20 20 20 20,20 20 20 20,Global optimal solution found at iteration: 41 Objective value: 68.00000,直接调运：85元,B13吨，B26吨，B35吨，B46吨,A17 吨，A24吨，A39吨,（设备生产计划） 某公司按照合同规定需要在当年每个季度末分别提供 10、15、25、20台同一规格的某种机器设备。 已知该公司各季度的生产能力以及生产每台设备的成本下表。 如果生产的设备当季度不交货， 则每台积压一个季度所需的存储、维护等费用为0.15万元。 试确定在完成合同任务的条件下， 使公司全年生产费用