数学模型运输方式选择.doc

《数学模型》
课程设计报告书

安徽工业大学数理学院

论文题目：选择运输方式
姓 名
赵星宇
专 业
信息与计算科学
班 级
信111
学 号
119084103
指导教师
侯为根

2014年 6 月 25 日

目录

一、 课程设计题目..........................................................................1

二、摘要..........................................................................................2

三、问题分析..................................................................................3

四、数学模型的表达.................................................................. 4-6

五、 模型实现................................................................................6-8

六、 计算结果...............................................................................8-9

七、附件LINGO...................................................................... .9-13

一、 课程设计题目
选择运输方式
题目：在法国西南部有一家公司，这家公司需要将 180 吨存放于仓库 D1 到 D4 中的化学产品运输到 3 个回收中心 C1，C2 和 C3。仓库 D1 到 D4 分别储存有 50，40，35， 和 65 吨化学产品，总计为 190 吨。可以选用两种运输方式：公路运输和铁路运输。 仓库 D1 只能通过公路向回收中心 C1 和 C2 进行运输，运费分别为 12 欧元/吨和 14 欧元/吨。仓库 D2 只能向回收中心 C2 运输，可以选择通过铁路或公路，运费分别为12 欧元/吨和 14 欧元/吨。仓库 D3 可以通过公路向回收中心 C2 运输（9 欧元/吨）， 或通过铁路或公路向回收中心 C3 运输，运费分别为 4 欧元/吨和 5 欧元/吨。仓库 D4 可以通过铁路或公路向回收中心 C2 运输，运费分别为 11 欧元/吨和 14 欧元/吨，或 者通过铁路或公路向回收中心 C3 运输，运费分别为 10 欧元/吨和 14 欧元/吨。此公司与铁路公司签订的化学物品运输合同规定，每次运输量至少应为 10 吨， 最多为 50 吨。除了标准的安全规章之外，对公路运输不存在其他特殊的限制。那么 此公司应如何运输这 190 吨化学物品才能够使总运费最低？

二、 摘要

运输费用最低化是我们在现代社会经常会遇到的一个问题。在社会的经济生产活动中，企业与客户都会想方设法合理调拨资源、降低运输费用，实现双方利益最大化，完成资源优化配置。本文以使物流运费成本最低为研究对象，在供应量，需求量和单位运费都已确定的情况下，可用线性规划方法来解决运输中的组织调拨问题。在本文中，我们主要解决的是化学物品配送最优的问题，即是使我们花费的总运费最少。我们运用系统的观点和方法，进行综合分析，发现问题，解决问题，使物流运输活动更加优化、物流运输成本更加合理化。根据题目中所给出的各约束条件，四个仓库、三个回收中心，每个仓库所能到达的回收中心及运费也不同。针对题目中所给信息，要使者190吨化学物品全部运输到回收中心，同时，每个仓库只能到达部分回收中心。基于这两个条件，我们建立了在运输目的地有限制情况下使用总运费最少的模型。我们依据此模型得出的最优运输方案最终要能符合双方要求，实现运输资源的合理优化使用。

关键词：化学物品运输  线性规划  运输优化问题  运费最少

三、 问题分析
在本文中，我们主要解决的是化学物品最优的问题。在这里的最优即是使我们的总运费花费的最少。根据题目中所给出的条件是有四个在不同位置的仓库，每个仓库可到达的回收中心有限制。一共有三个回收中心，到达每个回收中心的方式有两种，铁路和公路且费用不同。在这次的建模中我们所需要解决的问题正是求解一个最优的运输方案，使得总运费最少。
图形表达：

图一运输网络图

四、 数学模型的表达
我们将把此问题建模为一个具有固定总通过量的最小费用流问题（minimum cost flow problem）。我们先来构造一幅图 G = (NODES , ARCS )。首先向结点集合NODES 中加入一组结点，代表各个仓库，然后再加入一组结点，代表回收中心（参 照图 10.1）。弧集合 ARCS 中包含了在所有仓库和回收中心之间可能存在的连接。运输方案即对应于图 G 中的一个流，即在每一条弧 (i , j )上的流 flowij 。弧 (i , j )具有一个最小通过量 MINCAPij（除铁路运输其他均为 0），一个最大通过量 MAXCAPij（即 运力上限，除铁路运输外均为无穷大），以及每吨的运输成本 COSTij 。
从一个仓库到一个处理中心之间的两种运输方式需对应两条不同的弧。在这样的图中，两个结点之间至多有 p 条弧，称为 p -图。这样的图无法编码为（二维）矩阵： 例如费用矩阵中的元素 COSTij 只能表示一个费用。为将此图转化为两个结点之间至多有一条弧的图，可以为仓库 i 和处理中心 j 之间的每种运输方式都创建一个假想的结点。例如，在仓库 D2（结点 3）和处理中心 C1（结点 12）之间存在一条公路连 接和一条铁路连接。为避免生成具有两条弧 (3,12)的 2-图，我们可以创建一个结点 6对应于铁路运输，以及一个结点 7 对应于公路运输。则铁路运输即变为路径 (3,6,12) ， 公路运输即变为 (3,7,12)。只为弧 (3,6)和 (3,7) 设置通过量和费用。
在此图中未将仓库的存储量纳入考虑。为此，我们创建一个源结点（假想的结点1），此结点将用弧 (1,d ) 连接到每个仓库结点 d 上，且此弧的通过量为 MAXCAP1d ， 对应于仓库 d 处的存储量。因此离开仓库 d 的流不会超过此值。为方便数学模型的表达，我们也创建一个宿结点（假想的结点 15），并且连接到每个处理中心结点上。 这样最终得 到的图即可 以表示为图 10.1，其 中 每条弧 (i , j ) 都对应于一个三 元 组
( MINCAP ,MAXCAP ,COST )。“-”表示通过量为无穷大。

第 10 页 共 13 页

在此数学模型中包含了流守恒约束条件（10.2.2），也称为 Kirchhoff 定理：每个结点处的入流都等于此结点处的出流（除了源和宿结点之外）。每条弧上的流都至少取值为 MINCAPij （约束条件（10.2.3）），且不超过最大通过量 MAXCAPij （约束条 件（10.2.4））。式（10.2.5）对总流量加以约束，即 MINQ = 180 吨。这样就迫使离开源（结点 1）的流总量等于 MINQ 。由于在此网络中流保持守恒，因此也可以使 用宿结点的入流总量等于 MINQ 作为约束条件。在这个约束条件中，我们可以将等号替换为 ≥ 号，由于在最小化总成本时也将最小化总流量，因此此时总运输量将取此 下界值。最后要解释一下目标函数（10.2.1）。 COSTij 是每吨的运费成本，因此通过弧 (i , j )运输的流 flowij 的费用为 COSTij ⋅ flowij 。因此最小化总运费即最小化所有弧 上的总费用。
最终，通过定义这样的图，我们可以得到相当简洁的数学模型。注意，在约束条 件（10.2.3）中也隐含给出了变量非负的约束条件。
minimize （10.2.1）
∀i ∈ NODES ,i ≠ SOURCE ,SINK := (10.2.2)
∀(i,j) ∈ARCS,> (10.2.3)
∀(i,j) ∈ARCS,< (10.2.4)
= MINQ (10.2.5)
除了这种基于图的问题数学表达之外，也可以将使用方式 m 从仓库 d 运输到目 标 c 的运量表示为决策变量 trasnport dcm ，对每个可能出现的三元组 (d ,c,m)都建立 这样的决策变量，从而得到另一种问题表达方式。这样总运量就可以表示为所有有定义的变量 trasnport dcm 的和，目标函 数即所有可 行的三元组 (d ,c,m) 对应的 COSTdcm ⋅ trasnport dcm 的和。每种运输方式的最小和最大运力限制将表示为对应变 量 trasnport dcm 的上界和下界约束条件，这一点与上述的（10.2.3）和（10.2.4）很相似。对于我们这个问题，这种表达方式可能比基于图的模型表达要容易一些。但在后面的模型实现和进一步的讨论中，我们仍然使用这种更一般的最小费用流模型，即
（10.2.1）到（10.2.5）给出的模型。

五、 模型实现
从这个问题可以引出一个经典的问题，即图的编码。可以将图定义为 N × N 的 矩阵形式，其中 N 为结点总数，并为每对由弧相连的结点 (i , j )都定义一个流变量。 然而，对于稀疏图，如我们所使用的这个图，更常用（效率也更高）的方法是将图表示为弧的列表的形式。在下面的 Mosel 程序实现种就使用了这种表示方法。弧a = (i , j )将用标号 a 进行索引，而不是用对应的结点对 (i , j )进行索引。弧的列表为二维数组 A ，其中 Aa1 = i ， Aa 2 = i 。在读入数据后（即弧集为已知）将定义流变 量。注意在下面的实现中，未采用数字对结点进行编号，而是用名称“Source”，“D2”， “C4”等，这样能够能够方便对结果进行解释。
model "E-2 Minimum cost flow" uses ""
declarations
NODES: set of string ! 结点集合
MINQ : integer ! 运输总量
A: array(ARCS:range,1..2) of string ! 弧
COST: array(ARCS) of integer ! 每条弧的运输成本
MINCAP,MAXCAP: array(ARCS) of integer ! 弧的最小和最大通过量
end-declarations
initializations from ‘e2minflow.dat’
A MINQ MINCAP MAXCAP COST
end-initializations
finalize(ARCS)
! 计算结点集合
NODES:= union(a in ARCS) {A(a,1),A(a,2)}
declarations
flow: array(ARCS) of mpvar ! 弧上的流
end-declarations
! 目标函数：总运输成本
Cost:= sum(a in ARCS) COST(a)*flow(a)
! 流平衡：入流等于出流
For all(n in NODES | n<>"SOURCE" and n<>"SINK")
sum(a in ARCS | A(a,2)=n) flow(a) = sum(a in ARCS | A(a,1)=n) flow(a)
! 最小和最大流通过量
For all(a in ARCS | MAXCAP(a) > 0) do flow(a) >= MINCAP(a)
flow(a) <= MAXCAP(a)
end-do
! 最小运输量
sum(a in ARCS | A(a,1)="SOURCE" ) flow(a) >= MINQ
! 求解此问题
minimize(Cost)
end-model

六、 计算结果
最低运输成本为 1,715 欧元。图 10.2 示意了此时的解决方案：在实际用于运输 的弧上标出了运输量，未使用的弧用虚线表示。例如，仓库 D1 的所有 50 吨库存都 将通过公路运输到回收中心 2。
上图最优运输方案 应注意到，这种对弧上的流有最小约束的问题可能会无法找到可行解。在本例中，如果 MINQ = 9 ，则由于所有铁路运输的弧的最低通过量都是 10 吨，因此无法使用 铁路运输。

七、附件
Lingo编写模型程序：

model:
! 3 Warehouse,4 Customer Transportation Problem;
sets:
Warehouse/1..3/:a;
Customer/1..4/:b;
Routes(warehouse,customer):c,x;
End sets
!here are the parameters;
data:
a=30,25,21;
b=15,17,22,12;
c=6,2,6,7,
4,9,5,3,
8,8,1,5;
End data
! The objective;
[obj] min=@sum(routes:c*x);
!The supply constraints;
@for(warehouse(i):[sup]@sum(customer(j):x(i,j))<=a(i));
!The demand constraints;
@for(customer(j):[dem] @sum(warehouse(i):x(i,j))=b(j));
end

计算结果：
Global optimal solution found.
Objective value: 161.0000
Total solver iterations: 6

Variable Value Reduced Cost
A( 1) 30.00000 0.000000
A( 2) 25.00000 0.000000
A( 3) 21.00000 0.000000
B( 1) 15.00000 0.000000
B( 2) 17.00000 0.000000
B( 3) 22.00000 0.000000
B( 4) 12.00000 0.000000
C( 1, 1) 6.000000 0.000000
C( 1, 2) 2.000000 0.000000
C( 1, 3) 6.000000 0.000000
C( 1, 4) 7.000000 0.000000
C( 2, 1) 4.000000 0.000000
C( 2, 2) 9.000000 0.000000
C( 2, 3) 5.000000 0.000000
C( 2, 4) 3.000000 0.000000
C( 3, 1) 8.000000 0.000000
C( 3, 2) 8.000000 0.000000
C( 3, 3) 1.000000 0.000000
C( 3, 4) 5.000000 0.000000
X( 1, 1) 2.000000 0.000000
X( 1, 2) 17.00000 0.000000
X( 1, 3) 1.000000 0.000000
X( 1, 4) 0.000000 2.000000
X( 2, 1) 13.00000 0.000000
X( 2, 2) 0.000000 9.000000
X( 2, 3) 0.000000 1.000000
X( 2, 4) 12.00000 0.000000
X( 3, 1) 0.000000 7.000000
X( 3, 2) 0.000000 11.00000
X( 3, 3) 21.00000 0.000000
X( 3, 4) 0.000000 5.000000

Row Slack or Surplus Dual Price
OBJ 161.0000 -1.000000
SUP( 1) 10.00000 0.000000
SUP( 2) 0.000000 2.000000
SUP( 3) 0.000000 5.000000
DEM( 1) 0.000000 -6.000000
DEM( 2) 0.000000 -2.000000
DEM( 3) 0.000000 -6.000000

事实上，我们关心更多的是那些非零变量，因此，可选择“Lingo|solution..”弹出一个对话框（介绍此对话框），选择“nonzeros only”，即可只列出非零变量：
Global optimal solution found.
Objective value: 161.0000
Total solver iterations: 6

Variable Value Reduced Cost
A( 1) 30.00000 0.000000
A( 2) 25.00000 0.000000
A( 3) 21.00000 0.000000
B( 1) 15.00000 0.000000
B( 2) 17.00000 0.000000
B( 3) 22.00000 0.000000
B( 4) 12.00000 0.000000
C( 1, 1) 6.000000 0.000000
C( 1, 2) 2.000000 0.000000
C( 1, 3) 6.000000 0.000000
C( 1, 4) 7.000000 0.000000
C( 2, 1) 4.000000 0.000000
C( 2, 2) 9.000000 0.000000
C( 2, 3) 5.000000 0.000000
C( 2, 4) 3.000000 0.000000
C( 3, 1) 8.000000 0.000000
C( 3, 2) 8.000000 0.000000
C( 3, 3) 1.000000 0.000000
C( 3, 4) 5.000000 0.000000
X( 1, 1) 2.000000 0.000000
X( 1, 2) 17.00000 0.000000
X( 1, 3) 1.000000 0.000000
X( 2, 1) 13.00000 0.000000
X( 2, 4) 12.00000 0.000000
X( 3, 3) 21.00000 0.000000

Row Slack or Surplus Dual Price
SUP( 2) 0.000000 2.000000
SUP( 3) 0.000000 5.000000
DEM( 1) 0.000000 -6.000000
DEM( 2) 0.000000 -2.000000
DEM( 3) 0.000000 -6.000000
DEM( 4) 0.000000 -5.000000