开始吟唱
问题引入
定义
线性规划是在一组线性约束条件下，求一线性目标函数最大或最小的问题。
标准形式
要求
- 目标函数要求 \(\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} \] 标签：begin,27,end,matrix,04,sum,ge,mathbf,LinerProgramming From： https://www.cnblogs.com/Iridescent41/p/17528177.html