Applicable Mathematics/Linear Programming and Graphical Solutions

Linear Programming

Linear programming is a method that is used to find a minimum or maximum value for a function. That value is going to satisfy a known set of conditions constraints. Constraints are the inequalities in the linear programming problem. Their solution is graphed as a feasible region, which is a set of points. These points are where the graphs of the inequalities intersect. And, the region is said to be bounded when the graph of a system of constraints is a polygonal region.

There are 7 steps that are used when solving a problem using linear programming.

1. Define the variables.

2. Write a system of inequalities.

3. Graph the system of inequalities.

4. Find the coordinates of the vertices of the feasible region.

5. Write a function to be maximized or minimized.

6. Substitute the coordinates of the vertices into the function.

7. Select the greatest or least result. Answer the problem.

Many types of real-world problems can be solved using linear programming. These problems have restrictions placed on the variables. Some function of the variable must be maximized or minimized.

One Company sells two different products A and B, making a profit of Rs.40 and Rs.30 per unit, respectively. They are both produced with help of common production process and are sold in two different markets. The production process has a total capacity of 30000 man - hours. it takes 3 hours to produce an unit of A and one hour to produce an unit of B. The market has been surveyed and company officials feel that the maximum number of units of A that can be sold is 8000 units and that of B is 12000 units. Subject to those limitations; products can be sold in any combination. Formulate this problems as an Linear Programming Model to maximize profit.

Objective Function

Sometimes, in linear programming problems, identifying the feasible region is not the only thing necessary to be done. To maximize or minimize the function, the best combination of values must be found. This is what the objective function does. It can either have a maximum value, a minimum value, both, or neither. It all depends upon the feasible region.

There are two different general types of regions: bounded and unbounded regions. Bounded feasible regions have both a minimum and a maximum value. Unbounded feasible regions have either a minimum or maximum value, never both. The minimum or maximum value of such objective functions always occurs at the vertex of the feasible region. This mathematical idea, however, is a proof that is for more advanced mathematics.

Bounded Region Example

Graph the following system of inequalities. Name the coordinates of the vertices of the feasible region. Find the maximum and minimum values of the function f(x,y) = 3x + y for this region. x > 1

y > 0 2x + y < 6

1. Find the vertices of the region. Graph the inequalities.

The polygon formed is a triangle with vertices at (1, 4), (3, 0), and (1, 0).

2. Use a table to find the maximum and minimum values of f(x, y). Substitute the coordinates of the vertices into the function. The maximum value is 9 at (3, 0). The minimum value is 3 at (1, 0).

Unbounded Region Example

Graph the following system of inequalities. Name the coordinates of the vertices of the feasible region. Find the maximum and minimum values of the function f(x, y)= 5x + 4y for this region.

2x + y > 3

3y - x < 9

2x + y < 10

Graph the system of inequalities. There are only two points of intersection: (0, 3) and (3, 4).

The maximum is 31 at (3, 4).

Although f(0, 3) is 12, it is not the minimum value since there are other points in the solution that produce lesser values. For example, f(3, -2) = 7 and f(20, -35) = -40. It appears that way because the region is unbounded, f(x, y) has no minimum value.

Maximum and Minimum Values

Sometimes, it is necessary to find the minimum or maximum value that a linear function has for the points in a feasible region. The minimum or maximum value of a related function always occurs at one of the vertices of the feasible region.