MBB3202

Quantitative Techniques for

Business

Chapter 2: Linear Programming

Prepared for University College Sabah Foundation Studen

 By the end of this lecture, students should understand:
 How to graph linear inequalities.
 How to identify a feasible region defined by linear inequalities.
Learning  How to calculate the points that define a feasible region.
Outcomes  How to solve linear programming problems graphically.
 How to use objective functions and constrains.
 How to calculate a maximum or minimum point.
  Linear programming is a method used to
identify
optimal maximum or minimum values.
What is Linear
 It is used in business for practical planning,
Programming decision-making problems.
  Each different resource can be written as a linear
inequality called a constraint.
 These constraints can be resources like the number of
workers, amount of time on a given shift, number of
machines, availability of these machines, etc., etc.
Linear  By using what we call the corner point theorem, we can
Programming find an optimal solution(s) for our problem.
 When we graph these constraints, we will get a feasible
region that contains our solutions. The corner point
theorem says that if a maximum or minimum value
exists, it will occur at a corner point of this feasible
region.
  An objective function is the function of one or more
variables that one is interested in either maximizing or
minimizing. The function could represent the cost or
What is an profit of some manufacturing process.
 A linear function in x and y has the form
Objective
Function?  The function to be maximized or minimized is called the
objective function.

P  ax  by
What are  Constraints are equalities or inequalities that describe
restrictions involved with the minimization or maximization of the
Constraints? objective function.
  The simplest form of a linear inequality is presented as:
x≤y
 In order to draw this inequality we need to identify at least two
points on the line.
Graphing  The easiest way to do so is to replace the inequality with an equals
Inequalities sign:
 x=y

 Now we can randomly select values for x and then hence y to get
two co-ordinates on the line.
 (2,2), (5,5) etc.
Graphing
Inequalities
  Now we can identify the area that illustrates the original
inequality, x ≤ y, i.e. the area where x is less than or equal to y.
Graphing  This area is on or above the line x=y.
Inequalities  However it is common practise to shade the area that is excluded
by the inequality, hence we would shade beneath the line.
 • All points on the line show
where x = y.
• All points above the line
Graphing show where x ≤ y.

Inequalities • All points below the line

(and shaded) show where x
≥ y.
  Conventions regarding indicating the excluded area are:
 a bold line with shading either above or below
represents an inequality that includes the values on
the line; i.e. less than and equal to or more than an
Graphing equal to.
Inequalities  a dashed line with shading either above or below
represents an equality that does not include the
values on the line i.e. less than or greater than.
  By graphing two or more linear inequalities we can identify a
feasible region which consists of values of x and y that satisfy
several inequalities at the same time.
 We find this region by sketching each of the linear inequalities on
Graphing the same graph.

simultaneous  This is best illustrated with an example.

linear Example

inequalities  Illustrate the following inequalities on a graph:

 2x + 4y ≤ 16
 5x + 15y ≤ 45
  First you must find two sets of co-ordinates for each of the
inequalities and then you need to graph the inequalities to identify
the feasible area.
 This is done by plugging random values into each equation for x
(or y) and then finding the associated value of y (or x) that makes
Graphing the linear equation true.

simultaneous  In order to do this you must convert the inequality (≤ or ≥) into a

“=“.
linear  2x + 4y = 16
 x=0 → y = 4; y = 0 → x = 8;
inequalities  (0,4) and (8,0) are two co-ordinates on this line.
 5x + 15y = 45
 x=0 → y = 3; y = 0 → x = 9;
 (0,3) and (9,0) are two co-ordinates on this line.
 • The figure shows the two lines on
the same graph and uses shading to
illustrate the areas excluded by each
Graphing of the inequalities.
simultaneous • The figure also shows the two
linear additional inequalities x ≥ 0 and y ≥
0.
inequalities
  The non-shaded area that is created by graphing the linear
Graphing inequalities is the feasible region and is defined by the points of
intersection of the different inequalities:
simultaneous  Point A is the point on the line 5x + 15y ≤ 45 where
linear x=0, hence y ≤ 3. Thus the co-ordinates are (0,3).
inequalities  Point C is the point on the line 2x + 4y ≤ 16 where
y=0, hence x ≤ 8. Thus the co-ordinates are (8,0).
  Point D is of course (0,0).
 Point B is the point where the two inequalities
intersect. This point can be found by solving the
simultaneous equation:
Graphing  5x + 15y = 45
(1)
simultaneous  2x + 4y = 16 (2)
linear  From (2): x = 8 – 2y (3)
inequalities  Sub in (1): 5(8-2y) + 15y = 45 → 40-10y + 15y =
45 → y =1.
 Sub in (3): x = 8-2(1) = 6
 Point B = (6,1)
 Situation:
A factory has two machines, each able to operate for a maximum of
40 hours per week. The factory produces two products A and B.
Product A needs one hours work on machine 1 and two hours on
Example machine 2. Product B needs one hour on machine 1 and one hour on
machine 2. Product A has profits of $10 per unit and product B $8
per unit. How many of each should be produced to maximise
profits?
 Solving linear programming problems requires the following skills:

Step by step
problem 1. Creating equations and inequalities

solving 2. Solving systems of equations

3. Graphing straight lines

4. Correct interpretation of mathematical calculations.

 Let the number of Product A units produced be x and Product B, y.

Profit Machine 1 Machine 2

P  10 x  8 y 1x  1 y  40 2 x  1 y  40
Step 1
The profit equation is called an objective function; the machine inequalities
are called constraints.
Step 2. Solving x  y  40 -------------(1)
systems of Looking for two points
equations x  0  y  40  (0, 40)
y  0  x  40  (40, 0)
2 x  y  40 -------------(2)
x  0  y  40  (0, 40)
y  0  x  20  (20, 0)
 y
Step 3. Note : x, y  0
40
Graphing
straight lines Feasible region

x  y  40

40 x
20 2 x  y  40
  The area on the graph that is common to both is called the feasible
region.
 It can be shown that the objective function (profit) is a maximum at one of
the corner points of the feasible region.
Step 4. Correct  From the diagram, the corner points are (0, 0), (0, 40), (20, 0).
interpretation
of
mathematical The value of P at each of these points is
calculations. (0, 0) : P  10(0)  8(0)  0
(0, 40) : P  10(0)  8(40)  320
(20, 0) : P  10(20)  8(0)  200
 4
3 Feasible Region
The objective 2
A

function 1
C B
0
-1 0 1 2 3 4 5 6 7 8 9 10

The first step is to draw -2

the lines associated with -3
the inequalities and -4
shade the line excluded -5
from the inequality to Example
define the feasible Maximise – x + y subject to:
region. 3x + 4y ≤ 12
x≥0
y≥0
  Next we need to identify the points that make up the feasible
region, labelled A, B and C on the graph.
 Point A is the intersection of the first inequality and x ≥ 0, hence y ≤
3. The co-ordinates are therefore (0,3).
 Point B is the intersection of the first inequality and y ≥ 0, hence x ≤
4. The co-ordinates are therefore (4,0).
 Point C is the intersection of x ≥ 0 and y ≥ 0. The co-ordinates are
The objective therefore (0,0).

 We now need to evaluate the objective function at each of these

function co-ordinates:
 (0,3): 0 + 3 = 3
 (4,0): - 4 + 0 = -4
 (0,0): 0 + 0 = 0

 The objective function is therefore maximised when x=0 and

y =3.
  The previous example maximised some given objective function
but sometimes we will wish to minimise an objective function (i.e.
a cost function).
Minimising  The process is the same the only difference is that we select the
point in the feasible region that minimises the objective function.
the Example:
Objective  Minimise -5x + y subject to:
Function  4x + y ≤ 8
 -2x + 5y ≤ 10
 x≥0
 y≥0
  Again plotting the inequalities and shading the areas that are
excluded by the inequality we arrive at the feasible region ABCD.

Minimising the
Objective
Function 20
D
A Feasible
B Region
C
0
0 1 2 3 4 5
-20
  Next we need to identify the points that make up the feasible region, labelled A,
B, C and D on the graph.
 Point A is the intersection of the second inequality (-2x + 5y ≤ 10) and x ≥ 0, hence y ≤
2. The co-ordinates are therefore (0,2).
 Point C is the intersection of the first inequality (4x + y ≤ 8) and y ≥ 0, hence x ≤ 2. The
co-ordinates are therefore (2,0).
Minimising the  Point D is the intersection of x ≥ 0 and y ≥ 0. The co-ordinates are therefore (0,0).
 Point B is the intersection of the first inequality and the second inequality which can
Objective be solved using simultaneous equations. The co-ordinates are (15/11,28/11).
 We now need to evaluate the objective function at each of these co-ordinates A,
Function B, C and D:
 A - (0,2): -5(0) + 2 =2
 B - (15/11,28/11): - 5(15/11) + 28/11 = -75/11 + 28/11 = -47/11 = -4.27
 C - (2,0): -5(2) + 0 = -10
 D - (0,0): -5(0) + 0 = 0
 The objective function is therefore minimised when x=2 and y =0 (point C)
  Sometimes there are no solutions to a simultaneous linear
equation problem.
Unbounded  e.g. when the two lines are parallel, solving for the intersection point
yields no solution.
feasible  Hence when we draw the linear equations they will present
regions themselves as unbounded areas which do not have a complete set
of intersection points to define the feasible area.
 This is best illustrated with an example.
  Example
 Maximise 12x – 3y subject to:
Unbounded  2x + y ≥ 14
 3x – 4y ≥ 12
feasible  x≥0
regions:  y≥0

Example  The inequalities are plotted on the next slide.

 Note that the shaded area on the side of the line shows the area
that is excluded by the inequality.
Unbounded
feasible
regions:
Example Note that the feasible region is
not bounded on all sides,
hence there is no solution if we
are maximising. If we are
minimising then point B
represents the solution.
  Example
 APEX manufactures two models of car radio, the Standard (S)
and the Deluxe (D).
 The production of the Standard is very straightforward
involving 4 plastic components and 12 metal components.
Applications  The production of the Deluxe is more complex involving the
of Linear use of 18 plastic and 6 metal components.
Programming  There are 1296 plastic components and 1824 metal
components ordered by the company each month and the
company seeks to use up as many of the components each
month as it can while still maximising profit.
 If the profit on a Standard is £55 and the profit on a Deluxe is
£89 how should APEX arrange production to maximise profit?
  Hence APEX wishes to maximise:
 55S+ 89D

 Subject to the constraints:

Applications of  4S + 18 ≤ 1296
 12S + 6D ≤ 1824
Linear  In addition S and D cannot be negative:
Programming  S≥0
 D≥0

 Now we need to graph each of the constraints and identify the feasible
region – see next slide.
Metal Constraint: 12S + 6D ≤ 1824
S=0, D= 304 and D = 0, S= 152

Plastic Constraint: 4S + 18D ≤ 1296

D = 0, S= 324 and S=0, D= 72
  The feasible region is defined as A, B, C, D.
 We have found points A and C as:
 A: S=0, D=72 (0,72)
 C: S=152, D=0 (152,0)

Applications of  D is obviously (0,0) and B is the intersection of the two lines:

 12S + 6D ≤ 1824 (1)
Linear  4S + 18 D ≤ 1296 (2)
Programming  (2) x 3:
 12S + 54 D ≤ 3888 (3)

 (3) – (1):
 48D ≤ 2064 and so D ≤ 43 and S ≤ 130.5

 So point B is (130.5, 43)

  We must now substitute each of the co-ordinates into the original
objective function (55S + 89D) in order to find out which combination of
standard and deluxe radios will make the highest profit.
Applications of 

A (0,72) = 55(0) + 89(72) = 6409
B (130.5, 43) = 55(130.5) + 89(43) = 11004.5
Linear  C (152, 0) = 55(152) + 89(0) =8360
Programming  D (0,0) = 55(0) + 89(0) = 0

 This tells us that the objective function is maximised when the firm
makes 130.5 (rounded to 130) Standard models and 43 Deluxe models
(i.e. point B).