Linear programming is a considerable field of optimization for several reasons. Many practical problems in operations research can be expressed as linear programming problems. Certain special cases of linear programming, such as network flow problems and multicommodity flow problems are considered important enough to have generated much research on specialized algorithms for their solution. A number of algorithms for other types of optimization problems work by solving LP problems as sub-problems. Historically, ideas from linear programming have inspired many of the central concepts of optimization theory, such as duality, decomposition, and the importance of convexity and its generalizations. Likewise, linear programming is heavily used in microeconomics and company management, such as planning, production, transportation, technology and other issues. Although the modern management issues are ever-changing, most companies would like to maximize profits or minimize costs with limited resources. Therefore, many issues can boil down to linear programming problems.

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 of 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 minimization problems, problems with constraints on alternative forms, as well as problems involving negative variables can always be rewritten into an 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 by 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:

maximize  S_1 x_1 + S_2 x_2 \, (maximize the revenue — revenue is the “objective function”)
subject to  x_1 + x_2 \le A (limit on total area)
 F_1 x_1 + F_2 x_2 \le F (limit on fertilizer)
 P_1 x_1 + P_2 x_2 \le P (limit on insecticide)
 x_1 \ge 0,\, x_2 \ge 0 (cannot plant a negative area).

Which in matrix form becomes:

maximize \begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}
subject to \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} A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge 0.