比上一篇问题02进一步复杂化，我们把1种产品增加为3种产品，并且限制了货运量的总和。
本篇为第三篇，往期如下：
运输问题（三）
1. 问题描述和数学规划模型
某公司打算在GARY,CLEV,PITT 三个地方生产三种产品：bands，coils，plate。具体生产数量如下表所示：
GARY |
CLEV |
PITT |
|
bands |
400吨 |
700吨 |
800吨 |
coils |
800吨 |
1600吨 |
1000吨 |
plate |
200吨 |
300吨 |
300吨 |
这些产品将被运送到7个地点去销售，每个地点对这三个产品的需求各不相同，具体如图所示：
FRA |
DET |
LAN |
WIN |
STL |
FRE |
LAF |
|
bands |
300吨 |
300吨 |
100吨 |
75吨 |
650吨 |
225吨 |
250吨 |
coils |
500吨 |
750吨 |
400吨 |
250吨 |
950吨 |
850吨 |
500吨 |
plate |
100吨 |
100吨 |
0吨 |
50吨 |
200吨 |
100吨 |
250吨 |
已知将每吨不同的产品从不同的产地运送到不同的目的地的成本各不相同：
bands |
coils |
plate |
|
GARY , FRA |
30元/吨 |
39元/吨 |
41元/吨 |
GARY, DET |
10元/吨 |
14元/吨 |
15元/吨 |
GARY , LAN |
8元/吨 |
11元/吨 |
12元/吨 |
GARY, WIN |
10元/吨 |
14元/吨 |
16元/吨 |
GARY , STL |
11元/吨 |
16元/吨 |
17元/吨 |
GARY , FRE |
71元/吨 |
82元/吨 |
86元/吨 |
GARY , LAF |
6元/吨 |
8元/吨 |
8元/吨 |
CLEV , FRA |
22元/吨 |
27元/吨 |
29元/吨 |
CLEV , DET |
7元/吨 |
9元/吨 |
9元/吨 |
CLEV , LAN |
10元/吨 |
12元/吨 |
13元/吨 |
CLEV , WIN |
7元/吨 |
9元/吨 |
9元/吨 |
CLEV , STL |
21元/吨 |
26元/吨 |
28元/吨 |
CLEV ,FRE |
82元/吨 |
95元/吨 |
99元/吨 |
CLEV , LAF |
13元/吨 |
17元/吨 |
18元/吨 |
PITT , FRA |
19元/吨 |
24元/吨 |
26元/吨 |
PITT , DET |
11元/吨 |
14元/吨 |
14元/吨 |
PITT, LAN |
12元/吨 |
17元/吨 |
17元/吨 |
PITT , WIN |
10元/吨 |
13元/吨 |
13元/吨 |
PITT , STL |
25元/吨 |
28元/吨 |
31元/吨 |
PITT , FRE |
83元/吨 |
99元/吨 |
104元/吨 |
PITT , LAF |
15元/吨 |
20元/吨 |
20元/吨 |
现规定某起点到某个目的地运输三种商品的货量总和不得超过625吨，请问该如何分配运输到每个目的地的产品使得总成本最低？
2. 数学规划模型
以上问题，我们可以建立线性规划的数学模型如下。
集合
参数
决策变量
目标函数
约束
2. 使用MindOpt APL进行建模和求解
MindOpt建模语言(MindOpt Algebra Programming Language, MindOpt APL达摩院自己的建模语言，简称为MAPL)是一种高效且通用的代数建模语言。当前主要用于数学规划问题的建模，并支持调用多种求解器求解。下面将演示如何使用MAPL将上面的数学模型公式和数据输入，生成一个求解器可求解的问题，再调用求解器去进行求解。
阿里巴巴达摩院：https://damo.alibaba.com/
方法1：cell中直接输入建模代码运行
在求解数独问题时，MindOpt APL可以将其建模代码直接输入如下cell里运行。请注意内核（kernel）需要选MAPL。
其中，有一行我们增加do check的语句来进行验证，确保总产量等于总需求。
clear model;#清除model，多次run的时候使用 option modelname model/transport_03;#方便与方法2的中间文件生成在同一个目录 #---------建模----------------- # transport_03.mapl set ORIG := {"GARY", "CLEV", "PITT"}; # origins set DEST := {"FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"}; # destinations set PROD := {"bands", "coils", "plate"}; # products set ODP := ORIG * DEST * PROD; # 产地的各产品的生产数量 param supply[PROD * ORIG] := |"GARY", "CLEV", "PITT"| |"bands" | 400, 700, 800 | |"coils" | 800, 1600, 1800 | |"plate" | 200, 300, 300 |; # 目的地的需求量 param demand[PROD * DEST] := |"FRA", "DET", "LAN", "WIN", "STL", "FRE", "LAF"| |"bands" | 300, 300, 100, 75, 650, 225, 250 | |"coils" | 500, 750, 400, 250, 950, 850, 500 | |"plate" | 100, 100, 0, 50, 200, 100, 250 |; # 不同产品不同运输路径的成本 # 注意，输入这个多维表格时，列坐标需要是1维的，横坐标可以是多维的。 param cost[ORIG * DEST * PROD] := | "bands", "coils", "plate" | |"GARY", "FRA"| 30, 39, 41 | |"GARY", "DET"| 10, 14, 15 | |"GARY", "LAN"| 8, 11, 12 | |"GARY", "WIN"| 10, 14, 16 | |"GARY", "STL"| 11, 16, 17 | |"GARY", "FRE"| 71, 82, 86 | |"GARY", "LAF"| 6, 8, 8 | |"CLEV", "FRA"| 22, 27, 29 | |"CLEV", "DET"| 7, 9, 9 | |"CLEV", "LAN"| 10, 12, 13 | |"CLEV", "WIN"| 7, 9, 9 | |"CLEV", "STL"| 21, 26, 28 | |"CLEV", "FRE"| 82, 95, 99 | |"CLEV", "LAF"| 13, 17, 18 | |"PITT", "FRA"| 19, 24, 26 | |"PITT", "DET"| 11, 14, 14 | |"PITT", "LAN"| 12, 17, 17 | |"PITT", "WIN"| 10, 13, 13 | |"PITT", "STL"| 25, 28, 31 | |"PITT", "FRE"| 83, 99, 104 | |"PITT", "LAF"| 15, 20, 20 |; # 总运输量的限制 param limit[ORIG * DEST] := default 625; var Trans [<o, d, p> in ORIG * DEST * PROD] >= 0; # units to be shipped minimize Total_Cost: sum {<o, d, p> in ODP } cost[o, d, p] * Trans[o, d, p]; subto Supply: forall {<o, p> in ORIG * PROD} sum { <d> in DEST} Trans[o, d, p] == supply[p, o]; subto Demand: forall { <d, p> in DEST * PROD} sum { <o> in ORIG } Trans[o, d, p] == demand[p, d]; subto Multi: forall { <o, d> in ORIG * DEST} sum {<p> in PROD} Trans[o, d, p] <= limit[o, d]; #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 #display; #打印求解变量值，比较长，请删除注释#后进行打印 print "-----------------结果---------------"; print "最小成本 = "; print sum {<o, d, p> in ODP } cost[o, d, p] * Trans[o, d, p];
运行代码得到的结果如下：
-----------------用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:39:34). License validation terminated. Time : 0.003s Model summary. - Num. variables : 63 - Num. constraints : 51 - Num. nonzeros : 189 - Bound range : [5.0e+01,1.0e+20] - Objective range : [6.0e+00,1.0e+02] - Matrix range : [1.0e+00,1.0e+00] Presolver started. Presolver terminated. Time : 0.000s Simplex method started. Model fingerprint: =Y2diFmZ3dWY3N2Y Iteration Objective Dual Inf. Primal Inf. Time 0 0.00000e+00 0.0000e+00 1.3800e+04 0.00s 35 1.99500e+05 0.0000e+00 0.0000e+00 0.00s Postsolver started. Simplex method terminated. Time : 0.003s OPTIMAL; objective 199500.00 35 simplex iterations Completed. -----------------结果--------------- 最小成本 = 199500
方法2：导入.mapl文件运行建模然后求解
上面时直接在cell中运行所有的脚本，我们也可以建立个新文档，将中间建模的代码保存为transport_03.mapl文件。然后运行如下code，结果同方法1。
clear model;#清除model，多次run的时候使用 #------------------------------ model model/transport_03.mapl; #通过导入建模脚本.mapl文件进行建模 #------------------------------ print "-----------------用MindOpt求解---------------"; option solver mindopt; # 指定求解用MindOpt求解器 solve; # 求解 #display; #打印求解变量值，比较长，请删除注释#后进行打印 print "-----------------结果---------------"; print "最小成本 = "; print sum {<o, d, p> in ODP } cost[o, d, p] * Trans[o, d, p];
运行结果与方法1一致
3. 结果解析
display指令运行时，会打印出很多求解的结果，Trans@name 是决策变量的取值，后面的dual solution是对偶解的值。示意如下：
display; #运行 #输出： Primal Solution: Trans@<GARY,FRA,bands> = 0.000000000000000E+00 Trans@<GARY,FRA,coils> = 0.000000000000000E+00 Trans@<GARY,FRA,plate> = 0.000000000000000E+00 Trans@<GARY,DET,bands> = 0.000000000000000E+00 Trans@<GARY,DET,coils> = 0.000000000000000E+00 Trans@<GARY,DET,plate> = 0.000000000000000E+00 Trans@<GARY,LAN,bands> = 0.000000000000000E+00 Trans@<GARY,LAN,coils> = 0.000000000000000E+00 Trans@<GARY,LAN,plate> = 0.000000000000000E+00 Trans@<GARY,WIN,bands> = 0.000000000000000E+00 Trans@<GARY,WIN,coils> = 0.000000000000000E+00 Trans@<GARY,WIN,plate> = 0.000000000000000E+00 Trans@<GARY,STL,bands> = 4.000000000000000E+02 Trans@<GARY,STL,coils> = 2.500000000000000E+01 Trans@<GARY,STL,plate> = 2.000000000000000E+02 Trans@<GARY,FRE,bands> = 0.000000000000000E+00 Trans@<GARY,FRE,coils> = 6.250000000000000E+02 Trans@<GARY,FRE,plate> = 0.000000000000000E+00 Trans@<GARY,LAF,bands> = 0.000000000000000E+00 Trans@<GARY,LAF,coils> = 1.500000000000000E+02 Trans@<GARY,LAF,plate> = 0.000000000000000E+00 Trans@<CLEV,FRA,bands> = 2.750000000000000E+02 Trans@<CLEV,FRA,coils> = 0.000000000000000E+00 Trans@<CLEV,FRA,plate> = 0.000000000000000E+00 Trans@<CLEV,DET,bands> = 0.000000000000000E+00 Trans@<CLEV,DET,coils> = 5.250000000000000E+02 Trans@<CLEV,DET,plate> = 1.000000000000000E+02 Trans@<CLEV,LAN,bands> = 0.000000000000000E+00 Trans@<CLEV,LAN,coils> = 4.000000000000000E+02 Trans@<CLEV,LAN,plate> = 0.000000000000000E+00 Trans@<CLEV,WIN,bands> = 7.500000000000000E+01 Trans@<CLEV,WIN,coils> = 2.500000000000000E+02 Trans@<CLEV,WIN,plate> = 5.000000000000000E+01 Trans@<CLEV,STL,bands> = 2.500000000000000E+02 Trans@<CLEV,STL,coils> = 3.000000000000000E+02 Trans@<CLEV,STL,plate> = 0.000000000000000E+00 Trans@<CLEV,FRE,bands> = 0.000000000000000E+00 Trans@<CLEV,FRE,coils> = 5.000000000000000E+01 Trans@<CLEV,FRE,plate> = 1.000000000000000E+02 Trans@<CLEV,LAF,bands> = 1.000000000000000E+02 Trans@<CLEV,LAF,coils> = 7.500000000000000E+01 Trans@<CLEV,LAF,plate> = 5.000000000000000E+01 Trans@<PITT,FRA,bands> = 2.500000000000000E+01 Trans@<PITT,FRA,coils> = 5.000000000000000E+02 Trans@<PITT,FRA,plate> = 1.000000000000000E+02 Trans@<PITT,DET,bands> = 3.000000000000000E+02 Trans@<PITT,DET,coils> = 2.250000000000000E+02 Trans@<PITT,DET,plate> = 0.000000000000000E+00 Trans@<PITT,LAN,bands> = 1.000000000000000E+02 Trans@<PITT,LAN,coils> = 0.000000000000000E+00 Trans@<PITT,LAN,plate> = 0.000000000000000E+00 Trans@<PITT,WIN,bands> = 0.000000000000000E+00 Trans@<PITT,WIN,coils> = 0.000000000000000E+00 Trans@<PITT,WIN,plate> = 0.000000000000000E+00 Trans@<PITT,STL,bands> = 0.000000000000000E+00 Trans@<PITT,STL,coils> = 6.250000000000000E+02 Trans@<PITT,STL,plate> = 0.000000000000000E+00 Trans@<PITT,FRE,bands> = 2.250000000000000E+02 Trans@<PITT,FRE,coils> = 1.750000000000000E+02 Trans@<PITT,FRE,plate> = 0.000000000000000E+00 Trans@<PITT,LAF,bands> = 1.500000000000000E+02 Trans@<PITT,LAF,coils> = 2.750000000000000E+02 Trans@<PITT,LAF,plate> = 2.000000000000000E+02 Dual Solution: Supply_1 = 4.000000000000002E+00 Supply_2 = 8.000000000000000E+00 Supply_3 = 8.000000000000004E+00 Supply_4 = 1.300000000000000E+01 Supply_5 = 1.700000000000000E+01 Supply_6 = 1.800000000000000E+01 Supply_7 = 1.600000000000001E+01 Supply_8 = 2.100000000000001E+01 Supply_9 = 2.100000000000001E+01 Demand_1 = 9.000000000000002E+00 Demand_2 = 9.000000000000002E+00 Demand_3 = 1.100000000000000E+01 Demand_4 = -5.000000000000004E+00 Demand_5 = -7.000000000000006E+00 Demand_6 = -8.000000000000007E+00 Demand_7 = -4.000000000000005E+00 Demand_8 = -5.000000000000000E+00 Demand_9 = -5.000000000000000E+00 Demand_10 = -6.000000000000001E+00 Demand_11 = -7.999999999999999E+00 Demand_12 = -9.000000000000000E+00 Demand_13 = 8.000000000000000E+00 Demand_14 = 9.000000000000002E+00 Demand_15 = 9.999999999999998E+00 Demand_16 = 6.700000000000000E+01 Demand_17 = 7.800000000000000E+01 Demand_18 = 8.100000000000000E+01 Demand_19 = 0.000000000000000E+00 Demand_20 = 0.000000000000000E+00 Demand_21 = 0.000000000000000E+00 Multi_1 = 0.000000000000000E+00 Multi_2 = 0.000000000000000E+00 Multi_3 = 0.000000000000000E+00 Multi_4 = 0.000000000000000E+00 Multi_5 = -1.000000000000001E+00 Multi_6 = -4.000000000000004E+00 Multi_7 = 0.000000000000000E+00 Multi_8 = 0.000000000000000E+00 Multi_9 = -9.999999999999931E-01 Multi_10 = 0.000000000000000E+00 Multi_11 = 0.000000000000000E+00 Multi_12 = 0.000000000000000E+00 Multi_13 = 0.000000000000000E+00 Multi_14 = 0.000000000000000E+00 Multi_15 = -6.000000000000007E+00 Multi_16 = 0.000000000000000E+00 Multi_17 = 0.000000000000000E+00 Multi_18 = 0.000000000000000E+00 Multi_19 = -2.000000000000008E+00 Multi_20 = 0.000000000000000E+00 Multi_21 = -1.000000000000005E+00
同时，在最近建模的文件所在目录或option modelname指定的位置，会生成对应的文件.nl和.sol。其中.nl文件是建模的问题模型文件，可被多数求解器识别，.sol文件中存储了求解结果solution。
从打印的结果，我们可以得到该公司的最低运输成本为199500元。
