linear programming II

Linear programming, sometimes known as linear optimization, is the problem of maximizing or minimizing a linear function over a convex polyhedron specified by linear and non-negativity constraints. Simplistically, linear programming is the optimization of an outcome based on some set of constraints using a linear mathematical model.
Linear programming is implemented in Mathematica as LinearProgramming[c, m, b], which finds a vector which minimizes the quantity Cx subject to the constraints mx >=b and xi >=0 for x = (x1,...,xn) .
Linear programming theory falls within convex optimization theory and is also considered to be an important part of operations research. Linear programming is extensively used in business and economics, but may also be used to solve certain engineering problems.
Examples from economics include Leontief's input-output model, the determination of shadow prices, etc., an example of a business application would be maximizing profit in a factory that manufactures a number of different products from the same raw material using the same resources, and example engineering applications include Chebyshev approximation and the design of structures (e.g., limit analysis of a planar truss).
Linear programming can be solved using the simplex method (Wood and Dantzig 1949, Dantzig 1949) which runs along polytope edges of the visualization solid to find the best answer. Khachian (1979) found a O(x^5) polynomial time algorithm. A much more efficient polynomial time algorithm was found by Karmarkar (1984). This method goes through the middle of the solid (making it a so-called interior point method), and then transforms and warps. Arguably, interior point methods were known as early as the 1960s in the form of the barrier function methods, but the media hype accompanying Karmarkar's announcement led to these methods receiving a great deal of attention.
Linear programming in which variables may take on integer values only is known as integer programming.

Standard form

• A linear function to be maximized
  e.g. maximize C1X1+C2X2


• Problem constrints of the following form
  e.g.
  a11X1 + a12X2 <= b1
  a21X1 + a22X2 <= b2
  a31X1 + a32X2 <= b3


• Non-negative variable
  e.g.
  X1 >= 0
  X2 >= 0
  

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

maximize C^Tx
subject to Ax <= b , x >= 0

Augmented form (slack form)

This form introduces non-negative slack variables to replace inequalities with equalities in the constraints.

Maximize Z in:
X,Xs >= 0
where Xs are the newly introduced slack variables, and Z is the variable to be maximized.

Duality

maimize C^T X
subject to Ax <= b , x >=0

The corresponsding dual problem is:

minimize b^T y
subject to A^T y >= c , y >= 0

where y is used instead of x as variable vector.