一、线性规划的一般形式
线性规划问题，有 \(n\) 个变量 \(x_1, x_2, \cdots, x_n\)，满足一些线性约束的条件下，求目标函数的最值。
二、线性规划的标准形式
设有 \(n\) 个变量，\(m\) 个线性约束，目标函数为 \(z\)。
\[\max z = \sum_{i = 1} ^ n c_i x_i
\]
\[\text{s.t.} \begin{cases} \forall t \in [1, m], \sum\limits_{i = 1} ^ n a_{t, i} x_i = b_t \\ \forall i \in [1, n], x_i \ge 0 \end{cases}
\]
矩阵形式：
\[\max z = CX
\]
\[AX = b
\]
\[X \ge 0
\]
\[A = \begin{bmatrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m, 1} & a_{m, 2} & \cdots & a_{m, n} \end{bmatrix}
\]
-
目标函数求 \(\max\)。
-
线性约束为等式。
-
变量非负。
普通形式转标准形式
-
目标函数取 \(\min\) 可以通过取负变成取 \(\max\)。
-
线性不等式可以通过加变量变为线性等式。如 \(x_1 \le b\) 变为 \(x_1 + x_2 = b\)；\(x_1 \ge b\) 变为 \(x_1 - x_2 = b\)。
-
无约束变量 \(x \in \mathbb{R}\) 可以变为 \(x_1 - x_2, x_1 \ge 0, x_2 \ge 0\)。
三、线性规划对偶
最大化和最小化互换，常数与目标函数互换，改变不等号，变量与约束对应。
\[\max z = CX
\]
\[\text{s.t.} \qquad AX \le B, X \ge 0
\]
对偶形式为：
\[\min z = BY
\]
\[\text{s.t.} \qquad A ^ TY \ge C, Y \le 0
\]
例：
\[\max z = x_1 + x_2
\]
\[\text{s.t.} \begin{cases} x_1 \le 2 \\ x_2 \le 3 \\ x_1 \ge 0, x_2 \ge 0 \end{cases}
\]
对偶形式为：
\[\min z = 2y_1 + 3y_2
\]
\[\text{s.t.} \begin{cases} y_1 \ge 1 \\ y_2 \ge 1 \\ y_1 \ge 0, y_2 \ge 0 \end{cases}
\]
四、全幺模矩阵
充分条件：
-
仅由 \(-1, 0, 1\) 组成。
-
每列至多 \(2\) 个非零数。
-
行能被分成两个集合。
- 若一列中包含两个相同的非零数，处于第 \(x\) 和 \(y\) 行，则 \(x\) 和 \(y\) 不属于同一个集合。
- 若一列中包含两个不同的非零数，处于第 \(x\) 和 \(y\) 行，则 \(x\) 和 \(y\) 属于同一个集合。
充要条件：
任意一个子矩阵的行列式 \(\in \{0, 1, -1\}\)。
性质：
如果线性规划中 \(A\) 为全幺模矩阵，则存在一组线性规划最优解，使得 \(\forall i \in [1, n], x_i \in \{0, 1, -1\}\)。