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

混合整数线性规划-仓库选址问题-达摩院MindOpt

2023-07-28 713
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 仓库选址问题是一个重要的运筹学问题，它涉及到在一个给定的地理区域中选择最佳的仓库位置以最小化总成本或者提高效率。仓库选址问题在现代物流和供应链管理中具有重要的应用，因为仓库的位置直接影响到货物的运输成本、交货时间和库存量等因素。

仓库选址规划


仓库选址问题是一个重要的运筹学问题，它涉及到在一个给定的地理区域中选择最佳的仓库位置以最小化总成本或者提高效率。仓库选址问题在现代物流和供应链管理中具有重要的应用，因为仓库的位置直接影响到货物的运输成本、交货时间和库存量等因素。

image.png


为了解决这个问题，我们可以使用数学规划的方法，通过建立一个数学模型来优化仓库位置和相应的服务水平。这个仓库选址模型可以考虑多种因素，如仓库建设、运输成本、库存成本、交货需求等。这些因素可以通过如下方式进行量化和搜集数据。


  • 仓库建设成本：建设仓库的直接成本，包括土地成本、建筑成本、设备成本等。在实际应用中，这个成本因素通常是已知的，因为仓库建设成本是比较稳定的，可以通过市场价格或者预算来确定。
  • 运输成本：将货物从仓库运输到客户所需的成本。这个成本因素通常包括运输距离、运输方式、运输时间、运输成本等因素。在实际应用中，这个成本因素通常是在经过一定的调查和分析之后得出的，可以通过运输网络模型、运输成本数据库或者实地考察等方式来确定。
  • 库存成本：库存成本是在仓库中维护和管理存货所需的成本。这个成本因素包括存储成本、订单处理成本、库存租金、保险费用等。在实际应用中，我们需要通过调查和分析得出这些成本因素，以便在模型中考虑到它们对总成本的影响。
  • 交货需求：交货需求是指客户对货物的需求量。这个数据可以通过客户的订单量、历史数据等方式来获取。在实际应用中，我们需要考虑到客户对不同仓库的需求量，以便在模型中考虑到它对总成本的影响。


下面我们将通过一个简单的例子，讲解如何使用数学规划的方法来建模仓库选址的问题，并调用MindOpt APL来编程和求解问题。

1. 问题描述


考虑如下决策问题，某公司拥有9家商店，现需要建造工厂为商店提供商品。已知有ABCD四种工厂类型，每种工厂最多建造一个，建造不同的工厂的成本各不相同，A需要500，B需要600，C需要700，D需要800.不同的工厂拥有不同的库存容量，A为40，B为55，C为73，D为90。对于9家商店而言，其对商品的需求量各不相同，具体如下表所示：

商店

商品需求

1

10

2

14

3

17

4

8

5

9

6

12

7

11

8

15

9

16


并且，不同的工厂将货物运送到不同商店的代价也不相同，如下表所示：

商店1

商店2

商店3

商店4

商店5

商店6

商店7

商店8

商店9

A

55

4

17

33

47

98

19

10

6

B

42

12

4

23

16

78

47

9

82

C

17

34

65

25

7

67

45

13

54

D

60

8

79

24

28

19

62

18

45


本篇案例为了简化问题，我们假设每家商店仅能由一家工厂供货。

请问该建造哪些工厂，以及决定这些工厂向哪些商店供货，才能使得总成本最低？

2. 数学规划模型


以上问题的数学模型如下。


集合


  • 工厂集合 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。如果image.png，则表示image.png工厂将运送商品给image.png商店；如果image.png，则表示image.png工厂没有把商品运送给image.png商店。

目标函数


最小化建造及运输代价: image.png

约束

  • 每个商场仅有一个供货工厂：image.png
  • 只有建设了工厂才能提供货物给商店：image.png
  • 每间工厂的库存不能小于其所提供的商店的需求之和：image.png


这里我们汇总的等价数学建模公式是

image.png

3. MindOpt APL 建模和求解


MindOpt APL是一款代数建模语言，它可以方便地将数学语言描述成程序，然后调用多种求解器求解。MindOpt Solver对网络流的线性规划求解效率很不错，且能支持大规模的问题。


改写上面的数据图和数学模型，如下代码，在Notebook的cell中运行它：

clear model;
# 建模
# factory.mapl
# 声明集合
set PLANTS  := { "A" , "B" , "C" , "D" };
set STORES  := { 1 .. 9 };
# 声明参数
param building[PLANTS]:= <"A"> 500 , <"B"> 600 , <"C"> 700 , <"D"> 800;
param capacity[PLANTS]:= <"A"> 40 , <"B"> 55 , <"C"> 73 , <"D"> 90;
param demand [STORES]   :=  <1> 10 , <2> 14 ,
                            <3> 17 , <4> 8 ,
                            <5> 9 , <6> 12 ,
                            <7> 11 , <8> 15 ,
                            <9> 16;
param transport[PLANTS * STORES] :=
     |1,    2,  3,  4,  5,  6,  7,  8,  9|
|"A" |55,   4,  17, 33, 47, 98, 19, 10, 6|
|"B" |42,   12, 4,  23, 16, 78, 47, 9,  82|
|"C" |17,   34, 65, 25, 7,  67, 45, 13, 54|
|"D" |60,   8,  79, 24, 28, 19, 62, 18, 45|;
# 声明变量
var z[PLANTS]   binary;
var x[PLANTS * STORES]  binary;
# 声明目标
minimize cost:  sum {<p> in  PLANTS }  building[p] * z[p]
                    + sum {<p,s> in PLANTS * STORES }  transport[p,s] * x[p,s];
# 声明约束
subto assign:
    forall {<s> in STORES } 
        sum {<p> in PLANTS } x[p,s] == 1;
subto build:
    forall {<p,s> in PLANTS * STORES }
                z[p] >= x[p,s] ;
subto limit:
    forall {<p> in PLANTS }
        capacity[p] >= sum {<s> in STORES } demand[s] * x[p,s];
print "-----------------用MindOpt求解---------------";
option solver mindopt;     # （可选）指定求解用的求解器，默认是MindOpt
#option mindopt_options 'print=0'; #设置求解器输出级别，减少过程打印
solve;         # 求解
# 可以切换其他的求解器
#option solver cbc;    
#option cbc_options 'log=0'; #设置求解器输出级别，减少过程打印
#solve;         # 求解
print "-----------------Display---------------";
display;        # 展示结果
print "经过优化后，最小成本=" ,sum {<p> in  PLANTS }  building[p] * z[p]
                    + sum {<p,s> in PLANTS * STORES }  transport[p,s] * x[p,s];
print "其中，建立的工厂和对应的运输路线是：";
forall {<p,s>in PLANTS*STORES with z[p]>=1 and x[p,s] >= 1}
      print p,",供货给商店：",s;

运行代码结果为：

-----------------用MindOpt求解---------------
Running mindoptampl
wantsol=1
MindOpt Version 0.24.1 (Build date: 20230423)
Copyright (c) 2020-2023 Alibaba Cloud.
Start license validation (current time : 05-JUL-2023 20:38:44).
License validation terminated. Time : 0.006s
Model summary.
 - Num. variables     : 40
 - Num. constraints   : 49
 - Num. nonzeros      : 144
 - Num. integer vars. : 40
 - Bound range        : [1.0e+00,9.0e+01]
 - Objective range    : [4.0e+00,8.0e+02]
Branch-and-cut method started.
Original model: nrow = 49 ncol = 40 nnz = 144
Tolerance: primal = 1e-06 int = 1e-06 mipgap = 0 mipgapAbs = 0.0001
Limit: time = 1.79769313486232e+308 node = -1 stalling = -1 solution = -1
presolver terminated; took 0 ms
presolver terminated; took 1 ms
Parallelism: root=1, tree=1
tree 0     node 0 accept new sol: obj 2056 (heur) bnd vio 0 int vio 0 mipgap 4.86381322957198e+96 time 0
Model summary.
 - Num. variables     : 40
 - Num. constraints   : 49
 - Num. nonzeros      : 144
 - Bound range        : [1.0e+00,9.0e+01]
 - Objective range    : [4.0e+00,8.0e+02]
 - Matrix range       : [1.0e+00,1.7e+01]
Presolver started.
Presolver terminated. Time : 0.000s
Simplex method started.
Model fingerprint: =Y2djNmZ3d2Y352Y
    Iteration       Objective       Dual Inf.     Primal Inf.     Time
            0     0.00000e+00      0.0000e+00      9.0000e+00     0.00s    
           41     8.86018e+02      0.0000e+00      0.0000e+00     0.00s    
Postsolver started.
Simplex method terminated. Time : 0.002s
tree 0 #node(P:0 Q:0) #(dep:0 max:0) #(dual:886.017857142857 best:2056 gap:56%) #(conf:0 cut:0) #time = 0
tree 0     node 0 accept new sol: obj 1854 (heur) bnd vio 0 int vio 0 mipgap 0.522104715672677 time 0
tree 0     node 0 accept new sol: obj 1743 (node) bnd vio 0 int vio 0 mipgap 0.491670764691419 time 0
tree 0     node 0 accept new sol: obj 1567 (heur) bnd vio 0 int vio 0 mipgap 0.43457698969824 time 0
tree 0     node 0 accept new sol: obj 1538 (node) bnd vio 0 int vio 0 mipgap 0.423915567527401 time 0
tree 0     node 0 accept new sol: obj 1457 (heur) bnd vio 2.22044604925031e-16 int vio 8.88178419700125e-16 mipgap 0.391888910677517 time 0
Restart
presolver terminated; took 1 ms
tree 1     node -1 accept new sol: obj 1457 (node) bnd vio 8.88178419700125e-16 int vio 8.88178419700125e-16 mipgap 6.86341798215511e+96 time 0
Parallelism: root=1, tree=1
tree 1 #node(P:0 Q:0) #(dep:0 max:0) #(dual:1067.39285714286 best:1457 gap:26%) #(conf:0 cut:65) #time = 0
Branch-and-cut method terminated. Time : 1.793s
OPTIMAL; objective 1457.00
Completed.
-----------------Display---------------
Primal Solution:
     z@A = 1
     z@B = 0
     z@C = 1
     z@D = 0
 x@<A,1> = 0
 x@<A,2> = 1
 x@<A,3> = 1
 x@<A,4> = 1
 x@<A,5> = 0
 x@<A,6> = 0
 x@<A,7> = 0
 x@<A,8> = 0
 x@<A,9> = 0
 x@<B,1> = 0
 x@<B,2> = 0
 x@<B,3> = 0
 x@<B,4> = 0
 x@<B,5> = 0
 x@<B,6> = 0
 x@<B,7> = 0
 x@<B,8> = 0
 x@<B,9> = 0
 x@<C,1> = 1
 x@<C,2> = 5.07530526e-16
 x@<C,3> = 0
 x@<C,4> = 2.22044605e-16
 x@<C,5> = 1
 x@<C,6> = 1
 x@<C,7> = 1
 x@<C,8> = 1
 x@<C,9> = 1
 x@<D,1> = 8.8817842e-16
 x@<D,2> = 0
 x@<D,3> = 0
 x@<D,4> = 0
 x@<D,5> = 0
 x@<D,6> = 0
 x@<D,7> = 0
 x@<D,8> = 0
 x@<D,9> = 0
经过优化后，最小成本=1457
其中，建立的工厂和对应的运输路线是：
A,供货给商店：2
A,供货给商店：3
A,供货给商店：4
C,供货给商店：1
C,供货给商店：5
C,供货给商店：6
C,供货给商店：7
C,供货给商店：8
C,供货给商店：9

4. 结果


运行上述代码后，得到结果为：

经过优化后，最小成本=1457
其中，建立的工厂和对应的运输路线是：
A,供货给商店：2
A,供货给商店：3
A,供货给商店：4
C,供货给商店：1
C,供货给商店：5
C,供货给商店：6
C,供货给商店：7
C,供货给商店：8
C,供货给商店：9

即，最优的方案是选择A、C两个地方建厂，然后2、3、4商店的货由A厂提供，其他的厂的货由C厂提供。

文章标签：
供应链
达摩院
数据库
存储
关键词：
达摩院优化求解器
优化求解器达摩院
仓库选址优化求解器
整数线性规划优化求解器
决策智能Lab_运营小编003
目录
相关文章
决策智能Lab_运营小编003
|
2月前
|
达摩院 供应链 安全
光储荷经济性调度问题【数学规划的应用（含代码）】阿里达摩院MindOpt
本文介绍使用MindOpt工具优化光储荷经济性调度的数学规划问题。光储荷经济性调度技术旨在最大化能源利用率和经济效益，应用场景包括分布式光伏微网、家庭能源管理系统、商业及工业用电、电力市场参与者等。文章详细阐述了如何通过数学规划方法解决虚拟电厂中的不确定性与多目标优化难题，并借助MindOpt云建模平台、MindOpt APL建模语言及MindOpt优化求解器实现问题建模与求解。最终案例展示了如何通过合理充放电策略减少37%的电费支出，实现经济与环保双重效益。读者可通过提供的链接获取完整源代码。
决策智能Lab_运营小编003
61 2
决策智能Lab_运营小编003
|
2月前
|
达摩院 BI 索引
切割问题【数学规划的应用（含代码）】阿里达摩院MindOpt
本文主要讲述了使用MindOpt工具对切割问题进行优化的过程与实践。切割问题是指从一维原材料（如木材、钢材等）中切割出特定长度的零件以满足不同需求，同时尽可能减少浪费的成本。文章通过实例详细介绍了如何使用MindOpt云上建模求解平台及其配套的MindOpt APL建模语言来解决此类问题，包括数学建模、代码实现、求解过程及结果分析等内容。此外，还讨论了一维切割问题的应用场景，并对其进行了扩展，探讨了更复杂的二维和三维切割问题。通过本文的学习，读者能够掌握利用MindOpt工具解决实际切割问题的方法和技术。
决策智能Lab_运营小编003
63 2
决策智能Lab_运营小编003
|
2月前
|
达摩院 算法 安全
智慧楼宇多目标调度问题【数学规划的应用(含代码)】阿里达摩院MindOpt
本文探讨了使用MindOpt工具优化智慧楼宇的多目标调度问题，特别是在虚拟电厂场景下的应用。智慧楼宇通过智能化技术综合考虑能耗、舒适度等多目标，实现楼宇设备的有效管理和调度。虚拟电厂作为多能源聚合体，能够参与电力市场，提供调峰、调频等辅助服务。文章介绍了如何使用MindOpt云上建模求解平台及MindOpt APL建模语言对楼宇多目标调度问题进行数学建模和求解，旨在通过优化储能设备的充放电操作来最小化用电成本、碳排放成本和功率变化成本，从而实现经济、环保和电网稳定的综合目标。最终结果显示，在使用储能设备的情况下，相比不使用储能设备的情形，成本节约达到了约48%。
决策智能Lab_运营小编003
70 2
决策智能Lab_运营小编003
|
2月前
|
达摩院 供应链 JavaScript
网络流问题--仓储物流调度【数学规划的应用(含代码)】阿里达摩院MindOpt
本文通过使用MindOpt工具优化仓储物流调度问题，旨在提高物流效率并降低成本。首先，通过考虑供需匹配、运输时间与距离、车辆容量、仓库储存能力等因素构建案例场景。接着，利用数学规划方法，包括线性规划和网络流问题，来建立模型。在网络流问题中，通过定义节点（资源）和边（资源间的关系），确保流量守恒和容量限制条件下找到最优解。文中还详细介绍了MindOpt Studio云建模平台和MindOpt APL建模语言的应用，并通过实例展示了如何声明集合、参数、变量、目标函数及约束条件，并最终解析了求解结果。通过这些步骤，实现了在满足各仓库需求的同时最小化运输成本的目标。
决策智能Lab_运营小编003
76 1
决策智能Lab_运营小编003
|
3月前
|
达摩院 安全 调度
网络流问题--交通调度【数学规划的应用(含代码)】阿里达摩院MindOpt
本文探讨了如何利用数学规划工具MindOpt解决交通调度问题。交通调度涉及网络流分析，考虑道路容量、车辆限制、路径选择等因素，以实现高效运行。通过建立数学模型，利用MindOpt云平台和建模语言MAPL，设定流量最大化目标并确保流量守恒，解决实际的调度问题。案例展示了如何分配车辆从起点到终点，同时满足道路容量约束。MindOpt Studio提供在线开发环境，支持模型构建和求解，帮助优化大规模交通调度。
决策智能Lab_运营小编003
77 1
决策智能Lab_运营小编003
|
3月前
|
达摩院
人员排班【数学规划的应用(含代码)】阿里达摩院MindOpt
本文介绍了使用阿里巴巴达摩院的MindOpt工具解决人员排班的数学规划问题。人员排班在多个行业中至关重要，如制造业、医疗、餐饮和零售等。问题涉及多种约束，包括工作需求、员工能力、工作时间限制、连续工作天数及公平性。通过MindOpt云建模平台和建模语言MindOpt APL，建立数学模型并编写代码来解决最小化总上班班次的问题。案例中展示了如何声明集合、参数、变量和约束，并给出了部分代码示例。最后，通过MindOpt求解器得到最优解，并将结果输出到CSV文件中。
决策智能Lab_运营小编003
96 0
决策智能Lab_运营小编003
|
3月前
|
存储 达摩院 供应链
排产排程问题【数学规划的应用（含代码）】阿里达摩院MindOpt
**文章摘要：** 本文探讨了使用阿里巴巴达摩院的MindOpt优化求解器解决制造业中的排产排程问题。排产排程涉及物料流动、工序安排、设备调度等多个方面，通常通过数学规划方法建模。MindOpt支持线性规划、整数规划等，能有效处理大规模数据。案例以香皂制造工厂为例，考虑了多种油脂的购买、存储和生产计划，以及价格变化和存储成本。问题通过数学建模转化为MindOpt APL代码，求解器自动寻找最优解，以最大化利润。文章还提供了代码解析，展示了解决方案的细节，包括目标函数（利润最大化）、约束条件（如生产效率、库存管理）以及结果分析。
决策智能Lab_运营小编003
69 0
mindopt
|
5月前
|
达摩院 IDE 开发工具
阿里达摩院MindOpt优化求解器-月刊（2024年5月）
阿里达摩院MindOpt优化求解器-月刊（2024年5月版），新增了两个案例，如何使用LLM和MindOpt更准确地回答数学问题、如何使用MindOpt优化云计算集群虚拟机资源配置提高机器利用率，和如何利用IIS冲突分析指导不可解的问题解决方案。MindOpt的求解器已经可以在阿里云线上购买不联网版本。租户版也正式上线，可体验更多功能。新增QQ交流群。
mindopt
97 4
mindopt
|
4月前
|
达摩院 Python
阿里达摩院MindOpt优化求解器-月刊（2024年6月）
**阿里达摩院MindOpt优化求解器2024年6月月刊概览：** - 发布新功能，MAPL建模语言V2.5上线，Python APIs全面升级，旧版本不兼容。 提供快速入门教程、示例代码展示如何用Python调用MAPL。MindOpt Studio租户版新增Gradio支持，便于开发WebAPP，提供了案例源码展示如何开发。引入新案例： 1. 巡检线路的排班-2017全国大学生数学建模竞赛D题。包含最短路模型、TSP模型、弧分割模型。2. 商品组合定价策略：探讨如何最赚钱的加购区商品定价。
mindopt
103 0
决策智能Lab_运营小编003
|
4月前
|
供应链 定位技术 数据库
仓库选址问题【数学规划的应用(含代码)】阿里达院MindOpt
使用阿里云MindOpt工具，文章展示了如何解决仓库选址的数学规划问题。该问题涉及构建工厂以供应多个商店，考虑因素包括建设成本、库存成本、运输成本和需求量。MindOpt是一个优化求解器，能处理大规模数据的数学规划问题。通过声明集合、参数、变量、目标函数和约束条件，构建模型并求解，以最小化总成本。文中还提到了不同行业的应用场景，如农业、制造业、零售业和电商，并提供了视频讲解和代码示例。
决策智能Lab_运营小编003
76 0

达摩院 MindOpt 优化

热门文章

最新文章

  • 1
    C++模板初阶
  • 2
    SQL优化器原理 - Auto Hash Join
  • 3
    如何使用被信任的证书来配置SLB HTTPS协议，使slb站点支持ssl
  • 4
    PostgreSQL 9.6 并行计算 优化器算法浅析
  • 5
    MySQL · 捉虫动态 · order by limit 造成优化器选择索引错误
  • 6
    PostgreSQL 优化器案例之 - order by limit 索引选择问题
  • 7
    关键时刻HINT出彩 - PG优化器的参数优化、执行计划固化CASE
  • 8
    优化求解器之MPS文件的格式简介
  • 9
    MindOpt——优化虚拟电厂智能调度问题(一)
  • 10
    让SQL优化器更准确！AnalyticDB PG版发布统计信息自动收集功能
  • 1
    阿里达摩院MindOpt优化求解器-月刊（2024年4月）
    112
  • 2
    深入了解MindOpt优化求解器的License服务
    66
  • 3
    MindOpt APL向量化建模语法的介绍与应用（2）
    59
  • 4
    阿里达摩院MindOpt优化求解器-月刊（2024年3月）
    112
  • 5
    MindOpt APL 最新版本功能介绍，并且开放下载使用了！
    113
  • 6
    MindOpt APL向量化建模语法的介绍与应用（1）
    78
  • 7
    了解MindOpt优化求解器的各种调用方式、方法
    161
  • 8
    阿里达摩院MindOpt优化求解器-月刊（2024年2月）
    128
  • 9
    阿里达摩院MindOpt优化求解器-月刊（2024年1月）
    134
  • 10
    如何通过阿里达摩院MindOpt获得MILP多个解
    171

    • 相关课程

    更多
  • 达摩院MindOpt优化求解器入门与实践
  • 基于通义灵码实现高效 AI 编码
  • 人人都能学｜AI大模型应用搭建
  • 【新人赛】工业蒸汽量预测建模算法代码开源分享合集
  • 使用Higress AI网关优化AI调用成本
  • 云原生AI套件：五分钟微调宝可梦风格StableDiffusion

    • 相关电子书

    更多
  • 阿里技术专家一挃：MongoDB 优化器 & 执行器介绍
  • 《达摩院三维视觉产品方案介绍》
  • 打造多端多模态最优效果的百炼，共建大模型生态繁荣

    • 相关实验场景

    更多
  • SAE 极速部署专属 AI 证件照神器
  • 流水线运行出错排查难？AI帮你智能排查
  • AI克隆声音，基于函数计算部署GPT-Sovits语音生成模型
  • 奥运时刻！零代码生成奥运风格AI写真。
  • 【AI破次元壁合照】少年白马醉春风，函数计算一键部署AI绘画平台
  • 【玩转ComfyUI】基于函数计算一键部署AI生图平台 ComfyUI
    • 下一篇
    无影云桌面