什么是线性编程？

Question

我阅读了维基百科的文章,但这似乎超出了我的理解范围.它说这是为了优化,但它与其他任何优化方法的方法有什么不同？

给我介绍线性编程的答案让我可以开始深入研究一些不太适合初学者的材料,这将是最有帮助的.

Answer 1

到目前为止,答案给出了线性规划的代数定义和操作定义.但也有一个几何定义.甲多面体是多边形的n维泛化(在二维上)或多面体(在三维空间).甲凸多面体是多面体这也是一个凸集.根据定义,线性编程是一个优化问题,您希望在凸形多面体上最大化或最小化线性函数.

例如:假设您想购买一些红沙和蓝沙的组合.假设:

1. 你不能买任何一种负数.
2. 该仓库只有300磅的红沙和400磅的蓝沙.
3. 此外,您的吉普车的重量限制为500磅.

如果你在平面上画一幅图片,你可以用这些约束购买多少,它就是一个凸五边形.然后,无论你想要优化什么(比如,沙子中的金总量),你都可以知道最佳(不一定是唯一的最佳)是在多面体的一个顶点处.事实上,有一个更强大的结果:即使在高维度上,任何这样的线性规划问题都可以在多项式时间,约束的数量或多面体的假定边中求解.请注意,并非每个约束都对应于一侧.如果约束是相等的,则可能会减少多面体的维度.或者,如果约束是不等式,如果已经被所有其他约束暗示,则可能不会创建一个边.

线性编程存在许多实际的优化问题.其中一个例子是"饮食问题":给出一系列食物的菜单,最便宜的均衡饮食是什么？这是一个线性规划问题,因为成本是线性的,因为所有的约束(维生素,卡路里,你不能购买负面食物的假设等)是线性的.

但是,出于理论上的原因,线性规划更为重要.它是用于优化或用于任何其他目的的最强大的多项式时间算法之一.因此,作为近似解决其他优化问题的替代品,以及作为精确求解它们的子程序,它是非常重要的.

是的,两个概括是凸编程和整数编程.通过一些限定,凸面编程可以像线性编程一样工作,只要目标(最大化的东西)是线性的.事实证明,凸性而非平坦的边是线性规划具有良好算法的主要原因.

另一方面,整数编程通常很难.例如,假设在示例问题中,您必须购买固定尺寸的袋子而不是散装的沙子; 那就是整数编程.有一个定理它可以是NP难的.它在实践中的难度取决于线性编程的接近程度.有一些着名的整数规划问题的例子,奇迹般地,线性程序的所有顶点都是整数点.然后你可以解决线性程序,解决方案将成为不可或缺的.这种问题的一个例子是婚姻问题,如何将n男人和n女人相互结婚以最大化总幸福感.(或者,n个城市到n个工厂,n个工作人员到n个申请人,n个计算机到n个打印机等)

Answer 2

线性规划是"数学规划"的主题,也称为"数学优化".线性程序与一般数学程序的不同之处在于,对于线性程序(LP),所有约束函数和目标函数关于它们的变量是线性的.

一个良好的开始是在这里,如果你想在原来的工作由丹,或者如果你想获得一本教科书,我推荐这一个.如果你想查找自己的资源,首先要查找Simplex方法 - 这是解决这些程序的一种非常常见的技术,或者是不太常见但绝对多项式的时间Ellipsoid方法.虽然我还没有读完所有内容,但快速查看它也表明这个 PDF可能是一个很好的起点.确保你最终阅读的内容涵盖二元性(也许特别是Farkas的引理),因为它是大多数LP解算器的核心思想.

最自然的扩展是整数程序(类似于LP,但所有变量必须采用整数值 - 即,没有分数组件)或凸面编程(可能是更一般的扩展).一个好的凸优化教材是PDF格式提供在这里.