Linear programming

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

Augmented form (slack form)

Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace non-equalities with equalities in the constraints. The problem can then be written on the following form:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Maximize Z in:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 & -mathbf{c}^T & 0 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 & mathbf{A} & mathbf{I}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Z \ mathbf{x} \ mathbf{x}_s

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix} =

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 \ mathbf{b}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: mathbf{x}, , mathbf{x}_s ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where xs are the newly introduced slack variables, and Z is the variable to be maximized.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Example

The example above becomes as follows when converted into augmented form:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where x_3,x_4,x_5 are (non-negative) slack variables.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Which in matrix form becomes:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: Maximize Z in:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

1 & -S_1 & -S_2 & 0 & 0 & 0 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 & 1 & 1 & 1 & 0 & 0 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 & F_1 & F_2 & 0 & 1 & 0 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 & P_1 & P_2 & 0 & 0 & 1 \

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Z \ x_1 \ x_2 \ x_3 \ x_4 \ x_5

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix} =

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

0 \ A \ F \ P

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix}, ,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

egin{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

x_1 \ x_2 \ x_3 \ x_4 \ x_5

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

end{bmatrix} ge 0

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

~ ~ ~ ~ ~ ~ ~ ~ ~ ~