运筹学/线性规划

线性规划（LP）是一种数学建模技术，用于将有限的资源（如材料、机器等）分配给多个竞争性活动（如项目、服务等）。典型的线性规划问题包括一个线性目标函数，该函数需要在有限数量的线性约束条件下被最大化或最小化。（线性函数是指具有以下形式的函数 $a_{1}x_{1}+a_{2}x_{2}+\cdots a_{n}x_{n}$ 其中 $x_{1},x_{2}\cdots x_{n}$ 都是变量。)

线性规划的创始人包括乔治·B·丹齐格，他在 1947 年发表了单纯形法；约翰·冯·诺依曼，他在同年发展了对偶理论；以及列昂尼德·康托罗维奇，一位俄罗斯数学家，他在丹齐格之前就将类似的技术应用于经济学，并在 1975 年获得了诺贝尔经济学奖。线性规划问题最早被列昂尼德·哈奇扬在 1979 年证明可以在多项式时间内解决，但该领域更大的理论和实际突破出现在 1984 年，当时纳伦德拉·卡马卡尔提出了一种新的内点法来解决线性规划问题。

二元线性规划模型

实际情况下通常不存在二元线性规划模型，但它们的学习可以为我们提供一个关于如何处理一般模型的示例。

我们将通过一个示例来解释这个模型。

考虑一家生产两种盐类 X 和 Y 的化工厂。假设酸和碱是该公司生产这两种盐类所需的仅有的两种化学物质。此外，假设该公司所有者根据过去的经验获得了以下数据

生产 1 单位盐 X 需要 6 单位酸和 1 单位碱。生产 1 单位盐 Y 需要 4 单位酸和 2 单位碱。每天最多可以获得 24 单位酸和 6 单位碱。1 单位盐 X 可以为他带来 5 的利润（以任何货币），1 单位盐 Y 可以为他带来 4 的利润。此外，由于市场调查，他知道盐 Y 的日需求量不能超过盐 X 的需求量 1 个单位以上，并且盐 Y 的最大日需求量为 2 个单位。

该公司所有者希望获得最佳的“产品组合”。也就是说，他想了解他每天应该生产多少 X 和 Y，以获得最高的利润。

为了制定这个问题的线性规划模型，我们首先需要确定“决策变量”。这些是代表我们需要实际做出决策的实体的变量。在我们这个问题中，很明显，实体是盐 X 和 Y，因此变量应该代表每种盐类的生产量。因此，让

$x_{1}$ = 每天生产的盐 X 的单位数

$x_{2}$ = 每天生产的盐 Y 的单位数

下一步是决定模型的目标函数是什么。从名称本身就可以清楚地看出，目标函数代表我们的目标，即最大化我们的总利润。由于总利润通常是 X 和 Y 的利润之和，因此它应该等于 $5x_{1}+4x_{2}$ 。假设如果 1 单位 X（或 Y）带来 5（或 4）的利润，那么 $x_{1}$ （或 $x_{2}$ ）单位将带来 $5x_{1}$ （或 $4x_{2}$ ）的利润。因此，如果 z 代表每日总利润，目标是

最大化 z = $5x_{1}+4x_{2}$ .

现在我们考虑限制酸和盐使用的约束条件。我们知道每天使用的总酸量不能超过 24。由于 $6x_{1}$ 和 $4x_{2}$ 分别是制造盐 X 和 Y 所使用的酸量，我们可以得出结论，我们的约束条件是

$6x_{1}+4x_{2}\leq 24$

类似地，对于碱，

$x_{1}+2x_{2}\leq 6$

现在市场要求 Y 的日产量超过 X 的产量 $x_{2}-x_{1}$ 不能超过 1，这意味着

$x_{2}-x_{1}\leq 1$

此外，盐 Y 的最大日需求量为 2 单位，因此

$x_{2}\leq 2$

一个隐含的假设是变量 $x_{1}$ 和 $x_{2}$ 不能取负值（为什么？）。非负性约束， $x_{1},x_{2}\geq 0$ 考虑了这个要求。

完整的模型现在可以表述为

最大化 z = $5x_{1}+4x_{2}$

受制于，

$6x_{1}+4x_{2}\leq 24$ ,

$x_{1}+2x_{2}\leq 6$ ,

$x_{2}-x_{1}\leq 1$ ,

$x_{2}\leq 2$ ,

$x_{1},x_{2}\geq 0$ .

任何满足所有五个约束条件的 $x_{1}$ 和 $x_{2}$ 的值构成一个可行解。否则，该解是不可行的。例如，解 $x_{1}=3$ 和 $x_{2}=1$ 是可行的，因为在代入约束条件后，没有一个不等式被违反。另一方面，解 $x_{1}=4$ 和 $x_{2}=1$ 是不可行的，因为它不满足约束条件 (1)，即 6*4+4*1=28，大于等式右侧 (=24)。

我们的目标是找到最优解，即在可行的情况下，最大化目标函数的解。如何实现这一点将在后面的章节中讨论。

LP 模型的性质

LP 模型具有以下性质

**比例性**: 每个决策变量在目标函数和约束条件中的贡献与其值成正比。例如，第一个约束条件中第一个决策变量的贡献是 $6x_{1}$ 。这与 $x_{1}$ 成正比，比例常数为 6。简单来说，就是遵循了三数法则。

**可加性**: 目标函数和约束条件中所有变量的贡献等于每个变量单独贡献的总和。例如，总利润为 $5x_{1}+4x_{2}$ ，它是单个利润 $5x_{1}$ 和 $4x_{2}$ 的总和。

**确定性**: 所有目标函数和约束条件的系数都是确定的，也就是说关于利润、可用资源和需求的所有数据都是固定的。