线性规划

线性规划在满足线性和不等式约束的条件下优化线性目标，是应用最广泛的优化问题类别。

Definition

线性规划旨在最小化或最大化决策变量的线性函数，同时受线性约束；其可行域是一个凸多面体，如果存在最优解，则在顶点处取得。

Scope

本主题涵盖线性规划的标准形式、可行多面体的几何及其顶点、单纯形法、线性规划对偶和互补松弛、敏感性分析以及用于大规模问题的内点法。

Core questions

• 如何将实际资源问题表述为线性规划？
• 为什么最优解会出现在可行多面体的顶点处？
• 对偶线性规划能告诉我们关于原问题什么信息？
• 哪些算法能高效解决大型线性规划问题？

Key theories

线性规划基本定理

如果一个线性规划存在最优解，那么最优解将在可行多面体的一个顶点处取得，从而将搜索范围缩小到有限数量的候选点。

对偶性与互补松弛

每个线性规划都有一个对偶问题，其最优值等于原问题，互补松弛将活跃约束与非零对偶变量联系起来，提供了最优性证书和经济解释。

单纯形法和内点法

单纯形法在顶点之间移动以改进目标函数，而内点法则遍历内部，并能以可证明的多项式时间解决线性规划问题。

Clinical relevance

线性规划是运筹学的基石，用于生产计划、运输和物流、调度、饮食和混合问题以及网络流，并作为整数和非线性优化的子程序。

History

康托罗维奇于1939年引入线性优化用于生产计划，丹齐格于1947年提出了通用问题和单纯形法。冯·诺依曼认识到其与博弈论的对偶性，哈奇扬的椭球法和卡尔马卡的内点法后来确立了多项式时间可解性。

Key figures

• George Dantzig
• Leonid Kantorovich
• John von Neumann
• Narendra Karmarkar

Seminal works

• dantzig1963
• luenberger2008

Frequently asked questions

为什么最优解位于顶点？

线性目标函数在固定方向上增长最快，因此在凸多面体上，其最优值会被推到边界，并最终推到角点。除非目标函数在某条边或某个面上是常数，否则最优解将在顶点处取得。

单纯形法总是很快吗？

在实践中，单纯形法非常高效，但最坏情况的例子可能使其需要指数级的步骤。内点法提供了多项式时间保证，现代求解器会根据问题选择使用这两种方法。