备案控制台
开发者社区 达摩院 MindOpt 优化 文章 正文

运输问题的建模优化——MindOpt

2023-04-14 191
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： MindOpt在使用单纯形法求解线性规划问题这一功能上已经取得了不错的成绩，但在实际生活中，可能会遇到一些结构特殊的线性规划问题，这类问题可能存在比单纯形法更加简便的算法。本篇小编将介绍MindOpt如何求解这么一类特殊结构的线性规划问题——运输问题。

本篇是运输问题系列的第一篇，案例在云上建模求解平台可供复制学习。

问题描述

一般的运输问题是计算如何把某个商品从几个不同的产地，运输到几个不同的目的地，并知道运输量需求、不同运输路径的成本，或者不同目的地的需求等信息。问题如下：


某公司在如下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元/吨

数学规划模型

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


集合

  • 起点集合 image.png
  • 目的地集合 image.png


参数

  • 起点image.png的商品产量 image.png
  • 目的地 image.png的商品需求 image.png
  • 每吨商品从起点image.png运输至目的地 image.png所需成本 image.png


决策变量


起点image.png运送到目的地image.png的商品数量image.png


目标函数

工厂要最小化运输成本： image.png


约束


  • 起点image.png运送到各个目的地货物的总量等于其商品产量 image.png
  • 不同起点运送到目的地image.png的商品总量等于目的地商品的需求 image.png


使用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

更多更新通知：https://solver.damo.alibaba.com

文章标签：
C++
算法
存储
关键词：
优化求解器建模
决策智能Lab_运营小编003
目录
相关文章
决策智能Lab_运营小编003
|
3天前
|
达摩院 开发者 容器
「达摩院MindOpt」优化形状切割问题（MILP）
在制造业，高效地利用材料不仅是节约成本的重要环节，也是可持续发展的关键因素。无论是在金属加工、家具制造还是纺织品生产中，原材料的有效利用都直接影响了整体效率和环境影响。
决策智能Lab_运营小编003
87 0
「达摩院MindOpt」优化形状切割问题（MILP）
决策智能Lab_运营小编003
|
3天前
|
人工智能 自然语言处理 达摩院
MindOpt 云上建模求解平台：多求解器协同优化
数学规划是一种数学优化方法，主要是寻找变量的取值在特定的约束情况下，使我们的决策目标得到一个最大或者最小值的决策。
决策智能Lab_运营小编003
134 0
决策智能Lab_运营小编003
|
3天前
|
存储 达摩院 调度
「达摩院MindOpt」优化FlowShop流水线作业排班问题
在企业在面临大量多样化的生产任务时，如何合理地安排流水线作业以提高生产效率及确保交货期成为了一个重要的问题。
决策智能Lab_运营小编003
81 0
「达摩院MindOpt」优化FlowShop流水线作业排班问题
决策智能Lab_运营小编003
|
3天前
MindOpt APL建模语言自定小义函数的重要性和示例
在编程和建模语言中，函数是一段独立的、可重复使用的代码块，用于执行特定任务。在MindOpt APL中，自定义函数的使用非常重要，因为它们提高了建模过程的效率、可读性和灵活性。
决策智能Lab_运营小编003
47 0
决策智能Lab_运营小编003
|
3天前
|
人工智能 算法 决策智能
MindOpt云上建模求解平台功能的简单介绍
MindOpt云上建模求解平台是阿里巴巴达摩院研发的一款“优化领域”的云平台。它结合了最新的算法研究和云技术，为用户提供了一个易于使用的界面和强大的后台计算能力。该平台支持广泛的优化问题，包括线性规划、整数规划、非线性规划和混合整数规划等。
决策智能Lab_运营小编003
116 0
决策智能Lab_运营小编003
|
10月前
|
达摩院 调度
使用达摩院MindOpt优化交通调度_最大化通行量—线性规划问题
在数学规划中，网络流问题是指一类基于网络模型的流量分配问题。网络流问题的目标是在网络中分配资源，使得网络的流量满足一定的限制条件，并且使得某些目标函数最小或最大化。网络流问题通常涉及一个有向图，图中每个节点表示一个资源，每条边表示资源之间的关系。边上有一个容量值，表示该边上最多可以流动的资源数量。流量从源节点开始流出，经过一系列中间节点，最终到达汇节点。在这个过程中，需要遵守一定的流量守恒和容量限制条件。
决策智能Lab_运营小编003
129 0
决策智能Lab_运营小编003
|
6月前
|
达摩院 数据格式 索引
「达摩院MindOpt APL 建模语言」语法说明 print 将结果写表格文件
不同的编程语言写入表格文件的方式均不相同，下面将展示MindOpt APL建模语言的方式。
决策智能Lab_运营小编003
61 1
决策智能Lab_运营小编003
|
6月前
|
API Python
MindOpt V1.0优化种植计划问题，新的建模方法
种植计划是指农业生产中针对不同农作物的种植时间、面积和种植方式等方面的规划安排。根据具体情况进行合理的规划和安排，以实现农作物的高产、优质和可持续发展。
决策智能Lab_运营小编003
75 0
MindOpt V1.0优化种植计划问题，新的建模方法
决策智能Lab_运营小编003
|
10月前
|
达摩院 供应链 JavaScript
网络流：优化仓储物流调度问题-达摩院MindOpt
仓储物流调度是指在物流供应链中，对仓储和运输（运输路线、成本）进行协调和安排的过程。主要包含物流计划、运输调度、运发管理、库存管理等重要环节。随着网络、电商行业的迅速发展，仓储物流调度对于企业来说也非常重要，优秀的调度方案可以帮助降低库存成本、物流配送的效率、成本等等等，从而给企业带来降本增效。
决策智能Lab_运营小编003
224 0
网络流：优化仓储物流调度问题-达摩院MindOpt
决策智能Lab_运营小编003
|
10月前
|
数据可视化
MindOpt优化如何分散化风险并实现收益与风险最优配比问题
资产配置，投资组合是指通过分散投资资金的方式来规避投资过程中的风险。在实际的投资过程中，如何决定投资哪些产品来实现收益最大化和风险最小化是一个关键的问题。
决策智能Lab_运营小编003
107 0
MindOpt优化如何分散化风险并实现收益与风险最优配比问题

达摩院 MindOpt 优化

热门文章

最新文章

  • 1
    MindOpt APL 最新版本功能介绍，并且开放下载使用了！
  • 2
    SQL优化器原理 - Auto Hash Join
  • 3
    PostgreSQL 9.6 并行计算 优化器算法浅析
  • 4
    浅析Oracle 10gR2中优化器对表关联的优化
  • 5
    使用智能优化器提高Oracle的性能极限
  • 6
    【CBO Optimizer优化器】IX_SEL索引选择率
  • 7
    PolarDB-X 面向 HTAP 的 CBO 优化器
  • 8
    让SQL优化器更准确！AnalyticDB PG版发布统计信息自动收集功能
  • 9
    SQL Server优化器特性-隐式谓词
  • 10
    Oracle数据的优化器有两种优化方法：
  • 1
    阿里达摩院MindOpt优化求解器-月刊（2024年2月）
    97
  • 2
    阿里达摩院MindOpt优化求解器-月刊（2024年1月）
    91
  • 3
    如何通过阿里达摩院MindOpt获得MILP多个解
    111
  • 4
    阿里达摩院MindOpt求解器V1.1新增C#接口
    144
  • 5
    「达摩院MindOpt」优化形状切割问题（MILP）
    87
  • 6
    「达摩院MindOpt」优化FlowShop流水线作业排班问题
    81
  • 7
    MindOpt APL建模语言自定小义函数的重要性和示例
    47
  • 8
    阿里达摩院MindOpt优化求解器-月刊（2023年12月）
    80
  • 9
    MindOpt 云上建模求解平台：多求解器协同优化
    134
  • 10
    PyTorch基础之优化器模块、训练和测试模块讲解（附源码）
    76

    • 相关课程

    更多
  • 场景实践 - 基于阿里云PAI机器学习平台使用时间序列分解模型预测商品销量
  • 达摩院MindOpt优化求解器入门与实践
  • 场景实践 - 机器学习PAI实现精细化营销
  • 场景实践 - 基于机器学习进行收入预测分析
  • 【算法实战】7. 集成方法-随机森林
  • 【新人赛】工业蒸汽量预测建模算法代码开源分享合集

    • 相关电子书

    更多
  • 阿里技术专家一挃：MongoDB 优化器 & 执行器介绍
  • 智能运维里的时间序列：异常检测、根源分析、预测
  • AIOps 自适应机器学习异常检测

    • 相关实验场景

    更多
  • 基于阿里云E-HPC和OpenFoam进行流体仿真实验
  • 【企业数据中台交付】数据回刷实验
  • 汽车产线生产管控实操
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考