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

线性规划核心概念全解析：从规范型到基变量，一网打尽

news 2026/5/24 6:10:54

1. 线性规划入门：从实际问题到数学模型

第一次接触线性规划时，我被它强大的实用性震撼到了。想象你是一家工厂的生产主管，需要决定生产A、B两种产品各多少才能利润最大化——这就是典型的线性规划问题。这类问题有三个关键特征：目标明确（比如利润最大或成本最小）、资源有限（比如原材料或工时限制）、决策变量连续可调（比如产量可以是任意非负数）。

举个生活中的例子：假设你每天需要摄入至少5单位蛋白质和3单位维生素，牛肉每份提供2单位蛋白质1单位维生素价格30元，鸡蛋每份提供1单位蛋白质1单位维生素价格10元。如何以最低成本满足营养需求？这就是一个标准的线性规划问题：

# 最小化成本：30x1 + 10x2 # 约束条件： # 2x1 + x2 ≥ 5 (蛋白质) # x1 + x2 ≥ 3 (维生素) # x1, x2 ≥ 0

线性规划模型通常表示为：

目标函数：max/min c₁x₁ + c₂x₂ + ... + cₙxₙ
约束条件：a₁₁x₁ + ... + a₁ₙxₙ ≤/=/≥ b₁
非负约束：x₁, ..., xₙ ≥ 0

初学者常犯的错误是忽略非负约束，或者混淆最大化与最小化问题的转换。我在第一次建模时就曾把"≥"错写成"≤"，导致计算结果完全不合理。记住：约束条件的符号方向直接影响可行解的范围。

2. 规范型与标准型：线性规划的两种面孔

2.1 规范型（Canonical Form）

规范型是最接近自然描述的形态，具有以下特征：

目标函数：统一为最小化（若原问题为最大化，目标函数乘以-1）
约束条件：全部为"≥"不等式（资源限制类约束）
决策变量：全部非负

比如生产计划问题：

min -3x1 - 5x2 # 原为max 3x1 + 5x2 s.t. x1 + 2x2 ≥ 8 # 原料需求 3x1 + 2x2 ≥ 12 # 工时限制 x1, x2 ≥ 0

2.2 标准型（Standard Form）

标准型是算法处理的最佳形式，要求：

目标函数：统一为最大化
约束条件：全部为等式
决策变量：全部非负

转换技巧：

不等式转等式：引入松弛变量(slack variables)
- "≤"约束：加松弛变量（如x₃ = 8 - x₁ - 2x₂）
- "≥"约束：减剩余变量(surplus variables)
自由变量处理：
- 若x无符号限制，替换为x⁺ - x⁻（x⁺, x⁻ ≥ 0）

示例转换：原问题：

max x1 + 2x2 s.t. 3x1 + 4x2 ≤ 10 x1 - x2 ≥ 2 x1 ≥ 0 (x2无限制)

标准型：

max x1 + 2x2⁺ - 2x2⁻ s.t. 3x1 + 4x2⁺ - 4x2⁻ + x3 = 10 x1 - x2⁺ + x2⁻ - x4 = 2 x1,x2⁺,x2⁻,x3,x4 ≥ 0

提示：实际计算时建议先转换为规范型再转标准型，可以避免符号混乱。我在处理金融投资组合优化问题时，就曾因直接转换标准型导致约束方向错误，浪费了半天调试时间。

3. 基变量与可行解：寻找最优解的钥匙

3.1 基阵与基本解

假设标准型问题有m个等式约束和n个变量(n>m)。从系数矩阵A中选取m个线性无关的列向量组成基阵B，对应的变量称为基变量，其余为非基变量。

基本解的求法：

令所有非基变量=0
解方程组Bx_B = b得到基变量值

import numpy as np # 示例：max x1 + x2 | x1 + 2x2 + x3=8, 3x1 + 2x2 + x4=12 A = np.array([[1,2,1,0], [3,2,0,1]]) b = np.array([8,12]) # 选择第1、2列作为基 B = A[:,[0,1]] x_B = np.linalg.solve(B, b) # 得到x1=2, x2=3 基本解 = [2, 3, 0, 0] # x3,x4为非基变量