Linear Optimization Program

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):
  • a Quadratic Program.
  • a System of Polynomial Equations.
  • an Integer Program.
  • a System of Linear Equations.
• 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², 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₁ kilograms of fertilizer, and P₁ kilograms of insecticide, while every square kilometer of barley requires F₂ kilograms of fertilizer, and P₂ kilograms of insecticide. Let S₁ be the selling price of wheat per square kilometer, and S₂ be the price of barley. If we denote the area of land planted with wheat and barley by x₁ and x₂ respectively, then profit can be maximized by choosing optimal values for x₁ and x₂. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: S1x1 + S2x2		(maximize the revenue — revenue is the "objective function")
Subject to:	0 ≤ x1 + x2 ≤ L	(limit on total area)
	0 ≤ F1x1 + F2x2 ≤ F	(limit on fertilizer)
	0 ≤ P1x1 + P2x2 ≤ P	(limit on insecticide)
	x1 ≥ 0, x2 ≥ 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.

---