我阅读了维基百科的文章,但似乎超出了我的理解范围。它说它是用于优化的,但它与任何其他优化方法有什么不同呢?
一个介绍线性规划的答案可以帮助我开始深入研究一些不太适合初学者的材料。
我阅读了维基百科的文章,但似乎超出了我的理解范围。它说它是用于优化的,但它与任何其他优化方法有什么不同呢?
一个介绍线性规划的答案可以帮助我开始深入研究一些不太适合初学者的材料。
然而,线性规划由于一项理论原因而更为重要。它是最强大的多项式时间优化算法之一,可用作近似解决其他优化问题的替代方法,也可作为确切解决它们的子程序。
是的,另外两个常见泛化方法是凸规划和整数规划。在一定条件下,凸规划可以像线性规划一样有效,只要目标(要最大化的东西)是线性的。事实证明,凸性是线性规划具有良好算法的主要原因,而不是其相邻边是平的。
另一方面,整数规划通常很难。例如,在示例问题中,如果您必须购买固定大小的袋装沙子而不是散装,则属于整数规划。有一个定理表明它可能是NP-hard。在实践中它有多么难取决于它与线性规划的接近程度。有一些著名的整数规划问题,其中所有线性规划的顶点都是整数点,这时您可以解决线性规划问题并且解将恰好是整数值。例如,婚姻问题,如何将n个男人和n个女人彼此结婚以最大化总幸福感。(或者是将n个城市分配给n个工厂,将n个工作岗位分配给n个求职者,将n台计算机分配给n台打印机等)
Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1
,其中 Bob_Morning_Cook_Shift = {0,1}
和 Suzy_Morning_Cook_Shift = {0,1}
由上面提到的范围限制。这三个信息指定最多只能分配一个员工作为第一个早班厨师。线性规划的一个重要区别(或至少是其特征)是将约束建模为线性方程,即它们都采用c_1 x_1 + c_2 x_2...
的形式。维基百科文章的标准形式部分对此进行了很好的概述。
另一个不同之处/特点是,线性规划旨在最大化(或最小化)一个函数 - 您无法有效地进行多目标优化。