废话

• 小吐槽

  这篇文章是续7月份省选无法拿到博客源码和八月初博客挂掉之后的第一篇博客，这之间的博文全部都放在了 里有时间会移植过来。

什么是线性规划？

引入

线性规划问题是最优化问题的一个分支，通常用于解决工厂的资源配置问题。对于每组变量有与其对应的限制条件，在满足所有条件的前提下最大或最小化目标函数。举个现实例子：

现在有甲、乙两种资源，和 四中由甲乙资源生产出来的产品，现有资源数、单位产品所需资源数以及单位产品可获得利润如下表所示。问如何组织生产能够使得利润最大？

我们可以用数学公式来记录这几个变量之间的关系

设总利润为 ，产品 的生产量为 。

目标：

$$\max z=8x_1+20x_2+12x_3+15x_4$$

约束条件：

$$\left\{\begin{matrix} x_1+10x_2+2x_3+3x_4\le 18000\\ 3x_1+2x_2+5x_3+4x_4\le 13000\\ x_1,x_2,x_3,x_4\ge 0 \end{matrix}\right.$$

通过这个例子，我们可以抽象出来线性规划的模型：

$$\max \sum_{j=1}^nc_jx_j$$ $$\begin{array} \\s.t. \left\{\begin{matrix} \sum_{j=1}^na_{ij}x_j\le b_i \ \ \ (i=1,\dots,m)\\ x_j\ge 0 \ \ \ (j=1,\dots,n) \end{matrix}\right. \end{array}$$

其中 表示第 种产品的单位利润， 为第 种产品需要消耗第 种资源的消耗量， 为第 种资源的资源上限。

为了方便理解原问题和对偶问题的关系，这里先将刚才的例子转换为对偶问题再进行单纯形运算。

什么是对偶问题

我们将刚才的例子转换一下，现在要求将甲、乙两种资源租给其他单位，使得本单位获利不低于其他单位生产出来的产品利润，要求最小化甲、乙资源总价值之和。

转化为线性规划模型：

目标：

$$\min w = 18000y_1+13000y+2\\$$

约束条件：

$$\begin{cases} y_1+3y_2\ge8\\ 10y_1+2y_2\ge20\\ 2y_1+5y_2\ge12\\ 3y_1+4y_2\ge15\\ y_1,y_2\ge0 \end{cases}$$

如果我们用矩阵的视角来观察原问题和对偶型问题的线性规划模型便可发现，对偶型问题实际上就是将原问题行列互换，并将约束条件取反。具体的变换规则可以参考这篇博客。

那么接着，我们终于可以开始学习如何求出最后的最优策略了。

什么是单纯形

下面先介绍一些概念：

设 是约束方程组的 维系数矩阵，其秩为 ，是矩阵 中的一个 阶的满秩子矩阵，不失一般性，设

$$A=\begin{pmatrix} &a_{11} \ &\dots \ &a_{1m} \ &a_{1m+1} \ & \dots \ &a_{1n}\\ &\vdots \ &\ddots \ &\vdots \ &\vdots \ & \ddots \ &\vdots\\ &a_{m1} \ &\dots \ &a_{mm} \ &a_{mm+1} \ & \dots \ &a_{mn} \end{pmatrix}$$ $$X = \begin{pmatrix} x_1 \ \dots \ x_m \ x_{m+1} \ \dots \ x_{n} \end{pmatrix}^T$$ $$B=\begin{pmatrix} &a_{11} \ &\dots \ &a_{1m}\\ &\vdots \ &\ddots \ &\vdots\\ &a_{m1} \ &\dots \ &a_{mm} \end{pmatrix}$$

我们对线性规划问题的解进行一些分类：

• 可行解
  满足线性规划所有约束条件的一组解被称为可行解，可行解不一定满足最优策略。
• 最优解
  包含于可行解中，且满足最优策略。