「Note」Liner Programming

开始吟唱

问题引入

定义

线性规划是在一组线性约束条件下，求一线性目标函数最大或最小的问题。

标准形式

要求

• 目标函数要求 $\max$
• 约束条件均为等式
• 决策变量为非负约束

形式

$$ \begin{matrix} \max z = \sum_{j = 1}^{n}c_jx_j \\ s.t \begin{cases} \sum_{j = 1}^{n} a_{i, j}x_j = b_i & (i = 1, 2, \dots, m) \\ x_j \ge 0 & (j = 1, 2, \dots, n) \end{cases} \end{matrix} $$

可改写为矩阵形式

$$ \begin{matrix} \max \mathbf{z} = \mathbf{c}^T\mathbf{x} \\ A\mathbf{x} = \mathbf{b} \\ \mathbf{x} \ge 0 \\ A = \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{matrix} \right] \end{matrix} $$

改写

将普通形式改写为标准形式方法是

• 若目标函数为最小化，通过取负，求最大化
• 约束不等式为小于等于不等式，在左端加入非负变量，转变为等式
• 若存在取值无约束的变量，可转变为两个非负变量的差

对偶原理

对于原问题

$$ \begin{matrix} \max z = \sum_{j = 1}^{n}c_jx_j \\ s.t \begin{cases} \sum_{j = 1}^{n} a_{i, j}x_j \le b_i & (i = 1, 2, \dots, m) \\ x_j \ge 0 & (j = 1, 2, \dots, n) \end{cases} \end{matrix} $$

将其改写为

$$ \begin{matrix} \min z = \sum_{i = 1}^{m}b_jy_i \\ s.t \begin{cases} \sum_{i = 1}^{m} a_{i, j}y_i \ge c_i & (j = 1, 2, \dots, n) \\ y_i \ge 0 & (i = 1, 2, \dots, m) \end{cases} \end{matrix} $$

用矩阵表示为

$$ \begin{matrix} \max \mathbf{c}^T \mathbf{x} : &A\mathbf{x} \le \mathbf{b}, &\mathbf{x} \ge 0 \\ \min \mathbf{b}^T \mathbf{y} : &A^T\mathbf{y} \ge \mathbf{c}, &\mathbf{y} \ge 0 \end{matrix} $$