运输问题的建模优化(三)——MindOpt

简介: 本系列将讲解多篇运输问题的示例,讲解对于不同的运输问题场景,用数学规划的方法进行线性规划问题建模,并进行求解得到解决方案。

上一篇问题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. 数学规划模型

以上问题,我们可以建立线性规划的数学模型如下。

集合

image.png

参数

image.png

决策变量

image.png

目标函数

image.png

约束

image.png

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元。


相关文章
|
6月前
|
达摩院 开发者 容器
「达摩院MindOpt」优化形状切割问题(MILP)
在制造业,高效地利用材料不仅是节约成本的重要环节,也是可持续发展的关键因素。无论是在金属加工、家具制造还是纺织品生产中,原材料的有效利用都直接影响了整体效率和环境影响。
「达摩院MindOpt」优化形状切割问题(MILP)
|
1月前
|
机器学习/深度学习 算法 数据可视化
如果你的PyTorch优化器效果欠佳,试试这4种深度学习中的高级优化技术吧
在深度学习领域,优化器的选择对模型性能至关重要。尽管PyTorch中的标准优化器如SGD、Adam和AdamW被广泛应用,但在某些复杂优化问题中,这些方法未必是最优选择。本文介绍了四种高级优化技术:序列最小二乘规划(SLSQP)、粒子群优化(PSO)、协方差矩阵自适应进化策略(CMA-ES)和模拟退火(SA)。这些方法具备无梯度优化、仅需前向传播及全局优化能力等优点,尤其适合非可微操作和参数数量较少的情况。通过实验对比发现,对于特定问题,非传统优化方法可能比标准梯度下降算法表现更好。文章详细描述了这些优化技术的实现过程及结果分析,并提出了未来的研究方向。
25 1
|
4月前
|
人工智能 算法 调度
优化问题之如何选择合适的优化求解器
优化问题之如何选择合适的优化求解器
|
4月前
|
调度 决策智能
优化问题之优化求解器有哪些主要的评估特性
优化问题之优化求解器有哪些主要的评估特性
|
6月前
|
机器学习/深度学习 算法 测试技术
MindOpt APL向量化建模语法的介绍与应用(1)
向量化建模是一种高效的数学建模和编程技术,它涉及到对向量、矩阵和更高维数组进行操作,以实现操作的同时性和批量处理。在优化和数据分析等领域,向量化建模可以极大地提高计算效率,特别是当涉及到大量的重复计算时。由于向量化建模具有表述优势、操作优势、计算性能、可扩展性等优势,使得其适合于解决很大一类实际问题
|
6月前
|
测试技术 索引
MindOpt APL向量化建模语法的介绍与应用(2)
在数据科学、工程优化和其他科学计算领域中,向量和矩阵的运算是核心组成部分。MAPL作为一种数学规划语言,为这些领域的专业人员提供了强大的工具,通过向量式和矩阵式变量声明以及丰富的内置数学运算支持,大大简化了数学建模和优化问题的处理。在本文中,我们将探索MAPL的这些特性,并且通过示例来展示如何有效使用这些工具。
|
6月前
|
存储 达摩院 调度
「达摩院MindOpt」优化FlowShop流水线作业排班问题
在企业在面临大量多样化的生产任务时,如何合理地安排流水线作业以提高生产效率及确保交货期成为了一个重要的问题。
「达摩院MindOpt」优化FlowShop流水线作业排班问题
|
6月前
|
SQL 关系型数据库 数据库
ADBPG优化基础(一)ORCA优化器
AnalyticDB PostgreSQL(ADBPG)就是一堆并行的PostgreSQL?当然不是!ADBPG作为一个基于PostgreSQL的Massively Parallel Processing(MPP)全并行架构的分析型数据库,针对数据分析场景在很多方面得到了加强。如双优化器(GPORC...
ADBPG优化基础(一)ORCA优化器
|
6月前
|
人工智能 自然语言处理 达摩院
MindOpt 云上建模求解平台:多求解器协同优化
数学规划是一种数学优化方法,主要是寻找变量的取值在特定的约束情况下,使我们的决策目标得到一个最大或者最小值的决策。
|
达摩院 调度
使用达摩院MindOpt优化交通调度_最大化通行量—线性规划问题
在数学规划中,网络流问题是指一类基于网络模型的流量分配问题。网络流问题的目标是在网络中分配资源,使得网络的流量满足一定的限制条件,并且使得某些目标函数最小或最大化。网络流问题通常涉及一个有向图,图中每个节点表示一个资源,每条边表示资源之间的关系。边上有一个容量值,表示该边上最多可以流动的资源数量。流量从源节点开始流出,经过一系列中间节点,最终到达汇节点。在这个过程中,需要遵守一定的流量守恒和容量限制条件。