4.2 Graphical Solutions of Linear Programming
Wouldn’t it be nice if we could simply produce and sell infinitely many units of a product and thus make a never-ending amount of money? In business (and in day-to-day living) we know that some things are just unreasonable or impossible. Instead, our hope is to maximize or minimize some quantity, given a set of constraints.
In order to have a linear programming problem, we must have:
- Constraints, represented as inequalities
- An objective function, which is a function whose value we either want to be a large as possible (want to maximize it) or as small as possible (want to minimize it).
Let’s consider an extension of the example from the end of the last section:
Example of Linear Programming
A company produces a basic and premium version of its product. The basic version requires 20 minutes of assembly and 15 minutes of painting. The premium version requires 30 minutes of assembly and 30 minutes of painting. If the company has staffing for 3,900 minutes of assembly and 3,300 minutes of painting each week. They sell the basic products for a profit of $30 and the premium products for a profit of $40. How many of each version should be produced to maximize profit?
Let b = the number of basic products made, and p = the number of premium products made. Our objective function is what we’re trying to maximize or minimize. In this case, we’re trying to maximize profit. The total profit, P, is:
In the last section, the example developed our constraints. Together, these define our linear programming problem:
Objective function: MAX
Constraints: (We often say “Subject to:” or for short s.t.)
In this section, we will approach this type of problem graphically. We start by graphing the constraints to determine the feasible region – the set of possible solutions. Just showing the solution set where the four inequalities overlap, we see a clear region.
To consider how the objective function connects, suppose we considered all the possible production combinations that gave a profit of P = $3000, so that .That set of combinations would form a line in the graph. Doing the same for a profit of $5000 and $6500 would give additional lines. Graphing those on top of our feasible region, we see a pattern:
Notice that all the constant-profit lines are parallel, and that in general the profit increases as we move up to upper right. Notice also that for a profit of $5000 there are some production levels inside the feasible region for that profit level, but some are outside. That means we could feasibly make $5000 profit by producing, for example, 167 basic items and no premium items, but we can’t make $5000 by producing 125 premium items and no basic items because that falls outside our constraints.
The solution to our linear programming problem will be the largest possible profit that is still feasible. Graphically, that means the line furthest to the upper-right that still touches the feasible region on at least point. That