凸优化 - 线性规划

方法论

线性规划，也称为线性优化，是一种用于解决数学问题的方法，其中关系本质上是线性的。线性规划的基本性质是最大化或最小化一个**目标函数**，并受一些**约束**条件的限制。目标函数是一个线性函数，它是从问题的数学模型中获得的。约束条件是强加于模型上的条件，并且也是线性的。

**步骤 1** - 在以下约束条件下最大化 $5x+3y$

$x+y\leq 2$，

$3x+y\leq 3$，

$x\geq 0 \:和 \:y\geq 0$

**解** -

第一步是在图上找到可行域。

从图中可以清楚地看出，可行域的顶点是

$\left ( 0, 0 \right )\left ( 0, 2 \right )\left ( 1, 0 \right )\left ( \frac{1}{2}, \frac{3}{2} \right )$

令 $f\left ( x, y \right )=5x+3y$

将这些值代入目标函数，我们得到 -

$f\left ( 0, 0 \right )$=0

$f\left ( 0, 2 \right )$=6

$f\left ( 1, 0 \right )$=5

$f\left ( \frac{1}{2}, \frac{3}{2} \right )$=7

因此，函数在 $\left ( \frac{1}{2}, \frac{3}{2} \right )$ 处取得最大值。

**步骤 2** - 一家手表公司生产电子表和机械表。长期预测表明，每天至少需要 100 块电子表和 80 块机械表的需求。由于生产能力的限制，每天最多只能生产 200 块电子表和 170 块机械表。为了满足运输合同，每天必须运送至少 200 块手表。

如果每售出一块电子表就会损失 2 美元，但每售出一块机械表就会获得 5 美元的利润，那么每天应该生产多少块每种手表才能最大化净利润？

**解** -

令 $x$ 为生产的电子表数量

$y$ 为生产的机械表数量

根据题意，每天至少要生产 100 块电子表，最多生产 200 块电子表。

$\Rightarrow 100 \leq \:x\leq 200$

类似地，每天至少要生产 80 块机械表，最多生产 170 块机械表。

$\Rightarrow 80 \leq \:y\leq 170$

由于每天至少要生产 200 块手表。

$\Rightarrow x +y\leq 200$

由于每售出一块电子表就会损失 2 美元，但每售出一块机械表就会获得 5 美元的利润，

总利润可以计算为

$利润 =-2x + 5y$

我们需要最大化利润，因此，这个问题可以表述为 -

在以下约束条件下最大化 $-2x + 5y$

$100 \:\leq x\:\leq 200$

$80 \:\leq y\:\leq 170$

$x+y\:\leq 200$

将上述方程在图上绘制出来，我们得到，

可行域的顶点是

$\left ( 100, 170\right )\left ( 200, 170\right )\left ( 200, 180\right )\left ( 120, 80\right ) 和 \left ( 100, 100\right )$

目标函数的最大值在 $\left ( 100, 170\right )$ 处取得。因此，为了最大化净利润，应该生产 100 块电子表和 170 块机械表。

打印页面