线性规划

1. 前言

线性规划是个很有用的东西，本博客会讲解它的基本模型。

2. 样式

现在有$n$种资源，第$i$种资源有$p_i$件。现在有$m$种商品，第$k$种商品所要用的第$j$种资源数量为$a_{kj}$，利润为$f_k$。

3. 举例

现在有$110$张写字纸，$20$个封面。一个作业本需要$1$个封面$10$张纸，卖出$5$元；一个日记本需要$3$个封面$8$张纸，卖出$7$元，求在资源够的情况下各生产多少，才使获得利润最多?

4. 解法

4.1. 明确目标

依题意列方程或不等式。

比如上题的方程为：

$\text{解：设需要做本子}x\text{个，日记本}y\text{本，则有}$

$\begin{cases}x\ge 0\\y\ge0\\x+3y\le20\\10x+8y\le110\end{cases}$

4.2. 转换为函数

作$l1:x+3y=20=>y=\frac{20-x}{3}=>y=-\frac{1}{3}x+\frac{20}{3}$（这里划等号是为了不浪费资源）和$l2:10x+8y=110=>y=\frac{110-10x}{8}=>y=-\frac{5}{4}x+\frac{55}{4}$的图像，并且将交集部分涂上阴影，如下图所示。

4.3. 解方程

所求的答案即为$l1$和$l2$的交点坐标，即方程

$\begin{cases}x+3y=20\\10x+8y=110\end{cases}$

的解。

5. 后记

一般来讲也就考到$3$维了。

其实观察这个过程，本质就是解方程
$\begin{cases}\sum_{i=1}^m a_{i1}x_i=p_1\\\sum_{i=1}^m a_{i2}x_i=p_2\\...\\\sum_{i=1}^m a_{in}x_i=p_n\end{cases}$。

所以，应该考试顶多考到$3$维就够了。