供应链设施选址模型——Python实现-526互联

选址问题是运筹学中非常经典的问题。选址问题是指在确定选址对象，选址目标区，成本函数以及存在何种约束条件的前提下，以总物流成本最低或总服务最优或社会效益最大化为总目标，以确定物流系统中物流节点的数量、位置，从而合理规划物流网络结构。设施选址问题（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

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

参考文献

nebulagraph基础设施kubeblocks设施