Business Mathematics

Lecture 3
Linear Programming
Lecturer: Kahenya, N.P

Introduction to Lecture 3
This lecture introduces you to linear programming and their applications to solving economics
and business-related problems. We shall demonstrate how linear inequalities are used to model
business problems. Functions of two variables can be optimized subject to some given
constraints, and this can be demonstrated using linear inequalities.

Further Readings
These notes have been derived from diverse resources. These resources are recommended for
further reading to gain more insights on the application of linear inequalities to business or
commercial arithmetic. The resources also offer a background introduction to linear inequalities
that may not be covered in this lecture. These are (Jacques, 2006; P. Kahenya, 2017; P. N.
Kahenya, 2021; Murray & Robert, 2009).

Intended Learning Outcomes

At the end of this lecture, you will be able to;

(i) Define an objective function.

(ii) Represent linear inequalities graphically.
(iii) Solve business mathematics problems by applying linear programming.

Example 1: Given the linear inequalities; x + 3y ≤ 6; y + 2x ≥ 1; x ≥ 0; y ≥ 0, represent the

feasible region graphically.

Solution: Inequalities represent regions on the plane. Hence the first task is to determine the
boundary of this region. We shall shade the unwanted region in our examples.

If we consider the inequality 𝑥 + 3𝑦 ≤ 6 we can see that the boundary of this region is the line
x + 3y = 6. The boundary is part of the region since we have the inequality < and equals to
sign. Hence the boundary will be a continuous line, otherwise it would have been dotted.

The other region is represented by the inequality y + 2x ≥ 1 and hence its boundary is the line
𝑦 + 2𝑥 = 1.

1
The boundaries for the regions represented by 𝑥 ≥ 0 and 𝑦 ≥ 0 are the lines 𝑥 = 0 and 𝑦 = 0
which are the y-axis and the x-axis respectively. The feasible region is the region to right of the
line 𝑥 = 0 and above the line 𝑦 = 0.

Next we identify the corresponding points of 𝑥 and 𝑦 to plot the two boundaries i.e. x + 3y =
6 and y + 2x = 1

𝐱 + 𝟑𝐲 = 𝟔
x 0 3 6
y 2 1 0
𝐲 + 𝟐𝐱 = 𝟏
x 0 1 2
𝑦 1 -1 -3

The feasible region represented by the system of linear inequalities is as below;

Figure 1

Note that to determine the feasible region (when working manually), you can use the origin (0,0)
to test the required region. For example, consider inequality 𝑥 + 3𝑦 ≤ 6

Replacing x and y with 0 we get 0 ≤ 6. This is a valid statement, meaning that the origin lies in
the required region, and hence we shared the other side of the boundary where the origin is not
located.

Similarly we can test the inequality 𝑦 + 2𝑥 ≥ 1 to get 0 ≥ 1. This is invalid. Meaning that the
origin lies in the unwanted region and hence we can shade the opposite side which is the
required region.

2
Definition 1: In linear programming the main goal is to optimize the given problem. Objective
function is therefore an expression that defines the quantity to be maximized or minimized. The
purpose of the objective function is to determine the values for decision variables that optimize
i.e. maximize or minimize, while satisfying all the given constraints. It can be maximizing profit,
minimizing cost, minimizing time among other variables.

Example 2: A tailor has 50 square metres of clothing materials in which he plans to make skirts
and shorts, and maximize profit within some constraints (Kahenya, 2017). What is the number
of skirts and shorts that he has to make to maximize profit?

Objective: Maximize profit

Decision variables: The tailor makes x skirts and y shorts.

Constraints:

o A skirt requires 2 square metres of material while a short requires 0.5 square metres of
materials i.e. 2x + 0.5y ≤ 50
o He must make at least 10 shorts, i.e. 𝑦 ≥ 10
o He has at least 30 people available to make the skirts and shorts. Each skirt requires 3
people to make and a short requires 1 person to make it. That is; 3x + y ≥ 30

Non-negativity constraint:

o These are 𝑥 ≥ 0, 𝑦 ≥ 0 since the tailor cannot make negative number of clothing items.

Objective function:

o It is given that profit for selling one skirt is 200 KES and a short is 300 KES. This means
that our objective function is; P = 200x + 300y

Solution: We can plot the inequalities on a plane as shown below.

We can use the vertices of the feasible region to determine the maximum profit using the profit
function P = 200x + 300y.

Point 𝐱 𝐲 Total profit

A(0, 15) 0 4,500 4,500
10 2,000 1,000 3,000
B (10, )
3
C(22.5, 10) 4,500 3,000 7,500
D(0, 100) 0 30,000 30,000

3
 Figure 2

To maximize profit the tailor needs to make 100 shorts only so as to realize the maximum profit
of 30,000 KES.

Example 3: A certain firm produces two types of iron boxes 𝑥 and 𝑦 per day.

Objective: Maximize sales revenue.

Decision variables: The firm produces type 𝑥 iron boxes and type 𝑦 boxes per day.

Constraints:

o The firm can only ship out 300 iron boxes i.e. 𝑥 + 𝑦 ≤ 300
o The firm labourers can only offer at most 400 working hours. Type x iron box requires 2
hours to make while type y requires 1 hour i.e. 2𝑥 + 𝑦 ≤ 400

Non-negativity constraint:

o These are 𝑥 ≥ 0, 𝑦 ≥ 0 since the firm cannot make negative number of iron boxes.

Objective function:

o It is given that type 𝑥 iron box sells at 4200 KES and type 𝑦 sells at 3500 KES i.e.
objective function 𝑝 = 4200𝑥 + 3500𝑦

Solution: We can plot the inequalities on the xy-plane as below. We can use the sales revenue
function 𝑝 = 4200𝑥 + 3500𝑦 to determine the maximum sales revenue.

4
 Point 𝐱 𝐲 Sales Revenue
A(0, 0) 0 0 0
B(200,0) 840,000 0 840,000
C(100, 200) 420,000 700,000 1,120,000
D(0, 300) 0 1,050,000 1,050,000

Figure 3

To maximize sales revenue the firm needs to make 100 types x iron boxes and 200 type y iron
boxes.

Example 4: Alternative method to Example 3 above is to use the Simplex Method. This method
was developed by George Dantzig in the 1940s. It is an iterative method that systematically
moves from one feasible solution to another. This is done to improve on the objective function
value until an optimal is reached. We shall solve the previous Example 3 to demonstrate the
simplex method.

Step 1: Our objective function is P = 4200x + 3500y

Our constraints are: 2x + y ≤ 400 and x + y ≤ 300

5
Next we write the objective function as; −4200x − 3500y + P = 0 and the constraints as 2x +
y + s1 = 400 and x + y + s2 = 300 respectively.

Note we have added two values 𝑠1 and 𝑠2 . These are called slack variables. Slack variables are
introduced to convert the inequalities into equalities.

Now we have;

Maximize −4200x − 3500y + P = 0

Subject to:

2x + y + s1 = 400

x + y + s2 = 300

Note that 𝑥 ≥ 0, 𝑦 ≥ 0

Next we write the above coefficients of the above equations in a tableau as seen below;

𝐱 𝐲 𝐬𝟏 𝐬𝟐 𝐏
𝐬𝟏 2 1 1 0 0 400
𝐬𝟐 1 1 0 1 0 300
-4200 -3500 0 0 1 0

The last row has negatives. Our aim is to have all positives or zero in this row to achieve our
optimal.

Next identify the smallest negative value on the last row i.e. -4200 to know the column that we
need to pivot i.e. to make it 1 and the only non-zero in that column.

In this case it is the column with 𝑥.

Under the column x we have 2 and 1. We need to determine which of the two we shall pivot.

To do this we need to determine which of this row has lowest ratio. For row 1 we take the ratio
400 300
= 200 and for row 2 we take the ratio = 300. The smallest ratio is 200 for row 1. Hence
2 1

we need to pivot 2.
1
We pivot 2 by first, multiplying every coefficient in this row by 2 to get

𝐱 𝐲 𝐬𝟏 𝐬𝟐 𝐏
𝐬𝟏 1 0.5 0.5 0 0 200
𝐬𝟐 1 1 0 1 0 300
-4200 -3500 0 0 1 0

6
Next, we have to make the rest of the values below it i.e. 1 and -4200 all zeros. This is achieved
by following elementary row operations;

To change Row 2, R 2 ; (R1 − R 2 ) → R 2

To change Row 3, R 3 ; (4200R1 + R 3 ) → R 3 . To get the tableau;

𝐱 𝐲 𝐬𝟏 𝐬𝟐 𝐏
𝐱 1 0.5 0.5 0 0 200
𝐬𝟐 0 -0.5 0.5 -1 0 -100
0 -1400 2100 0 1 840,000

Note that when we get the pivot point corresponding to x, the row 1 is now headed x
instead of 𝒔𝟏

Our third row is not yet optimal since we have a negative value – 1400.

To determine which between 0.5 and – 0.5 will be our pivot point, we first check the ratio. For
200 −100
row 1 we have; = 400 and for row 2 we have = 200. The lowest ratio is 200 and hence
0.5 −0.5

we make -0.5 the pivot i.e. first, we multiply row 2 by – 2 to get;

𝐱 𝐲 𝐬𝟏 𝐬𝟐 𝐏
𝐱 1 0.5 0.5 0 0 200
𝐲 0 1 -1 2 0 200
0 -1400 2100 0 1 840,000

Next, we have to make the rest of the values in column y to be zero i.e. 0.5 and -1400. This is
achieved by following elementary row operations;

To change Row R 3 ; (1400R 2 + R 3 ) → R 3

1
To change Row 1, R1 ; (R1 − 2 R 2 ) → R1 to get the tableau;

𝐱 𝐲 𝐬𝟏 𝐬𝟐 𝐏
𝐱 1 0 0.25 -0.5 0 100
𝐲 0 1 -1 2 0 200
0 0 700 2800 1 1,120,000
Note that when we get the pivot point corresponding to y, the row 1 is now headed y
instead of 𝒔𝟏

7
The last row, Row 3, is all positive, and hence this is the optimal. Therefore from Row 1 we can
conclude that x = 100 and from Row 2 y = 200, and from Row 3 we get our maximum sales
revenue as 1,120,000.

Example 3: Use the Simplex Method to work out the following:

Minimize P = 3x + 2y

Subject to the constraints:

2x + y ≥ 10
x + 3y ≥ 15
x≥0
y≥0
Solution: We need to convert our case to a maximization case. First we write in matrix form and
transpose the matrix i.e.

2 1 10 T 2 1 3
(1 3|15) = ( 1 3 |2)
3 2 1 10 15 1
Note that the 1 in the last row, last column i.e. 𝑎33 is the coefficient of P in the objective
function. Thus we have the constraints as;

2a + b ≤ 3
a + 3b ≤ 2
And the objective function that we need to maximize is from the last row i.e. Z = 10a + 15b or
−10𝑎 − 15𝑏 + 𝑍 = 0

We introduce 𝑥 and 𝑦 as the slack variables to get;

2a + b + x = 3
a + 3b + y = 2

Our initial tableau becomes;

𝒂 𝐛 𝐱 𝐲 𝒁
𝐱 2 1 1 0 0 3
𝐲 1 3 0 1 0 2
-10 -15 0 0 1 0

Our aim is to ensure that the last row is all positive or zero.

The smallest value is -15, hence we need to make either 1 or 3 in column b a pivot entry.

8
 3 2
We find the ratio for the two rows. For row 1, the ratio is 1 = 3 and for row 2, the ratio is 3. The
2
smallest ratio is 3 hence we work with row 2.

1 1
Next multiply row 2 by 3 to make 3 1 i.e. 3 R 2 → R 2 to get the tableau

𝐚 𝐛 𝐱 𝐲 𝐙
2 1 1 0 0 3
1 1 0 1 0 2
3 3 3
-10 -15 0 0 1 0

For it to be a pivot entry, it must be the only none zero in the column. Hence we need to make 1
and -15 zero by applying the elementary operations; (15R 2 + R 3 ) → R 3 and (R1 − R 2 ) → R1
to get;

𝐚 𝐛 𝐱 𝐲 𝐙
5 0 1 1 0 7
−
3 3 3
1 1 0 1 0 2
3 3 3
-5 0 0 5 1 10

5 1
Again in Row 3 we have a negative 5. We need to make either 3 or 3 a pivot entry. The ratio of
7 5 7 3 7 2 1 2 3
row 1 is 3 ÷ 3 = 3 × 5 = 5 and the ratio of row 2 is 3 ÷ 3 = 3 × 1 = 2. This implies that we
5
need to make 3 the pivot entry. Hence we carry out the following elementary operations;

3
R → R1
5 1
To get the tableau;

𝐚 𝐛 𝐱 𝐲 𝐙
1 0 3 1 0 7
−
5 5 5
1 1 0 1 0 2
3 3 3
-5 0 0 5 1 10

9
 Next we ensure the entry is the only non-zero in the column by carrying out the following
1
operations; (3 R1 − R 2 ) → R 2 and (5R 3 + R 3 ) → R 3 to get;

𝐚 𝐛 𝐱 𝐲 𝐙
1 0 3 1 0 7
−
5 5 5
0 -1 1 2 0 1
− −
5 5 5
0 0 3 4 1 17

The integers in our last row are all positive. Therefore, x = 3, y = 4 and our minimum value is
17

Example 4: Maximize 𝑍 = 4𝑥1 + 3𝑥2 + 2𝑥3

Subject to the constraints;

2x1 + x2 + x3 ≤ 10
x1 + 3x2 + 2x3 ≤ 20
3x1 + 2x2 + 4x3 ≤ 30
x≥0
y≥0
z≥0
Solution: We introduce 3 slack variables 𝑠1 , 𝑠2 , 𝑠3 to get the initial tableau;

𝐱𝟏 𝐱𝟐 𝒙𝟑 𝐬𝟏 𝐬𝟐 𝒔𝟑 𝒁
𝐬𝟏 2 1 1 1 0 0 0 10
𝐬𝟐 1 3 2 0 1 0 0 20
𝒔𝟑 3 2 4 0 0 1 0 30
-4 -3 -2 0 0 0 1 0

The smallest value in row 4 is -4, hence we make either 2, 1, or 3 a pivot entry.
10 20 30
The ratio for Row 1; = 5; ratio for Row 2 is = 20; and ratio for row 3 is = 10
2 1 3

1
5 is the smallest ratio hence we make 2 the pivot entry by 2 R1 → R1 to get;

𝐱𝟏 𝐱𝟐 𝐱𝟑 𝐬𝟏 𝐬𝟐 𝐬𝟑 𝐙
𝐬𝟏 1 0.5 0.5 0.5 0 0 0 5
𝐬𝟐 1 3 2 0 1 0 0 20
𝐬𝟑 3 2 4 0 0 1 0 30

10
 -4 -3 -2 0 0 0 1 0

Next we, (R1 − R 2 ) → R 2 ; (3R1 − R 3 ) → R 3 and (4R1 + R 4 ) → R 4

𝐱𝟏 𝐱𝟐 𝐱𝟑 𝐬𝟏 𝐬𝟐 𝐬𝟑 𝐙
𝒙𝟏 1 0.5 0.5 0.5 0 0 0 5
𝐬𝟐 0 -2.5 -1.5 0.5 -1 0 0 -15
𝐬𝟑 0 -0.5 -2.5 1.5 0 -1 0 -15
0 -1 0 2 0 0 1 20

We have negative 1 in the last row, hence no optimal equation. We need to find a pivot entry in
5 15 15
this column. The ratios is : Row 1 is 0.5 = 10; Row 2 is − −2.5 = 6; Row 3 is − −0.5 = 30. The
2
smallest ratio is for Row 2. Hence we make -2.5 a pivot entry by − 5 R 2 → R 2 to get the tableau;

𝐱𝟏 𝐱𝟐 𝐱𝟑 𝐬𝟏 𝐬𝟐 𝐬𝟑 𝐙
𝒙𝟏 1 0.5 0.5 0.5 0 0 0 5
𝐬𝟐 0 1 0.6 -0.2 0.4 0 0 6
𝐬𝟑 0 -0.5 -2.5 1.5 0 -1 0 -15
0 -1 0 2 0 0 1 20

Next we make the pivot entry the only non-zero entry in the column by (R1 − 0.5R 2 ) → R1 ;
(0.5𝑅2 + 𝑅3 ) → 𝑅3 ; (𝑅2 + 𝑅4 ) → 𝑅4 to get

𝐱𝟏 𝐱𝟐 𝐱𝟑 𝐬𝟏 𝐬𝟐 𝐬𝟑 𝐙
𝒙𝟏 1 0 0.2 0.6 -0.2 0 0 2
𝐱𝟐 0 1 0.6 -0.2 0.4 0 0 6
𝐬𝟑 0 0 -2.2 1.4 0.2 -1 0 -12
0 0 0.6 1.8 0.4 0 1 26

The last row is all positive and zero, hence we have 𝑥1 = 2, 𝑥2 = 6, 𝑥3 = 0 and the maximum
value of 26

11
Exercise

1) Represent the following inequalities on a the xy-plane

y + 2x < 12 y ≥ −3 x<5
a) c) y ≥ 2
2y − 5x ≥ 15 b) 2y < 7x
3y + 4x ≤ 18 x>0
2) Kevin has KES 900 which he intends to use on buying books and pens. Each book costs
KES 50 while each pen costs KES 30. The number of books should be at least 5 and the
number of pens must be more than 4. By letting x to be the number of books bought, and y
to be the number of pens bought, represent the information on a cartesian plane (Adopted
from (Kahenya, 2017)).
3) Use Simplex method to minimize: P = 3x + 5y
Subject to the constraints: x + y ≥ 1; 2x + 5y ≥ 26; x ≥ 0; y ≥ 0
4) Use Simplex method to maximize: P = 5x + 3y
Subject to the constraints: 2x + y ≤ 10; x + 3y ≤ 12; x ≥ 0, y ≥ 0
5) Use graphical method to solve Questions 3 and 4 above.
6) Use Simplex method to maximize: P = 3x + 4y + 5z
Subject to the constraints:
2x + y + 3z ≤ 20
x + 2y + z ≤ 15
3x + 2y + 4z ≤ 30
x ≥ 0, y ≥ 0, z ≥ 0

References

Jacques, I. (2006). Mathematics for economics and business (5th ed.). Prentice Hall.

Kahenya, P. N. (2017). Foundation Maths. LAP Lambert Academic Publishers.

Kahenya, P. N. (2021). Basic Mathematics. HUFOCW. [Link]

Lay, D. C. (2003). Linear Algebra and its Application (3rd ed.). Pearson Education, Inc.

Lay, D. C., Lay, S. R., & McDonald, J. J. (2016). Linear Algebra and its Application (5th ed.).
Pearson.

Murray, S., & Robert, M. (2009). College Algebra. McGraw-Hill.

❖ The Simplex Method and the Dual : A Minimization Example ❖ ([Link])

12