线性规划的仿射缩放法求解示例
字数 2000 2025-10-26 19:15:23

线性规划的仿射缩放法求解示例

题目描述
考虑以下线性规划问题：
最大化目标函数：\(z = 3x_1 + 5x_2\)
约束条件：

  1. \(x_1 \leq 4\)
  2. \(2x_2 \leq 12\)
  3. \(3x_1 + 2x_2 \leq 18\)
  4. \(x_1, x_2 \geq 0\)

要求使用仿射缩放法求解该问题，逐步展示从初始内点出发收敛到最优解的过程。

解题过程

1. 标准化问题
首先将问题转化为标准型（等式约束、变量非负）。引入松弛变量 \(x_3, x_4, x_5 \geq 0\)：

  • \(x_1 + x_3 = 4\)
  • \(2x_2 + x_4 = 12\)
  • \(3x_1 + 2x_2 + x_5 = 18\)
    目标函数：\(z = 3x_1 + 5x_2 + 0x_3 + 0x_4 + 0x_5\)。
    约束矩阵 \(A = \begin{bmatrix} 1&0&1&0&0 \\ 0&2&0&1&0 \\ 3&2&0&0&1 \end{bmatrix}\)，右端项 \(b = [4,12,18]^T\)，成本向量 \(c = [3,5,0,0,0]^T\)。

2. 选择初始内点
仿射缩放法需从严格内点（所有变量 > 0）开始。例如，取 \(x^0 = [1,1,3,10,13]^T\)：

  • \(x_1 + x_3 = 1 + 3 = 4\)
  • \(2x_2 + x_4 = 2×1 + 10 = 12\)
  • \(3x_1 + 2x_2 + x_5 = 3×1 + 2×1 + 13 = 18\)
    所有变量为正，满足内点条件。

3. 仿射缩放方向计算
设当前迭代点为 \(x^k\)，对角矩阵 \(D_k = \text{diag}(x^k)\)。投影矩阵 \(P_k = I - D_k A^T (A D_k^2 A^T)^{-1} A D_k\)。
移动方向 \(d_k = D_k P_k D_k c\)。
步骤详解（以第一次迭代为例）：

  • \(x^0 = [1,1,3,10,13]^T\)，\(D_0 = \text{diag}(1,1,3,10,13)\)。
  • 计算 \(A D_0^2 A^T\)：
    \(D_0^2 = \text{diag}(1,1,9,100,169)\)，
    \(A D_0^2 A^T = \begin{bmatrix} 1&0&9&0&0 \\ 0&4&0&100&0 \\ 3&2&0&0&169 \end{bmatrix} \begin{bmatrix} 1&0&3 \\ 0&2&2 \\ 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 10 & 0 & 3 \\ 0 & 104 & 4 \\ 3 & 4 & 182 \end{bmatrix}\)。
  • 求逆：\((A D_0^2 A^T)^{-1}\)（具体数值略，记为 \(M^{-1}\)）。
  • 计算 \(P_0 = I - D_0 A^T M^{-1} A D_0\)。
  • 方向 \(d_0 = D_0 P_0 D_0 c\)，其中 \(D_0 c = [3,5,0,0,0]^T\)。
    最终得 \(d_0\) 为梯度 \(c\) 在约束空间内的投影，指向目标函数增长方向。

4. 步长选择与更新
为保证迭代点留在可行域内部，采用保守步长：
\(\alpha_k = 0.99 \times \min \left\{ \frac{-x_i^k}{(d_k)_i} \mid (d_k)_i < 0 \right\}\)。
若 \(d_k\) 无负分量，则问题无界（本例中不会发生）。
更新：\(x^{k+1} = x^k + \alpha_k d_k\)。

5. 收敛判断
重复步骤3-4，直到满足停止条件（如对偶间隙小于阈值 \(\epsilon = 10^{-6}\)）：
对偶间隙定义为 \(c^T x^k - b^T y^k\)，其中 \(y^k = (A D_k^2 A^T)^{-1} A D_k^2 c\) 为对偶变量估计。
当对偶间隙接近0时，当前解接近最优。

6. 最终结果
经过多次迭代后，解收敛至 \(x^* = [2,6,2,0,0]^T\)，目标函数值 \(z^* = 3×2 + 5×6 = 36\)。
与单纯形法结果一致，但仿射缩放法通过内部路径逼近最优解。

线性规划的仿射缩放法求解示例 题目描述 考虑以下线性规划问题： 最大化目标函数：\( z = 3x_ 1 + 5x_ 2 \) 约束条件： \( x_ 1 \leq 4 \) \( 2x_ 2 \leq 12 \) \( 3x_ 1 + 2x_ 2 \leq 18 \) \( x_ 1, x_ 2 \geq 0 \) 要求使用仿射缩放法求解该问题，逐步展示从初始内点出发收敛到最优解的过程。 解题过程 1. 标准化问题 首先将问题转化为标准型（等式约束、变量非负）。引入松弛变量 \( x_ 3, x_ 4, x_ 5 \geq 0 \)： \( x_ 1 + x_ 3 = 4 \) \( 2x_ 2 + x_ 4 = 12 \) \( 3x_ 1 + 2x_ 2 + x_ 5 = 18 \) 目标函数：\( z = 3x_ 1 + 5x_ 2 + 0x_ 3 + 0x_ 4 + 0x_ 5 \)。 约束矩阵 \( A = \begin{bmatrix} 1&0&1&0&0 \\ 0&2&0&1&0 \\ 3&2&0&0&1 \end{bmatrix} \)，右端项 \( b = [ 4,12,18]^T \)，成本向量 \( c = [ 3,5,0,0,0 ]^T \)。 2. 选择初始内点 仿射缩放法需从严格内点（所有变量 > 0）开始。例如，取 \( x^0 = [ 1,1,3,10,13 ]^T \)： \( x_ 1 + x_ 3 = 1 + 3 = 4 \) \( 2x_ 2 + x_ 4 = 2×1 + 10 = 12 \) \( 3x_ 1 + 2x_ 2 + x_ 5 = 3×1 + 2×1 + 13 = 18 \) 所有变量为正，满足内点条件。 3. 仿射缩放方向计算 设当前迭代点为 \( x^k \)，对角矩阵 \( D_ k = \text{diag}(x^k) \)。投影矩阵 \( P_ k = I - D_ k A^T (A D_ k^2 A^T)^{-1} A D_ k \)。 移动方向 \( d_ k = D_ k P_ k D_ k c \)。 步骤详解（以第一次迭代为例） ： \( x^0 = [ 1,1,3,10,13]^T \)，\( D_ 0 = \text{diag}(1,1,3,10,13) \)。 计算 \( A D_ 0^2 A^T \)： \( D_ 0^2 = \text{diag}(1,1,9,100,169) \)， \( A D_ 0^2 A^T = \begin{bmatrix} 1&0&9&0&0 \\ 0&4&0&100&0 \\ 3&2&0&0&169 \end{bmatrix} \begin{bmatrix} 1&0&3 \\ 0&2&2 \\ 1&0&0 \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} 10 & 0 & 3 \\ 0 & 104 & 4 \\ 3 & 4 & 182 \end{bmatrix} \)。 求逆：\( (A D_ 0^2 A^T)^{-1} \)（具体数值略，记为 \( M^{-1} \)）。 计算 \( P_ 0 = I - D_ 0 A^T M^{-1} A D_ 0 \)。 方向 \( d_ 0 = D_ 0 P_ 0 D_ 0 c \)，其中 \( D_ 0 c = [ 3,5,0,0,0 ]^T \)。 最终得 \( d_ 0 \) 为梯度 \( c \) 在约束空间内的投影，指向目标函数增长方向。 4. 步长选择与更新 为保证迭代点留在可行域内部，采用保守步长： \( \alpha_ k = 0.99 \times \min \left\{ \frac{-x_ i^k}{(d_ k)_ i} \mid (d_ k)_ i < 0 \right\} \)。 若 \( d_ k \) 无负分量，则问题无界（本例中不会发生）。 更新：\( x^{k+1} = x^k + \alpha_ k d_ k \)。 5. 收敛判断 重复步骤3-4，直到满足停止条件（如对偶间隙小于阈值 \( \epsilon = 10^{-6} \)）： 对偶间隙定义为 \( c^T x^k - b^T y^k \)，其中 \( y^k = (A D_ k^2 A^T)^{-1} A D_ k^2 c \) 为对偶变量估计。 当对偶间隙接近0时，当前解接近最优。 6. 最终结果 经过多次迭代后，解收敛至 \( x^* = [ 2,6,2,0,0]^T \)，目标函数值 \( z^* = 3×2 + 5×6 = 36 \)。 与单纯形法结果一致，但仿射缩放法通过内部路径逼近最优解。