Linear Progamming Summary

Dictionary definition

lin•e•ar pro•gram•ming
noun
1. a mathematical technique for maximizing or minimizing a linear function of several variables, such as output or cost.

Fundamental theorem of linear programming

The maxima and minima of a linear programming problem each occur at a vertex of the feasible region (or along one edge of the region connecting vertices with the same value).

Graphical solution procedure

1. Identify the physical quantity to be optimized (maximized or minimized), e.g. profit, weight, cost, speed, efficiency, volume.
2. Compose a formula for that quantity. (This is known as the objective function.)
3. Identify the problem constraints on the solution. These will usually be expressed as a series of inequalities.
4. Identify the formal constraints on the solution, e.g. that variables cannot be negative.
5. Graph the constraint inequalities (usually by finding their intercepts).
6. Identify the feasible region.
7. Find the coordinates of each vertex of the feasible set.
8. Evaluate the objective function at each vertex of the feasible set.
9. Identify the optimal solution.