另一方面，整数编程通常很困难。例如，假设在示例问题中，您必须购买固定尺寸的袋子而不是散装的沙子；这就是整数规划。有一个定理，它可以是 NP 困难的。实践中有多难取决于它与线性规划的接近程度。有一些著名的整数规划问题的例子，其中奇迹般地，线性规划的所有顶点都是整数点。然后你可以求解线性规划并且解恰好是积分的。此类问题的一个例子是婚姻问题，即如何让n个男人和n个女人彼此结婚以使总幸福最大化。 （或者，n 个城市到 n 个工厂，n 个工作到 n 个申请人，n 个计算机到 n 个打印机，等等）
The answers so far have given an algebraic definition of linear programming, and an operational definition. But there is also a geometric definition. A polytope is an n-dimensional generalization of a polygon (in two dimensions) or a polyhedron (in three dimensions). A convex polytope is a polytope which is also a convex set. By definition, linear programming is an optimization problem in which you want to maximize or minimize a linear function on a convex polytope.
For example: Suppose that you want to buy some combination of red sand and blue sand. Suppose also:
You can't buy a negative amount of either kind.
The depot only has 300 pounds of red sand and 400 pounds of blue sand.
Also your jeep has a weight limit of 500 pounds.
If you draw a picture in the plane of how much you can buy with these constraints, it's a convex pentagon. Then, whatever you want to optimize (say, the total amount of gold in the sand), you can know that an optimum (not necessarily the only optimum) is at one of the vertices of the polytope. In fact, there is a much stronger result: Even in high dimensions, any such linear programming problem can be solved in polynomial time, in the number of constraints, or putative sides of the polytope. Note that not every constraint corresponds to a side. If the constraint is an equality, it might reduce the dimension of the polytope. Or if the constraint is an inequality, it might be not create a side if it is already implied by all of the other constraints.
There are a lot of practical optimization problems that are linear programming. One of the first examples was the "diet problem": Given a menu of a bunch of kinds of food, what is the cheapest possible balanced diet? It's a linear programming problem because the cost is linear, and because all of the constraints (vitamins, calories, the assumption that you can't buy a negative amount of food, etc.) are linear.
But, linear programming is even more important for a theoretical reason. It is one of the most powerful polynomial-time algorithms for optimization or for any other purpose. As such, it is very important as a substitute for approximately solving other optimization problems, and as a subroutine for exactly solving them.
Yes, two generalizations are convex programming and integer programming. With some qualificiations, convex programming can work just as well as linear programming, provided that the objective (the thing to maximize) is linear. It turns out that convexity, not flat sides, is the main reason that linear programming has a good algorithm.
Integer programming, on the other hand, is usually hard. For instance, suppose in the example problem you have to buy the sand in fixed-size bags rather than in bulk; that is then integer programming. There is a theorem that it can be NP-hard. How hard it is in practice depends on how close it is to linear programming. There are some celebrated examples of integer programming problems in which, miraculously, all of the vertices of the linear program are integer points. Then you can solve the linear program and the solution will happen to be integral. One example of such a problem is the marriage problem, how to marry n men and n women to each other to maximize total happiness. (Or, n cities to n factories, n jobs to n applicants, n computers to n printers, etc.)
最自然的扩展是整数规划（类似于 LP，但所有变量都必须采用整数值，即没有小数部分）或凸规划（可能是更通用的扩展）。 此处提供了一本优秀的凸优化教科书的 PDF 格式。
Linear programming is a topic of 'mathematical programming', which is also called 'mathematical optimization'. Linear programs differ from general mathematical programs in that for a Linear Program (LP) all constraint functions and the objective function are linear with respect to their variables.
A good place to start would be here if you want the original work by Dantzig, or if you want to get a textbook, I recommend this one. If you want to look up your own resources, start with looking up the Simplex method--it is a very common technique to solve these programs, or the less common but definitely polynomial time Ellipsoid method. Though I haven't read it all, looking it over quickly also suggests this PDF may be a good place to start. Make sure whatever you end up reading covers duality (and perhaps specifically the Farkas' lemma) as it's a central idea in most LP solvers.
The most natural extensions are either Integer programs (similar to LP's, but all variables must take on integer values--that is, no fractional components) or Convex programming (perhaps a more general extension). A good convex optimization text book is available in PDF form here.
As everyone else has said, Linear Programming is a way to solve optimization problems, in which the terms are linear.
It might help to understand what types of problems LP's solve
One example where I've used Linear Programming is building a restaurant schedule. In a restaurant you have skill sets:
Cooks
Servers
Dishwashers
Hosts
Bussers
Manager
etc
And you have employees, each with one or more skill sets. Each employee also has a specific availability. For example, Bob can't work Sunday mornings because he's a pastor at a local church. Employees also have an associated cost. Bob might be $10.50/hr while Suzy is $5.15/hr. Finally Employees might have minimum guaranteed hours. Since Bob has been an employee for 15 years, the boss says he'll always get at least 35 hours.
The restaurant itself has demands. For example it has 3 shifts: Morning, Afternoon, and Night, and each of these shifts has a set of staffing requirements: We need 1 cook, 1 server, 1 manager in the morning, 3 cooks, 2 servers, 2 hosts, 2 managers in the afternoon, and 4 cooks, 4 servers, 3 hosts, 2 managers, 2 bussers in the evening. Each shift will have a duration, and you can figure out the cost of each shift by multiplying the duration by the employee's hourly wage.
Finally we have state and federal laws, and some basic "business" rules: No employee can work more than 8-hours without going into overtime. No employee can be scheduled for less than 2 hours (because it would suck to make a 30 minute commute for a 2 hour shift), employees can't work two overlapping shifts, etc.
Now given all these requirements, give me a schedule that has meets all requirements, and produces the lowest labor cost.
This is an example of a linear programming optimization problem.
A linear program typically consists of:
An objective function, variables, variable bounds, and constraints.
Since we want to minimize cost, our objective function is going to involve shifts that employees work, and the associated costs (shift duration * wage).
The variables in this case, are the shifts that each employee can work.
The bounds on these variables integers between 0 and 1, because either an employee is working the shift (1), or the employee is not working the shift (0). This, by the way, is a special program, called a Binary Integer Program or BIP for short, because all the variables are integers (no fractional values) and all values are either 0 or 1.
The constraints are equality/inequality constraints based on the requirements above.
For example, if Bob and Suzy can both work as cooks in the morning, then Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1, with Bob_Morning_Cook_Shift = {0,1} and Suzy_Morning_Cook_Shift = {0,1} due to the bounds mentioned above. These three pieces of information specify that at most only a single employee can be assigned as the first morning cook.
So once you've defined all the constraints that model your problem, you can begin to solve the problem. If a solution can be found (and depending on the constraints the problem may be infeasible), it will give you the employee assignments that produce the lowest weekly labor cost.
在设置 LP 问题时，确保约束正确限制目标函数非常重要。可以定义导致不可能的解决方案的约束（例如x > 1 和-x > 1）。这已经是过度约束了。也有可能对问题进行欠约束（例如，找到最小 x 使得 x < 1）。
Linear programming is an optimization technique that involves linear constraints and a linear objective function. The constraints are written to bound the problem space, while the objective function is something that you are attempting to minimize (or possibly maximize) that satisfies the constraints. The simplex algorithm is typically used to walk along edges of the constraint intersection to find the minimum (or maximum) value of the objective function satisfying the constraints.
When setting up an LP problem, it's important to make sure that the constraints properly bound the objective function. It's possible to define constraints which result in no possible solution (e.g. x > 1 and -x > 1). This is over constrained. It's also possible to under-constrain a problem (e.g. find min x such that x < 1).
One big difference (or at least, distinguishing feature) of linear programming is that the constraints are modeled as linear equations, i.e. they're all of the form c_1 x_1 + c_2 x_2.... The standard form section of the wikipedia article gives a pretty good overview of this.
Another difference/feature is that linear programming is seeking to maximize (or minimize) ONE function - you can't effectively do multi-objective optimization.
发布评论
评论（5）
到目前为止，答案已经给出了线性规划的代数定义和操作定义。但还有一个几何定义。 多面体是多边形（二维）或多面体（三维）的n维推广。 凸多面体是一个多面体，也是一个凸集。根据定义，线性规划是一个优化问题，您希望在凸多面体上最大化或最小化线性函数。
例如：假设您想购买红沙和蓝沙的某种组合。还假设：
如果你在平面上画出在这些限制下你能买多少钱的图，它就是一个凸五边形。然后，无论您想要优化什么（例如，沙子中的黄金总量），您都可以知道最佳值（不一定是唯一最佳值）位于多面体的顶点之一。事实上，有一个更强有力的结果：即使在高维中，任何此类线性规划问题都可以在多项式时间、约束数量或多面体的假定边数内解决。请注意，并非每个约束都对应一条边。如果约束是等式，则可能会减少多胞形的维数。或者，如果约束是不等式，则如果所有其他约束已经隐含了该边，则可能不会创建边。
有很多实际的优化问题都是线性规划。第一个例子是“饮食问题”：给定一份包含多种食物的菜单，什么是最便宜的均衡饮食？这是一个线性规划问题，因为成本是线性的，并且所有约束（维生素、卡路里、假设你不能购买负量的食物等）都是线性的。
但是，由于理论上的原因，线性规划更为重要。它是用于优化或任何其他目的的最强大的多项式时间算法之一。因此，它作为近似解决其他优化问题的替代品以及作为精确解决这些问题的子程序非常重要。
是的，两个概括是凸规划和整数规划。在某些条件下，凸规划可以与线性规划一样工作，只要目标（要最大化的东西）是线性的。事实证明，线性规划具有良好算法的主要原因是凸性，而不是平坦的边。
另一方面，整数编程通常很困难。例如，假设在示例问题中，您必须购买固定尺寸的袋子而不是散装的沙子；这就是整数规划。有一个定理，它可以是 NP 困难的。实践中有多难取决于它与线性规划的接近程度。有一些著名的整数规划问题的例子，其中奇迹般地，线性规划的所有顶点都是整数点。然后你可以求解线性规划并且解恰好是积分的。此类问题的一个例子是婚姻问题，即如何让n个男人和n个女人彼此结婚以使总幸福最大化。 （或者，n 个城市到 n 个工厂，n 个工作到 n 个申请人，n 个计算机到 n 个打印机，等等）
The answers so far have given an algebraic definition of linear programming, and an operational definition. But there is also a geometric definition. A polytope is an n-dimensional generalization of a polygon (in two dimensions) or a polyhedron (in three dimensions). A convex polytope is a polytope which is also a convex set. By definition, linear programming is an optimization problem in which you want to maximize or minimize a linear function on a convex polytope.
For example: Suppose that you want to buy some combination of red sand and blue sand. Suppose also:
If you draw a picture in the plane of how much you can buy with these constraints, it's a convex pentagon. Then, whatever you want to optimize (say, the total amount of gold in the sand), you can know that an optimum (not necessarily the only optimum) is at one of the vertices of the polytope. In fact, there is a much stronger result: Even in high dimensions, any such linear programming problem can be solved in polynomial time, in the number of constraints, or putative sides of the polytope. Note that not every constraint corresponds to a side. If the constraint is an equality, it might reduce the dimension of the polytope. Or if the constraint is an inequality, it might be not create a side if it is already implied by all of the other constraints.
There are a lot of practical optimization problems that are linear programming. One of the first examples was the "diet problem": Given a menu of a bunch of kinds of food, what is the cheapest possible balanced diet? It's a linear programming problem because the cost is linear, and because all of the constraints (vitamins, calories, the assumption that you can't buy a negative amount of food, etc.) are linear.
But, linear programming is even more important for a theoretical reason. It is one of the most powerful polynomial-time algorithms for optimization or for any other purpose. As such, it is very important as a substitute for approximately solving other optimization problems, and as a subroutine for exactly solving them.
Yes, two generalizations are convex programming and integer programming. With some qualificiations, convex programming can work just as well as linear programming, provided that the objective (the thing to maximize) is linear. It turns out that convexity, not flat sides, is the main reason that linear programming has a good algorithm.
Integer programming, on the other hand, is usually hard. For instance, suppose in the example problem you have to buy the sand in fixed-size bags rather than in bulk; that is then integer programming. There is a theorem that it can be NP-hard. How hard it is in practice depends on how close it is to linear programming. There are some celebrated examples of integer programming problems in which, miraculously, all of the vertices of the linear program are integer points. Then you can solve the linear program and the solution will happen to be integral. One example of such a problem is the marriage problem, how to marry n men and n women to each other to maximize total happiness. (Or, n cities to n factories, n jobs to n applicants, n computers to n printers, etc.)
线性规划是“数学规划”的一个主题，也称为“数学优化”。线性程序与一般数学程序的不同之处在于，对于线性程序 (LP)，所有约束函数和目标函数相对于其变量都是线性的。
如果您想要 Dantzig 的原创作品，此处是一个不错的起点，或者如果您想获得一本教科书，我推荐这本。如果您想查找自己的资源，请首先查找 Simplex 方法 - 它是解决这些问题的一种非常常见的技术，或者不太常见但绝对是多项式时间椭球体方法。虽然我还没有全部读完，但快速浏览一下也表明这个< /a> PDF 可能是一个不错的起点。确保你最终阅读的内容涵盖了二元性（也许特别是Farkas 引理），因为它是大多数 LP 求解器的中心思想。
最自然的扩展是整数规划（类似于 LP，但所有变量都必须采用整数值，即没有小数部分）或凸规划（可能是更通用的扩展）。 此处提供了一本优秀的凸优化教科书的 PDF 格式。
Linear programming is a topic of 'mathematical programming', which is also called 'mathematical optimization'. Linear programs differ from general mathematical programs in that for a Linear Program (LP) all constraint functions and the objective function are linear with respect to their variables.
A good place to start would be here if you want the original work by Dantzig, or if you want to get a textbook, I recommend this one. If you want to look up your own resources, start with looking up the Simplex method--it is a very common technique to solve these programs, or the less common but definitely polynomial time Ellipsoid method. Though I haven't read it all, looking it over quickly also suggests this PDF may be a good place to start. Make sure whatever you end up reading covers duality (and perhaps specifically the Farkas' lemma) as it's a central idea in most LP solvers.
The most natural extensions are either Integer programs (similar to LP's, but all variables must take on integer values--that is, no fractional components) or Convex programming (perhaps a more general extension). A good convex optimization text book is available in PDF form here.
正如其他人所说，线性规划是解决优化问题的一种方法，其中项是线性的。
它可能有助于理解 LP 解决什么类型的问题。
我使用线性规划的一个例子是制定餐厅时间表。在餐厅里，您拥有以下技能：
等等
你有员工，每个人都拥有一套或多套技能。每个员工也有特定的空闲时间。例如，鲍勃不能在周日早上工作，因为他是当地教堂的牧师。员工也有相关成本。 Bob 的工资可能是 10.50 美元/小时，而 Suzy 的工资可能是 5.15 美元/小时。最后，员工可能有最低保证工作时间。由于鲍勃已经成为员工 15 年，老板说他总是会得到至少 35 个小时的工作时间。
餐厅本身有要求。例如，它有 3 个班次：早上、下午和晚上，每个班次都有一组人员配置要求：我们需要 1 名厨师、1 名服务员、1 名上午经理、3 名厨师、2 名服务员、2 名主持人、2 名服务员。下午是经理，晚上是 4 名厨师、4 名服务员、3 名主持人、2 名经理、2 名服务员。每个班次都会有一个持续时间，您可以通过将持续时间乘以员工的小时工资来计算出每个班次的成本。
最后，我们有州和联邦法律，以及一些基本的“商业”规则：任何员工在不加班的情况下都不能工作超过 8 小时。任何员工的工作时间都不能少于 2 小时（因为 2 小时的轮班需要 30 分钟的通勤时间，这太糟糕了），员工不能工作两个重叠的轮班，等等。
现在考虑到所有这些要求，给我一个时间表满足所有要求，并产生最低的劳动力成本。
这是线性规划优化问题的示例。
线性程序通常由以下部分组成：
目标函数、变量、变量界限和约束。
由于我们希望最大限度地降低成本，因此我们的目标函数将涉及员工的轮班以及相关成本（轮班时间 * 工资）。
本例中的变量是每个员工可以工作的班次。
这些变量的界限为 0 到 1 之间的整数，因为员工要么正在轮班工作 (1)，要么员工没有轮班工作 (0)。顺便说一句，这是一个特殊的程序，称为二进制整数程序或简称 BIP，因为所有变量都是整数（没有小数值）并且所有值都是 0 或 1。
约束是基于等式/不等式约束上述要求。
例如，如果 Bob 和 Suzy 早上都可以当厨师，则
Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1，其中Bob_Morning_Cook_Shift = {0,1}和Suzy_Morning_Cook_Shift = {0,1}由于上述边界。这三条信息指定最多只能指派一名员工作为第一个早晨厨师。因此，一旦定义了对问题进行建模的所有约束，您就可以开始解决问题。如果可以找到解决方案（并且根据限制，问题可能不可行），它将为您提供每周劳动力成本最低的员工分配。
As everyone else has said, Linear Programming is a way to solve optimization problems, in which the terms are linear.
It might help to understand what types of problems LP's solve
One example where I've used Linear Programming is building a restaurant schedule. In a restaurant you have skill sets:
etc
And you have employees, each with one or more skill sets. Each employee also has a specific availability. For example, Bob can't work Sunday mornings because he's a pastor at a local church. Employees also have an associated cost. Bob might be $10.50/hr while Suzy is $5.15/hr. Finally Employees might have minimum guaranteed hours. Since Bob has been an employee for 15 years, the boss says he'll always get at least 35 hours.
The restaurant itself has demands. For example it has 3 shifts: Morning, Afternoon, and Night, and each of these shifts has a set of staffing requirements: We need 1 cook, 1 server, 1 manager in the morning, 3 cooks, 2 servers, 2 hosts, 2 managers in the afternoon, and 4 cooks, 4 servers, 3 hosts, 2 managers, 2 bussers in the evening. Each shift will have a duration, and you can figure out the cost of each shift by multiplying the duration by the employee's hourly wage.
Finally we have state and federal laws, and some basic "business" rules: No employee can work more than 8-hours without going into overtime. No employee can be scheduled for less than 2 hours (because it would suck to make a 30 minute commute for a 2 hour shift), employees can't work two overlapping shifts, etc.
Now given all these requirements, give me a schedule that has meets all requirements, and produces the lowest labor cost.
This is an example of a linear programming optimization problem.
A linear program typically consists of:
An objective function, variables, variable bounds, and constraints.
Since we want to minimize cost, our objective function is going to involve shifts that employees work, and the associated costs (shift duration * wage).
The variables in this case, are the shifts that each employee can work.
The bounds on these variables integers between 0 and 1, because either an employee is working the shift (1), or the employee is not working the shift (0). This, by the way, is a special program, called a Binary Integer Program or BIP for short, because all the variables are integers (no fractional values) and all values are either 0 or 1.
The constraints are equality/inequality constraints based on the requirements above.
For example, if Bob and Suzy can both work as cooks in the morning, then
Bob_Morning_Cook1_Shift + Suzy_Morning_Cook1_Shift = 1, withBob_Morning_Cook_Shift = {0,1}andSuzy_Morning_Cook_Shift = {0,1}due to the bounds mentioned above. These three pieces of information specify that at most only a single employee can be assigned as the first morning cook.So once you've defined all the constraints that model your problem, you can begin to solve the problem. If a solution can be found (and depending on the constraints the problem may be infeasible), it will give you the employee assignments that produce the lowest weekly labor cost.
线性规划是一种涉及线性约束和线性目标函数的优化技术。编写约束是为了限制问题空间，而目标函数是您试图最小化（或可能最大化）以满足约束的函数。 单纯形算法通常用于沿着约束交集的边缘行走以找到最小值（或满足约束条件的目标函数的最大值）。
在设置 LP 问题时，确保约束正确限制目标函数非常重要。可以定义导致不可能的解决方案的约束（例如x > 1 和-x > 1）。这已经是过度约束了。也有可能对问题进行欠约束（例如，找到最小 x 使得 x < 1）。
Linear programming is an optimization technique that involves linear constraints and a linear objective function. The constraints are written to bound the problem space, while the objective function is something that you are attempting to minimize (or possibly maximize) that satisfies the constraints. The simplex algorithm is typically used to walk along edges of the constraint intersection to find the minimum (or maximum) value of the objective function satisfying the constraints.
When setting up an LP problem, it's important to make sure that the constraints properly bound the objective function. It's possible to define constraints which result in no possible solution (e.g. x > 1 and -x > 1). This is over constrained. It's also possible to under-constrain a problem (e.g. find min x such that x < 1).
线性编程的一个很大的区别（或者至少是显着特征）是约束被建模为线性方程，即它们都是
c_1的形式x_1 + c_2 x_2...。维基百科文章的标准形式部分对此提供了很好的概述。另一个区别/特征是线性规划寻求最大化（或最小化）一个函数 - 您无法有效地进行多目标优化。
One big difference (or at least, distinguishing feature) of linear programming is that the constraints are modeled as linear equations, i.e. they're all of the form
c_1 x_1 + c_2 x_2.... The standard form section of the wikipedia article gives a pretty good overview of this.Another difference/feature is that linear programming is seeking to maximize (or minimize) ONE function - you can't effectively do multi-objective optimization.