Lesson 2: Linear Programming

Objectives

After reading and studying this lesson, the students will be able to:

• define linear programming

• determine the restrictions on linear programming using the graphical method
• explain the concepts of optimal solution, feasible solution, extreme point, constraints, and
minimal solution
• solve problems which have multiple solutions such as the concept of infeasibility and
unboundedness
• solve linear programming problems graphically and interpret the solutions correctly
• formulate linear programming problems
• explain the Importance of linear programming in correct and accurate decision making
• answer linear programming problems

Introduction

Most business students secretly dream of someday running their own business. Many of the problems
met by managers involve making decisions that will maximize or minimize quantities. For example, a
plant manager can determine the most economical way of shipping goods from the factory to the
market. A Chef may want to design a diet satisfying certain nutritional requirements at minimal cost. A
manufacturer may wish to blend ingredients, subject to specification, to maximize the profits. In this
lesson, several problems on linear programming - which is a vital tool for every manager in making a
good decision - are explained.

Linear programming refers to planning through the use of a linear relationship of the variables involved.
It applies mathematical techniques to find the best possible solution to problems in spite of limited
resources. A good manager can maximize profit and minimize cost without violating the limitation or
restriction of variables, such as time and quantity of available raw material. It is, therefore, a must for
any prospective manager to learn

and understand linear programming problems (maximization and minimization). Two methods -the
graphical method and the simplex method are used in linear programming. The graphical method can
only be used the problem has two or three variables, since there are only two coordinate axes in a plane
and three coordinates in space. The problems on maximization or minimization involving more than
three variables can be handled by the simplex method which will be discussed in the next lesson.
The Graphical Method

In this method a graph is used to arrive at the optimal solution. The optimal solution is one that makes
the objective function as large as possible in the case of a maximization process and as small as possible
in the case of a minimization process. The set of all points in the graph satisfying the constraints is called
feasible solution. These points are located at the feasible region (shaded portion) of the graph.

A linear program consists of two parts: the objective function and the constraints or limitation. The
objective function is a mathematical expression introduced by the words “maximize” or “minimize”.
The constraints are introduced by the word "subject to”. The mathematical expression in the constraints
is written as inequalities. Two kinds of constraints may occur. Explicit constraint means that a condition
expressed in a mathematical sentence is derived from the condition of the problems. Implicit
constraints are implied conditions such as when time or raw materials are variables in the problems.
These factors must always be expressed as positive values.

Mathematical Formulation

More often than not, optimization problems are stated word problems which need to be transformed to
algebraic symbols. The following are recommended in converting word problems into mathematical
symbols

1. Represent the unknown value in the problem by a variable. If necessary, tabulate the data to
form mathematical sentences.

2. Formulate the objective function and constraints.

3. Using a coordinate plane, graph the constraints to determine the feasible region.

4. The point of intersection of lines can be seen. Solve for the coordinates of the point.

5. Substitute the coordinates at the vertices of the feasible region in the objective function.

6. From the values of coordinates at the vertices, the decision will rely on either the highest value
which corresponds to maximization or the lowest value which corresponds to minimization.
Linear Programming: Maximization Problems

Example 1: Graphic Art Inc., a manufacturer of photographic products, prepares two types of film
developers each day: fine and extra fine, using solutions A and B as the raw material. Suppose that each
quart of fine contains 2 oz. of solution A and 1 oz. of solution B, while each quart of extra fine contains 1
oz. solution A and 2 oz. of solution B. Suppose also that the profit is Php 80 for each quart of fine and
Php 100 for each quart of extra fine. If the firm has 50 oz. of solution A and 70 oz. of solution B available
each day, how many quarts of fine and how many quarts of extra fine should be made daily to maximize
the profit?

Solution:

Step 1: Tabulate the data and statement of variables.

Representation of Number of Quart of Number of Quart of Profit
Variables Fine and Extra Fine Fine and Extra Fine
Contained in Solution A Contained in Solution B
Let X be the number of 2x x 80x
fine to be made
Let Y be the number of Y 2y 100y
extra fine to be made
Total 2x + y X + 2y 80x + 100y

Step 2. Formulate the objective function and constraints.

Maximize (This is just the same as asking for the value of x and y that will maximize the objective
function)
𝑷 = 𝟖𝟎𝒙 + 𝟏𝟎𝟎𝒚 (objective function)

Subject to: (The restrictions that must be satisfied by x and y)

2𝑥 + 𝑦 ≤ 50
𝑥 + 2𝑦 ≤ 70
𝑥 ≥ 0, 𝑦 ≥ 0
Step 3. Graph the objective functions by first converting the inequalities into equations. Next, find their
intercepts. As a result:
2𝑥 + 𝑦 = 50
𝑥 + 2𝑦 = 70
𝑥 = 0, 𝑦 = 0

The feasible solution is bounded by vertices 1 to 4. The coordinates of three vertices are already
identified. However, V3 is still unknown so the coordinate points must be solved.

2𝑥 + 𝑦 = 50 (Eq. 1)
𝑥 + 2𝑦 = 70 (Eq. 2)

Multiply the second equation by 2.

2𝑥 + 𝑦 = 50 (Eq. 1)
2𝑥 + 4𝑦 = 140 (Eq. 3)
−3𝑦 = −90
Y = 30

Solving for x, substitute the derived value of y for y in equation 1.

2𝑥 + 30 = 50
2𝑥 = 20
X = 10

Thus, the coordinates of V3 , is (10, 30).

Step 4. Maximize the objective function of 80x + 100y to the different vertices of the graph.
Vertices Value of P = 80x + 100y in Php
V1 (0,0) 0
V2 (0, 35) 3500
V3 (10, 30) 3800
V4 (25, 0) 2000

Step 5. Decision – Making

The manufacturer must make 10 quarts of fine solution and 30 quarts of extra fine solution
each day to have a maximum profit of Php 3,800 per day.

Example 2: Shane, the production manager of Pantene shampoo, wants to determine the production
mix that will yield the maximum profit. As a manager, she needs to analyze data for her to decide. It
takes 5 minutes to mix 1 case of men's shampoo and 10 minutes to mix 1 case of women's shampoo.
This process it done for 100 minutes per day. It takes 7 minutes to bottle 1 case of men's shampoo and 7
minutes to bottle 1 case of women's shampoo. Eighty-four minutes is consumed for the bottling process
per day. It takes 9 minutes to pack 1 case of men's shampoo and 5 minutes to pack 1 case of women's
shampoo. The total number of minutes available for the packing process is 90 minutes. The company
earns Php 60 for every case of men's shampoo and Php 80 for every case of women's shampoo. How
many cases of men's and women's shampoo should be produced per day to maximize the profit?

Solution: Let x be the number of minutes for mixing, bottling and packing the product for one case of
men's shampoo.

Let y be the number of minutes for mixing, bottling and packing the product for one case of
women's shampoo

The table below summarizes the data.

Product
Process Number of Minutes per Case
Available Minutes per Day
Men’s Shampoo Women’s Shampoo
Mixing 5x 10y ≤ 100
Bottling 7x 7y ≤ 84
Packing 9x 5y ≤ 90
Profit per case in Php 60x 80y = Maximize
Objective function
Maximize: 𝑃𝑟𝑜𝑓𝑖𝑡 (𝑃 ) = 60𝑥 + 80𝑦

Constraints

Subject to: 5𝑥 + 10𝑦 ≤ 100

7𝑥 + 7𝑦 ≤ 84
9𝑥 + 5𝑦 ≤ 90
𝑥 = 0, 𝑦 = 0

Determine the intercept for each equation and graph. Converting each inequality into equation:
For 5𝑥 + 10𝑦 = 100, the intercepts are (0,10) and (20,0).
For 7𝑥 + 7𝑦 = 84, the intercepts are (0,12) and (12,0).
For 9𝑥 + 5𝑦 = 90, the intercepts are (0,18) and (10,0).

From the graph, the feasible solution is the region bounded by vertices 1 to 5. From these, two vertices
have no given values yet because they are points of intersection between two lines. To find the values,
use the system of simultaneous equations, V3 the point of intersection between the two lines
represented by the equations 7x + 7y = 84 and 5x+ 10y = 100.
Solving for the x and y coordinates of V3, the answers are: x = 4 and y = 8

V4, is represented by the intersections between the equations 7x + 7y = 84 and 9x + 5y = 90.

Again, solving the equations by the same method results in:

15 9
𝑥= or 7.5 and 𝑦 = or 4.5
2 2

Finding the optimal solution

Taking the coordinates at the vertices and substituting them in the objective function shows:
Vertices Value of P = 60x + 80y in Php
V1 (0,0) 0
V2 (0, 10) 800
V3 (4,8) 880
15 9 810
V4 ( , ) 2 2
V5 (10, 0) 600

Decision – Making

Pantene Shampoo should produce 4 cases of men’s shampoo and 8 cases of women’s shampoo
per day in order to get the maximum profit of Php 880 per day.

Linear Programming: Minimization Problems

Example 1: The ABCD Fertilizer Company has two plants where the products are made. In a week,
plant A can make at most 30 tons of fertilizers and plant B can make at most 40 tons. The production
manager wants to make a total of at least 50 tons of fertilizer per week. The amount of particulate
matter in the atmosphere over the nearby town is measured weekly and found out to be 20 pounds for
each ton of product made in plant A and 30 pounds for each ton of product made in plant B. How many
tons should be made weekly in each plant to minimize the total amount of particulate matter in the
atmosphere?

Let X be the number of tons of product made in plant A per week.

Let Y be the number of tons of product made in plant B per week.

Let X + Y be the total amount of product manufactured per week in plants A and B.
Since the production manager wants to make a total of at least 50 tons per week, 𝑥 + 𝑦 ≥ 50. Plant A
can make 30 tons at most; hence, x ≤ 30, Plant B can make 40 tons at most, which is y ≤ 40. Of course, x
and y cannot be negative so x ≥ 0 and y ≥ 0. The amount of particulate matter in pounds is P= 20x + 10y.
This is what the company wants to minimize.

Minimize: 𝑃 = 20𝑥 + 40𝑦

Subject to: 𝑥 + 𝑦 ≥ 50
𝑥 ≤ 30
𝑦 ≤ 40
𝑥 ≥ 0, 𝑦 ≥ 0

Graphing the constraints, the intercept of x + y = 50 are (0, 50) and (50, 0).

The feasible region is bounded by vertices A, B, and C with their corresponding coordinates as (10,40)
(30,40) and (30, 20). Finding the optimum solution from each vertex results in:

Vertices Value of P = 20x + 30y in pounds

A (10,40) 1400
B (30,40) 1800
C (30,20) 1200
Decision-making
The Atlas Fertilizer Company should produce 30 tons of products in plant A and 20 tons in plant B. If
this course of action is followed, the total amount of particulate matter over the town will be minimized
to 1,200 pounds weekly.

Example 2: The purchasing manager of a food company wants to determine the supply mix with the
least cost. He collects the data necessary for him to make a decision. A gallon of Liberty milk can
produce 5 cases of cheese, 7 cases of butter, and 9 cases of cream. In contrast, a gallon of Alaska milk
can make 10 cases of cheese, 8 cases of butter, and 4 cases of cream. He must produce at least 100
cases of cheese, 112 cases of butter, and 72 cases of cream per day. Liberty milk costs $5 per gallon
while Alaska milk costs $6 per gallon. How many gallons of Liberty milk and Alaska milk should he
purchase per day co minimize cost? The data are given below.

Number of Cases/Gallon Number of

Product Supplier
Liberty Alaska Cases/Day
Cheese 5 10 ≥ 100
Butter 7 8 ≥ 112
Cream 9 4 ≥ 72
Cost per gallon ($) 5 6 = Minimum

Solution:

Let X be the number of gallons of Liberty Milk to be purchased per day.

Let Y be the number of gallons of Alaska Milk to be purchased per day.

Objectives function
Minimize: 𝐶 = 5𝑥 + 6𝑦

Subject to: (constraints)

5𝑥 + 10𝑦 ≥ 100
7𝑥 + 8𝑦 ≥ 112
9𝑥 + 4𝑦 ≥ 72
𝑥 ≥ 0, 𝑦 ≥ 0

The intercepts of the constraints are as follows:

For 5𝑥 + 10𝑦 = 100, the intercepts are (0,10) and (20,0).
For 7𝑥 + 8𝑦 = 112, the intercepts are (0, 14) and (16,0).
For 9𝑥 + 4𝑦 = 72, the intercepts are (0,18) and (8,0).
Graphing the coordinates of the constraints:

From the graph, the feasible solution/region is found on the four corners denoted by A, B, C, and D. The
coordinates A and D are already given while B and C are not.

Corner B is the intersection of the lines:

9𝑥 + 4𝑦 = 72
7𝑥 + 8𝑦 = 112

Solving its intersection using systems of simultaneous equations:

𝟑𝟐 𝟏𝟐𝟔
𝒙= 𝒂𝒏𝒅 𝒚 =
𝟏𝟏 𝟏𝟏
Corner C is the intersection of the lines:
7𝑥 + 8𝑦 = 112
5𝑥 + 10𝑦 = 100

Solving its intersection using systems of simultaneous equations:

𝟑𝟐 𝟏𝟒
𝒙= 𝒂𝒏𝒅 𝒚 =
𝟑 𝟑

Finding the optimum solution for each vertex gives:

Vertices Value of C = 5x + 6y in $
A (20,0) 100
32 126 83.2727
B( , )
11 11
𝟑𝟐 𝟏𝟒 81.3333
C(𝟑 , 𝟑
)
D (0,18) 108

Decision – Making
𝟑𝟐 14
The purchasing manager should buy or 10.6667 gallons of Liberty Milk and or 4.6667
𝟑 3
gallons of Alaska Milk per day in order to achieve a minimum total cost of $81.3333.