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.



    • Suppose that a farmer has a piece of farm land, say L km2, 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 F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. 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 + x2L (limit on total area)
0 ≤ F1x1 + F2x2F (limit on fertilizer)
0 ≤ P1x1 + P2x2P (limit on insecticide)
x1 ≥ 0, x2 ≥ 0 (cannot plant a negative area).
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]


    • 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.)


    • 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.