Binalonan, Pangasinan

Linear Programming- Graphical Method

Course Title: Management Science

Course Code: ACC4

Name:_____________________________________________________________________

Course and Year:_____________________________________________________________

Date and Time Allotment:______________________________________________________

Introduction:

To the Learners,

Welcome to Module 2!

This learning material is composed of learning objectives, activities, and assessment.

Those parts are based on the course syllabus of said subject.

Hoping you will enjoy reading and answering the different ways of questioning here.

Goodluck and God bless!

I. Objectives:

In this module the learners shall be able to:

1. Formulate the objective function and the explicit constraints of the problem.
2. Determine the feasible solutions area utilizing the graphical methods of solving linear
programming problems; and
3. Formulate the decisions of linear programming problems if an optimal solution is reached.

II. Lecture and Discussions of the Lesson/s

Mathematical formulation of a linear programming problem

Mathematical formulation of a linear programming problem:

The procedure for mathematical formulation of a linear programming problem consists of

the following steps.

(i) Identify the decision variables.

(ii) Identify the objective function to be maximized or minimized and express it as a linear
function of decision variables.

(iii) Identify the set of constraint conditions and express them as linear inequalities or equations
in terms of the decision variables.

Example 1

A furniture dealer deals only two items viz., tables and chairs. He has to invest
Rs.10,000/- and a space to store atmost 60 pieces. A table cost him Rs.500/– and a chair
Rs.200/–. He can sell all the items that he buys. He is getting a profit of Rs.50 per table and
Rs.15 per chair. Formulate this problem as an LPP, so as to maximize the profit.

Solution:

(i) Variables: Let x1 and x2 denote the number of tables and chairs respectively.

(i) Objective function:

Profit on x1 tables = 50 x1

Profit on x2 chairs = 15 x2

Total profit = 50 x1+15x2

1
Let Z = 50 x1+15 x2, which is the objective function.

Since the total profit is to be maximized, we have to maximize Z=50x1+15x2

(iii) Constraints:

The dealer has a space to store atmost 60 pieces

x1+x2 ≤ 60

The cost of x1 tables = Rs.500 x1

The cost of x2 tables = Rs. 200 x2

Total cost = 500 x1 + 200 x2 ,which cannot be more than 10000

500 x1 + 200 x2 ≤ 10000

5x1+ 2x2 ≤ 100

(iv) Non-negative restrictions: Since the number of tables and chairs cannot be negative, we
have x1 ≥0, x2 ≥0

Thus, the mathematical formulation of the LPP is

Maximize Z=50 x1+15x2

Subject to the constrains

x1+x2 ≤60

5x1+2x2≤100

x1, x2≥0

Example 2

A company is producing three products P1, P2 and P3, with profit contribution of Rs.20,
Rs.25 and Rs.15 per unit respectively. The resource requirements per unit of each of the products
and total availability are given below.

2
Formulate the above as a linear programming model.

Solution:

(i) Variables: Let x1, x2 and x3 be the number of units of products P1, P2 and P3 to be produced.

(ii) Objective function: Profit on x1 units of the product P1 = 20 x1

Profit on x2 units of the product P2 = 25 x2

Profit on x3 units of the product P3 = 15 x3

Total profit = 20 x1 +25 x2 +15 x3

Since the total profit is to be maximized, we have to maximize Z= 20 x1+25 x2 +15 x3

Constraints:

6x1 +3 x2 +12 x3 ≤ 200

2 x1 +5 x2 +4 x3 ≤ 350

x1 +2 x2 + x3 ≤ 100

Non-negative restrictions: Since the number of units of the products A,B and C cannot be
negative, we have x1, x2, x3 ≥ 0

Thus, we have the following linear programming model.

Maximize Z = 20 x1 +25 x2 +15 x3

Subject to

6 x1 +3 x2 +12 x3≤ 200

2x1+5x2 +4 x3 ≤ 350

x1+2 x2 + x3≤ 100

x1, x2, x3 ≥ 0

Example 3

A dietician wishes to mix two types of food F 1 and F2 in such a way that the vitamin
contents of the mixture contains atleast 6units of vitamin A and 9 units of vitamin B. Food
F1 costs Rs.50 per kg and F2 costs Rs 70 per kg. Food F1 contains 4 units per kg of vitamin A and

3
6 units per kg of vitamin B while food F2 contains 5 units per kg of vitamin A and 3 units per kg
of vitamin B. Formulate the above problem as a linear programming problem to minimize the
cost of mixture.

Solution:

(i) Variables: Let the mixture contains x1 kg of food F1 and x2 kg of food F2

(ii) Objective function:

cost of x1 kg of food F1 = 50 x1

cost of x2 kg of food F2 = 70x2

The cost is to be minimized

Therefore minimize Z= 50 x1+70x2

(iii) Constraints:

We make the following table from the given data:

Resources F1 (X1) F2 (X2) Requirement

Vitamin A (units/kg) 4 5 6

Vitamin B (units/kg) 6 3 9

Cost (Rs/kg) 50 70

4x1+5x2 ≥6 (since the mixture contains ‘atleast 6’ units of vitamin A,we have the inequality of
the type ≥ )

6x1+3x2 ≥9(since the mixture contains ‘atleast 9’ units of vitamin B ,we have the inequality of
the type ≥ )

(iv) Non-negative restrictions:

Since the number of kgs of vitamin A and vitamin B are non-negative, we have x1, x2 ≥0

Thus, we have the following linear programming model

Minimize Z = 50 x1 +70x2

4
subject to 4 x1+5x2 ≥6

6 x1+3x2 ≥9

and x1, x2≥0

Example 4

A soft drink company has two bottling plants C1 and C2. Each plant produces three
different soft drinks S1, S2 and S3. The production of two plants in number of bottles per day are:

A market survey indicates that during the month of April there will be a demand for
24000 bottles of S1, 16000 bottles of S2 and 48000 bottles of S3. The operating costs, per day, of
running plants C1 and C2 are respectively Rs.600 and Rs.400. How many days should the firm
run each plant in April so that the production cost is minimized while still meeting the market
demand? Formulate the above as a linear programming model.

Solution:

(i) Variables: Let x1 be the number of days required to run plant C 1 and x2 be the number of days
required to run plant C2

Objective function: Minimize Z = 600 x1 + 400 x2

(ii) Constraints: 3000 x1 + 1000 x2 ≥ 24000(since there is a demand of 24000 bottles of drink A,
production should not be less than 24000)

1000x1 + 1000 x2 ≥ 16000

2000x1+ 6000 x2 ≥ 48000

(iii) Non-negative restrictions: Since be the number of days required of a firm are non-
negative, we have x1, x2 ≥0

Thus we have the following LP model.

Minimize Z = 600 x1 + 400 x2

5
subject to 3000 x1 + 1000 x2 ≥ 24000

1000 x1 + 1000 x2 ≥ 16000

2000 x1 + 6000 x2 ≥ 48000

and x1, x2 ≥0

Linear Programming Problems - Graphical Method

Graphical Method of Solving Linear Programming Problems
We already know how to plot the graph of any linear equation in two variables. The
process involves plotting the points that satisfy the equation on the coordinate axis and joining
them. In the problems involving linear programming, we know that we have more than one
simultaneous linear equation, based on the conditions given and then we try to find the range of
solutions based on the given conditions. In this article, we will try finding the solutions of Linear
Programming Problems using graphical method.
Let us try to understand this approach using an example.
The Linear Programming Problem is to maximize the profit function Z = 40x + 15y,
subject to constraints,
x + 2y is less than or equal to 100
x + 2y is less than or equal to 70
x is greater than or equal to 0, y

Step-1: In the above equations, we can see that x is greater than or equal to 0 and y is greater
than or equal to 0, hence we will be focusing only on 1st quadrant.
Step-2: Let us plot the linear equations x + 2y = 100 by plotting two points (0,50) and (100,0) &
x + y = 70 by plotting the points (70,0) and (0,70).

6
Once you plot the graph with all the given constraints, aim is to identify the Feasible
Region. Feasible region is the common region which is determined by all the given constraints in
the linear programming problem. In the above problem, feasible region is shown as below:

Each and every point lying in the feasible region is the feasible choice and will satisfy all
the given conditions. Any point lying outside the given feasible region is an infeasible solution
and will not satisfy all the conditions simultaneously.

After potting the above graphs, we know the range of x and y that will satisfy all the
given conditions. The graphical solution can also be used to find the optimal solution of the
above problem. Any point in the feasible region that gives the maximum or minimum value of
the objective function is called an optimal solution. In the feasible region, we can see that there
are infinitely many points that satisfy the given constraints simultaneously. But how will we get
the maximum or minimum value of the objective function Z = 40x + 15y?
In order to find the optimal solution, we follow the below-given theorems:
Theorem 1: Let R be the feasible region for a linear programming problem and let Z = Ax
+ By be the objective function. Then the optimal value (maximum or minimum) of Z will occur
at a corner point (vertex) of the feasible region, provided that the optimal value of Z exists and
where the variables x and y are subject to constraints described by linear inequalities.
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 Z has both a maximum and a minimum
value on R and each of these occurs at a corner point (vertex) of R.
If R is unbounded then the maximum and minimum value of Z may not exist, but if it
exists, then it will occur at the corner point of region R.
In the above linear programming problem, the corner points are (0,0), (70,0), (40,30), and
(0,50)
Substituting the above values in the objective function Z= 40x + 15y we get,
Z= 0 for (0,0)
Z= 2800 for (70,0)

7
Z= 2050 for (40,30)
Z= 750 for (0,50)
Hence the maximum value of Z occurs at (70,0) and minimum value of Z occurs at (0,0).

8
III. Application/Activity

Problem Number 1
The Linear Programming Problem is to maximize the profit function Z = 50x + 80y, subject to
constraints,
2x + 2y is less than or equal to 90
2x + 2y is less than or equal to 80
x is greater than or equal to 0, y

Instruction: Create a graph out of above equation and find the maximum and minimum values of
Z.

Problem Number 2
A furniture dealer deals only two items viz., tables and chairs. He has to invest P 10,000
and a space to store atmost 80 pieces. A table cost him P 400 and a chair P500. He can sell all
the items that he buys. He is getting a profit of P150 per table and P100 per chair. Formulate this
problem as an LPP, so as to maximize the profit.

9
IV. Assessment

The Linear Programming Problem is to maximize the profit function Z = 80x + 30y, subject to
constraints,
2x + 2y is less than or equal to 100
2x + 2y is less than or equal to 70
x is greater than or equal to 0, y

Instruction: Create a graph out of above equation and find the maximum and minimum values of
Z.

Problem Number 2
A furniture dealer deals only two items viz., tables and chairs. He has to invest P 20,000
and a space to store atmost 80 pieces. A table cost him P 600 and a chair P300. He can sell all
the items that he buys. He is getting a profit of P50 per table and P15 per chair. Formulate this
problem as an LPP, so as to maximize the profit.

10
V. References

Graphical Method of Solving Linear Programming Problems (byjus.com)

Mathematical formulation of a linear programming problem - Linear programming problem

(brainkart.com)

Prepared by:

LEONIDES L. GAVINA, DBA, CPA

Subject Teacher

Checked by:

BONIFACIO V. TARAPE, MBA, CPA

Program Head, CBE

11