Linear Programming

Note on Introduction to Linear Programming

Linear programming (LP, also called linear optimization) is a method to archive the best outcome (maximum profit or lowest cost) in a mathematical model.

Framework: calculate the maximum (or minimum) value of an affine function (the linear form plus a constant) with finite number of linear constraints.

Linear programming can be expressed in matrix form: a linear form $c_1x_1+c_2x_2+…+c_nx_n$, with $n$ variables $x_1$, $x_2$, … , $x_n$, can be noted as the matrix product, among which $c=[c_1,c_2,…,c_n]$ is the coefficients row, $x=[x_1, x_2,…,x_n]^T$ is the variables column. The constants column can be noted as $b=[b_1,b_2,..,b_n]^T$.

Any questions or suggestions, please leave a comment.

If there is something wrong with the formulae, please refresh this page or wait a moment.

Standard Form

If the variables of a minimum problem are all non-negative, and the other constraints are all linear functions, then we call this linear programming as standard form.

Canonical Form

if the variables of a minimum problem are all non-negative, and the other constraints are in the form of $\leq$.

e.g., $2x+3y-z \rightarrow min,\ subject \ to \ z\leq 2, \ x,y,z\geq 0. $

All the linear programming problems can be formalized into these two forms to utilize uniform algorithms to solve these problems.

Some Techniques

Here are some useful tips which can be used to convert linear programming into the two aforementioned forms.

  1. A constraint $f\leq c$ can be extended into two constraints $f+s=c$ and $s\geq 0$, using affiliation (relaxation) variables. $f\geq c$ can be written into $f-s=c,\ s\geq0$. The newly-introduced variable $s$ is also called surplus (or excess) variable.

  2. $f=c$ is equivalent to $f\leq c,\ -f \leq -c$.

    e.g., canonical form: $cx+d\rightarrow min, Ax\leq b, x\geq 0$ can be converted to standard form $cx+d\rightarrow min, Ax+u=b,x\geq 0,u\geq 0$.

  3. Any variable in linear programming can be expressed as the difference of two auxiliary variables $x’$ and $x’’$, i.e. $x’-x’’$, $x’\geq 0$ and $x’’\geq0$.

    This technique can be used to remove the variables which may be negative.

    e.g.:

    given $x\leq a$, replace it with $x=a-x’’, x’’ \geq 0$.

    given $x\geq a$, replace it with $x=x’+a, x’ \geq 0$.

Even after using these techniques several times, the feasible regions of the origin programming $P$ and the new programming $P’$ are still in one to one relationship under the following affine transformation:

called the affine equivalence.

e.g.:

  1. Please transform $2x+3y-z\rightarrow min,\ x,y,z \geq 0, \ x+y+z=1$ into canonical form.

    • $2x+3y-z\rightarrow min,\ x,y,z\geq0, x+y+z \leq 1, -(x+y+z)\leq-1$;

      or

    • let $z=1-x-y$, then $x+2y-1\rightarrow min, \ \ x,y\geq0, \ \ x+y\leq1$.

  1. Please transform $f=2x+3y-z\rightarrow max, \ x,y\geq0,\ x+y+z\geq1$ into canonical form.

    let $z=z’-z’’,\ z’,z’’\geq0$, then we have $-f=-2x-3y+z\rightarrow min$, $x,y\geq0$, $-x-y-z’+z’’\leq-1$.

Pivot Step

Given the following linear equations:

It can be expressed in the form of row tableaux:

or

Similarly, the standard form of linear programming can be expressed as follow:

The canonical form can be expressed as follow:

Here we use the thoughts of Gauss-Jordan Elimination. To solve the linear equations, firstly we solve one equation (pivot function) for one variable (pivot variable), and then use back substitution to eliminate this variable in other equations. Now we obtain a new equation set with one less variable and one less equation. Repeat this step until all the variables and equations are all eliminated.

One step in Gauss Elimination is as follow:

  1. For an unknown $x_1$ in equation $2x_1+3x_2=4$:

    $x_1=4/2-(3/2)x_2​$.

  2. Plug $x_1$’s expression into the second equation $5x_1+6x_2=7$, then we have:

    $5(4/2-(3/2)x_2)+6x_2=7$ or $5 \cdot4/2+(6-5 \cdot 3/2)x_2=7$.

    The new table is

For any linear equation set:

and the corresponding tableau:

Assume $\alpha^$ is non-zero, which is called *pivot entry. We solve the first equation for $x$ and substitute it into the second equation, then obtain the following tableau:

The transformation from the first tableau to the second tableau is called pivot step.

We can conduct the similar pivot operation on tableaus of any size. Here are some examples:

Pivot Rules:

  1. Exchange the pivot row’s and column’s character ($x \leftrightarrow u$, these’re the only changes of the upper margin and right margin of the pivot tableau).
  2. Substitute pivot entry $\alpha \neq 0​$ with its reciprocal $\alpha’ =1/\alpha​$ ($\alpha \rightarrow 1/\alpha​$).
  3. Every entry $\beta$ in pivot row while not in pivot column should be divided by $-\alpha$ (i.e. every such $\beta$ should be substituted with $\beta’ =-\alpha \beta$).
  4. Every entry $\delta$ which is not in pivot row and pivot column should be substituted with $\delta-\beta\gamma/\alpha=\delta+\beta’ \gamma$.
  5. Every entry $\gamma$ in pivot column while not in pivot row should be divided by pivot entry $\alpha$ (i.e. every such $\gamma$ should be substituted with $\gamma’=-\alpha ‘ \gamma$).

Row Tableau

We express the linear programming in the form of tableau, and solve it through pivot operation.

e.g.:

Now we introduce the relaxation variable $u$, and substitute $z\geq \frac{1}{2}$ with $z-v_2 \geq 0$.

What is critical in standard row tableau is that the variables on right and upper margins must be $\geq0$.

More specifically, a tableau is standard if :

  • Coefficient matrix doesn’t have any unknowns.
  • Each row indicates a linear equation (not inequality), while the last row may be exceptional.
  • The last row represents the objective function that is to be minimized.
  • All variables on the margin of tableaus should be non-negative (objective variables may be the exception).
  • All variables on the margin of tableaus are different independent variables.
  • There happens to be only constant on the upper margin. It’s $1$ and in the last column.

Transform to standard row tableau

  1. from common linear programming canonical form to standard tableau:

    canonical form: $minimize \ cx +d, \ subject \ to Ax\leq b, x\geq 0$.

    $\Rightarrow$ standard row tableau:

  2. from common linear programming standard form to standard tableau:

    standard form: $minimize \ cx+d, subject \ to Ax=b, x\geq 0$.

    Then: $Ax-b=0 \Rightarrow Ax-b \geq 0, -Ax+b \geq 0$.
    $\Rightarrow$ $Ax-b=v, -Ax+b=u,v\geq 0,u\geq 0$.
    $\Rightarrow$

Simplex Method

Simplex method, which is expressed in the form of standard row tableau, can be regarded as a method to select the pivot entry, in order to reach the terminal state through finite pivot operations.

The following linear programming in the form of standard row tableau:

here $A$ is the coefficient matrix, $b$ is the column vector composed of the right hand of the linear equations, $c$ is the row vector composed of the coefficients of objective function, and $d$ is a given constant. $x$ is the row vector composed of variables (named as non-basic variable), $u$ is the column vector composed of variables (called basic variable). $z$ is the objective variable.

The matrix form is:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ minimize \ z=cx^T+d, subject \ to \ Ax^T+b=u\geq0, x\geq0$.

The canonical form is:

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ minimize\ z=cx^T+d,subject\ to\ -Ax^T\geq b,x\geq0$.

$u$ is the relaxation variable, after some pivot steps, some relaxation variables may turn into basic variables (turn into the variables on the upper margin). Now we can say these variables and inequality constraints are active.

A system of linear equation $A^T\cdot x+b=u$ has the solution $x=0,u=b$. For a given standard row tableau, this solution is called basic solution, and the corresponding objective function value is $d$. This means the following theorems are reasonable.

  1. If $b\geq 0$ (i.e., the basic solution is feasible), we say the standard tableau (S.1) is row feasible.
  2. If $b\geq 0$ and $c\geq 0$, we say (S.1) is optimal. Here, basic solution is the optimizer, and $d$ is the optimum.

Bad column

For a column in the standard tableau, if it is not the last column(the upper margin is 1) and the last element is negative, while the other elements are non-negative, we call this column bad column.

The meaning of bad column is: If there is a bad column, we can make this column’s corresponding top variable take bigger and bigger value and set other variables on the upper margin as 0, to let the objective function take smaller and smaller feasible solution. Now we can say the problem is unbounded and has no optimizers.

Bad row

Bad row is a row which is not the last row in a standard tableau, whose last element is strictly negative and other elements are non-positive.

Namely, it’s a row $[A_i,b_i]$ in the matrix $[A,b]$ which satisfies the $A_i\leq0,b_i<0$. The constraint corresponding to this bad row is $A_i^Tx+b=u_i$.The formula’s left side is strictly negative while the right side is non-negative. Therefore, this formula is a paradox. Because the bad column and non-negative conditions are incompatible, this standard tableau has no feasible solutions.