线性规划的椭圆法求解示例
题目描述
考虑以下线性规划问题：
最小化 \(c^T x\)
满足约束 \(Ax = b\) 且 \(x \geq 0\)，
其中
\(c = \begin{pmatrix} -1 \\ -2 \end{pmatrix}\),
\(A = \begin{pmatrix} 1 & 1 \end{pmatrix}\),
\(b = \begin{pmatrix} 5 \end{pmatrix}\).
要求使用椭圆法（Ellipsoid Method）求解该问题，并详细解释其原理和步骤。
解题过程
1. 椭圆法简介
椭圆法是解决线性规划问题的一种理论算法，尤其以多项式时间复杂性著称。其核心思想是：
- 将线性规划问题转化为可行性问题（即寻找满足 \(Ax \leq b, x \geq 0\) 的点）。
- 从一个包含潜在解的椭圆体（椭球）开始，通过迭代缩小椭圆体体积，最终找到可行解或证明问题无解。
对于本例，问题可改写为：
\[\begin{cases} \min -x_1 - 2x_2 \\ x_1 + x_2 = 5 \\ x_1, x_2 \geq 0 \end{cases} \]
由于等式约束可转化为不等式（\(x_1 + x_2 \leq 5\) 且 \(-x_1 - x_2 \leq -5\)），椭圆法可处理此类系统。
2. 构造可行性问题
定义可行域 \(P = \{ x \mid Ax \leq b, x \geq 0 \}\)，其中：
\[A = \begin{pmatrix} 1 & 1 \\ -1 & -1 \end{pmatrix}, \quad b = \begin{pmatrix} 5 \\ -5 \end{pmatrix}. \]
加入非负约束 \(x_1 \geq 0, x_2 \geq 0\)，系统共4个不等式。
3. 初始化椭圆体
选择一个足够大的椭圆体 \(E_0\) 包含可行域 \(P\)。通常以原点为中心，半径足够大的球体开始。
- 中心 \(x_0 = (0, 0)\)
- 初始椭圆体矩阵 \(A_0 = R^2 I\)，取 \(R = 10\) 确保包含可行解（例如 \((5, 0)\) 在圆内）。
\[E_0 = \{ x \mid (x - x_0)^T A_0^{-1} (x - x_0) \leq 1 \} \]
4. 迭代过程
第1轮迭代：
- 当前椭圆体中心 \(x_0 = (0,0)\)。
- 检查是否满足所有约束：
- 约束 \(x_1 + x_2 \leq 5\) 满足（0 ≤ 5）。
- 约束 \(-x_1 - x_2 \leq -5\) 不满足（0 ≤ -5 为假）。
- 选择违反的约束作为切割平面： \(-x_1 - x_2 \leq -5\) 即 \(x_1 + x_2 \geq 5\)。
- 通过中心的切割平面将椭圆体分为两部分，保留包含可行解的一半（因为 \(P\) 在 \(x_1 + x_2 \geq 5\) 一侧）。
- 构建新椭圆体 \(E_1\) 包含半椭圆体：
- 计算切割平面法向量 \(a = (1, 1)\)。
- 更新公式（省略详细矩阵运算）：
\[ x_{1} = x_0 - \frac{1}{n+1} \frac{A_0 a}{\sqrt{a^T A_0 a}} \]
\[ A_1 = \frac{n^2}{n^2-1} \left( A_0 - \frac{2}{n+1} \frac{A_0 a a^T A_0}{a^T A_0 a} \right) \]
其中 $ n=2 $。代入 $ A_0 = 100I $, $ a = (1,1) $，得：
\[ x_1 \approx (3.54, 3.54), \quad A_1 \approx \begin{pmatrix} 50 & -50 \\ -50 & 50 \end{pmatrix}. \]
5. 继续迭代
第2轮迭代：
- 中心 \(x_1 = (3.54, 3.54)\)。
- 检查约束：
- \(x_1 + x_2 = 7.08 > 5\) 违反 \(x_1 + x_2 \leq 5\)。
- 切割平面： \(x_1 + x_2 \leq 5\)。
- 更新椭圆体 \(E_2\) 保留中心满足 \(x_1 + x_2 \leq 5\) 的部分。
- 类似计算得新中心 \(x_2 \approx (2.5, 2.5)\)，椭圆体缩小。
重复迭代直到椭圆体体积足够小（例如小于阈值 \(\varepsilon = 0.001\)），或中心满足所有约束。
6. 最终解与验证
- 最终中心收敛至 \(x^* = (0, 5)\)（可行点）。
- 代入目标函数： \(c^T x = -1 \times 0 - 2 \times 5 = -10\)。
- 验证：
- 约束 \(x_1 + x_2 = 5\) 满足，非负性满足。
- 最优性：通过画图或单纯形法可验证 \((0,5)\) 确实是最优解。
7. 关键点总结
- 椭圆法通过切割平面逐步缩小椭圆体，逼近可行解。
- 每次迭代利用违反约束构造切割平面，确保保留可行解。
- 本例展示了椭圆法处理小规模问题的过程，实际中多用于理论证明。