本篇是运输问题系列的第一篇，案例在云上建模求解平台可供复制学习。
问题描述
一般的运输问题是计算如何把某个商品从几个不同的产地，运输到几个不同的目的地，并知道运输量需求、不同运输路径的成本，或者不同目的地的需求等信息。问题如下：
某公司在如下3个地方生产商品，并运送到另外7个地点进行销售，请问该公司运输货物的最低成本是多少？
在这个问题里，3个产地的商品产量如下：
地点 |
产量 |
GARY |
1400吨 |
CLEV |
2600吨 |
PITT |
2900吨 |
以上的6900吨商品将被运送到7个地点进行销售，每个地点的需求量各不相同，如图所示：
地点 |
需求 |
FRA |
900吨 |
DET |
1200吨 |
LAN |
600吨 |
WIN |
400吨 |
STL |
1700吨 |
FRE |
1100吨 |
LAF |
1000吨 |
已知从产地运输货物到销售地的每吨所需成本如下：
GARY |
CLEV |
PITT |
|
FRA |
39元/吨 |
27元/吨 |
24元/吨 |
DET |
14元/吨 |
9元/吨 |
14元/吨 |
LAN |
11元/吨 |
12元/吨 |
17元/吨 |
WIN |
14元/吨 |
9元/吨 |
13元/吨 |
STL |
16元/吨 |
26元/吨 |
28元/吨 |
FRE |
82元/吨 |
95元/吨 |
99元/吨 |
LAF |
8元/吨 |
17元/吨 |
20元/吨 |
数学规划模型
以上问题，我们可以建立线性规划的数学模型如下。
集合
- 起点集合
- 目的地集合
参数
- 起点
的商品产量 
- 目的地
的商品需求 
- 每吨商品从起点
运输至目的地 
所需成本 
决策变量
起点
运送到目的地的商品数量
目标函数
工厂要最小化运输成本： 
约束
- 起点运送到各个目的地货物的总量等于其商品产量
- 不同起点运送到目的地的商品总量等于目的地商品的需求
使用MindOpt APL进行建模和求解
MindOpt建模语言(MindOpt Algebra Programming Language, MindOpt APL，简称为MAPL)是一种高效且通用的代数建模语言。当前主要用于数学规划问题的建模，并支持调用多种求解器求解。下面将演示如何使用MAPL将上面的数学模型公式和数据输入，生成一个求解器可求解的问题，再调用求解器去进行求解。
方法1：cell中直接输入建模代码运行
在求解数独问题时，MindOpt APL可以将其建模代码直接输入如下cell里运行。请注意内核（kernel）需要选MAPL。
其中，有一行我们增加do check的语句来进行验证，确保总产量等于总需求。
clear model;#清除model，多次run的时候使用 option modelname model/transport_01;#方便与方法2的中间文件生成在同一个目录 #---------建模----------------- # transport_01.mapl set ORIG := {"GARY", "CLEV", "PITT"}; set DEST := {"FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"}; param supply[ORIG] := <"GARY"> 1400, <"CLEV"> 2600, <"PITT"> 2900; param demand[DEST] := <"FRA"> 900, <"DET"> 1200, <"LAN"> 600, <"WIN"> 400, <"STL"> 1700, <"FRE"> 1100, <"LAF"> 1000; param cost[ORIG * DEST] := | "FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"| |"GARY"| 39, 14, 11, 14, 16, 82, 8 | |"CLEV"| 27, 9, 12, 9, 26, 95, 17 | |"PITT"| 24, 14, 17, 13, 28, 99, 20 |; check sum {<o> in ORIG } supply[o] == sum {<d> in DEST } demand[d]; #增加do check的语句来进行验证，确保总产量等于总需求 var Trans[<o, d> in ORIG * DEST] >= 0; minimize Total_Cost: sum {<o, d> in ORIG * DEST } cost[o, d] * Trans[o, d]; subto Supply: forall { <o> in ORIG } sum {<d> in DEST } Trans[o, d] == supply[o]; subto Demand: forall { <d> in DEST } sum { <o> in ORIG } Trans[o, d] == demand[d]; #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 display; print "-----------------结果---------------"; print "最小成本 = "; print sum { <o, d> in ORIG * DEST } cost[o, d] * Trans[o, d];
运行结果如下：
-----------------用MindOpt求解--------------- Running mindoptampl wantsol=1 mip_integer_tolerance=1e-9 MindOpt Version 0.23.0 (Build date: 20221129) Copyright (c) 2020-2022 Alibaba Cloud. Start license validation (current time : 01-MAR-2023 20:37:59). License validation terminated. Time : 0.004s Model summary. - Num. variables : 21 - Num. constraints : 10 - Num. nonzeros : 42 - Bound range : [4.0e+02,1.0e+20] - Objective range : [8.0e+00,9.9e+01] - Matrix range : [1.0e+00,1.0e+00] Presolver started. Presolver terminated. Time : 0.001s Simplex method started. Model fingerprint: ==gZ3V2Y3ZWZ3dmZ Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 1.3800e+04 0.01s 9 1.96200e+05 0.0000e+00 0.0000e+00 0.01s Postsolver started. Simplex method terminated. Time : 0.007s OPTIMAL; objective 196200.00 9 simplex iterations Completed. Primal Solution: Trans@<GARY,FRA> = 0.000000000000000E+00 Trans@<GARY,DET> = 0.000000000000000E+00 Trans@<GARY,LAN> = 0.000000000000000E+00 Trans@<GARY,WIN> = 0.000000000000000E+00 Trans@<GARY,STL> = 3.000000000000000E+02 Trans@<GARY,FRE> = 1.100000000000000E+03 Trans@<GARY,LAF> = 0.000000000000000E+00 Trans@<CLEV,FRA> = 0.000000000000000E+00 Trans@<CLEV,DET> = 1.200000000000000E+03 Trans@<CLEV,LAN> = 6.000000000000000E+02 Trans@<CLEV,WIN> = 4.000000000000000E+02 Trans@<CLEV,STL> = 0.000000000000000E+00 Trans@<CLEV,FRE> = 0.000000000000000E+00 Trans@<CLEV,LAF> = 4.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,DET> = 0.000000000000000E+00 Trans@<PITT,LAN> = 0.000000000000000E+00 Trans@<PITT,WIN> = 0.000000000000000E+00 Trans@<PITT,STL> = 1.400000000000000E+03 Trans@<PITT,FRE> = 0.000000000000000E+00 Trans@<PITT,LAF> = 6.000000000000000E+02 Dual Solution: Supply_1 = 8.000000000000004E+00 Supply_2 = 1.700000000000000E+01 Supply_3 = 2.000000000000000E+01 Demand_1 = 3.999999999999999E+00 Demand_2 = -7.999999999999999E+00 Demand_3 = -5.000000000000000E+00 Demand_4 = -7.999999999999999E+00 Demand_5 = 7.999999999999998E+00 Demand_6 = 7.399999999999999E+01 Demand_7 = 0.000000000000000E+00 -----------------结果--------------- 最小成本 = 196200
方法2：导入.mapl文件运行建模然后求解
上面时直接在cell中运行所有的脚本，我们也可以建立个新文档，将中间建模的代码保存为transport_01.mapl文件。然后运行如下code，结果同方法1。
clear model;#清除model，多次run的时候使用 #------------------------------ model model/transport_01.mapl; #通过导入建模脚本.mapl文件进行建模 #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 display; print "-----------------结果---------------"; print "最小成本 = "; print sum { <o, d> in ORIG * DEST } cost[o, d] * Trans[o, d];
结果解析
display指令运行时，会打印出很多求解的结果，Trans@name 是决策变量的取值，后面的dual solution是对偶解的值。示意如下：
Primal Solution: Trans@<GARY,FRA> = 0.000000000000000E+00 Trans@<GARY,DET> = 0.000000000000000E+00 Trans@<GARY,LAN> = 0.000000000000000E+00 Trans@<GARY,WIN> = 0.000000000000000E+00 Trans@<GARY,STL> = 3.000000000000000E+02 Trans@<GARY,FRE> = 1.100000000000000E+03 Trans@<GARY,LAF> = 0.000000000000000E+00 Trans@<CLEV,FRA> = 0.000000000000000E+00 Trans@<CLEV,DET> = 1.200000000000000E+03 Trans@<CLEV,LAN> = 6.000000000000000E+02 Trans@<CLEV,WIN> = 4.000000000000000E+02 Trans@<CLEV,STL> = 0.000000000000000E+00 Trans@<CLEV,FRE> = 0.000000000000000E+00 Trans@<CLEV,LAF> = 4.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,DET> = 0.000000000000000E+00 Trans@<PITT,LAN> = 0.000000000000000E+00 Trans@<PITT,WIN> = 0.000000000000000E+00 Trans@<PITT,STL> = 1.400000000000000E+03 Trans@<PITT,FRE> = 0.000000000000000E+00 Trans@<PITT,LAF> = 6.000000000000000E+02 Dual Solution: Supply_1 = 8.000000000000004E+00 Supply_2 = 1.700000000000000E+01 Supply_3 = 2.000000000000000E+01 Demand_1 = 3.999999999999999E+00 Demand_2 = -7.999999999999999E+00 Demand_3 = -5.000000000000000E+00 Demand_4 = -7.999999999999999E+00 Demand_5 = 7.999999999999998E+00 Demand_6 = 7.399999999999999E+01 Demand_7 = 0.000000000000000E+00 -----------------结果--------------- 最小成本 = 196200
同时，在最近建模的文件所在目录或option modelname指定的位置，会生成对应的文件.nl和.sol。其中.nl文件是建模的问题模型文件，可被多数求解器识别，.sol文件中存储了求解结果solution。
从打印的结果，我们可以得到该公司的最低运输成本为196200元。并且此成本时，运输方案是：
Trans@<CLEV,DET> = 1.200000000000000E+03 Trans@<CLEV,LAF> = 4.000000000000000E+02 Trans@<CLEV,LAN> = 6.000000000000000E+02 Trans@<CLEV,WIN> = 4.000000000000000E+02 Trans@<GARY,FRE> = 1.100000000000000E+03 Trans@<GARY,STL> = 3.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,LAF> = 6.000000000000000E+02 Trans@<PITT,STL> = 1.400000000000000E+03
联系我们
钉钉群号：32451444
邮箱地址：solver.damo@list.alibaba-inc.com
