什么是线性规划

线性规划的英文是 Linear Programming。注意，Programming 不是编程的意思，它指的是一类优化问题。从字面翻译，Linear Programming 就是一种线性的优化问题。

线性规划 link

我们看一个例子。

第一行的表达式 $7x_1 + 6x_2$ 称为目标函数，它前面那个 max 是 maximize 的缩写，代表优化方向。即，找到满足条件的 $x_1, x_2$ 使得这个目标函数值最大。接下来的三行公式描述 $x_1, x_2$ 要满足的条件，其中 s.t. 是 subject to 的缩写。

以第一个条件为例，如果 $x_1=40, x_2=0$, 它满足 $3x_1 + x_2 \leq 120$ 这个条件。但是，它不满足第三个条件 $x_1\leq 35$。因此 $x_1=40, x_2=0$ 不符合要求。

可以验证 $x_1=0, x_2=0$ 满足上述三个条件，因此它是一个可行解。显然，它不是最优解。最优解要使得目标函数值最大。

如果把一个优化问题写成上面的形式，即目标函数和约束条件的形式，一般称它为数学规划。线性规划指的就是目标函数和约束条件都是线性的数学规划问题。

什么是线性？简单来说，就是变量的系数是常数，而且指数是1，例如 $3 x_1 + x_2 $。二次及以上就是非线性，比如 $2 x_1^2 + 3$，$4x_1 + x_1x_2$。

我们的核心问题就是求线性规划问题的最优解。换句话说，要找到一个算法，任给一个线性规划的例子，能够在合理的时间内计算这个例子的最优解，或者判断无解。

有什么用 link

注意数学规划的形式，它有两个关键要素，一个是目标，另一个是约束条件。在企业的经营和管理中，很多问题都可以这样去描述。

粗略地讲，经营的目标一般是收益，约束条件可以是成本、效率或者资源等等。目标和约束还可以相互转换。当问题规模很大时，决策就变得复杂。人工决策不仅效率低，而且质量得不到保证。

在这种情况下，自动化的决策决策工具，就能发挥很大的价值。那么线性规划，就为自动化决策工具提供了算法基础。

接下来我举几个实际应用的场景。

• 商品采购 一家大型超市，或者电商平台，有几千种商品在卖。可能每天都需要补货。如果多补点货，采购成本会降低，但是库存成本会增加；如果少补一点，万一缺货了，顾客体验就差。问题来了，什么时候补货，补哪些商品，补多少货。收益和成本怎么平衡。
• 物流规划 物流简单说就是运货。需要把货物从出发地运输到目的地。目标是费用越少越好，约束是时效要保障。这就涉及到车辆的路径规划，仓库的选址规划，车辆的调度等等。简单来说，给你一批货，如果要暂存，仓库建哪里，建几个；运输的时候，用什么交通工具，货车还是火车或者飞机；如果是货车，用大车还是小车；货物装车的时候，怎么装才能装满；运输的时候，走什么路线等等。
• 机器人调度 在制造业中，尤其是汽车和半导体行业，有大量的工业机器人在车间7*24小时工作。注意，工业机器人是满足特定功能的自动化设备，不一定是人的形态。例如机械臂，机械手，自动化的物流车等。一个工件对应多个任务，一个任务对应一种机器人。给定一批工件和任务，如何调度机器人执行任务，才能最大化效率。
• 生产运营 制造业的生产运营一般有两类决策问题：一是排产；二是排班。工厂一般有多条流水线，每条流水线负责一些产品的生产任务。不同的任务有不同的工序和加工时间，以及需要的资源。如何安排这些任务，使得工厂的产能最大化。排班主要是安排人，把人安排在对应的任务，或者对应的机器，目标是人和机器的产出最大化。
• 广告营销 假如你需要打广告，也就是买流量。广告平台采取的是竞价模式。如果买流量的人多，那流量就贵，那么收益就少。所以，什么时候买，买多少流量，收益能最大化。你有一些用户，你想给用户发优惠券，让他来买你的东西。问题来了，发给哪些用户，发什么优惠券，发多少金额。

还有更多的例子，但是没必要都列出来。我们知道它有用就够了。它的核心功能就是作为一个基础的决策工具。