Linear Programming

Linear Programming

How to solve linear programming problems: example and its solution.

Example

A chocolate milk is made by adding 1 spoon of chocolate powder and 2 cups of milk. A chocolate shake is made by adding 2 spoons of chocolate powder and 1 cup of milk. There are 10 spoons of chocolate powder and 11 cups of milk. The price of a chocolate milk is $1. And the price of a chocolate shake is $1.5. Find the maximum sales that can be made.

Make a table to write
two linear inequalities and one linear equation.

Set the number of chocolate milk as x
and the number of a chocolate shake as y.

Write 'Choco Milk (x)' and 'Chocolate Shake (y)'
as the titles of 2nd and 3rd column.

Fill each row using each condition.

Powder:

1⋅x spoons are needed
to make x cups of choco milk.

2⋅y spoons are needed
to make y cups of choco shake.

There are 10 spoons of powder.

So 1⋅x + 2⋅y ≤ 10.

Milk:

2⋅x cups are needed
to make x cups of choco milk.

1⋅y cups are needed
to make y cups of choco shake.

There are 11 cups of milk.

So 2⋅x + 1⋅y ≤ 11.

Sales:

1⋅x dollars income from x cups of choco milk.

1.5⋅y dollars income from y cups of choco shake.

Let's say the total sales is $k.

Then 1⋅x + 1.5⋅y = k

Write the powder inequality in slope-intercept form.

y ≤ -(1/2)x + 5

It's for graphing and comparing the slopes.

Write the milk inequality in slope-intercept form.

y ≤ -2x + 11

Write the sales equation in slope-intercept form.

y ≤ (-2/3)x + 2/3k

Draw the inequalities on the coordinate plane.
Color the intersecting region. (blue region)
(Of course x ≥ 0, y ≥ 0.)

System of linear inequalities

Then think about the sales equation:
y ≤ (-2/3)x + 2/3k. (red line)

To maximize k (sales),
the y-intercept, + 2/3k, has to be maximized.

And the slope is (-2/3),
which is between -1/2 and -2.

Then, to maximize + 2/3k,
the red line has to pass the red point:
the intersecting point of
the 'powder equation' and the 'milk equation'.

To find the red point,
solve the system of
the powder equation (x + 2y = 10)
and the milk equation (2x + y = 11).

Then the red point is (4, 3).

System of linear equations: elimination method

So the sales (k) is maximized
if the sales equation (x + 1.5y = k)
passes through (4, 3).

So put (4, 3) into the sales equation.
Then k = 8.5.

This means the maximum sales is $8.5.