线性规划：解决真实世界中的优化问题

运营管理者常常面临同样的难题：决策太多、约束太多，却没有显而易见的方法找到最优解。一个配送网络需要在几十条路线中最小化燃料成本，同时要遵守送达时间窗、车辆容量和司机排班。

这两类问题共享同一种数学结构。当您的目标和约束可以用线性关系表示时，您处理的就是线性规划问题。我们重视线性规划，因为在资源有限、需求相互竞争的情况下，它能够找到最优解。

线性规划的强大之处在于它的保证：如果可行解存在，算法将找到最优解。当然，现实应用很少能与教科书示例完全契合，但理解核心框架有助于您识别什么时候可以用优化替代拍脑袋的估计。

本文将带您从基础走向可运行的 Python 实现。我们会从您能用几何直观可视化的两个变量的简单问题，逐步过渡到需要算法求解的复杂场景。您既会理解支撑优化起作用的数学理论，也会掌握亲自实现解法的实用技能。

什么是线性规划？

线性规划是在一组线性约束下优化线性目标函数。在我参与的一个配送路径项目中，目标是在满足车辆容量和送达时间窗等约束的前提下，最小化总行驶距离。

理解基本结构

每个线性规划问题都包含三个组成部分：决策变量、目标函数和约束条件。

决策变量代表您要做的选择。在路径问题中，二元变量可表示某辆车是否访问某个地点。在生产计划中，变量可能代表生产数量。

目标函数定义您要优化的内容。它必须是决策变量的线性组合。约束定义了问题的规则与限制，形式包括等式、小于等于或大于等于的不等式。

from scipy.optimize import linprog

c = [10, 15]
A_ub = [[1, 0], [0, 1]]
b_ub = [100, 80]
A_eq = [[1, 1]]
b_eq = [150]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, 
                 bounds=bounds, method='highs')

print(f"Optimal solution: Truck 1 = {result.x[0]:.1f}, Truck 2 = {result.x[1]:.1f}")
print(f"Total cost: ${result.fun:.2f}")技术支持

上述代码在个体上限和总覆盖需求的约束下，最小化两个决策变量的总成本。目标系数 [10, 15] 表示单位成本，不等式约束限制各变量的取值范围，而等式约束确保总覆盖量。

几何解释

从几何角度理解线性规划，改变了我对优化的思考方式。每个约束定义一个半空间，它们的交集构成可行域。该区域总是一个凸多面体，意味着连接任意两个内部点的线段都位于其内。

关键洞见在于：最优解总是出现在可行域的顶点。沿着一条边移动要么改善目标，要么不变，因此会一直移动直到到达拐角。这个性质让线性规划算法更高效。

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 8, 400)
y1 = (10 - x) / 2
y2 = 12 - 2*x

plt.figure(figsize=(10, 8))
plt.plot(x, y1, 'r-', label='x + 2y ≤ 10', linewidth=2)
plt.plot(x, y2, 'b-', label='2x + y ≤ 12', linewidth=2)

y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), 
                 alpha=0.3, color='green', label='Feasible region')

vertices = [(0, 0), (0, 5), (14/3, 8/3), (6, 0)]
for v in vertices:
    plt.plot(v[0], v[1], 'ko', markersize=10)
    obj_value = 3*v[0] + 4*v[1]
    plt.annotate(f'({v[0]:.1f}, {v[1]:.1f})\nObj: {obj_value:.1f}',
                 xy=v, xytext=(v[0]+0.3, v[1]+0.3))

plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True, alpha=0.3)
plt.title('Geometric View: Optimal Solution at Vertex (4.7, 2.7)')
plt.show()技术支持

该可视化展示了两个约束相交处的顶点 (4.7, 2.7) 给出最优解。凸的可行域保证不存在让算法“卡住”的隐藏山谷，确保局部最优即为全局最优。

将现实问题转化为模型

最难的部分不是解数学，而是把凌乱的现实问题转化为清晰的模型。定义变量和约束往往比运行优化本身更费时。

定义决策变量需要识别最基本的选择。对路径问题，您可以用二元变量表示车辆-地点的指派，或引入连续变量来表示访问顺序以简化约束。

构建约束意味着将业务规则翻译成不等式，这会暴露隐藏假设。经理说“每个地点需要一次配送”，是指恰好一次还是至少一次？这些细节会完全改变模型形式。

下面是一个使用 PuLP 的建模示例：

from pulp import *

prob = LpProblem("Food_Bank_Routing", LpMinimize)

trucks = ['Truck_A', 'Truck_B', 'Truck_C']
centers = ['North', 'South', 'East', 'West', 'Central']

x = LpVariable.dicts("route", 
                     [(i, j) for i in trucks for j in centers],
                     cat='Binary')

distances = {
    ('Truck_A', 'North'): 15, ('Truck_A', 'South'): 20,
    ('Truck_A', 'East'): 10, ('Truck_A', 'West'): 25,
    ('Truck_A', 'Central'): 5,
    ('Truck_B', 'North'): 18, ('Truck_B', 'South'): 15,
    ('Truck_B', 'East'): 12, ('Truck_B', 'West'): 22,
    ('Truck_B', 'Central'): 8,
    ('Truck_C', 'North'): 20, ('Truck_C', 'South'): 25,
    ('Truck_C', 'East'): 15, ('Truck_C', 'West'): 18,
    ('Truck_C', 'Central'): 10,
}

prob += lpSum([distances[i, j] * x[i, j] 
               for i in trucks for j in centers])

for j in centers:
    prob += lpSum([x[i, j] for i in trucks]) == 1

max_stops = {'Truck_A': 3, 'Truck_B': 2, 'Truck_C': 3}
for i in trucks:
    prob += lpSum([x[i, j] for j in centers]) <= max_stops[i]

prob.solve()

print(f"Status: {LpStatus[prob.status]}")
print(f"Total distance: {value(prob.objective)} miles")
for i in trucks:
    route = [j for j in centers if value(x[i, j]) == 1]
    print(f"{i} visits: {', '.join(route)}")技术支持

上述模型使用二元变量表示卡车-中心的指派，最小化总距离，确保每个中心恰好得到一次配送，并遵守卡车的停靠上限。

经典问题模式提供了模板。膳食问题在满足营养要求的同时最小化成本。运输问题最小化运费。这一类模型直接适用于我的路径挑战。识别这些模式有助于加速建模，因为您很少在解决真正全新的问题。

线性规划在由约束定义的可行域顶点处找到最优解。图片来自作者

求解方法与算法途径

理解算法工作原理改变了我对调用 linprog() 的看法。它们并非黑盒，而是优雅的数学过程。

单纯形法

由 George Dantzig 于 1947 年提出的 单纯形算法是起点。其洞见是：以系统方式从一个顶点沿边移动到相邻顶点，不断改进目标，直到达到最优。

该算法维护一个表并执行主元（pivot）运算以在顶点间移动。每次迭代通过选择主元并用行变换更新，从而改进目标或判定最优性。

from scipy.optimize import linprog
import numpy as np

c = [-3, -2]
A_ub = [[2, 1], [2, 3], [3, 1]]
b_ub = [18, 42, 24]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Optimal solution: x1 = {result.x[0]:.2f}, x2 = {result.x[1]:.2f}")
print(f"Maximum value: {-result.fun:.2f}")
print(f"Iterations: {result.nit}")技术支持

上述代码通过对目标系数取负来用单纯形法求解一个最大化问题。求解器在约束定义的可行域顶点间有序移动，仅用几次迭代就到达最优解。在更大问题上，单纯形法通常用远少于可行顶点数的步骤找到最优，哪怕存在上千种可能，迭代次数往往也少于 20。

内点法

单纯形在边界上行进，而内点法则在可行域内部导航。对于包含数百资产的大型投资组合优化，单纯形可能变慢，而内点法可在数秒内求解。

其关键优势是多项式时间复杂度。Karmarkar（1984）的算法让内点法走向实用，在改进目标的同时保持远离约束边界。现代求解器如 Gurobi 会根据问题特征在单纯形与内点法之间自动选择。

二元变量的图解法

对于两个变量的问题，我总会先用图解法求解。这能建立可迁移到高维的直觉。绘制约束、识别可行域，再找出哪个拐角使目标最优。

from scipy.optimize import linprog

c = [-30, -40]
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Bread loaves: {result.x[0]:.0f}")
print(f"Cakes: {result.x[1]:.0f}")
print(f"Maximum profit: ${-result.fun:.0f}")技术支持

该面包房生产问题在烘焙与装饰工时限制下最大化面包与蛋糕的利润。解答揭示了哪个拐点在几何上最优，使算法沿顶点跳转的行为更加直观。

跨行业的应用

线性规划使用同一数学框架，解决迥然不同领域中的问题。

制造与生产

生产计划是我第一次严肃应用的场景。产品组合问题用于确定生产数量，变量代表产量，目标最大化利润，约束刻画资源限制。

from pulp import *

products = ['Phone', 'Tablet', 'Laptop']

profits = {'Phone': 120, 'Tablet': 200, 'Laptop': 350}
assembly_time = {'Phone': 2, 'Tablet': 3, 'Laptop': 5}
testing_time = {'Phone': 1, 'Tablet': 1.5, 'Laptop': 2}

assembly_available = 500
testing_available = 200
min_production = {'Phone': 50, 'Tablet': 30, 'Laptop': 20}

model = LpProblem("Production_Planning", LpMaximize)
production = LpVariable.dicts("produce", products, lowBound=0, cat='Integer')

model += lpSum([profits[p] * production[p] for p in products])
model += lpSum([assembly_time[p] * production[p] for p in products]) <= assembly_available
model += lpSum([testing_time[p] * production[p] for p in products]) <= testing_available

for p in products:
    model += production[p] >= min_production[p]

model.solve()

print(f"Status: {LpStatus[model.status]}")
for p in products:
    print(f"{p}: {production[p].varValue:.0f} units")
print(f"Total profit: ${value(model.objective):,.0f}")技术支持

上述模型在三条产品线间优化电子产品生产，在装配与测试产能与最低产量要求之间取得平衡。

配比（混配）问题则优化满足规格的混合物以最小成本，例如在满足营养要求的同时最小化食品配方成本。

运输与物流

运输问题是另一类经典案例。其经典结构是：供给地有供给量，需求地有需求量，目标是最小化总运输成本。

warehouses = ['Warehouse_A', 'Warehouse_B', 'Warehouse_C']
supply = {'Warehouse_A': 300, 'Warehouse_B': 400, 'Warehouse_C': 200}

customers = ['Customer_1', 'Customer_2', 'Customer_3', 'Customer_4']
demand = {'Customer_1': 200, 'Customer_2': 150, 'Customer_3': 250, 'Customer_4': 200}

costs = {
    ('Warehouse_A', 'Customer_1'): 8,  ('Warehouse_A', 'Customer_2'): 6,
    ('Warehouse_A', 'Customer_3'): 10, ('Warehouse_A', 'Customer_4'): 7,
    ('Warehouse_B', 'Customer_1'): 9,  ('Warehouse_B', 'Customer_2'): 12,
    ('Warehouse_B', 'Customer_3'): 8,  ('Warehouse_B', 'Customer_4'): 11,
    ('Warehouse_C', 'Customer_1'): 14, ('Warehouse_C', 'Customer_2'): 7,
    ('Warehouse_C', 'Customer_3'): 10, ('Warehouse_C', 'Customer_4'): 12,
}

model = LpProblem("Transportation", LpMinimize)

routes = [(w, c) for w in warehouses for c in customers]
shipments = LpVariable.dicts("ship", routes, lowBound=0)

model += lpSum([costs[i, j] * shipments[i, j] for (i, j) in routes])

for w in warehouses:
    model += lpSum([shipments[w, c] for c in customers]) <= supply[w]

for c in customers:
    model += lpSum([shipments[w, c] for w in warehouses]) >= demand[c]

model.solve()技术支持

网络流问题将运输问题推广到包含中转节点的图。据我所知，航空公司在机组排班与航材调度中大量使用这类模型。

金融服务与医疗

在金融应用中，资本预算问题在预算约束下选择使回报最大化的项目：

projects = {
    'Project_A': {'return': 25000, 'cost': 100000, 'staff': 5},
    'Project_B': {'return': 30000, 'cost': 150000, 'staff': 7},
    'Project_C': {'return': 20000, 'cost': 80000, 'staff': 4},
}

budget = 300000
staff_available = 15

model = LpProblem("Capital_Budgeting", LpMaximize)
select = LpVariable.dicts("select", projects.keys(), cat='Binary')

model += lpSum([projects[p]['return'] * select[p] for p in projects])
model += lpSum([projects[p]['cost'] * select[p] for p in projects]) <= budget
model += lpSum([projects[p]['staff'] * select[p] for p in projects]) <= staff_available

model.solve()技术支持

医疗系统中充满优化挑战。我曾为一家诊所的排班问题提供咨询，为护士排班时既要满足技能要求，又要平衡工作量。

现代技术应用

线性规划也在机器学习中意外现身。特征选择可被表述为在稀疏约束下最小化预测误差。云计算利用它为分布式系统进行资源分配。

计算复杂度与性能

当问题从玩具示例扩展到生产系统时，复杂度变得至关重要。

单纯形法的复杂度

单纯形法的复杂度颇为有趣。其最坏情况是指数级，但平均表现极佳。像 Klee-Minty 立方体这样的病态案例会迫使它检查每个顶点，但典型问题只需检查很小一部分，规模大致呈二次关系增长。

我通过求解规模递增的随机生成问题进行了测试：

import time
import numpy as np
from scipy.optimize import linprog

def benchmark_simplex(num_vars, num_constraints):
    c = np.random.randn(num_vars)
    A_ub = np.random.randn(num_constraints, num_vars)
    b_ub = np.random.rand(num_constraints) * 10
    
    start = time.time()
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='simplex')
    elapsed = time.time() - start
    
    return elapsed, result.nit

problem_sizes = [(10, 20), (50, 100), (100, 200), (200, 400)]

for n_vars, n_const in problem_sizes:
    times, iterations = [], []
    for _ in range(10):
        t, it = benchmark_simplex(n_vars, n_const)
        times.append(t)
        iterations.append(it)
    print(f"{n_vars}x{n_const}: {np.mean(times):.4f}s, {np.mean(iterations):.1f} iterations")技术支持

我的基准测试显示，问题规模翻倍，耗时增加不足 4 倍，印证了典型分布下近似多项式的行为。

性能改进

现代求解器通过预处理、并行计算和自动算法选择实现了惊人的性能。预处理能在求解前自动将问题规模缩小 30% 以上。

退化发生在最优解处有多于定义该顶点所需的紧约束，可能导致循环。我遇到过两条路线成本相同的情形。求解器利用扰动技术避免循环，尽管退化问题会更慢。

数值不稳定出现在尺度不佳的问题中。将货币金额（成千上万）与数量（个位数）混在一起会引发求解器警告。重缩放立刻解决了问题。

求解器性能对比：商业方案在大规模问题上表现更佳。图片来自作者

软件工具与实现

工具选择会显著影响生产力。我从手写单纯形算法逐步过渡到使用能处理超大规模问题的专业求解器。

商业求解器与建模语言

CPLEX 和 Gurobi在工业优化中占据主导地位，对于大问题，相较开源替代品可带来数量级的性能提升。我曾使用 Gurobi 的学术许可做供应链工作。用 SciPy 需要几分钟的问题在几秒内就能解决。

PuLP 是我在 Python 中的常用工具。它提供简洁的 API 来构建模型，并由多种后端求解：

from pulp import *

model = LpProblem("my_problem", LpMaximize)

x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

model += 3*x + 2*y
model += x + y <= 100
model += 2*x + y <= 150

model.solve()

print(f"Used solver: {model.solver}")
print(f"Status: {LpStatus[model.status]}")技术支持

这种抽象层带来与求解器解耦的代码，可在不同系统上运行。Pyomo 为复杂优化提供更高级的功能，包括非线性与随机规划。

云端与开源替代方案

云平台为不定期的大规模问题提供“优化即服务”。您上传问题数据，经由 API 获取解。无服务器架构很优雅，但对小问题来说通常比本地求解更慢。

GLPK（GNU 线性规划工具包）是可靠的开源主力。我用它来教学与个人项目。HiGHS 是较新的求解器，展现出令人印象深刻的性能。SciPy 近期已采用 HiGHS 作为默认后端，我的基准测试显示它在许多问题上与 Gurobi 不相上下。

线性规划示例

通过完整示例的演练，比单看理论更能加深理解。

示例 1：膳食问题

经典的膳食问题在满足营养需求的同时最小化成本：

from pulp import *

foods = {
    'Oatmeal': {'cost': 0.50, 'calories': 110, 'protein': 4, 'vitamin': 2},
    'Chicken': {'cost': 2.50, 'calories': 250, 'protein': 30, 'vitamin': 0},
    'Eggs':    {'cost': 0.80, 'calories': 155, 'protein': 13, 'vitamin': 1},
    'Milk':    {'cost': 1.20, 'calories': 150, 'protein': 8, 'vitamin': 4},
    'Bread':   {'cost': 0.30, 'calories': 80, 'protein': 3, 'vitamin': 0}
}

min_calories, min_protein, min_vitamin = 2000, 50, 10

model = LpProblem("Diet_Optimization", LpMinimize)
servings = LpVariable.dicts("servings", foods.keys(), lowBound=0)

model += lpSum([foods[f]['cost'] * servings[f] for f in foods])
model += lpSum([foods[f]['calories'] * servings[f] for f in foods]) >= min_calories
model += lpSum([foods[f]['protein'] * servings[f] for f in foods]) >= min_protein
model += lpSum([foods[f]['vitamin'] * servings[f] for f in foods]) >= min_vitamin

model.solve()

print(f"Total cost: ${value(model.objective):.2f}")
for food in foods:
    if servings[food].varValue > 0.01:
        print(f"{food}: {servings[food].varValue:.2f} servings")技术支持

上述模型找到满足每日营养需求的最低成本食物组合。这也表明，若不添加关于多样性、口味或饮食偏好的额外约束，LP 的最优解未必实用。

同一框架也可作为商业决策的基础，例如优化生产计划或分配营销预算。

示例 2：多周期规划

多周期规划考虑库存水平如何在多个时期中影响未来需求：

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']

centers = {
    'North': {'daily_demand': [100, 80, 90, 110, 85], 'capacity': 250},
    'South': {'daily_demand': [120, 100, 95, 105, 130], 'capacity': 300},
}

delivery_cost = {'Monday': 50, 'Tuesday': 50, 'Wednesday': 50,
                 'Thursday': 50, 'Friday': 70}

model = LpProblem("Multiperiod_Routing", LpMinimize)

deliveries = LpVariable.dicts("deliver",
                              [(c, d) for c in centers for d in days],
                              lowBound=0)
inventory = LpVariable.dicts("inventory",
                            [(c, d) for c in centers for d in days],
                            lowBound=0)

model += lpSum([delivery_cost[d] * deliveries[c, d] 
                for c in centers for d in days])

for c in centers:
    for i, day in enumerate(days):
        if i == 0:
            model += inventory[c, day] == deliveries[c, day] - centers[c]['daily_demand'][i]
        else:
            prev_day = days[i-1]
            model += (inventory[c, day] == inventory[c, prev_day] + 
                     deliveries[c, day] - centers[c]['daily_demand'][i])
        model += inventory[c, day] <= centers[c]['capacity']

model.solve()技术支持

多周期模型会增大问题规模，但能释放更复杂的优化能力。模型会在更便宜的日子集中配送，并利用库存容量降低总体成本。

混合整数规划

许多问题涉及离散决策：建不建厂、指不指派员工。这需要混合整数规划（MIP），在线性规划中引入整数和二元变量。

入门与分支定界

路径问题需要整数决策。二元变量 x[i][j] 表示车辆 i 是否访问地点 j。车辆不可能进行“分数次”的访问。

分支定界通过求解连续 LP 松弛来系统搜索离散解空间：

from pulp import *

model_continuous = LpProblem("Continuous", LpMaximize)
x_cont = LpVariable("x", lowBound=0)
y_cont = LpVariable("y", lowBound=0)

model_continuous += 3*x_cont + 4*y_cont
model_continuous += x_cont + 2*y_cont <= 10
model_continuous += 2*x_cont + y_cont <= 12

model_continuous.solve()
print(f"Continuous: x={x_cont.varValue:.2f}, y={y_cont.varValue:.2f}")

model_integer = LpProblem("Integer", LpMaximize)
x_int = LpVariable("x", lowBound=0, cat='Integer')
y_int = LpVariable("y", lowBound=0, cat='Integer')

model_integer += 3*x_int + 4*y_int
model_integer += x_int + 2*y_int <= 10
model_integer += 2*x_int + y_int <= 12

model_integer.solve()
print(f"Integer: x={x_int.varValue:.0f}, y={y_int.varValue:.0f}")技术支持

整数解不同于对连续解四舍五入。分支定界能找到最优整数解，但计算代价显著更高。

何时使用整数规划

当决策本质上是离散的：开/不开设施、指派/不指派员工、车辆是否访问地点时，请使用整数变量。债券市场中的优化常需要混合整数解。连续变量可能产生不合常理的“分数指派”，而二元变量能给出可执行的方案。

然而，整数规划的代价要高得多。含数百个整数变量的问题可能需要数小时，而连续 LP 只需数秒。若生产数量很大，整数性的重要性会降低，因为四舍五入对解影响甚微。务必先求解连续松弛以检查界，再决定是否投入完整的整数规划。

结语

线性规划会重塑您处理优化问题的方式。同一数学框架适用于截然不同的领域，从路径到生产计划再到投资组合管理。

从能用几何可视化的两个变量问题入手。实现基础的单纯形，以理解商业求解器背后的机制。围绕真实需求进行建模，将业务要求翻译为数学约束。

如欲深入学习，欢迎探索我们的 Python 优化入门 与 数据科学线性代数 课程，夯实数学基础。我们的 Python 路线 机器学习科学家 也是极佳选择。