线性规划问题的对偶问题及其求解

### 线性规划对偶问题概述

线性规划中的对偶问题是基于原始线性规划模型构建的另一个线性规划问题。当原问题是求目标函数最小化时，对偶问题旨在找到原问题目标函数的下界；反之，如果原问题是最大化，则对偶问题寻求的是上界[^4]。

对于标准形式的线性规划问题：

\[
\begin{align*}
& \text{minimize} & c^T x \\
& \text{subject to} & Ax = b,\\
&& x \geq 0,
\end{align*}
\]

对应的对偶问题可表示为:

\[
\begin{align*}
& \text{maximize} & b^Ty \\
& \text{subject to} & A^Ty + s = c,\\
&& s \geq 0.
\end{align*}
\]

这里 \(y\) 是对偶变量向量，\(s\) 表示松弛变量[^1]。

### 对偶问题的应用场景

某些特定条件下，处理对偶问题能够简化计算过程或提供更好的数值稳定性。例如，在资源分配类问题中，通过分析对偶变量的意义可以获得关于成本敏感度的信息，这对于决策制定非常有价值。另外，强对偶定理指出，若原问题有最优解，则其对偶问题也必定存在相同的最优值，这意味着可以通过转换成较易解决的形式间接获得解答。

### 求解方法

#### 单纯形法

单纯形算法不仅适用于直接求解原问题，也可以用来高效地求解对偶问题。该方法利用迭代更新的方式逐步接近最优点直到收敛为止。具体实现涉及到基变换操作以及引入人工变量等技巧来初始化可行域内的起点位置[^2]。

% MATLAB代码片段展示如何调用内置函数linprog求解LP及其对偶问题
f = [-5; -4]; % 目标系数取负号因为MATLAB默认是最小化
A = [1 2; 3 2];
b = [18; 42];
lb = zeros(2,1); % 变量非负约束
[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);
disp('Optimal solution:');
disp(x);
disp('Dual variables (Lagrange multipliers):');
disp(lambda.ineqlin);

上述Matlab脚本展示了怎样借助`linprog()`命令快速获取线性规划问题的最佳解及相应的拉格朗日乘子（即对偶变量）。注意这里的输入参数设置需严格遵循官方文档说明以确保正确性。