Management

Science
Chapter 2
Linear Programming
Graphical Method

Name: Block:
Course Schedule: Date:

Lesson title: Linear Programming Materials:

Pen and non-scientific calculator
Lesson Objectives:
At the end of this module, you should be able to: Management Science by Aduana
1. Determine the maximum combination using
graphical approach. References:
2. Calculate linear programming problems using Management Science by Ben Taylor
the algebraic approach.

Productivity Tip:
"Always know when to take a break."

A. LESSON PREVIEW/REVIEW
1) Introduction
Linear programming was developed during World War II, when a system with which to maximize
the efficiency of resources was of utmost importance. New war-related projects demanded
attention and spread resources thin. “Programming” was a military term that referred to activities
such as planning schedules efficiently or deploying men optimally.

2) Activity 1: What I Know Chart, part 1

Try answering the questions below by writing your ideas under the first column What I Know.

What I Know Questions: What I Learned (Activity 4)

1. What is linear programming?

2. What is objective function?

3. What is feasible region?

B. MAIN LESSON
1) Activity 2: Content Notes

1
Lesson Objective 1
A furniture dealer deals in only two items–tables and chairs. He has ₱50,000 to invest and has
storage space of at most 60 pieces. A table costs ₱2,500 and a chair costs ₱500. He estimates that
from the sale of one table, he can make a profit of ₱250 and that from the sale of one chair a profit of
₱75. He wants to know how many tables and chairs he should buy from the available money so as to
maximize his total profit, assuming that he can sell all the items which he buys.
Such type of problems which seek to maximize (or, minimize) profit (or, cost) form a general
class of problems called optimization problems. Thus, an optimization problem may involve finding
maximum profit, minimum cost, or minimum use of resources etc.
A special but a very important class of optimization problems is linear programming problem.
The above stated optimization problem is an example of linear programming problem. Linear
programming problems are of much interest because of their wide applicability in industry, commerce,
management science etc.

Mathematical formulation of the problem

Let x be the number of tables and y be the number of chairs that the dealer buys. Obviously, x and y
must be non-negative, i.e.,
x0 ... (1)
(Non-negative constraints)
y0 ... (2)

 The dealer is constrained by the maximum amount he can invest (₱50,000). A table costs
₱2,500 (x) and a chair costs ₱500 (y). Stated mathematically,
(Investment constraint)
or ... (3)

 The dealer is also constrained by the maximum number of items he can store (60).
(Storage constraint) ... (4)

 The dealer wants to invest in such a way so as to maximize his profit. The dealer can make a
profit of ₱250 from a sale of one table and ₱75 from a sale of one chair. Let us say ‘z’ is stated
as a function of ‘x’ and ‘y’, the objective function is stated as:
(Objective function) ... (5)

 Mathematically, the given problem now reduces to:

maximize
subjects to the constraints:

So, we have to maximize the linear function ‘z’ subject to certain conditions determined by a set
of linear inequalities with variables as non-negative. There are also some other problems where we
have to minimize a linear function subject to certain conditions determined by a set of linear inequalities
with variables as non-negative. Such problems are called Linear Programming Problems.
Thus, a Linear Programming Problem is one that is concerned with finding the optimal value
(maximum or minimum value) of a linear function (called objective function) of several variables (say x

2
and ‘y’), subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities
(called linear constraints). The term linear implies that all the mathematical relations used in the problem
are linear relations while the term programming refers to the method of determining a particular program or
plan of action.

Note: Usual linear programming problems for decision making involves maximization of contribution margin and
minimization of cost.

Definition of Terms
Before we proceed further, we now formally define some terms (which have been used above) which
we shall be using in the linear programming problems:
1. Objective function. Linear function z = ax + by, where ‘a’ and ‘b’ are constants, which has to be
maximized or minimized is called a linear objective function.
 In the above example, z = 250x + 75y is a linear objective function. Variables ‘x’ and ‘y’ are
called decision variables.

2. Constraints. The linear inequalities or equations or restrictions on the variables of a linear

programming problem are called constraints. The conditions x ≥ 0, y ≥ 0 are called non-negative
restrictions. In the above example, the set of inequalities (1) to (4) are constraints.

3. Optimization problem. A problem which seeks to maximize or minimize a linear function (say of two
variables ‘x’ and ‘y’) subject to certain constraints as determined by a set of linear inequalities is called
an optimization problem. Linear programming problems are special type of optimization problems. The
above problem of investing a given sum by the dealer in purchasing chairs and tables is an example of
an optimization problem as well as of a linear programming problem.

Linear Programming Assumptions

Before we get too focused on solving linear programs, it is important to review some theory. For
instance, several assumptions are implicit in linear programing problems. These assumptions are:
1. Proportionality. The contribution of any variable to the objective function or constraints is
proportional to that variable. This implies no discounts or economies to scale. For example, the value of
8x is twice the value of 4x, no more or less.
2. Additivity. The contribution of any variable to the objective function or constraints is independent of
the values of the other variables.
3. Divisibility. Decision variables can be fractions. However, by using a special technique called
integer programming, we can bypass this condition. Unfortunately, integer programming is beyond the
scope of this paper.
4. Certainty. This assumption is also called the deterministic assumption. This means that all
parameters (all coefficients in the objective function and the constraints) are known with certainty.
Realistically, however, coefficients and parameters are often the result of guess-work and
approximation. The effect of changing these numbers can be determined with sensitivity analysis

3
 Graphical Approach
Let us now solve the problem. In order to solve the problem, we have to use construct a graph and use
algebraic method.

Let us graph the constraints stated as linear inequalities:

... (1)
... (2)
... (3)
... (4)
To graph the constraints:
 Constraint (1) and (2) are at point ‘0’
 For constraint (3):
x-axis:
Let y = 0

 Plot point 20 at x-axis which is also point ‘A’ in the graph below.

y-axis:
Let x = 0

 Plot the point 100 at y-axis.

 For constraint (4):

x- axis:
Let y = 0

 Plot point 60 at x-axis

y-axis:
Let x = 0

4
  Plot point 60 at y-axis.

The graph will look like this:

The graph of this system (shaded region) consists of the points common to all half planes
determined by the inequalities (1) to (4). Each point in this region represents a feasible choice open to
the dealer for investing in tables and chairs. The region, therefore, is called the feasible region for the
problem. Every point of this region is called a feasible solution to the problem. With this, we have the
Feasible region. The common region determined by all the constraints including non-negative
constraints ‘x’, ‘y’ ≥ 0 of a linear programming problem is called the feasible region (or solution
region) for the problem. In the problem, the region OABC (shaded) is the feasible region for the
problem. The region other than feasible region is called an infeasible region.
Feasible solutions Points within and on the boundary of the feasible region represent feasible
solutions of the constraints. In the problem, every point within and on the boundary of the feasible
region OABC represents feasible solution to the problem. For example, the point (10, 50) is a feasible
solution of the problem and so are the points (0, 60), (20, 0), etc.
Any point outside the feasible region is called an infeasible solution. For example, the point (25, 40)
is an infeasible solution of the problem.

Optimal (feasible) solution. Any point in the feasible region that gives the optimal value (maximum or
minimum) of the objective function is called an optimal solution. Now, we see that every point in the
feasible region OABC satisfies all the constraints as given in (1) to (4), and since there are infinitely
many points, it is not evident how we should go about finding a point that gives a maximum value of the
objective function z = 250x + 75y. To handle this situation, we use the following theorems which are
fundamental in solving linear programming problems.

Theorem 1. Let R be the feasible region (convex polygon) for a linear programming problem and let z =

5
ax + by be the objective function. When ‘z’ has an optimal value (maximum or minimum), where the
variables x and y are subject to constraints described by linear inequalities, this optimal value must
occur at a corner point (vertex) of the feasible region.

Note: A corner point of a feasible region is a point in the region which is the intersection of two boundary lines.
Theorem 2. Let R be the feasible region for a linear programming problem, and let z = ax + by be the
objective function. If R is bounded, then the objective function ‘z’ has both a maximum and a minimum
value on R and each of these occurs at a corner point (vertex) of R.

Note: A feasible region of a system of linear inequalities is said to be bounded if it can be enclosed within a circle.
Otherwise, it is called unbounded. Unbounded means that the feasible region does extend indefinitely in any
direction.

Remark: If R is unbounded, then a maximum or a minimum value of the objective function may not
exist. However, if it exists, it must occur at a corner point of R. (By Theorem 1)

In the above example, the corner points (vertices) of the bounded (feasible) region are: O, A, B and C.
It is easy to find their coordinates as (0, 0), (20, 0), (10, 50) and (0, 60), respectively. Let us now
compute the values of ‘z’ at these points. To compute the value of ‘z’, just substitute the value of the
coordinates to the equation z = 250x + 75y.
Example: At point ‘A’, the coordinates are (20,0). To find the value of ‘z’ at point ‘A’,

The value of ‘z’ in all the vertices are as follows:

We observe that the maximum profit to the dealer results from the investment strategy (10, 50), i.e.
buying 10 tables and 50 chairs.

Lesson Objective 2
Algebraic Approach
Step 1: Use constraints (3) and (4) and convert them into equations.

6
Step 2: Using the equations, find the value of ‘x’ or ‘y’. Let us try to find the value of y first. In order to
find the value of ‘y’, we have to cancel ‘x’. To cancel ‘x’, we have to multiply the whole second equation
by a number that would make the coefficient of ‘x’ equal in both equations. After that, deduct the
second equation from the frist equation.

Tip: To find the number that would make the coefficient of ‘x’ in both equations equal, just divide the coefficient of ‘a’ in the first
equation by the coefficient of ‘x’ in the second equation

Now that ‘x’ has already been cancelled, we can solve for the value of ‘y’

Note: If you want to solve for the value of x first, the same procedure will apply (cancel ‘y’ first). You use can these procedures
to compute for the value of both ‘x’ and ‘y’ and not proceed in step 3.

Step 3: When you already have the value of ‘x’ or ‘y’, substitute the value in either the first or second
equation. Either equation will arrive at the same answer.
In our case, we computed the value of ‘y’ first so let us substitute the value of ‘y’ in the first equation.

Note: If you have computed the value of ‘x’ first, then the same procedures will apply (substitute the value of ‘x’ in the first or
second equation).

7
 2) Activity 3: Skill-building Activities
A store has requested a manufacturer to produce pants and sports jackets.
For materials, the manufacturer has 750 m2 of cotton textile and 1,000 m2 of polyester. Every pair of
pants (1 unit) needs 1 m2 of cotton and 2 m2 of polyester. Every jacket needs 1.5 m2 of cotton and 1 m2
of polyester. The contribution margin per unit of the pants ist ₱50 and the jacket, ₱40. What is the
number of pants and jackets that the manufacturer must give to the stores so that these items obtain a
maximum sale?

Check your answers against the Key to Corrections found at the end of this SAS. Be sure to complete
each activity before looking. Write your score on your paper.

3) Activity 4: What I Know Chart, part 2

Let us see how your knowledge changed by reviewing the questions in the What I Know Chart
from Activity 1. Write your answers to the questions based on what you now know in the third
column of the chart.

4) Activity 5: Check for Understanding

Maria has an online shop where she sells handmade paintings and cards. She sells the painting for
₱50 and the card for ₱20. It takes her 2 hours to complete 1 painting and 45 minutes to make a single
card. She also has a day job and makes paintings and cards in her free time. She cannot spend more
than 15 hours a week to make paintings and cards. Additionally, she should make not more than 10
paintings and cards per week.
She makes a profit of ₱25 on painting and ₱15 on each card.

8
How much profit would she make at the optimum combination of resources?

C. LESSON WRAP-UP
1) Activity 6: Thinking about Learning
Congratulations for finishing this module! Shade the number of this module that you just have finished.

What part of the topic did you find difficult?