Linear Programming Standard Form

So breifly, a sentence on the history of LP from Chvatal’s book on LP. Basicaly Linear Programming “started in 1947 when G. B. Dantzig designed the simplex method for solving linear programming formulations of the U.S. Air Force planning problems”. From there on it expanded to a bunch of other applications and became a field in its own. Anyways, part of the latest assignment is converting a linear program into standard form. The basic steps for doing this are pretty thoroughly explained in these U.Wash. slides so I won’t go into too much detail. Basically, you want to make sure that several conditions are met:

  • All equations are inequalities in less than or equal to form. So any equations such as:
$$ x_2 + 2x_2 \ge 5 $$

must become:

$$ -x_2 - 2x_2 \le -5 $$

obviously by multiplying by -1.

  • All minimization problems must become maximization problems, again just multiply the equation by -1. to do this and replace min with max.
  • All variables must be in form:
$$ x_1, x_2, x_n \ge 0 $$

if they aren’t, for example:

$$ x_1 \ge -1 $$

you have to replace it by:

$$ z_2 = x_2 + 1 \text{ or } x_2 = x_2 -1 \text{ with } z_2 \ge 0$$

This actually means that your final standard form will have a bunch of z’s instead of x’s in it.

  • If there are free variables (i.e. those without a condition like: $x_2 \ge 0$), then you need to replace them with $x_2 = z_1^+ - z_1^-$ with bounds $0 \le z_1^+ \text{ and } 0 \le z_1^-$
Written on October 4, 2014