FINANCIAL

MATHEMATICS

U2

LINEAR
PROGRAMMING

prepared by

Bibhya N an d Sh ar m a, Ja i R a j, Ro b in
H a vea , T o kau a T e kab u
Unit 2: Linear Programming 2.2
Study Organiser
Before you begin this unit, please check through your study organiser. It shows
the topics that we will be covering, the skills you need to acquire (the outcomes)
and the activities you will do to help you acquire these skills.
Topic Learning outcomes Activities
2.1 Systems of linear  Explain the systems of linear Activity 2.1
inequalities inequalities
2.2 Linear programming  Solve linear programming problems Activity 2.2
problems
2.3 Steps for solving a  Discuss the steps for solving a
linear programming linear programming problem
problem

You are expected to spend 12 hours on this unit.

Unit 2: Linear Programming 2.3

Introduction
In this unit, we study systems of linear inequalities and develop the problem to
Linear Programming. In an inequality, the equal (=) sign is replaced by an
inequality, “greater than” (>), “less than” (<), “greater than or equal to” () or
“less than or equal to” () sign.

A linear inequality is both a line graph and a region above or below the line. In
linear programming, we have a system of linear inequalities as constraints, and
the goal is to maximise or minimise a given linear equation, by having an
Objective function. If the relationships between the various products, resources,
production requirements, costs, and profits are all linear, then these activities may
be programmed in the best optimal way by using linear programming. In this
course, we are concerned with linear programming problems that involve only
two variables. We solve these problems using a geometric approach.

2.1 Systems of linear inequalities

This section covers sketching graphs of linear inequalities. To graph linear
inequalities, is same as graphing linear equations.

Graphing a Linear Inequality

Step 1: Graph the corresponding linear equation. If inequality is < or >,
then graph, using dashes otherwise use a solid line.

Step 2: Select a test point not on the line.

Step 3: Substitute the test point into the given inequality. If it satisfies,
then all points on the side of the test point will satisfy the
inequality. If not then all points on the opposite side will satisfy
the inequality.
Example 2.1

Graph the inequality 2x + 4y  6.

Solution
Step 1:Draw the line 2x + 4y = 6. The points on this line satisfy 2x + 4y  6
because of the inequality “greater than or equal to” ().
To draw the line, find the x and y-intercepts.
3
That is, to find the y-intercept, let x = 0, then y = ; and to find the
2
x- intercept, let y = 0, then x = 3. Plot the points, and join them with a
straight line.

Unit 2: Linear Programming 2.4

 y

2

1
 x
0 1 2 3
2x + 4y = 6

Step 2: Decide whether to shade above the line or below the line. To do this,
select a test point, for example, (0, 0). Now substitute these values
into the inequality. If the inequality is satisfied, then the shaded
region is on the same side as the test point. If the inequality is not
satisfied, then the shaded region is on the other side of the test point.

Step 3: Take the x and y values of the test point and substitute them into the
inequality.

2x + 4y  6
2 (0) + 4(0)  6
0  6.

This is false, since 0 is not greater than or equal to 6. The inequality is

not satisfied. Hence, the region to shade is on the other side of the test
point.

y
2x + 4y  6
2

1
 x
Test point (0, 0) 1 2 3

Note: For  and , the line is part of the graph, so draw a solid line. For > and <,
the line is not part of the graph, so use a dashed line.

Unit 2: Linear Programming 2.5

Example 2.2
Graph the inequality 2x – y > – 4

Solution
Step 1: Graph 2x – y = – 4, using a dashed line. To draw the line, find the
x and y- intercepts. That is, to find the y- intercept, let x = 0, then y
= 4 ; and to find the x- intercept, let y = 0, then x = 2 . Plot the
points, and join them with a straight line.
y
2x – y = – 4

 (0, 4)

 x
0
(-2, 0)

Step 2: Test point, for example (0, 0). Note that the test point could be
any point in the x-y plane, and not necessarily (0, 0).

Step 3: Take the x and y values of the test point and substitute them into
the inequality.
2x – y > – 4
2(0) – (0) > – 4
This is true as 0 > – 4.
Since the test point is satisfied, the shaded region should be on the same side
as the test point.
y

2x – y > –4

(0, 0) x
Test point

Unit 2: Linear Programming 2.6

Example 2.3
Graph the system

2x – 3y  2
x + 4y  6
Solution

Step 1: Graph the 2 equations, with solid lines. To draw the line, find the x
and y- intercepts. That is, to find the y- intercept, let x = 0; and to find
the x - intercept, let y = 0, then x = 2 .

2x – 3y = 2 and x + 4y = 6
2 3
The points are (0,  ), (1,0) and (0, ), (6, 0), respectively.
3 2

2x – 3y = 2

3
(0, )
 2

  x
2  (1, 0) (6, 0)
(0,  ) x + 4y = 6
3

Step 2: Choose 1 test point and for each inequality, decide which side of the
line to shade. For example (0, 0)

2x – 3y  2
2(0) – 3(0)  2
0  2 false

Hence the shaded region is on the opposite side of the test point.

x + 4y  6
0 + 4(0)  6
0  6 true
Hence the shaded region is on the same side as the test point.

Unit 2: Linear Programming 2.7

 y 2x – 3y  2

x + 4y  6

 x
(0,
0)

Step 3: The solution of the system of linear inequalities is the region that
is common to both inequalities. Hence,
y

2x – 3y = 2
x + 4y = 6

 3
 0, 2

  x
0, 23   (1,0) (6,0)
Common region

If you draw each inequality using a different colour, it will be easier for you to
identify the common region.

Activity 2.1

Spend at least 20 – 30 minutes on this activity.

Graph
3x  y  6
3x  y  3
.

Unit 2: Linear Programming 2.8

2.2 Linear programming problems
A linear programming problem in two variables, x and y, consist of optimising an
objective function
z  Ax  By
where A and B are given real numbers, not both zero, subject to certain conditions
or constraints expressible as a system of linear inequalities in x and y.

In Example 3 above, we solved two inequalities graphically and came up with the
solution which was the region common to both. The region that is common to a
system of linear inequalities is called the feasible region. In linear
programming, we have an objective function that needs to be maximised or
minimised subject to the restrictions or constraints imposed by the inequalities.
In other words, the feasible region is the region where the constraints are met. Is
there a point in the feasible region that maximises or minimises the objective
function?

2.3 Steps for solving a linear

programming problem

Step 1: State the Objective function.

Step 2: Determine all the constraints and graph the set of feasible points.
Step 3: List the corner points of the feasible region.
Step 4: Determine the value of the objective function at each corner point.
Step 5: Select the max or min value of the objective function.

Note: If the solution exists it has to be at a corner point.

Example 2.4
Maximise and minimise the objective function z = 2x + 3y subject to the
following constraints:

x + 2y  1
x + 2y  10
x+ y  2
x+ y  8
x  0
y  0

Unit 2: Linear Programming 2.9

Solution

Graph each inequality in a different shade and then find the common region or
the set of feasible points. All lines are solid lines (, ).

x+y=8

x + 2y = 10  (0, 8)

 (0, 5) Feasible region

x+y=2

x + 2y = 1
(0, 2) 


   
1
(0, ) (1, 0) (2, 0) (8, 0)
2 (10, 0)

There are five corner points bounding the feasible region: (0, 2), (2, 0), (8, 0),
point of intersection of lines x + y = 8 and x + 2y = 10, and (0, 5).

Point of intersection of lines

x + 2y = 10
x+y = 8
Eliminating x, we have y = 2. If we back-substitute y into the second equation,
we have
y = 8–x
= 8–2
= 6

Therefore, the point of intersection is (6, 2).

Unit 2: Linear Programming 2.10

Now let us evaluate the objective function at each of the corner points.

Corner points Objective function

(x, y) z = 2x + 3y

(0, 2) z = 2(0) + 3(2) = 6

(2, 0) z = 2(2) + 3(0) = 4
(8, 0) z = 2(8) + 3(0) = 16
(6, 2) z = 2(6) + 3(2) = 18
(0, 5) z = 2(0) + 3(5) = 15

Therefore, z has a minimum value of 4 at (2, 0), and a maximum of 18 at (6, 2).

Example 2.5
Find the maximum and minimum value of z  7 x  6 y , subject to the
conditions

2 x  4 y  4
 2 x  3 y  12


 x0

 y0

Solution
We first sketch the graph of the constraints.

4

2

| | |
2 4 6 x

Unit 2: Linear Programming 2.11

The corner points of the set of feasible points are: 1, 0  ,  0, 2  ,  0, 4  ,  6, 0  .

Corner Points Value of Objective function

 x, y  z  7x  6 y

1, 0  z7

 0, 2  z  12

 0, 4  z  24

 6, 0  z  42

Maximum value of z is 42 when x = 6 and y = 0 and the minimum value of z is 7

when x = 1 and y = 0.

Example 2.6
Paradise Handicrafts produces two different types of handicrafts, Tanoa and Bilo,
each requiring the raw materials m1 and m2. At least 18 kilograms of m1 and 12
kilograms of m2 must be used daily. Also, at most 34 hours of labour are to be
utilised. Two kilograms of m1 are needed for each Tanoa, and 1 kilogram of m1
for each Bilo. For each Tanoa and Bilo, 1 kilogram of m2 is required. It takes 3
hours to manufacture a Tanoa and 2 hours to manufacture a Bilo. The profit is $5
for each Tanoa and $3 for each Bilo. How many of each type of handicraft should
be produced daily to maximise the profit?

Without seeing the solution below, read the question several times, define the
variables and write down the objective function and the constraints. Then, check
them against the solution. If not correct, try again. This way, you will learn to
translate a linear programming problem in words into a mathematical equation
and inequalities. Once the word problem is translated into the objective function
and the linear inequalities, the most difficult step is overcome. The rest of the
problem solving is the standard procedure:
 graph the inequalities;

 find the common shaded region;

 find the corner points;

 evaluate the objective function at the corner points; and

 find the point at which profit is maximum.

Unit 2: Linear Programming 2.12

Solution
Let x = the number of Tanoa produced
y = the number of Bilo produced
Note: In any word problem, your variables have to be defined.

Step 1: Maximise the profit P = 5x + 3y subject to the constraints:

x  0 The number of Tanoa cannot be negative.

y  0 The number of Bilo cannot be negative
2x + y  18 Constraint for material m1
x + y  12 Constraint for material m2
3x + 2y  34 Constraint for labour

Notice that “at least” has been translated into “” and “at most” has been
translated into “.

Step 2: Graph the constraints, in different shades, and clearly indicate the
feasible region. The graph below is the final stage, showing only
the feasible region.
y
2x + y = 18
3x + 2y = 34

x + y = 12 20

16 A
12

8
4 B 
C
  
0 2 4 6 8 1 12 x
0

Unit 2: Linear Programming 2.13

Step 3: Solve the set of simultaneous equations to find the three points of
intersection:

A: Point of intersection of 2x + y = 18 and 3x + 2y = 34

Solve and confirm: A = (2, 14)
B: Point of intersection of 2x + y = 18 and x + y = 12
Do this for yourself: B = (6, 6)
C: Point of intersection of x + y = 12 and 3x + 2y = 34
Check: C = (10, 2)
Step 4: Evaluate the profit at the corner points:

Corner Points Value of Objective function

 x, y  P  5x  3y
(2, 14) $52
(6, 6) $48
(10, 2) $56

Step 5: The maximum profit is $56 and is realised when 10 units of model
X and 2 units of model Y are produced.

Activity 2.2

Spend at least 20 – 30 minutes on this activity.

Quality Carpet Manufacturers has available 1200 square meters of wool and
1000 square meters of nylon for the manufacturing of two grades of carpets:
high-grade, which sells for $500 per roll, and low-grade, which sells for $300 per
roll. 20 square meters of wool and 40 square meters of nylon are used in a roll of
high-grade carpet, and 40 square meters of nylon are used in a roll of low-grade
carpet. 40 work hours are required to manufacture each roll of high-grade carpet
and 20 work hours are required for each roll of low-grade carpet. A maximum of
800 work hours are available. How many rolls of each type of carpet should be
manufactured to maximise the revenue?

Example 2.7
A toy company in Fiji manufacturers two sizes of trucks – small and large. In the
manufacturing process, each small truck requires 1 hour of grinding and 1 hour of
finishing, while each large truck requires 1 hour of grinding and 2 hours of
finishing. The company’s grinder works at most 80 hours per week and the
finisher works at most 100 hours per week. The company needs to manufacture at
least 30 small toy trucks. If the profit on each small truck is $20 and on each

Unit 2: Linear Programming 2.14

large truck is $25, how many of each truck should be manufactured to maximise
the profit? What is the maximum profit?

Solution
Let x = no of units of small trucks manufactured

y = no of units of large trucks manufactured

The quantity to be maximised, the profit, which we shall denote by P, is

P  20 x  25 y

The constraints specified by the problem are:

x  y  80
x  2 y  100
x  30
y0

80

50
x
 60, 20 

x
30 80 100
x x x
The corner points of the set of feasible points are:
 30, 0  ,  30,35 ,  60, 20  , 80, 0  .
Value of Objective function
Corner Points
P  20 x  25 y
 x, y 
 30, 0  P  $600

 30,35 P  $1475

 60, 20  P  $1700

80, 0  P  $1600

Maximum profit obtained by producing 60 units of small truck and 20 units of

large truck.

Unit 2: Linear Programming 2.15

 Tutorial

Spend at least 30 – 45 minutes on this activity.

1. There are two chemical plants at the South Pacific Fertilizer Company that
produces three types of fertiliser, low phosphorous (LP), a medium
phosphorous (MP), and high phosphorous (HP). At each plant, the fertiliser is
produced in a single production run, so the three types are produced in fixed
proportions. The first plant produces 1 ton of LP, 2 tons of MP, and 3 tons of
HP in a single operation, and it charges $600 for what is produced in one
operation, whereas one operation of the second plant produces 1 ton of LP, 5
tons of MP, and 1 ton of HP, and it charges $1000 for what it produces in one
operation. If a customer needs 100 tons of LP, 260 tons of MP, and 180 tons
of HP, how many production runs should be ordered from each plant to
minimise costs?

2. Teri’s farm in Labasa has 6000 acres available to plant with corn and beans.
3
Each acre of corn requires 9 bags of fertiliser and hour of labour to
4
harvest. Each acre of bean requires 3 bags of fertilizer and 1 hour of labour to
harvest. Teri’s farm has available at most 40,500 bags of fertiliser and at most
5250 hours of labour for harvesting. If the profits per acre are $60 for corn
and $40 for beans, how many acres of each crop should the Teri’s farm plant
in order to maximise his profit? What is the maximum profit?

3. A manufacturing company produces two types of suitcases: standard and

economy. The company can produce at most 100 pieces of suitcases per day.
Each standard piece of suitcase requires 8 m of material and each economy
piece requires 5 m of material. A maximum of 560 m of material is available.
Each standard piece of suitcase requires 2 hours of labour and each economy
piece requires 3 hours of labour. The manufacturer wishes to utilise at least
210 hours of labour. If the profit is $20 per standard piece of suitcase and $25
per economy piece, how many of each type of suitcase should be produced to
maximise profit?

Unit 2: Linear Programming 2.16

 Tutorial Solution

1. Let x represent the number of operations requested from the first plant and
y represent the number of operations requested from the second plant. Then
to minimise cost C  600 x  1000 y

First Plant Second plant Requirements

Units of LP 1 1 100
Units of MP 2 5 260
3 1 180
Units of HP

The constraints specified by the problem are:

x y  100
2 x  5 y  260
3 x  y  180
x0
y0
y
feasible region

180

100

50

60 100 130 x

The corner points of the set of feasible points are:

 0,180  ,  40, 60  , 80, 20  , 130,0  .
Evaluating C at each corner points, we obtain

Unit 2: Linear Programming 2.17

 ( x, y) C  600 x  1000 y
(0,180) C  180,000
(40,60) C  84,000
(80,20) C  68,000
(130,0) C  78,000

Thus, by placing orders requiring 80 production runs from the first plant and 20
production runs from the second plant, the customer needs will be satisfied with
at a minimum cost of $68,000.

2. Let x  the number of acres of corn and y  the number of acres of

soybeans. Objective function to maximise profit: P  60 x  40 y
Subject to (Constraints):
x  y  6000
9 x  3 y  40500
3
x  y  5250
4
x0
y0

6000

5250

feasible region

4500 6000 7000 x

Unit 2: Linear Programming 2.18

The corner points of the set of feasible points are:
 0, 0  ,  4500, 0  ,  3750, 2250 ,  3000,3000 and  0,5250  .
Evaluating P at each corner points, we obtain
( x, y) C  600 x  1000 y

 0, 0  P0

 4500, 0  C  270,000

 3750, 2250 C  315,000

 3000,3000 C  300,000

 0,5250  C  210,000

Thus, by planting 3750 acres of corns and 2250 acres of beans, Teri’s will be a
maximum of $315,000.

3. Let x = no of standard suitcases and y = no of economy suitcases.

The quantity to be maximised, the profit, which we shall denote by P, is
P  20 x  25 y
The conditions specified by the problem are:
x  y  100
8 x  5 y  560
2 x  3 y  210
x0
y0

Unit 2: Linear Programming 2.19

 y

112

100

feasible region

70

70 100 110 x

The corner points of the set of feasible points are:

 0, 70  ,  0,100  ,  20,80  ,  45, 40 

Corner Points Value of Objective fn

 x, y  P  20 x  25 y
 0, 70  P  $1750
 0,100  P  $2500
 20,80  P  $2400
 45, 40  P  $1900

Thus the maximum profit is $2,500, and is obtained by producing 100 economy
suitcases only.

Summary
In this Unit, we further discussed about equations and inequalities. Using the
knowledge, you solved linear programing problems by identifying objective
functions and constraints. Graphing has been an important tool to successfully
complete linear programming problems.

Unit 2: Linear Programming 2.20