什么是线性规划[[关闭]

迄今为止的答案给出了线性规划的代数定义和运算定义。但也有一个几何定义。A 凸多面体 是一个多面体,也是一个凸集。根据定义,线性规划是一个最优化问题,在这个问题中,你想最大化或最小化凸多面体上的线性函数。

例如:假设你想买一些红砂和蓝砂的组合。同时假设:

1. 两种都买不到负数。
2. 仓库只有300磅的红砂和400磅的蓝砂。
3. 你的吉普车也有500磅的重量限制。

有很多实际的优化问题都是线性规划问题。最早的一个例子是“饮食问题”:给定一系列食物的菜单,最便宜的均衡饮食是什么?这是一个线性规划问题,因为成本是线性的,因为所有的约束条件(维生素、卡路里、不能买负量食物的假设等)都是线性的。

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

另一方面,整数规划通常很难。例如,假设在示例问题中,您必须购买固定尺寸的袋装砂,而不是散装砂;那就是整数规划。有一个定理证明它是NP难的。它在实践中的难度取决于它与线性规划的接近程度。有一些著名的整数规划问题的例子,其中,奇迹般地,所有的顶点的线性规划是整数点。然后你就可以解线性规划,而解恰好是积分。婚姻问题就是这样一个例子,如何让n个男人和n个女人彼此结婚,以最大限度地获得幸福感(或者,n个城市对应n个工厂,n个职位对应n个申请人,n台计算机对应n台打印机,等等)

线性规划是“数学规划”的一个主题,也称为“数学优化”。线性规划不同于一般的数学规划,因为对于线性规划(LP),所有约束函数和目标函数相对于它们的变量都是线性的。

一个好的开始是 here 如果你想要丹泽的原著,或者想要一本教科书,我推荐你 this 一个。如果您想查找自己的资源,请从查找 Simplex method Ellipsoid method . 虽然我还没读完,但快速翻阅一下也会发现 this PDF可能是一个很好的开始。确保你最终读到的内容涵盖了二元性(也许特别是 Farkas' lemma

最自然的扩展要么是整数规划(类似于LP,但所有变量都必须采用整数值——也就是说,没有分数分量)要么是凸规划(也许是更一般的扩展)。一本很好的凸优化教科书是PDF格式的 here .

我使用线性规划的一个例子是建立餐厅时间表。在餐馆里,你有各种技能:

• 厨师
• 服务器
• 主机
• 比塞尔
• 经理 等

你有员工,每个人都有一套或多套技能。每个员工也有特定的可用性。例如,鲍勃星期天早上不能工作,因为他是当地教堂的牧师。员工也有相关成本。鲍勃可能是10.50美元/小时,而苏西是5.15美元/小时。最后,员工可能有最低保障时间。鲍勃已经当了15年的雇员,老板说他至少能工作35个小时。

餐厅本身也有要求。例如,它有三个班次:早上、下午和晚上,每个班次都有一套人员配置要求:早上需要1个厨师、1个服务员、1个经理,下午需要3个厨师、2个服务员、2个主持人、2个经理,晚上需要4个厨师、4个服务员、3个主持人、2个经理、2个服务员。每个班次都有一个持续时间,您可以通过将持续时间乘以员工的小时工资来计算每个班次的成本。

最后,我们有州和联邦法律,还有一些基本的“商业”规则:没有加班的员工不能工作超过8小时。任何员工的工作时间都不能少于2小时(因为2小时轮班30分钟的通勤时间很糟糕),员工不能工作两个重叠的轮班,等等。

现在给我所有这些要求,给我一个时间表,已满足所有要求,并产生最低的劳动力成本。

线性规划通常包括:

目标函数、变量、变量边界和约束。

因为我们想要最小化成本,我们的目标函数将涉及员工工作的班次,以及相关成本(班次时间*工资)。

本例中的变量是每个员工可以工作的班次。

这些变量的界限是0到1之间的整数,因为要么员工正在轮班(1),要么员工没有轮班(0)。顺便说一下,这是一个特殊的程序,简称为二进制整数程序或BIP,因为所有变量都是整数(没有分数值),所有值都是0或1。

这些约束是基于上述要求的等式/不等式约束。

例如,如果鲍勃和苏西早上都能当厨师,那么 Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1 ,与 Bob_Morning_Cook_Shift = {0,1} 和 Suzy_Morning_Cook_Shift = {0,1}

线性规划是一种涉及线性约束和线性目标函数的优化技术。编写约束是为了约束问题空间,而目标函数是您试图最小化(或可能最大化)满足约束的对象。这个 simplex algorithm 通常用于沿约束相交的边行走,以找到满足约束的目标函数的最小值(或最大值)。

当建立一个线性规划问题时,重要的是要确保约束正确地约束了目标函数。可以定义导致不可能的解决方案的约束(例如x>1和-x>1). 这是过度约束。也可以对问题进行约束(例如,找到min x,使x<1).

一个很大的区别(或者至少,区别特征) 线性的 编程就是将约束建模为 线性的 方程,即它们都是 c_1 x_1 + c_2 x_2...

另一个区别/特点是,线性规划是寻求最大化(或最小化)一个函数-你不能有效地做多目标优化。