Linear Programming: Word Problems and Applications

Example 1

A store sells two types of toys, A and B. The store owner pays $8 and$14 for each one unit of toy A and B respectively. One unit of toys A yields a profit of $2 while a unit of toys B yields a profit of$3. The store owner estimates that no more than 2000 toys will be sold every month and he does not plan to invest more than $20,000 in inventory of these toys. How many units of each type of toys should be stocked in order to maximize his monthly total profit profit?

Solution to Example 1
Let x be the total number of toys A and y the number of toys B; x and y cannot be negative, hence
x ? 0 and y ? 0
The store owner estimates that no more than 2000 toys will be sold every month
x + y ? 2000
One unit of toys A yields a profit of $2 while a unit of toys B yields a profit of$3, hence the total profit P is given by
P = 2 x + 3 y
The store owner pays $8 and$14 for each one unit of toy A and B respectively and he does not plan to invest more than $20,000 in inventory of these toys
8 x + 14 y ? 20,000
What do we have to solve?
Find x and y so that P = 2 x + 3 y is maximum under the conditions
$$\begin{cases} \ x \ge 0 \\ \ x \ge 0 \\ \ x + y \le 2000 \\ \ 8 x + 14 y \le 20,000 \\ \end{cases}$$

.

Vertices of the solution set:
A at (0 , 0)
B at (0 , 1429)
C at (1333 , 667)
D at (2000 , 0)
Calculate the total profit P at each vertex
P(A) = 2 (0) + 3 ()) = 0
P(B) = 2 (0) + 3 (1429) = 4287
P(C) = 2 (1333) + 3 (667) = 4667
P(D) = 2(2000) + 3(0) = 4000
The maximum profit is at vertex C with x = 1333 and y = 667.
Hence the store owner has to have 1333 toys of type A and 667 toys of type B in order to maximize his profit.

Example 2

A company produces two types of tables, T1 and T2. It takes 2 hours to produce the parts of one unit of T1, 1 hour to assemble and 2 hours to polish.It takes 4 hours to produce the parts of one unit of T2, 2.5 hour to assemble and 1.5 hours to polish. Per month, 7000 hours are available for producing the parts, 4000 hours for assembling the parts and 5500 hours for polishing the tables. The profit per unit of T1 is $90 and per unit of T2 is$110. How many of each type of tables should be produced in order to maximize the total monthly profit?

Solution to Example 2
Let x be the number of tables of type T1 and y the number of tables of type T2. Profit P(x , y) = 90 x + 110 y $$\begin{cases} \ x \ge 0 \\ \ x \ge 0 \\ \ 2x + 4y \le 7000 \\ \ x + 2.5y \le 4000 \\ \ 2x + 1.5y \le 5500 \\ \end{cases}$$

.
Vertices:

A at (0,0)
B at (0,1600)
C at (1500,1000)
D at (2300,600)
E at (2750,0)

Evaluate profit P(x,y) at each vertex
A at (0,0) : P(0 , 0) = 0
B at (0,1600) : P(0 , 1600) = 90 (0) + 110 (1600) = 176000
C at (1500,1000) : P(1500,1000) = 90 (1500) + 110 (1000) = 245000
D at (2300,600): P(2300,600) = 90 (2300) + 110 (600) = 273000
E at (2750,0) : P(2750,0) = 90 (2750) + 110 (0) = 247500

The maximum profit of $273000 is at vertex D. Hence the company needs to produce 2300 tables of type T1 and 600 tables of type T2 in order to maximize its profit.

Example 3

A farmer plans to mix two types of food to make a mix of low cost feed for the animals in his farm. A bag of food A costs $10 and contains 40 units of proteins, 20 units of minerals and 10 units of vitamins. A bag of food B costs$12 and contains 30 units of proteins, 20 units of minerals and 30 units of vitamins. How many bags of food A and B should the consumed by the animals each day in order to meet the minimum daily requirements of 150 units of proteins, 90 units of minerals and 60 units of vitamins at a minimum cost?

Solution to Example 3
Let x be the number of bags of food A and y the number of bags of food B.
Cost C(x,y) = 10 x + 12 y
$$\begin{cases} \ x \ge 0 \\ \ y \ge 0 \\ \ 40x + 30y \ge 150 \\ \ 20x + 20y \ge 90 \\ \ 10x + 30y \ge 60 \\ \end{cases}$$

.

Vertices:
A at intersection of $10x + 30y = 60$ and $y = 0$ (x-axis) coordinates of A: (6 , 0)
B at intersection of $20x + 20y = 90$ and $10x + 30y = 60$ coordinates of B: (15/4 , 3/4)
C at intersection of $40x + 30y = 150$ and $20x + 20y = 90$ coordinates of C : (3/2 , 3)
D at at intersection of $40x + 30y = 150$ and $x = 0$ (y-axis) coordinates of D: (0 , 5)

Evaluate the cost c(x,y) = 10 x + 12 y at each one of the vertices A(x,y), B(x,y), C(x,y) and D(x,y).
At A(6 , 0) : c(6 , 0) = 10 (6) + 12 (0) = 60
At B(15/4 , 3/4) : c(15/4 , 3/4) = 10 (15/4) + 12 (3/4) = 46.5
At C(3/2 , 3) : c(3/2 , 3) = 10 (3/2) + 12 (3) = 51
At D(0 , 5) : c(0 , 5) = 10 (0) + 12 (5) = 60
The cost c(x , y) is minimum at the vertex B(15/4 , 3/4) where x = 15/4 = 3.75 and y = 3/4 = 0.75.
Hence 3.75 bags of food A and 0.75 bags of food B are needed to satisfy the minimum daily requirements in terms of proteins, minerals and vitamins at the lowest possible cost.

Example 4

John has $20,000 to invest in three funds F1, F2 and F3. Fund F1 is offers a return of 2% and has a low risk. Fund F2 offers a return of 4% and has a medium risk. Fund F3 offers a return of 5% but has a high risk. To be on the safe side, John invests no more than$3000 in F3 and at least twice as much as in F1 than in F2. Assuming that the rates hold till the end of the year, what amounts should he invest in each fund in order to maximize the year end return?

Solution to Example 4
Let x be the amount invested in F1, y the amount invested in F2 and z the amount invested in F1.
x + y + z = 20,000
z = 20,000 - (x + y)
Total return R of all three funds is given by
R = 2% x + 4% y + 5% z = 0.02 x + 0.04 y + 0.05 (20,000 - (x + y))
Simplifies to
R(x ,y) = 1000 - 0.03 x - 0.01 y : This is the return to maximize
Constraints: x, y and z are amounts of money and they must satisfy
x ? 0
y ? 0
z ? 0
Substitute z by 20,000 - (x + y) in the above inequality to obtain
20,000 - (x + y) ? 0 which may be written as x + y ? 20,000
John invests no more than $3000 in F3, hence
z ? 3000
Substitute z by 20,000 - (x + y) in the above inequality to obtain
20,000 - (x + y) ? 3000 which may be written as x + y ? 17,000
Let us put all the inequalities together to obtain the following system
$$\begin{cases} \ x \ge 0 \\ \ y \ge 0 \\ \ (x + y) \ge 17,000 \\ \ (x + y) \le 20,000 \\ \ x \ge 2 y \\ \end{cases}$$

.

Vertices:
A at intersection of $x + y = 20000$ and $y = 0$ , coordinates of A: (20000 , 0)
B at intersection of $x+y = 17000$ and $y=0$ , coordinates of B: (17000 , 0)
C at intersection of $x+y = 17000$ and $x = 2y$ , coordinates of C : (11333 , 5667)
D at at intersection of $x = 2y$ and $x + y = 20000$ , coordinates of D: (13333 , 6667)

Evaluate the return R(x,y) = 1000 - 0.03 x - 0.01 y at each one of the vertices A(x,y), B(x,y), C(x,y) and D(x,y).
At A(20000 , 0) : R(20000 , 0) = 1000 - 0.03 (20000) - 0.01 (0) = 400
At B(17000 , 0) : R(17000 , 0) = 1000 - 0.03 (17000) - 0.01 (0) = 490
At C(11333 , 5667) : R(11333 , 5667) = 1000 - 0.03 (11333) - 0.01 (5667) = 603
At D(13333 , 6667) : R(13333 , 6667) = 1000 - 0.03 (13333) - 0.01 (6667) = 533
The return R is maximum at the vertex At C(11333 , 5667) where x = 11333 and y = 5667 and z = 20,000 - (x+y) = 3000
For maximum return, John has to invest $11333 in fund F1,$5667 in fund F2 and $3000 in fund F3.

Example 5

Each month a store owner can spend at most $100,000 on PC's and laptops. A PC costs the store owner$1000 and a laptop costs him $1500. Each PC is sold for a profit of$400 while laptop is sold for a profit of $700. The sore owner estimates that at least 15 PC's but no more than 80 are sold each month. He also estimates that the number of laptops sold is at most half the PC's. How many PC's and how many laptops should be sold in order to maximize the profit?

Solution to Example 5
Let x and y be the numbers of PC's and laptops respectively that should be sold.
Profit = 400 x + 700 y to maximize
Constraints
15 ? x ? 80 "least 15 PC's but no more than 80 are sold each month"
y ? (1/2) x
1000 x + 1500 y ? 100,000 "store owner can spend at most $100,000 on PC's and laptops"
$$\begin{cases} \ 15 \le x \le 80 \\ \ y \ge 0 \\ \ y \le (1/2) x \\ \ 1000 x + 1500 y \le 100,000 \\ \end{cases}$$

.

Vertices:
A at intersection of $x = 15$ and $y = 0$ (x-axis) coordinates of A: (15 , 0)
B at intersection of $x = 15$ and $y = (1/2) x$ coordinates of B: (15 , 7.5)
C at intersection of $y = (1/2) x$ and $1000 x + 1500 y = 100000$ coordinates of C : (57.14 , 28.57)
D at at intersection of $1000 x + 1500 y = 100000$ and $x = 80$ (y-axis) coordinates of D: (80 , 13.3)

Evaluate the profit at each vertex
A(15 , 0), P = 400 × 15 + 700 × 0 = 6000
B(15 , 7.5) , P = 400 × 15 + 700 × 7.5 = 11250
C(57.14 , 28.57) , P = 400 × 57.14 + 700 × 28.57 = 42855
D (80 , 13.3) , P = = 400 × 80 + 700 × 13.3 = 41310