4.5　了解线性规划

线性规划背后的基本算法是由加州大学伯克利分校的乔治·丹特兹格（George Dantzig）在20世纪40年代初开发的。丹特兹格在为美国空军工作时，用这个概念来试验部队的后勤供应和能力规划。在第二次世界大战结束时，丹特兹格开始为五角大楼工作，并将他的算法发展为一种技术，他将其命名为线性规划。它被用于军事作战计划。

如今，线性规划用于求解一些重要的实际问题，这些问题与基于某些约束的变量最小化或最大化有关。这些问题领域的一些示例如下：

• 根据资源情况，尽量缩短在汽修厂修车的时间
• 在分布式计算环境中分配可用的分布式资源，以尽量减少响应时间
• 在公司内部资源优化配置的基础上，实现公司利润的最大化

线性规划问题的形式化描述

使用线性规划的条件如下：

• 能够用一组方程来表述问题。
• 方程中使用的变量必须是线性的。

定义目标函数

请注意，前面给出的三个例子，其目标都是将某个变量最小化或最大化。该目标在数学上被表示为其他变量的线性函数，称为目标函数。线性规划问题的目的就是在给定的约束条件下最小化或最大化目标函数。

给定约束条件

当试图最小化或最大化某些事物时，在现实世界中存在某些约束条件需要加以考虑。例如，当试图最小化修理一辆汽车所需的时间时，我们还需要考虑可用的机械修理工数量有限。通过线性方程来给定每个约束条件是制定线性规划问题的重要部分。