Linear programming

In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear.

Standard form

Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• A linear function to be maximized

: e.g. maximize c_1 x_1 + c_2 x_2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Problem constraints on the following form

: e.g. a_{11} x_1 + a_{12} x_2 le b_1

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: a_{21} x_1 + a_{22} x_2 le b_2

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: a_{31} x_1 + a_{32} x_2 le b_3

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• Non-negative variables

: e.g. x_1 ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:: x_2 ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The problem is usually expressed in matrix form, and then becomes:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: maximize mathbf{c}^T mathbf{x}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: subject to mathbf{A}mathbf{x} le mathbf{b}, , mathbf{x} ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Other forms, such as minimalization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into a equivalent problem in standard form.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Example

Suppose that a farmer has a piece of farm land, say A square kilometres large, to be planted with either wheat or barley or some combination of the two. The farmer has a limited permissible amount F of fertilizer and P of insecticide which can be used, each of which is required in different amounts per unit area for wheat (F1, P1) and barley (F2, P2). Let S1 be the selling price of wheat, and S2 the price of barley. If we denote the area planted with wheat and barley with x1 and x2 respectively, then the optimal number of square kilometres to plant with wheat vs barley can be expressed as a linear programming problem:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Which in matrix form becomes:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: maximize egin{bmatrix} S_1 & S_2 end{bmatrix} egin{bmatrix} x_1 \ x_2 end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: subject to egin{bmatrix} 1 & 1 \ F_1 & F_2 \ P_1 & P_2 end{bmatrix} egin{bmatrix} x_1 \ x_2 end{bmatrix} le egin{bmatrix} A \ F \ P end{bmatrix}, , egin{bmatrix} x_1 \ x_2 end{bmatrix} ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~