原始-对偶（Primal-Dual）算法求解线性规划_原始对偶算法

​原始-对偶（Primal-Dual）算法（Dantzig, Ford, and Fulkerso,1956）是用来求解线性规划的一种算法，可以看作是单纯形法的一种变体，目的是减少迭代次数。

构建该算法的核心依据为原问题和对偶问题的最优解满足的互补松弛关系。
考虑以下线性规划问题$P$：
$$\begin{gathered} \min {\mathbf{c}}^T\mathbf{x} \\ s.t. \\ \mathbf{A}\mathbf{x}⩾\mathbf{b} \\ \mathbf{x}⩾0 \end{gathered}$$

和他的对偶问题$D$：
$$\begin{gathered} \max {\mathbf{b}}^T\mathbf{y} \\ s.t. \\ {\mathbf{A}}^{\mathbf{T}}\mathbf{y}⩽\mathbf{c} \\ \mathbf{y}⩾0 \end{gathered}$$
​
其中$\mathbf{A}$ 是$m\times n$的矩阵, $\mathbf{b}$ 和 $\mathbf{c}$ 都大于0。
​
假设 $\mathbf{x}$ 和 $\mathbf{y}$ 分别是问题 $P$, $D$ 的可行解，判断 $\mathbf{x}$ 和 $\mathbf{y}$ 是否为最优解，需要同时考虑两种互补松弛条件：

• 第一种：primal complementary slackness conditions
  $$\begin{gathered} x_j>0\Rightarrow A^{j}y=c_j\left(1\right) \\ {A}^{j}y<c_j\Rightarrow x_j=0\left(2\right) \end{gathered}$$
  其中 ${\mathbf{A}}^{\mathbf{j}}$ 表示系数矩阵的第 $j$ 列。
  ​
  (1)表示，当原问题的可行解 $x_j>0$ 时，它对应的对偶问题的约束为紧约束（等号成立）。
  (2)表示，当对偶问题的某个约束为松约束时，它对应的原问题的可行解 $x_j=0$ 。

​- 第二种：dual complementary slackness conditions
$$\begin{gathered} {y}_i>0\Rightarrow A_{i}x=b_i\left(3\right) \\ {A}_{i}x<b_i\Rightarrow y_i=0\left(4\right) \end{gathered}$$
​其中 ${\mathbf{A}}_{\mathbf{i}}$ 表示系数矩阵的第 $i$ 行。

可以从经济分析的角度理解这一条件：
假设原问题是形如 $D$ 的资源分配模型，$\mathbf{c}$ 为资源限额，此时每条供给约束都对应着一个影子价格。影子价格的定义是：管理层愿意为获取额外一定单位的既定资源而多付出的最大价格。

表达式 (3)表示当影子价格大于0时，表示在现有基础资源限额上，每增加一单位资源，收益便会改善，说明现有资源已经被消耗殆尽，约束为紧约束；

表达式(4)说明假如当前资源过剩，并不稀缺时，说明并不需要获取额外单位的既定资源，因此影子价格为0 。

只有当上述条件 (1)~(4) 全部同时满足的时候，$\mathbf{x}$ 和 $\mathbf{y}$ 才会是最优解。

因此，为了找到最优解，首先需要找到能够满足上述条件的松、紧约束的下标集合。这里考虑两种集合：
J = { j    ∣    y A j = c j } I = { i    ∣    y i = 0 } J = \{j \;|\;\boldsymbol{y}\boldsymbol{A}^j=c_j\}\\ I = \{i \;|\;y_i=0\} J={ j∣y