Home

Woodcutting

Products

Download

Purchase

Links

Awards

Contacts

A Linear Program (LP) is a program that can be expressed as the following:  

   Minimize    f(x) = cx
   Subject to   Ax  = b  and  x >= 0

where

    x = [x₁, x₂, .. , x_n]   vector of optimization variables

    c = [c₁, c₂, .. , c_n]   vector of objective coefficients (so-called "cost coefficients")

    b = [b₁, b₂, .. , b_n]   >= 0   vector of right-hand sides of constraint.

This type of linear program is called Standard Form of linear program.

The function f(x) is called the objective function of linear program and the equations Ax = b are called the constraints.

The dimension of all these entities must be consistent. The dimension of vectors x, c and column count of the matrix A are the same and equal to n. The dimension of vector b and row count of the matrix A are the same and equal to m. The matrix A has more columns than rows usually. It allows to choose such values of x which minimize the objective function of linear program f(x).

Linear program in the Standard Form can be solve by two most wide known methods: the Simplex Method and Interior Point Methods. The Simplex Method was introduced by Dantzig in the late 1940s and it continues to be widely used method for of all optimization tools.

The basic idea of the Simplex Method is to have a basic feasible solution of linear program that satisfies all constrains and try to improve the solution at each iteration of the method. "Improve" suppose to get the objective function with lower value than it has at the current basic solution. At each iteration a new non-basic variable replaces one of basic variables in the linear program. Once a variable went out from the basic solution it should not entry basic solution again, otherwise there is a risk to get an infinite loop. The Simplex Method looks like moving from one feasible solution to another along the edges of the boundary. Interior Point methods by contrast of the Simplex Method go to descent direction until an optimum reached. The most known methods are Affine Scaling Method and Mehrotra Predictor - Corrector algorithm. 

Unfortunately, the most of the real world linear programs are not in standard form. To be able to solve those linear problems they have to be converted to Standard Form.