本篇为第二篇，往期如下：
运输问题（二）本篇
1. 线性规划问题——运输问题
运输问题是线性规划问题里面常研究的一个问题。一般的运输问题是计算如何把某个商品从几个不同的产地，运输到几个不同的目的地，并知道运输量需求、不同运输路径的成本，或者不同目的地的需求等信息。
某公司在如下3个地方生产商品，并运送到另外7个地点进行销售，请问该公司如何配送运输的成本最低？
地点 |
产量 |
GARY |
1400吨 |
CLEV |
2600吨 |
PITT |
2900吨 |
总共生产的6900吨商品将被运送到七个地点进行销售，每个地点的需求量各不相同，如图所示：
地点 |
需求 |
FRA |
900吨 |
DET |
1200吨 |
LAN |
600吨 |
WIN |
400吨 |
STL |
1700吨 |
FRE |
1100吨 |
LAF |
1000吨 |
已知从产地运输货物到销售地的路线有如下几条，且每条路线的价格不相同：
线路 |
每吨价格 |
GARY , DET |
14元 |
GARY , LAN |
11元 |
GARY , STL |
16元 |
GARY , LAF |
8元 |
CLEV , FRA |
27元 |
CLEV , DET |
9元 |
CLEV , LAN |
12元 |
CLEV , WIN |
9元 |
CLEV , STL |
26元 |
CLEV , LAF |
17元 |
PITT , FRA |
24元 |
PITT , WIN |
13元 |
PITT , STL |
28元 |
PITT , FRE |
99元 |
2. 数学规划模型
以上问题，我们可以建立线性规划的数学模型如下。
集合
参数
决策变量
目标函数
约束
3. 使用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_02;#方便与方法2的中间文件生成在同一个目录 #---------建模----------------- # transport_02.mapl set ORIG := {"GARY", "CLEV", "PITT"}; set DEST := {"FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"}; set LINKS := {<"GARY","DET">, <"GARY","LAN">, <"GARY","STL">, <"GARY","LAF">, <"CLEV","FRA">, <"CLEV","DET">, <"CLEV","LAN">, <"CLEV","WIN">, <"CLEV","STL">, <"CLEV","LAF">, <"PITT","FRA">, <"PITT","WIN">, <"PITT","STL">, <"PITT","FRE">}; 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[LINKS] := <"GARY","DET"> 14, <"GARY","LAN"> 11, <"GARY","STL"> 16, <"GARY","LAF">8, <"CLEV","FRA"> 27, <"CLEV","DET"> 9, <"CLEV","LAN"> 12, <"CLEV","WIN"> 9, <"CLEV","STL"> 26, <"CLEV","LAF"> 17, <"PITT","FRA"> 24 , <"PITT","WIN"> 13, <"PITT","STL"> 28, <"PITT","FRE"> 99; check sum { <o> in ORIG } supply[o] == sum { <d> in DEST } demand[d];#增加do check的语句来进行验证，确保总产量等于总需求 var Trans[LINKS] >= 0; minimize Total_Cost: sum {<o, d> in LINKS } cost[o, d] * Trans[o, d]; subto Supply: forall { <o> in ORIG } sum { <o, d> in LINKS } Trans[o, d] == supply[o]; subto Demand: forall {<d> in DEST } sum { <o, d> in LINKS } Trans[o, d] == demand[d]; #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 display; print "-----------------结果---------------"; print "最小成本 = "; print sum { <o, d> in LINKS } 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:38:43). License validation terminated. Time : 0.003s Model summary. - Num. variables : 14 - Num. constraints : 9 - Num. nonzeros : 27 - 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.000s Simplex method started. Model fingerprint: =Y2djZ2dgdHZ Iteration Objective Dual Inf. Primal Inf. Time 0 1.75100e+05 0.0000e+00 2.8000e+03 0.00s 2 2.01700e+05 0.0000e+00 0.0000e+00 0.00s Postsolver started. Simplex method terminated. Time : 0.003s OPTIMAL; objective 201700.00 2 simplex iterations Completed. Primal Solution: Trans@<GARY,DET> = 0.000000000000000E+00 Trans@<GARY,LAN> = 0.000000000000000E+00 Trans@<GARY,STL> = 8.000000000000000E+02 Trans@<GARY,LAF> = 6.000000000000000E+02 Trans@<CLEV,DET> = 1.200000000000000E+03 Trans@<CLEV,LAN> = 6.000000000000000E+02 Trans@<CLEV,STL> = 0.000000000000000E+00 Trans@<CLEV,LAF> = 4.000000000000000E+02 Trans@<CLEV,FRA> = 0.000000000000000E+00 Trans@<CLEV,WIN> = 4.000000000000000E+02 Trans@<PITT,STL> = 9.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,WIN> = 0.000000000000000E+00 Trans@<PITT,FRE> = 1.100000000000000E+03 Dual Solution: Supply_1 = 0.000000000000000E+00 Supply_2 = 9.000000000000000E+00 Supply_3 = 1.200000000000000E+01 Demand_1 = 1.200000000000000E+01 Demand_2 = 0.000000000000000E+00 Demand_3 = 3.000000000000000E+00 Demand_4 = 0.000000000000000E+00 Demand_5 = 1.600000000000000E+01 Demand_6 = 8.000000000000000E+00 -----------------结果--------------- 最小成本 = 201700
方法2：导入.mapl文件运行建模然后求解
上面时直接在cell中运行所有的脚本，我们也可以建立个新文档，将中间建模的代码保存为transport_02.mapl文件。然后运行如下code，结果同方法1。
clear model;#清除model，多次run的时候使用 #------------------------------ model model/transport_02.mapl; #通过导入建模脚本.mapl文件进行建模 #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 display; print "-----------------结果---------------"; print "最小成本 = "; print sum { <o, d> in LINKS } cost[o, d] * Trans[o, d];
4. 结果解析
display指令运行时，会打印出很多求解的结果，Trans@name 是决策变量的取值，后面的dual solution是对偶解的值。示意如下：
Primal Solution: Trans@<GARY,DET> = 0.000000000000000E+00 Trans@<GARY,LAN> = 0.000000000000000E+00 Trans@<GARY,STL> = 8.000000000000000E+02 Trans@<GARY,LAF> = 6.000000000000000E+02 Trans@<CLEV,DET> = 1.200000000000000E+03 Trans@<CLEV,LAN> = 6.000000000000000E+02 Trans@<CLEV,STL> = 0.000000000000000E+00 Trans@<CLEV,LAF> = 4.000000000000000E+02 Trans@<CLEV,FRA> = 0.000000000000000E+00 Trans@<CLEV,WIN> = 4.000000000000000E+02 Trans@<PITT,STL> = 9.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,WIN> = 0.000000000000000E+00 Trans@<PITT,FRE> = 1.100000000000000E+03 Dual Solution: Supply_1 = 0.000000000000000E+00 Supply_2 = 9.000000000000000E+00 Supply_3 = 1.200000000000000E+01 Demand_1 = 1.200000000000000E+01 Demand_2 = 0.000000000000000E+00 Demand_3 = 3.000000000000000E+00 Demand_4 = 0.000000000000000E+00 Demand_5 = 1.600000000000000E+01 Demand_6 = 8.000000000000000E+00 -----------------结果--------------- 最小成本 = 201700
同时，在最近建模的文件所在目录或option modelname指定的位置，会生成对应的文件.nl和.sol。其中.nl文件是建模的问题模型文件，可被多数求解器识别，.sol文件中存储了求解结果solution。
从打印的结果，我们可以得到该公司的最低运输成本为201700元。并且此成本时，运输方案是：
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,LAF> = 6.000000000000000E+02 Trans@<GARY,STL> = 8.000000000000000E+02 Trans@<PITT,FRA> = 9.000000000000000E+02 Trans@<PITT,FRE> = 1.100000000000000E+03 Trans@<PITT,STL> = 9.000000000000000E+02
可以看出，在运输路径不一样的时候，会带来运输方案和最低成本不一样。
