A-level 数学/OCR/D1/线性规划

线性规划是一种利用直线图形和不等式寻找问题最佳解决方案（优化）的方法。

线性规划问题的例子

一家工厂生产两种类型的椅子，A 型和 B 型。工厂生产 A 型椅子每把利润为 10 英镑，生产 B 型椅子每把利润为 10 英镑。A 型椅子需要 20 个工时，B 型椅子需要 30 个工时。每把 A 型椅子需要 3 平方米木材；每把 B 型椅子需要 5 平方米木材。假设每周有 400 个工时和 50 平方米木材可用，那么每周应该生产多少把每种类型的椅子才能使工厂的利润最大化？

图形法

解决这个问题的一种方法是在坐标轴上绘制 a 和 b，然后绘制一条线来表示每个约束作为不等式。这将导致一个可行区域，该区域是满足所有约束条件的区域。问题的最佳解决方案将位于该区域的顶点之一。

单纯形法

首先，我们需要用线性方程来表示这个问题。我们将生产的 A 型椅子数量称为 *a*，生产的 B 型椅子数量称为 *b*。然后我们可以看到

${\begin{aligned}20a+30b\leq 400\Rightarrow &2a+3b\leq 40\\&3a+5b\leq 50\\&a\geq 0\\&b\geq 0\end{aligned}}$

这些被称为线性规划问题的约束。要最大化的函数（称为目标函数）为

$P=10a+10b\,$

P 表示在给定的 a 和 b 值下的利润。要使用单纯形法，我们必须将约束条件和目标函数转换为以下格式

${\begin{aligned}P-10a-10b=0\\2a+3b+s=40\\3a+5b+t=50\end{aligned}}$

变量 s 和 t 被称为松弛变量。它们允许我们表示在达到该约束的最大值之前我们拥有的余地。这也意味着我们不再需要使用不等式。我们将所有方程中变量的系数设置在一个初始“表格”中，最后一行是每个方程的右边，如下所示

${\begin{matrix}P&a&b&s&t&=\\1&-10&-10&0&0&0\\0&2&3&1&0&40\\0&3&5&0&1&50\end{matrix}}$

设置好表格后，就按照单纯形算法进行操作

1. 考虑顶行有负数的任何一列，将最后一列的值除以同一行中正在考虑的列的正值。在我们当前的例子中，我们看到 a 列和 b 列在顶行有负值。我们任意决定考虑 a 列，因此我们将执行

${\frac {40}{2}}=20$

${\frac {50}{3}}=16{\frac {2}{3}}$

现在我们选择 a 列中的值 3，因为它在我们将 50 除以它时给了我们最小的值。3 现在被称为枢轴。

2. 将枢轴所在的整行除以枢轴。

3. 现在我们需要将其他两行中 a 的值减至 0。我们必须通过添加或减去枢轴行的常数倍数来做到这一点。

4. 如果顶行中仍然存在任何负数，我们必须重复算法。

参见

• 运筹学/单纯形法