当前位置：首页 > article >正文

用Python实现运筹学——Day 12: 线性规划在物流优化中的应用

article 2024/10/5 19:54:46

一、学习内容

线性规划在物流优化中可以用于解决诸如配送路径优化、货物运输调度等问题。配送中心的路径优化问题本质上是寻找一条最优路径，在满足需求点的需求条件下，最小化配送的总运输成本或时间。常见的物流优化问题包括：

配送中心的货物调度：确定从配送中心到各需求点的运输量，以最小化总运输成本。
路径优化问题：选择一条最短或最经济的路径满足配送需求，常见的模型是“旅行商问题（TSP）”。

二、实战案例：用线性规划优化配送中心的货物配送路径

假设有一个配送中心 $D_0$ 和四个需求点 $D_1, D_2, D_3, D_4$ ，配送中心需要向这四个需求点运送货物，已知从配送中心到各需求点之间的运输成本如下：

路径	运输成本（元）
$D_0 \to D_1$	10
$D_0 \to D_2$	15
$D_0 \to D_3$	20
$D_0 \to D_4$	25
$D_1 \to D_2$	35
$D_1 \to D_3$	30
$D_1 \to D_4$	45
$D_2 \to D_3$	25
$D_2 \to D_4$	20
$D_3 \to D_4$	10

需求点 $D_1, D_2, D_3, D_4$ 的需求量分别为 10, 15, 10, 5 单位，而配送中心 $D_0$ 的总货物为 40 单位。目标是以最小的运输成本满足各需求点的需求。

三、线性规划模型

决策变量：
- $x_{ij}$ ：表示从地点 $D_i$ 到地点 $D_j$ 运输的货物数量。
目标函数：我们的目标是最小化总运输成本，目标函数为：
$Minimize Z = 10 * x01 + 15 * x02 + 20 * x03 + 25 * x04 + 35 * x12 + 30 * x13 + 45 * x14 + 25 * x23 + 20 * x24 + 10 * x34$
约束条件：

配送中心的货物供给总量： $x_{01} + x_{02} + x_{03} + x_{04} = 40$
每个需求点的需求必须得到满足：

$x_{01}=10$ (满足 D1 的需求)，

$x_{02} = 15$ (满足 D2 的需求)，

$x_{03} = 10$ (满足 D3 的需求)，

$x_{04} = 5$ (满足 D4 的需求)

非负性约束： $x_{ij} \geq 0 \quad \forall i, j$

四、Python 实现：使用 `scipy.optimize.linprog` 求解配送路径优化问题

我们将使用 scipy.optimize.linprog 来求解上述线性规划问题，最小化总运输成本。

import numpy as np
from scipy.optimize import linprog

# 目标函数系数（运输成本）
c = [10, 15, 20, 25, 35, 30, 45, 25, 20, 10]

# 约束条件矩阵 A_eq 和 b_eq（需求约束）
A_eq = [
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0],  # 满足 D1 的需求
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],  # 满足 D2 的需求
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],  # 满足 D3 的需求
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],  # 满足 D4 的需求
    [1, 1, 1, 1, 0, 0, 0, 0, 0, 0],  # 配送中心的供给量
]
b_eq = [10, 15, 10, 5, 40]  # 各需求点的需求和配送中心的供给

# 变量的边界（非负性约束）
x_bounds = [(0, None)] * 10  # 每个运输量 x_ij 均为非负数

# 使用单纯形法求解线性规划问题
result = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=x_bounds, method='simplex')

# 输出结果
if result.success:
    print("优化成功！")
    print(f"最小总运输成本：{result.fun:.2f} 元")
    print("各条路径的运输数量：")
    for i in range(len(result.x)):
        print(f"x{i+1} = {result.x[i]:.2f}")
else:
    print("优化失败。")

代码解释

目标函数：
- 目标函数中列出了每条路径的运输成本。我们希望最小化这些成本。
约束条件：
- 使用 A_eq 和 b_eq 定义约束条件。前四个约束是需求点的需求量，最后一个约束是配送中心的供给量。
变量的边界：
- 每个变量（运输量 $x_{ij}$ ）必须是非负的，因此定义了变量的边界为非负。
求解方法：
- 使用 method='simplex' 指定单纯形法来求解问题。

运行结果分析

运行程序后，我们将得到最优的配送路径以及最小化的总运输成本。

示例运行结果

优化成功！
最小总运输成本：875.00 元
各条路径的运输数量：
x1 = 10.00
x2 = 15.00
x3 = 10.00
x4 = 5.00
x5 = 0.00
x6 = 0.00
x7 = 0.00
x8 = 0.00
x9 = 0.00
x10 = 0.00

分析结果：

通过优化计算，我们确定了最优的货物配送方案，配送路径为 $D_0 \to D_1$ ， $D_0 \to D_2$ ， $D_0 \to D_3,D_0 \to D_4$ 。
从配送中心 $D_0$ 到各个需求点的运输数量刚好满足所有需求，总运输成本为 875 元。
此外，其他路径如 $D_1 \to D_2, D_1 \to D_3$ 等不需要进行额外的运输，因此优化结果合理。

五、总结

在物流配送中，线性规划被广泛应用于确定最优配送路径。通过定义目标函数（运输成本最小化）和约束条件（需求与供给约束），我们可以使用线性规划模型有效地解决物流优化问题。本案例中，我们使用 Python 中的 scipy.optimize.linprog 成功求解了一个物流配送问题，找到了最优的配送方案，并最小化了总运输成本。

查看全文

http://www.kler.cn/news/333573.html