首页 > 编程语言 >供应链设施选址模型——Python实现

供应链设施选址模型——Python实现

时间:2023-11-26 15:23:46浏览次数:50  
标签:20 设施 Python 0.0 sum 问题 供应链 选址

选址问题是运筹学中非常经典的问题。选址问题是指在确定选址对象,选址目标区,成本函数以及存在何种约束条件的前提下,以总物流成本最低或总服务最优或社会效益最大化为总目标,以确定物流系统中物流节点的数量、位置,从而合理规划物流网络结构。设施选址问题(Facility Location Problem)自20世纪60年代初期以来,在运筹学中一直占据着中心位置。它来自于工厂、仓库、超市、学校、医院、图书馆、火车站、代理服务器、传感器等位置的确定问题。

一、设施选址问题

1.1 无容量设施选址方法

线性规划舍入(LP rounding)法。此类技巧整体思路为建立问题的整数线性规划,松弛得到线性规划。通过求解线性规划得到分数解,再将其舍入成整数解。由于算法设计是在松弛线性规划的分数最优解基础上进行的,在分析时有下界门槛,利于得到近似比。但同时, 也由于求解线性规划,丢失了问题自身的组合结构。

原始对偶(primal-dual)法。此类技巧整体思路为建立问题的整数线性规划, 松弛得到线性规划。此时不需要求解松弛规划,而是建立松弛规划的对偶规划。利用对偶上升的过程构造对偶规划可行解。进一步通过对偶变量与整数规划的关系构造原始整数可行解。原始对偶技巧具有较好的可移植性, 在很多选址的拓展问题有较好的应用。一般来说, 这类技巧所得的近似比较高。

局部搜索(local search)法。此类技巧整体思想为以任意可行解为初始解,定义在当前解的基础上进行增加一个设施、减少一个设施和交换一对设施三类运算。如果三类运算可以改进当前解,进行更新,否则算法终止。局部搜索技巧结构简单,易于实现。但同时,分析过程复杂,难移植且近似比较高。

1.2 带容量限制的设施选址

实际问题的选址环境由于资源有限,顾客需求丰富等原因会复杂得多,这样出现了大量选址的拓展问题。

(a)带软容量限制的设施选址问题: 每个设施都有容量限制,但可以通过支付多倍的设施费用得到多倍的容量从而对顾客提供服务。该问题的目标为选择每个设施开设的次数, 连接顾客到开设设施上且不违背设施的容量限制,使得开设费用和服务费用总和最小。
(b)带硬容量设施选址问题:每个设施都有容量限制, 且设施的容量不能通过多次支付费用获得。该问题的目标为选择开设一些设施, 连接顾客到开设的设施上且不违背设施的容量限制,使得开设费用和服务费用总和最小。
(c)带惩罚的设施选址问题:在选址中,可以对于某些距离较远的顾客不进行服务。由于不服务会导致利润的损失,或者说成本的上升。因此,每个顾客有不被服务的惩罚成本。该问题的目标为选择开设哪些设施,惩罚哪些顾客,使得开设费用、服务费用和惩罚费用总和最小。
(d)带异常点的设施选址问题:在选址中,商家可以设置顾客异常点的个数。在选址中允许有至多个顾客不被服务,同时选择选择开设哪些设施,服务哪些顾客使得开设费用和服务费用总和最小。
(e)多层设施选址问题:顾客需求的复杂会导致选址是一个“流水线”过程,需要通过多个步骤完成,这样产生了多层设施选址问题。在每一步中都需要选择一些设施开设,每个顾客的需求由每一阶段开设的设施组成的一组开设设施满足,最终使得开设费用和服务费用总和最小。

设施选址的其他变形 根据实际生产生活中的需求,设施选址问题还衍生了一些重要拓展问题, 如k-中位问题、随机设施问题、在线设施选址问题、容错设施选址问题、整合配送网络设计问题等等。

二、产能受限型工厂选址模型

在确定了潜在设施地点后,管理者就要决定具体的设施选址并进行产能分配。除了设施选址,管理者还要决定如何将每个市场的需求分配给各个设施。进行产能分配时必须考虑到响应时间方面的顾客服务约束。随着成本和市场的变化,需求分配决策可定期进行调整。在网络设计时,通常选址决策和分配决策时同时进行的。假设:
\(n\) 是工厂地点的数量;\(m\) 是市场或需求点的数量
\(D_j\) 是市场\(j\)的年需;\(K_i\) 是工厂\(i\)的产能
\(f_i\) 是维持工厂\(i\)开工的年固定成本
\(c_{ij}\) 是工厂\(i\)运送单位产量到市场\(j\)的成本
\(x_{ij}\) 是工厂\(i\)运送单位产量到市场\(j\)的数量

\[y_{i}= \begin{cases} 1, & 工厂选址在地点i\\ 0, & 其他\end{cases} \]

则所讨论问题可表述为线性规划问题:

\[\min \quad \sum_{i=1}^n f_i y_i+\sum_{i=1}^n \sum_{j=1}^m c_{i j} x_{i j} \]

约束条件为:

\[\begin{gathered} \sum_{j=1}^m x_{i j} \leq K_i y_i, \quad i=1,2, \ldots, n \\ \sum_{i=1}^n x_{i j}=D_j, \quad j=1,2, \ldots, m \\ x_{i j}\geq 0, \quad y_i \in\{0.1\} \end{gathered} \]

第一个约束条件是为确保工厂产量不超过其产能;第二个约束条件是为确保所有的市场需求得到满足。

三、案例分析-Python

为便于编程,将上面模型转化为:

\[\min \quad \sum_{i=1}^n f_i y_i+\sum_{i=1}^n \sum_{j=1}^m c_{i j} x_{i j} \]

约束条件为:

\[\begin{gathered} \sum_{j=1}^m x_{i j} -K_i y_i \leq 0, \quad i=1,2, \ldots, n \\ \sum_{i=1}^n x_{i j}=D_j, \quad j=1,2, \ldots, m \\ x_{i j}\geq 0, \quad y_i \in\{0.1\} \end{gathered} \]

某供应链企业欲重构北美洲、南美洲、欧洲、非洲和亚洲这5个区域的全球化供应网络,收集到成本(单位:千美元)和需求(单位:百万)数据如下表所示:

产 地 北美洲B1 南美洲B2 欧洲B3 亚洲B4 非洲B5 固定成本 最高供应量H
北美洲A1 81 92 101 130 115 9000 20
南美洲A2 117 77 108 98 100 6750 20
欧 洲A3 102 105 95 119 111 9750 20
亚 洲A4 115 125 90 59 74 6150 20
非 洲A5 142 100 103 105 71 6000 20
需求量 12 8 14 16 7

每个区域的年需求见表中最后一行,中间区域(第2列到第6列)包含了在一个区域组织生产来满足每一个区域的需求所需的生产、库存和运输可变成本(包括税收和关税),如北美洲生产100万单位产品然后到南美洲销售的可变成本是92000美元;对于每个可供选择的工厂都需固定成本见表中(第7列),他们都可生产2000万单位的产品,如在北美洲兴建一个工厂所需的固定成本为9000000美元,最高生产能力为2000万。试问选择哪些工厂组织生产,使得整个供应网络运作的总成本最小?

import pulp
import numpy as np

# Coefficients for the linear programming problem
coefficients = [1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-20,0,0,0,0,
                0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-20,0,0,0,
                0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,-20,0,0,
                0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,-20,0,
                0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,-20,
                  1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
                  0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,
                  0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,
                    0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,
                0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0]

# Reshape the coefficients into a matrix
coeff_matrix = np.array(coefficients).reshape((10, 30), order='C')  # Use 'C' order for row-wise reshaping

# Transportation costs and fixed costs
costs = np.array([81, 92, 101, 130, 115, 117, 77, 108, 98, 100, 102, 105, 95, 119, 111,
                  115, 125, 90, 59, 74, 142, 100, 103, 105, 71, 9000, 6750, 9750, 6150, 6000])

# Demand and supply constraints
demand_constraints = [12, 8, 14, 16, 7]
supply_constraints = [0, 0, 0, 0, 0]

# Create a linear programming problem
prob = pulp.LpProblem("Linear_Problem", pulp.LpMinimize)

# Define decision variables
x = [pulp.LpVariable(f'x_{j}', lowBound=0, cat=pulp.LpContinuous) for j in range(30)]

# Set the last 5 variables as binary
for j in range(25, 30):
    x[j] = pulp.LpVariable(f'x_{j}', lowBound=0, upBound=1, cat=pulp.LpBinary)

# Objective function
prob += pulp.lpDot(np.array(x).flatten(), costs)

# Supply constraints
for i in range(5):
    prob += pulp.lpDot(np.array(x).flatten(), coeff_matrix[i]) <= supply_constraints[i]

# Demand constraints
for i in range(5):
    prob += pulp.lpDot(np.array(x).flatten(), coeff_matrix[i + 5]) == demand_constraints[i]

# Solve the problem
prob.solve()

# Display the results in a 6x5 matrix format
print('最小值为:', pulp.value(prob.objective))
print('\n各变量的取值为:')
for i in range(6):
    for j in range(5):
        idx = i * 5 + j
        print(f'x_{idx + 1}: {pulp.value(x[idx])}', end='\t')
    print()
最小值为: 23751.0
各变量的取值为:
x_1: 0.0	x_2: 0.0	x_3: 0.0	x_4: 0.0	x_5: 0.0	
x_6: 12.0	x_7: 8.0	x_8: 0.0	x_9: 0.0	x_10: 0.0	
x_11: 0.0	x_12: 0.0	x_13: 0.0	x_14: 0.0	x_15: 0.0	
x_16: 0.0	x_17: 0.0	x_18: 4.0	x_19: 16.0	x_20: 0.0	
x_21: 0.0	x_22: 0.0	x_23: 10.0	x_24: 0.0	x_25: 7.0	
x_26: 0.0	x_27: 1.0	x_28: 0.0	x_29: 1.0	x_30: 1.0	
#共计30个变量,前面25个是按照运输问题给出的25个变量,最后5个是选址变量

根据计算结果,选择南美洲、亚洲和非洲工厂组织生产。调运方案为从南美洲工厂调运12个单位到北美洲,调运8个单位到南美洲;亚洲工厂调运4个单位到欧洲,调运16个点位到亚洲;非洲工厂调运10个单位到欧洲,调运7个单位到非洲。

参考文献

  1. OM | 设施选址问题简介
  2. 补充3 需求分配和工厂选址模型

标签:20,设施,Python,0.0,sum,问题,供应链,选址
From: https://www.cnblogs.com/haohai9309/p/17857278.html

相关文章

  • GPU部署llama-cpp-python(llama.cpp通用)
    title:GPU部署llama-cpp-python(llama.cpp通用)banner_img:https://cdn.studyinglover.com/pic/2023/08/a5e39db5abf0853e6c456728df8bd971.jpgdate:2023-8-623:01:00tags:-踩坑GPU部署llama-cpp-python(llama.cpp通用)通用流程我们的安装平台是Ubuntu20.04,Python3.......
  • 【Python爬虫】第10篇:js逆向解析和Mongodb数据库。md集合文档(已分享,附代码)
    本文主要学习一下关于爬虫的相关前置知识和一些理论性的知识,通过本文我们能够知道什么是爬虫,都有那些分类,爬虫能干什么等,同时还会站在爬虫的角度复习一下http协议。全套笔记和代码自取地址:请移步这里感兴趣的小伙伴可以自取哦,欢迎大家点赞转发~共8章,37子模块JS的解析......
  • 【Python】异步迭代器与普通迭代器的区别
    异步迭代器是一个协程,并且每个迭代器返回一个在asyncio事件循环中调度和执行的等待对象,所以我们可以在迭代器的主体内执行和等待awaitable对象。普通迭代器需要实现__iter__和__next__函数,异步迭代器需要实现__aiter__和__anext__函数。......
  • 【Python】async与await用法
    async用于修饰函数,将普通函数变为异步函数。asyncdeft2():print(2)直接调用异步函数不会返回结果,而是返回一个协程对象。协程需要通过其他方式来驱动,如async.run函数。await函数只能在异步函数中使用,可以通过该关键字,挂起当前协程,让另一个协程执行完毕,再次执行本协程......
  • 【Python】迭代器与可迭代对象的区别与关系
    定义可迭代对象:能逐一返回其成员的对象,如列表、字符串、字典等;迭代器:表示一连串数据流的对象;区别可迭代对象实现了__iter__方法,可以通过该方法返回迭代器;迭代器对象实现了__iter__和__next__方法,__iter__用来返回其本身,__next__用来获取下一个成员。联系迭代器一定是可迭......
  • 【Python】使用vscode编码提示找不到模块
    问题描述已经使用pip安装了模块,但是使用vscode没有代码提示。解决办法这种情况一般是因为pc安装了多个python版本,安装模块的pip不是vscode指定的编译环境。点击右下角,选择环境变量中配置的python版本。解决问题:......
  • Python 潮流周刊#28:两种线程池、四种优化程序的方法
    你好,我是猫哥。这里每周分享优质的Python、AI及通用技术内容,大部分为英文。本周刊开源,欢迎投稿。另有电报频道作为副刊,补充发布更加丰富的资讯。......
  • 运输问题和指派问题——Python实现
    随着社会和经济的不断进步,现代物流业蓬勃发展,如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值,是物流运作必须解决的问题。日益复杂的运输活动使得运输问题变得越来越庞杂,但是其核心思想仍然是实现现有资源的最优化配置。运输问题经常出现在计划货物配送和从某些供给......
  • python 控制台 等待用户输入
    Python控制台等待用户输入的实现方法1.总览在Python中,要实现控制台等待用户输入的功能,可以使用input()函数来实现。input()函数会暂停程序的执行,直到用户输入一条信息并按下回车键。本文将详细介绍如何使用input()函数实现这一功能。2.实现步骤下表展示了整个实现过程的步骤......
  • python 矩阵 换行
    Python矩阵换行实现流程为了帮助初学者实现Python矩阵的换行,下面将提供一个详细的步骤,通过代码和注释的形式指导他们完成这个任务。在开始之前,确保已经了解Python的基本语法和矩阵的基本概念。步骤步骤描述步骤1创建一个二维矩阵步骤2使用循环遍历二维矩阵的每一......