In a linear programming problem, we are given a set of variables, and we want to assign real values to them so as to
- satisfy a set of linear equations and/or linear inequalities involving these variables
- maximize or minimize a given linear objective function
Simplex
Linear Programs can be solved by the simplex method, devised by George Dantzig in 1947. Typically there are three steps:
- starts at a vertex
- repeatedly looks for an adjacent vertex of better objective value, and moves to it
- if no better neighbors, simplex declares this vertex to be the optimal and halts.