LP Example
Page Summary
This page…. This page covers just the basics.
Related Pages

A Quick example

linear-programming-01.gif

Let's say that to survive, we need 100 units of vitamin A and 100 units of vitamin B per day. An apple provides 30 units of A and 50 units of B. An orange provides 60 units of A and 20 units of B. An apple costs 1 dollar and an orange costs 3 dollars. What's the cheapest way to get the nutrition you need?
Let $X_A$ be the number of apples we consume and $X_O$ be the number of oranges. Here's our cost equation:

(1)
\begin{equation} COST=X_A+3X_O \end{equation}

Our nutrition requirements can be stated this way for vitamin A:

(2)
\begin{align} 30X_A+60X_O\geq100 \end{align}

And this way for vitamin B:

(3)
\begin{align} 50X_A+20X_O\geq100 \end{align}

Let's just look informally at a few dietary combinations. Suppose I eat 2 apples and 2 oranges; how am I doing?

linear-programming-02.gif
(4)
\begin{align} Vitamin A=30 \times 2+60 \times 2=180 \end{align}
(5)
\begin{align} Vitamin B=50 \times 2+20 \times 2=140 \end{align}

I'm overdoing it and could probably eat more cheaply. How about 1 of each?

linear-programming-03.gif
(6)
\begin{align} Vitamin A=30 \times 1+60 \times 1=90 \end{align}
(7)
\begin{align} Vitamin B=50 \times 1+20 \times 1=70 \end{align}

Not quite enough. What if I have 1 apple and 2 oranges?

linear-programming-04.gif
(8)
\begin{align} Vitamin A=30 \times 1+60 \times 2=150 \end{align}
(9)
\begin{align} Vitamin B=50 \times 1+20 \times 2=90 \end{align}

Not a great combo. Too much A and not enough B. So let's try the other way round.

linear-programming-05.gif
(10)
\begin{align} Vitamin A=30 \times 2+60 \times 1=120 \end{align}
(11)
\begin{align} Vitamin B=50 \times 2+20 \times 1=120 \end{align}

Just about right, but still, 20% more than I need. What about 4 apples and 0 oranges?

linear-programming-06.gif
(12)
\begin{align} Vitamin A=30 \times 4+60 \times 0=120 \end{align}
(13)
\begin{align} Vitamin B=50 \times 4+20 \times 0=200 \end{align}

That would work too – and it would be cheaper than the previous one.
And notice that we haven't asked yet about the price, which, is really what we are trying to optimize here (that is, we want to get the nutrition we need at the cheapest price). The table below summarizes the cost of each of the diets we've just considered.

Unsupported math environment "tabular"

If we assume we can cut the fruit and save a bit for the next day, it is starting to look like we should be able to get all of our vitamins for less than 4 dollars per day. But how much, exactly? Can we do better than this "trying every case" method? Yes.
Let's start with a chart of apple-orange space. This will be the usual 2 dimensional Cartesian coordinate system with the vertical (Y) axis representing number of oranges and the horizontal (X) axis representing number of apples. Each point (x,y) represents a diet of x apples and y oranges per day.

linear-programming-07.gif


Our task is to determine which point or set of points (that is, which diet or diets) give us all the nutrition we need at the cheapest price. The collection of all the diets (that is, combinations of apples and oranges) that provide enough nutrition (that is, meet our constraints) is called the "feasible set." The goal of this analysis is to find the optimal point (or points) within this set of acceptable points.
As a first step to delimiting the feasible set, we notice that we cannot eat negative apples or oranges. Both X1 and X2 have to be non-negative:

(15)
\begin{align} X_1\geq0 \end{align}
(16)
\begin{align} X_2\geq0 \end{align}

This rules out all the points to the left of the vertical axis and all of the points below the horizontal axis as shown below. This means we can concentrate on just the upper right quadrant of "apple-orange space."

linear-programming-08.gif


Our vitamin A constraint, $30X_1+60X_2≥100$, looks a bit like the equation for a line (in "y = mx + b" form). Remembering that X2 refers to oranges and that oranges is the vertical (Y) axis, we can re-write this equation like this:

(17)
\begin{align} 60X_2\geq100-30X_1 \end{align}

or

(18)
\begin{align} 6X_2\geq10-3X_1 \end{align}

or

(19)
\begin{align} X_2\geq \frac{10}{6}-\frac{3}{6} X_1 \end{align}

The y-intercept is, thus, 10/6=1 2/3 and the slope is -1/2. We plot this line on the graph. And then what do we do with the inequality sign? It says that the constraint is that X2 is greater than (above) or equal to this line and so we shade the area above and to the right of the line as a smaller feasible set.

linear-programming-09.gif


Next, we look at the equation describing the vitamin B constraint

(20)
\begin{align} 50X_1+20X_2\geq100 \end{align}
(21)
\begin{align} 20X_2\geq100-50X_1 \end{align}
(22)
\begin{align} X_2\geq\frac{10}{2}-\frac{5}{2} X_1 \end{align}

We shade the apple-orange points that fit with this constraint blue. The dietary combinations that meet both these constraints (and the non-negative constraints) appear a muddy purple.

linear-programming-10.gif


Next we look at our "objective function" – that is, the equation that describes the thing we are trying to optimize. In this case, it's cost and the equation looks like this:

(23)
\begin{equation} COST=X_1+3X_2 \end{equation}

Let's rewrite this in y=mx+b form:

(24)
\begin{align} X_2=-\frac{1}{3} X_1+\frac{COST}{3} \end{align}

This is the equation of a family of lines with slope -1/3 and different y-intercepts, several of which are shown as dashed lines in the diagram below.

linear-programming-11.gif


In each case, the y-intercept is one third of our cost. To minimize the cost, we want to line that has the smallest y-intercept and goes through at least one point of the feasible set (the purple points).

linear-programming-12.gif


Thus, our best diet will consist of 3 1/3 apples per day at a cost of $3.33