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

本专题具体围绕线性规划和单纯形方法展开，结合MATLAB的`linprog`函数进行实战分析。

news 2026/5/12 13:30:22

本专题具体围绕线性规划和单纯形方法展开，结合MATLAB的linprog函数进行实战分析。

一、MATLAB 线性规划基础

1.1 linprog 函数标准形式

MATLAB的linprog函数求解的标准形式为：

\[\begin{aligned} \min \quad & c^T x \\ \text{s.t.} \quad & A \cdot x \leq b \\ & A_{eq} \cdot x = b_{eq} \\ & lb \leq x \leq ub \end{aligned}\]

关键要点：MATLAB默认求解的是最小化问题！

1.2 函数调用格式

% 完整格式
[x, fval, exitflag, output, lambda] = linprog(c, A, b, Aeq, beq, lb, ub, options)% 简化格式（无缺省参数时）
x = linprog(c, A, b)

参数	说明
`c`	目标函数系数向量（列向量）
`A, b`	不等式约束 \(Ax \leq b\)
`Aeq, beq`	等式约束 \(A_{eq}x = b_{eq}\)
`lb, ub`	变量下界和上界
`x`	最优解
`fval`	最优目标函数值
`exitflag`	收敛标志（1=收敛，-2=无可行解等）

二、实战案例详解（教材例题）

例题：求解以下线性规划问题

\[\begin{aligned} \min \quad & -x_1 + 4x_2 \\ \text{s.t.} \quad & x_1 + 3x_2 \leq 2 \\ & -x_1 + 2x_2 \geq 4 \\ & x_2 \geq 0 \end{aligned}\]

步骤1：转化为MATLAB标准形式

关键转换：将 \(\geq\) 约束转化为 \(\leq\) 约束

第二个约束 \(-x_1 + 2x_2 \geq 4\) 等价于 \(x_1 - 2x_2 \leq -4\)

步骤2：MATLAB代码实现

%% 线性规划求解示例
clear; clc;% 定义目标函数系数（注意是列向量）
c = [-1; 4];           % min -x1 + 4*x2% 不等式约束矩阵 A*x <= b
A = [1, 3;             % x1 + 3*x2 <= 21, -2];           % x1 - 2*x2 <= -4 （原约束转换）
b = [2; -4];% 等式约束（本题无）
Aeq = [];
beq = [];% 变量下界（x2 >= 0，x1无下界用-Inf）
lb = [-1e10; 0];       % x1 >= -10^10, x2 >= 0
ub = [];               % 无上界% 调用linprog求解
[x, fval, exitflag, output, lambda] = linprog(c, A, b, Aeq, beq, lb, ub);%% 结果输出
fprintf('========== 求解结果 ==========\n');
fprintf('最优解 x = [%.4f; %.4f]\n', x(1), x(2));
fprintf('最优值 fval = %.4f\n', fval);
fprintf('退出标志 exitflag = %d (%s)\n', exitflag, output.message);
fprintf('迭代次数: %d\n', output.iterations);
fprintf('算法: %s\n', output.algorithm);

步骤3：运行结果解析

Optimal solution found.x =-4.00000.0000fval =4.0000

结果分析：

最优解：\(x^* = (-4, 0)^T\)
最优值：\(f^* = 4\)
迭代次数：1次（使用对偶单纯形法）

三、高级参数与输出详解

3.1 exitflag 含义（表2-14）

值	含义	处理建议
1	收敛到最优解 ✓	正常，结果可用
0	迭代次数超过限制	增大`MaxIterations`
-2	无可行解	检查约束条件是否矛盾
-3	问题无界	检查是否遗漏约束
-4	算法执行中遇到NaN	检查数据有效性
-5	原问题与对偶问题都不可行	重新建模
-7	步长太小或其他病态条件	缩放问题数据

3.2 output 结构体详解

output = 包含以下字段的 struct:iterations: 1              % 迭代次数constrviolation: 0         % 约束违反量message: 'Optimal solution found.'  % 退出信息algorithm: 'dual-simplex'  % 使用的算法firstorderopt: 0           % 一阶最优性度量

3.3 lambda 结构体（对偶变量/影子价格）

lambda = 包含以下字段的 struct:lower: [2×1 double]        % 下界约束的Lagrange乘子upper: [2×1 double]        % 上界约束的Lagrange乘子eqlin: []                  % 等式约束的Lagrange乘子ineqlin: [2×1 double]      % 不等式约束的Lagrange乘子

经济意义：lambda.ineqlin 表示约束条件的影子价格，即约束右端项每增加1单位，目标函数的改善量。

四、算法选择（重要！）

MATLAB linprog 提供三种算法：

算法	特点	适用场景
`dual-simplex`	默认，对偶单纯形法	大多数问题，尤其是约束较多时
`interior-point`	内点法	大规模问题
`interior-point-legacy`	原始-对偶内点法	兼容旧版本

切换算法示例

% 设置使用内点法
options = optimoptions('linprog', 'Algorithm', 'interior-point');% 调用时传入options
[x, fval] = linprog(c, A, b, [], [], lb, [], options);

五、单纯形方法原理（配合MATLAB理解）

5.1 单纯形表迭代过程

教材中的Beale循环例子展示了单纯形法的退化与循环问题：

初始表 → 迭代1 → 迭代2 → ... → 迭代6 → 回到初始表（循环！）

关键观察：当存在退化的基本可行解（基变量为0）时，可能出现循环。

5.2 克服循环的方法

方法	核心思想	实现方式
摄动法	避免步长为0	在约束右端加微小扰动 \(\omega = (\epsilon, \epsilon^2, ...)^T\)
字典序法	按字典序选择离基变量	向量按第一个不同分量排序
Bland规则	最小下标规则	进基：选最小下标的负检验数；离基：选最小下标的比值

5.3 Bland规则实现效果

使用Bland规则后，同样的例子在6次迭代后收敛：

\[x^* = \left(\frac{3}{4}, 0, 0, 1, 0, 1, 0\right)^T, \quad z^* = -\frac{5}{4} \]

六、完整实战：生产计划优化（习题1）

问题描述

某工厂用甲、乙两台机床加工A、B、C三种零件，数据如下：

机床	可用机时	A(时间/成本)	B(时间/成本)	C(时间/成本)
甲	80	1机时/2元	1机时/3元	1机时/5元
乙	100	1机时/3元	2机时/4元	3机时/6元

需求：A=70件，B=50件，C=20件

MATLAB建模与求解

%% 生产计划优化问题
clear; clc;% 决策变量：x1=甲加工A, x2=甲加工B, x3=甲加工C
%          x4=乙加工A, x5=乙加工B, x6=乙加工C% 目标函数：最小化总成本
c = [2; 3; 5; 3; 4; 6];% 约束1：机时限制
% 甲机床：x1 + x2 + x3 <= 80
% 乙机床：x4 + 2*x5 + 3*x6 <= 100
A = [1, 1, 1, 0, 0, 0;0, 0, 0, 1, 2, 3];
b = [80; 100];% 约束2：需求满足（等式约束）
% A零件：x1 + x4 = 70
% B零件：x2 + x5 = 50
% C零件：x3 + x6 = 20
Aeq = [1, 0, 0, 1, 0, 0;0, 1, 0, 0, 1, 0;0, 0, 1, 0, 0, 1];
beq = [70; 50; 20];% 非负约束
lb = zeros(6, 1);
ub = [];% 求解
[x, fval, exitflag, output] = linprog(c, A, b, Aeq, beq, lb, ub);%% 结果展示
fprintf('========== 最优生产计划 ==========\n');
fprintf('甲机床：A=%.1f件, B=%.1f件, C=%.1f件\n', x(1), x(2), x(3));
fprintf('乙机床：A=%.1f件, B=%.1f件, C=%.1f件\n', x(4), x(5), x(6));
fprintf('最小总成本: %.2f元\n', fval);
fprintf('甲机床使用: %.1f/80 机时\n', sum(x(1:3)));
fprintf('乙机床使用: %.1f/100 机时\n', x(4)+2*x(5)+3*x(6));

七、常见错误与调试技巧

7.1 错误排查清单

现象	可能原因	解决方案
`exitflag = -2`	约束矛盾	检查是否所有需求都能被满足
`exitflag = -3`	目标函数可无限减小	添加缺失的约束条件
结果明显不对	最大化/最小化混淆	`max`问题转为`min`时，c取负
约束不满足	方向转换错误	\(\geq\) 约束需乘以-1转为 \(\leq\)

7.2 调试技巧

% 1. 检查约束是否满足
residual = A*x - b;  % 应 <= 0
fprintf('约束违反量: %e\n', max(residual));% 2. 验证等式约束
eq_residual = Aeq*x - beq;
fprintf('等式约束误差: %e\n', norm(eq_residual));% 3. 显示详细迭代过程
options = optimoptions('linprog', 'Display', 'iter');