Linear Optimization Program
Jump to navigation
Jump to search
A linear optimization program is a mathematical optimization program with a linear cost function, [math]\displaystyle{ \mathbf{c}^\top \mathbf{x} }[/math], subject to a linear constraints, [math]\displaystyle{ A \mathbf{x} \leq \mathbf{b} }[/math], where [math]\displaystyle{ \mathbf{x} }[/math] represents vector variables whose values (to be determined) are [math]\displaystyle{ x_i\ge0 }[/math]; [math]\displaystyle{ c }[/math] and [math]\displaystyle{ b }[/math] are vectors; and [math]\displaystyle{ A }[/math] is a matrix of coefficients.
- AKA: LP, Linear Programming Problem, Matrix Equation.
- Context:
- It can be the input to a Linear Programming Task and be solved by a Linear Programming Algorithm.
- It can range from being a Min-Max Linear Program to being a Max-Min Linear Program.
- Example(s):
- [math]\displaystyle{ \mathbf{c}=[3,5] }[/math], [math]\displaystyle{ A=\begin{bmatrix} 2.3 & 5\cr 0.5 & 7 \cr 1 & 9 \end{bmatrix} }[/math], [math]\displaystyle{ \mathbf{b}=[2,5,3] }[/math], and [math]\displaystyle{ [x_1,x_2] \ge [0,0] }[/math]
- a LINPACK Benchmark Task.
- …
- Counter-Example(s):
- See: Linear Program Dual Form, Eigenvalue, Numerical Linear Algebra.
References
2010
- http://en.wikipedia.org/wiki/Linear_programming#Example
- Suppose that a farmer has a piece of farm land, say L km^{2}, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F_{1} kilograms of fertilizer, and P_{1} kilograms of insecticide, while every square kilometer of barley requires F_{2} kilograms of fertilizer, and P_{2} kilograms of insecticide. Let S_{1} be the selling price of wheat per square kilometer, and S_{2} be the price of barley. If we denote the area of land planted with wheat and barley by x_{1} and x_{2} respectively, then profit can be maximized by choosing optimal values for x_{1} and x_{2}. This problem can be expressed with the following linear programming problem in the standard form:
Maximize: S_{1}x_{1} + S_{2}x_{2} | (maximize the revenue — revenue is the "objective function") | |
Subject to: | 0 ≤ x_{1} + x_{2} ≤ L | (limit on total area) |
0 ≤ F_{1}x_{1} + F_{2}x_{2} ≤ F | (limit on fertilizer) | |
0 ≤ P_{1}x_{1} + P_{2}x_{2} ≤ P | (limit on insecticide) | |
x_{1} ≥ 0, x_{2} ≥ 0 | (cannot plant a negative area). |
- http://en.wikipedia.org/wiki/Linear_programming#Example
- Which in matrix form becomes:
- maximize [math]\displaystyle{ \begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} }[/math]
- subject to [math]\displaystyle{ \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \le \begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. }[/math]
2009
- http://en.wikipedia.org/wiki/Linear_Programming
- Linear programs are problems that can be expressed in canonical form: maximize [math]\displaystyle{ \mathbf{c}^\top \mathbf{x} }[/math] subject to [math]\displaystyle{ A \mathbf{x} \leq \mathbf{b} }[/math] and [math]\displaystyle{ \mathbf{x} \ge \mathbf{0} }[/math] where x represents the vector of variables (to be determined), c and 'b are vectors of (known) coefficients and [math]\displaystyle{ A }[/math] is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function ([math]\displaystyle{ \mathbf{c}^\top \mathbf{x} }[/math] in this case). The equations A \mathbf{x} \leq \mathbf{b}</math> are the constraints which specify a convex polytope over which the objective function is to be optimized. (In this context, two vectors are comparable when every entry in one is less-than or equal-to the corresponding entry in the other. Otherwise, they are incomparable.)
2007
- http://wiki.mcs.anl.gov/NEOS/index.php/Linear_Programming_FAQ#What_is_Linear_Programming.3F
- A Linear Program (LP) is a problem that can be expressed as follows (the so-called Standard Form): minimize cx subject to Ax = b AND [math]\displaystyle{ x }[/math] >= 0, where [math]\displaystyle{ x }[/math] is the vector of variables to be solved for, A is a matrix of known coefficients, and c and b are vectors of known coefficients. The expression "cx" is called the objective function, and the equations "Ax=b" are called the constraints. All these entities must have consistent dimensions, of course, and you can add "transpose" symbols to taste. The matrix A is generally not square, hence you don't solve an LP by just inverting A. Usually A has more columns than rows, and Ax=b is therefore quite likely to be under-determined, leaving great latitude in the choice of x with which to minimize cx.