Linear Programming

| Tags Algorithm 

In a linear programming problem, we are given a set of variables, and we want to assign real values to them so as to

  1. satisfy a set of linear equations and/or linear inequalities involving these variables
  2. maximize or minimize a given linear objective function


Linear Programs can be solved by the simplex method, devised by George Dantzig in 1947. Typically there are three steps:

  1. starts at a vertex
  2. repeatedly looks for an adjacent vertex of better objective value, and moves to it
  3. if no better neighbors, simplex declares this vertex to be the optimal and halts.

Previous     Next