Linear programming is the field of mathematics concerned with maximizing or minimizing linear functions under constraints. A linear programming problem includes an objective function and constraints. To solve the linear programming problem, you must meet the requirements of the constraints in a way that maximizes or minimizes the objective function. The ability to solve linear programming problems is important and useful in many fields, including operations research, business and economics.
Graph the feasible region of your problem. The feasible region is the region in space defined by the linear constraints of the problem. For example, if your problem contains the inequalities x + 2y > 4, 3x - 4y < 12, x > 1 and y > 0, you graph the intersection of these regions as your feasible region.
Find the corner points of the region. If your problem is solvable, there will be visible sharp points, or corners, in your region. Mark these points on your graph.
Calculate the coordinates of these points. If you graphed the feasible region well, you often will be able to know immediately the coordinates of the corner points. If not, you can calculate them by hand by substituting your inequalities into each other and solving for x and y. In the given example, you will find (4,0) is a corner point, as well as (1,1.5).
Substitute these corner points into the objective function of the linear programming problem. You will have as many answers as you do corner points. For example, assume your objective function is to maximize the function x + y. In this example, you will have two answers: one for the point (4,0) and one for the point (1,1.5). The answers these points yield are 4 and 2.5, respectively.
Compare all your answers. If your objective function is one of maximization, you inspect your answers to find the largest one. Likewise, if your objective function is one of minimization, you inspect your answers, looking for the smallest one. In our example, since the objective function is for the purpose of maximization, the point (4,0) solves the linear programming problem, yielding an answer of 4.
- "An Introduction to Linear Programming and Game Theory"; Thie and Keough; 2008
- calculadora image by Dantok from Fotolia.com