Finding solution to systems of linear inequalities is a representation of finding solutions in a Linear Programming

Problem. Let’s have a closer look on how are these two related, and how Linear Programming is used in various
fields.

LINEAR PROGRAMMING
Linear Programming is a technique that uses linear functions to illustrate complex relationships. It is also a
method which aims to find the maximum or minimum choice from among several choices available. Linear
programming is applied in many areas, like, manufacturing, engineering, healthcare, agriculture, airlines and other
businesses. Example, if a company produces several different products from the same materials, the company can
use Linear Programming to determine how much of each product should be produced to maximize its profit or
minimize the product cost.

Solving Linear Programming Problems or LP Problems

All Linear Programming problems have four properties in common:
1. LP problems seek to maximize or minimize some quantity (usually profit or cost). We refer to this as
the objective function of an LP problem. Typically, the objective is to maximize profits and minimize
cost in the long run.
2. There must be alternative courses of action to choose from or the decision variables.
3. The presence of restrictions or constraints limits the mark to which we can pursue our objective, and
the non-negativity constraints which means the values for decision variables should be greater than
or equal to 0.
4. The objective and constraints in LP problems must be expressed in terms of linear equations or
inequality.
Below are some steps in solving Linear Programming Problems by graphical method.
1. State the objective function.
2. Write all the constraints.
3. Graph the constraints.
4. Shade the feasible region.
5. Find the corner points.
6. Solve for the objective function at each corner point.
7. Determine the corner point that gives the minimum or maximum value, and come up with a decision.

Remember:
 Feasible region is the solution set of the collection of constraints
 The maximum or minimum value is always located at the vertex or corner points of the feasible
region.
 Maximum means “at most”, “up to” or the symbol ≤
 Minimum means “at least”, “not lower than” or the symbol ≥

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 1
 Examples. Solve the following LP problems using graphical method.
1. A retail store stocks two types of customized bags, tote bags & duffel bags. The store can sell a
maximum of 400 tote bags and a maximum of 300 duffel bags per week. However, the retail store can
only store up to 600 bags of both types because of limited storage capacity. The store earns a profit of
Php30 per tote bag and a profit of Php50 per duffel bag. How many of each type of bags should the
store keep to maximize its profit?

 First, we can summarize the details of the problem using a table:

Product Max. no. of bags/week Profit
Tote bag (x) 400 Php30
Duffel bag (y) 300 Php50
Storage -
600
Capacity

 Second is to represent the variables (decision variables, objective function, constraints).

Let: x = tote bag y = duffel bag
Objective function: Maximize profit (Z) or Z = 30x + 50y
Constraints: 𝑥 ≤ 400 Subject to the no. of x bags per week. The word
Subject to the no. of y bags per week. The word 𝑦 ≤ 300 used is “maximum”, therefore we use the symbol ≤.
used is “maximum”, therefore we use the symbol ≤.
𝑥 + 𝑦 ≤ 600
Subject to the storage capacity for the types of bag.
Since we’re dealing about real life objects, there will be no 𝑥 ≥ 0 𝑎𝑛𝑑 𝑦 ≥ 0 The word used is “up to”, so we use the symbol ≤
negative values, thus we have these non-negative constraints.

 Third is to graph the constraints.

We begin by finding points that satisfy the constraint lines. Finding the coordinates were
For constraint 1 𝑥 ≤ 400, we have the coordinates (400, 0) already discussed on the first
part of this module
constraint 2 𝑦 ≤ 300, we have (0, 300)
constraint 3 𝑥 + 𝑦 ≤ 600 we have (0, 600) & (600, 0)
x y
0 600
600 0
Now we are ready to graph the constraints.

Since there are no negatives, we

will just focus on the 1st
quadrant of the plane.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 2
  Fourth, is to shade the feasible region and find the corner points.

 The corner points (0, 300) and (400, 0) of

the feasible region, based from the graph
earlier, were already given.
 The corner point (300, 300) is the
intersection of constraints 2 &3. Solve for
x & y of the two constraints, to find the
coordinates of their intersection.
y = 300 Again, we will solve them as an
x + y = 600 equation. Since y = 300, we can
x + 300 = 600 already substitute that to the value
of y in x +y = 600. Hence, the
x = 600 - 300
coordinates (300, 300)
x = 300
Again, use the tes t point (0, 0) to determine the feasible region for each line. The region
 The corner point (400, 200) is the
which is common among these inequalities together with the boundary lines will be the
solution or the feasible region.
intersection of constraints 1 and 3
Hence, the solution set is the region bounded by the vertices x = 400 Since x = 400, we can already
(0, 300), (300, 300), (400, 200), and (400, 0) x + y = 600 substitute that to the value of x
400 + y = 600 in x +y = 600. Hence, the
y = 600 - 400 coordinates (400, 200)
y = 200

 Fifth, is to solve for the objective function at each corner point.

Construct a table of values and solve for the profit.

Vertices
Z = 30x + 50y Just substitute the values of x & y of
(x, y) the vertices to the objective function.
(0, 300) Z = 30(0) + 50(300) = 15 000
(300, 300) Z = 30(300) + 50(300) = 24 000
(400, 200) Z = 30(400) + 50(200) = 22 000
(400, 0) Z = 30(400) + 50(0) = 12 000

 Sixth is to determine the corner point that gives the maximum value and come up with a
decision.
Based on the computations above, the x & y values that yield the maximum profit is
at (300, 300).
Hence, the maximum profit will be obtained if the retail store will keep 300 duffel
bags and 300 tote bags per week.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 3
 2. An airline offers economy and first class tickets. For the airline to be profitable, it must sell a minimum
of 25 first class tickets and a minimum of 40 economy tickets. The company makes a profit of $225
for each economy ticket, and $200 for each first class tickets. At most, the plane has a capacity of 150
travelers. How many of each ticket should be sold in order to maximize profits?

 First, we can summarize the details of the problem using a table:

Product Min. no. of tickets Profit
Economy (x) 40 225
First class (y) 25 200
Plane -
150
Capacity

 Second is to represent the variables (decision variables, objective function, constraints).

Let: x = economy y = first class
These are the decision variables
Objective function: Maximize profit (Z) or Z = 225x + 200y
Constraints: 𝑥 ≥ 40 Subject to the no. of x economy tickets. The word
Subject to the no. of y first class tickets. The word 𝑦 ≥ 25 used is “minimum”, therefore we use the symbol ≥.
used is “minimum”, therefore we use the symbol ≥. 𝑥 + 𝑦 ≤ 150
Subject to the airplane capacity. The word
𝑥 ≥ 0 𝑎𝑛𝑑 𝑦 ≥ 0
Non-negative constraints. used is “at most”, so we use the symbol ≤

 Third is to graph the constraints.

We begin by finding points that satisfy the constraint lines.

For constraint 1 𝑥 ≥ 40, we have the coordinates (40, 0)
constraint 2 𝑦 ≥ 25, we have (0, 25)
constraint 3 𝑥 + 𝑦 ≤ 150 we have (0, 150) & (150, 0)
x + y ≤ 150
x y
0 150
150 0

Now we are ready to graph the constraints.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 4
  Fourth, is to shade the feasible region and find the corner points.

 We have vertices A, B, and C.

 To find vertex A use constraints 1 & 2
x = 40 and y = 25, the coordinates of
vertex A are (40, 25)
 To find vertex B, use constraints 1 & 3
x = 40 and x + y = 150
40 + y = 150
y = 110
The coordinates of vertex B are (40, 110)
constraint 2
 To find vertex C, use constraints 2 & 3
y = 25 and x + y = 150
x + 25 = 150
y = 125
The coordinates of vertex C are (125, 25)
Hence, the solution set is the region bounded by the vertices
(40, 25), (40, 110), and (125, 25)

 Fifth, is to solve for the objective function at each corner point.

Construct a table of values and solve for the profit.

Vertices
Z = 225x + 200y
(x, y)
(40, 25) Z = 225(40) + 200(25) = 14 000
(40, 110) Z = 225(40) + 200(110) = 31 000
(125, 25) Z = 225(125) + 200(25) = 33 125

 Sixth is to determine the corner point that gives the maximum value and come up with a
decision.
Based on the computations above, the x & y values that yield the maximum profit is
at (125, 25).
Therefore, the airline should sell 125 economy tickets and 25 first class tickets in
order to maximize profits.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 5
 3. A dietician wishes to mix two types of foods (Food I & Food II) in such a way that vitamin contents
of the mixture contain at least 8 units of Vitamin A, and 10 units of Vitamin C. Food I contains
2units/kg of Vitamin A and 1unit/kg of Vitamin C. Food II contains 1unit/kg of Vitamin A and
2units/kg of Vitamin C. It costs Php50 per kg to purchase Food I and Php70 per kg to purchase Food
II. How many units of each type should be mixed to minimize cost?

 First, we can summarize the details of the problem using a table:

Resources Vitamin A/kg Vitamin C/kg Cost (Php/kg)
Food I (x) 2 1 50
Food II (y) 1 2 70
Required -
8 10
vitamin content

 Second is to represent the variables (decision variables, objective function, constraints).

Let: x = Food I y = Food II
Objective function: Minimize cost Z = 50x + 70y
Constraints: 2𝑥 + 𝑦 ≥ 8 Subject to the required amount of Vitamin A for Food I and Food
Subject to the required amount of Vitamin C for Food I and 𝑥 + 2𝑦 ≥ 10 II. The word used is “at least”, therefore we use the symbol ≥.
Food II. The word used is “at least”, therefore we use the 𝑥 ≥ 0 𝑎𝑛𝑑 𝑦 ≥ 0
symbol ≥. Non-negative constraints.

 Third is to graph the constraints.

We begin by finding points that satisfy the constraint lines.

For constraint 1 2𝑥 + 𝑦 ≥ 8, we have the coordinates (0, 8) and (4, 0)
2x + y ≥ 8
x y
0 8
4 0

constraint 2 𝑥 + 2𝑦 ≥ 10 we have (0, 5) & (10, 0)

x + 2y ≥ 10
x y
0 5
10 0

Now we are ready to graph the constraints.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 6
  Fourth, is to shade the feasible region and find the corner points.

 Observe that the feasible region is

unbounded, meaning, the shaded region is
not a closed figure.
 Vertex A has coordinates (0, 8)
 Vertex B has coordinates (10, 0)
 To find vertex C, use constraints 1 & 2
2x + y = 8
x + 2y = 10
Solve x in terms of y
y = 8 – 2x
x + 2(8 – 2x) = 10 Substitute y of the second constraint
x + 16 – 4x = 10 with 8 – 2x, then solve for x.
-3x = -6
Hence, the solution set is the unbounded region with vertices x=2
Now going back to this equation, we can
(0, 8), (10, 0), and (2, 4) y = 8 – 2x now solve for the value of y. By
substituting x with 2, y will be equal to 4.
y = 8 – 2(2)
y =4
The coordinates of vertex C are (2, 2).

 Fifth, is to solve for the objective function at each corner point.

Construct a table of values and solve for the profit.

Vertices
Z = 50x + 70y
(x, y)
(0, 8) Z = 50(0) + 70(8) = 560
(10, 0) Z = 50(10) + 70(0) = 500
(2, 4) Z = 50(2) + 70(4) = 380

 Sixth is to determine the corner point that gives the minimum value and come up with a
decision.
Based on the computations above, the x & y values that gives the minimum value is
at (2, 4).
Therefore, the dietician should mix 2kg of Food I and 4kg of Food II to attain the
minimum cost which is Php380.

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 7
 REFERENCES
Romeo M. Daligdig, EdD (2019). Mathematics in the Modern World. Introduction to Linear Programming.

Lorimar Publishing,Inc.

Earnhart, R T., and Adina E M. (2018). Mathematics in the Modern World. Introduction to Linear

Programming. C & E Publishing,Inc.

Medallon M, Calubaquib (2018). Mathematics in the Modern World. Introduction to Linear Programming.

Mindshapers Co., Inc. 15, 27 - 32

(nd). Inequalities and Linear programming. From https://www.courses.lumenlearning.com/sanjacinto-

finitemath1/chapter/reading-meeting-demands-with-linear-prgramming

THIS MODULE IS FOR THE EXCLUSIVE USE OF THE UNIVERSITY OF LA SALETTE, INC. ANY FORM OF REPRODUCTION, DISTRIBUTION, UPLOADING,
OR POSTING ONLINE IN ANY FORM OR BY ANY MEANS WITHOUT THE WRITTEN PERMISSION OF THE UNIVERSITY IS STRICTLY PROHIBITED. 8