Mathematics for

Finance
CHAPTER THREE
INTRODUCTION TO LINEAR
PROGRAMMING
 Chapter Content
3.1 Introduction to linear
programming
3.2 Mathematical Model
Formulation
3.3 Graphical Solution Method
 3.1 Introduction to Linear
Programming
 Linear programming is a mathematical technique
which is an optimization method designed to aid
managers in allocating scarce resources such as
labor, capital, or energy among competing activities.
 It reflects, in the form of a model, the organization's

attempt to achieve some objective;

 Maximizing profit contribution, production
capacity,
 Minimizing cots, in view of limited or
constrained resources available such as capital
or labor, raw material, market demand, production
process, service levels, machine time, budgets and
storage capacity etc.
 3.1 Introduction to Linear
Programming
Linear Programming Models (LPM)
 LPM are mathematical representations of LP problems.

 LP Models have certain characteristics in common.

 Knowledge of these characteristics enables us to recognize

problems that are amenable to a solution using LP models

and to correctly formulate a LP model.
 The characteristics can be grouped into two categories:

Components and Assumptions.

 The components relate to the structure of a model, whereas

the assumptions reveal the conditions under which the

model is valid.
Components of LP Model
1. Objective and Objective Function - a single,
quantifiable objective must be specified by the decision
maker
 Maximization
 Minimization
2. Decision Variables - unknown quantities to be solved for
3. Constraints - restrictions or limits coming from a variety of
sources
 System constraints – involve more than one decision variable
 Individual constraints – involve only one variable
 Non-negativity constraints – specify that no variable will be
allowed to take on a negative value
4. Parameters – are fixed values that specify the impact that
one unit of each decision variable will have on the objective
LP Model Example
 Assumptions of LPP
There are four basic assumptions of LP models.
i) Linearity: requirement is that each decision variable
has a linear impact on the objective function and in each
constraint
ii) Divisibility: pertains to potential values of decision
variables can assume non-integer values are acceptable .
iii) Certainty: requirement involves two aspects of LP
models, one aspect relates to the model parameters (i.e.,
numerical value). It is assumed that those values are
known and constant. It is the assumption that all relevant
constraints have been identified and represented in the
model
iv) Non-negativity
3.2 Mathematical
Model Formulation
 Steps in Model Formulation

 Steps for Formulating the LP Model

1. Identify the unknown decision variables
to be determined and assign symbols to
them.
2. Identify all the restrictions or constraints
in the problem and express them as linear
equations or inequalities of decision
variables.
3. Identify the objective or aim and
represent it also as a linear function of
decision variables.
 Example 1.
A firm that assembles computer and computer equipment is about
to start production of two new microcomputers. Each type of
micro-computer will require assembly time, inspection time and
storage space. The amount of each of these resources that can be
devoted to the production of microcomputers is limited. The
manger of the firm would like to determine the quantity of each
microcomputer to produce in order to maximize the profit
generated by sales of these microcomputers.

Additional information
In order to develop a suitable model of the problem, the manager
has met with design and manufacturing personnel. As a result of
these meetings, the manger has obtained the following information:
 Cont’d…
Type 1 Type 2
Profit per unit Birr 60 Birr 50
Assembly time per unit 4hrs 10hrs
Inspection time per unit 2hrs 1hr
Storage space per unit 3cubic ft 3cubic ft
 The manager also has acquired information on the availability of

company resources. These weekly amounts are:

Resource Resource available
Assembly time 100hrs
Inspection time 22hrs
Storage space 39 cubic feet
Required: Formulate the Linear programming model.
 Example 2.
 A firm manufactures two products A & B on
which the profits earned per unit are Birr 3 & 4
respectively. Each product is processed on two
machines M1 & M2. Product A requires one
minute of processing time on M1 and two minute
on M2, while product B requires one minute in
M1 and one minute on M2. Machine M1 is
available for not more than 7:30 hours and M2 is
available for 10 hours, during any working day.
 Formulate the mathematical LP model that will
determine the optimal production quantities for
profit maximization
 Example 3.
An electronics firm produces three types of switching devices. Each type
involves a two-step assembly operation. Assembly times are given as follows:
Assembly time per Unit (in minutes)
Station 1 Station 2
Model A 2.5 3.0
Model B 1.8 1.6
Model C 2.0 2.2
Each workstation has a daily working time of 37.5 hrs. Model A yields a
profit of Birr 8.25 per unit, Model B a profit of Birr 7.50 per unit and
Model C a profit of Birr 7.80 per unit. Assume that the firm can sell all it
produces during this time, but it must fill outstanding orders for 20 units
of each model type. Formulate the mathematical LP model
that will determine the optimal production quantities
 Example 4.
A diet is to include at least 140 mgs of vitamin A and at least
145 Mgs of vitamin B. These requirements are to be obtained
from two types of foods: Type 1 and Type 2. Type 1 food
contains 10Mgs of vitamin A and 20mgs of vitamin B per
pound. Type 2 food contains 30mgs of vitamin A and 15 mgs of
vitamin B per pound. If type 1 and 2 foods cost Birr 5 and Birr
8 per pound respectively.
Vitamins
Foods A B
Type 1 10 20
Type 2 30 15
Required: Formulate the linear programming model of this problem.
3.3 Graphical Solution
Method
 Considerations in Graphical
Solution Method

 In graphical method:
 The inequalities (structural constraints) are
considered to be equations. This is because; one
cannot draw a graph for inequality.
 Only two variable problems are considered,
because we can draw straight lines in two-
dimensional plane (X-1 axis and X-2 axis).
 More over as we have non negativity constraint
in the problem that is all the decision variables
must have positive values always the solution to
the problem lies in first quadrant of the graph.
 Cont…
 This method consists of the
following steps:
 Formulate the mathematical model for
the given problem.
 Convert the constraints given in the
form inequality to that of equality.
 Draw the x and y intercepts.
 Plot each of the constraints on the
graph.
 Identify the feasible (solution) region.
 Techniques of Graphical
Method
 Corner (extreme) point method: this
method includes the following steps.
 Identify each of the extreme points of the
feasible region.
 Find the values of objective function at each
extreme point.
 The optimal solution occurs at that corner point
which maximizes objective function in case of
maximization problem.
 The optimal solution occurs at that corner point
which minimizes objective function in case of
minimization problem.
 1. Maximization Problem
Example: a microcomputer firm is about to start production
of two new microcomputers, X1 and X2. The manager
wants to determine how much of each computer to produce
in order to maximize the profit generated by selling them.
Resources Amount Available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet
Type 1 Type 2
Profit per unit $60 $50
Assembly time per unit 4 hours 10 hours
Inspection time per unit 2 hours 1 hour
Storage space per unit3 cubic feet 3 cubic feet
1. Maximization Problem
 The model is:
 Maximize Z= 60X1 + 50X2
 Subject to: Assembly 4X 1 +10 X 2 < 100 hours
Inspection 2X 1 + 1X 2 < 22 hours
Storage 3 X 1 + 3X 2 < 39 cubic feet
Where; X1, X2 > 0
 Required: Solve the problem using graphic
method
 Interpret the result
 Check resource consumption (availability
of slack)
Cont…
Cont.….
Corne Coordinate Value of Objective Function
r Point (Z=60X1 + 50X2)
Point (X1, X2)
a (0, 10) 60(0) + 50(10) = 500
b (5, 8) 60(5) + 50(8) = 700
c (9, 4) 60(9) + 50(4) = 740
d (11, 0) 60(11) + 50(0) = 660
Interpretation:
 For a firm to maximize its profit (740), it should
produce 9 units of the Model I microcomputer
and 4 units of model II.
Checking resource consumption (availability
of slack)
 (4*9) + (10*4) = 76 assembly hours
 1. Maximization Problem
A company manufactures two types of boxes, corrugated
and ordinary cartons. The boxes undergo two major
processes: cutting and pinning operations. The profits per
unit are Br. 6 and Br. 4 respectively. Each corrugated box
requires 2 minutes for cutting and 3 minutes for pinning
operation, whereas each carton box requires 2 minutes
for cutting and 1 minute for pinning. The available
operating time is 120 minutes and 60 minutes for cutting
and pinning machines.
Required: Determine the optimum quantities
Interpret the result
Check if there is any slack/unused resource
2. Minimization Problem
 Example 2:
 Min. Z = 0.1X+0.07Y
 Subject to:

6X+2Y > 18
8X+10Y > 40
Y>1
 Where; X, Y > 0
 Find the values of X and Y which
makes the objective function
minimum.
 Cont…
Solution:
 The coordinates of corner point’s feasible region are:
 A = (0, 9), B = (2.27, 2.18), C = (3.75, 1)
Compute objective function value at each corner
point of the feasible region.
Corner point coordinates(x1, x2) Z =
0.1x1+0.07x2
A (0, 9) (0.1x 0) + (0.07 x 9) =0.63

B (2.27, 2.18) (0.1 x 2.27) + (0.07 x2.18) =0.38

C (3.75, 1) (0.1 x 3.75) + (0.07 x 1) = 0.445
 Example
A diet is to include at least 140 mgs of vitamin
A and at least 145 Mgs of vitamin B. These
requirements are to be obtained from two
types of foods: Type 1 and Type 2. Type 1 food
contains 10Mgs of vitamin A and 20mgs of
vitamin B per pound. Type 2 food contains
30mgs of vitamin A and 15 mgs of vitamin B
per pound. If type 1 and 2 foods cost Birr 5 and
Birr 8 per pound respectively.
Required: How many pounds of each type
should be purchased to satisfy the
requirements at a minimum cost?
Exercise
A company owns two flour mills (A and B) which
have different production capacities for HIGH,
MEDIUM and LOW grade flour. This company has
entered contract supply flour to a firm every
week with 12, 8, and 24 quintals of HIGH,
MEDIUM and LOW grade respectively. It costs the
Co. $1000 and $800 per day to run mill A and mill
B respectively. On a day, Mill A produces 6, 2, and
4 quintals of HIGH, MEDIUM and LOW grade flour
respectively. Mill B produces 2, 2 and 12 quintals
of HIGH, MEDIUM and LOW grade flour
respectively.
Required:
Exercise - Mix of
Constraints

ABC Gasoline Company has two refineries with

different production capacities. Refinery A can
produce 4,000 gallons per day of SUPER
UNLEADED GASOLINE, 2,000 gallons per day of
REGULAR UNLEADED GASOLINE and 1,000
gallons per day of LEADED GASOLINE. On the
other hand, refinery B can produce 1,000 gallons
per day of SUPER UNLEADED, 3,000 gallons per
day of REGULAR UNLEADED and 4,000 gallons
per day of LEADED. The company has made a
contract with an automobile manufacturer to
provide 24,000 gallons of SUPER UNLEADED,
42,000 gallons of REGULAR UNLEADED and
Exercise Cont…

Required:
a. Formulate this problem as a LPP.
b. Determine the number of days the
gasoline company should operate each
refinery in order to meet the terms of the
above contract most economically (i.e. At a
minimum running cost)
c. Which grade of gasoline would be over
produced?
Graphical Solutions
for the Special
Cases of LP
 i) Unboundedness
 Example:
Max Z = 10X1 + 20X2
Subject to 2X1 + 4X2 > 16
X1 + 5X2 > 15
X1, X2 > 0
The reason for it may be concluded to be wrong
formulation of the problem such as incorrectly
maximizing instead of minimizing and/or errors
in the given problem.
Checking equalities or rethinking the problem
statement will resolve the problem.
 Cont…

The shaded area represents the set of all

feasible solutions and as can be seen from
the graph, the solution is unbounded.
 ii) Infeasibility

 Infeasibility is a condition that arises when

no value of the variables satisfy all the
constraints simultaneously.
 Such a problem arises due to wrong model
formulation with conflicting constraints
 Example:
Max Z = 3X1+2X2
Subject to: 2X1 + X2 < 2
3X1 + 4X2 > 12
X1, X2 > 0
Cont…
 iii) Multiple Optimal Solutions

 Example:
Max Z = 8X1+16X2
Subject to: X1 + X2 < 200 ……. C1
3X1 + 6X2 < 900 ……. C2
X2 < 125 ……. C3
X1, X2 > 0
 Cont..

 The objective function assumes its maximum

value of 2,400 at two corner points;
 B (50,125) and C (100,100).
Therefore, the optimal solution is found on the
line segment connecting the two corner points.
 Important terms of Solutions
in LPP
 Solutions: are values of decisions variable of linear
programming model
 A feasible solution is a solution for which all the
constraints are satisfied.
 An infeasible solution is a solution for which at least
one constraint is violated.
 The feasible region is the collection of all feasible
solutions.
 An optimal solution is a feasible solution that has
the most favorable value of the objective function.
The most favorable value is;
 the largest value if the objective function is to be
maximized,
 whereas it is the smallest value if the objective
 Slack Versus Surplus
Slack:
 Slack is the amount of a scarce resource that is
unused by a given solution. Slack can potentially
exist in a < constraint. Slack variables are
considered in the objective function by using a
coefficient of zero for each of them. When all the
constraints are written as equalities after adding a
slack variable to each of them, the linear program
is said to be in standard form. For example, in
the Assembly constraint 4X1 +10X2 < 100 hrs,
the slack value is 100 – [4(9) +10(4)] = 24.
 Cont…
 Surplus: on the other hand is the amount by
which the optimal solution causes a > constraint
to exceed the required minimum amount. It can
be determined in the same way that slack can,
i.e., substitute the optimal values of the decision
variables into the left side of the constraint and
solve. The difference between the resulting
value and the original right hand side amount is
the amount of surplus. Surplus should also be
accounted for in the objective function by using
coefficients of zero like wise.
2.4 THE SIMPLEX SOLUTION
METHOD
 Steps in Simplex Method

1. Write the Problem in Standard Form

 Characteristics:
 All constraints are expressed in the form of equalities
or equations.
 All right hand sides are non-negative
 All variables are non-negative
 Standardization/Tableau Form/:
Types of constraint Standard form
≤ Add a slack variable
= Add an artificial variable
≥ Subtract a surplus variable
and add an artificial variable
 Cont…
2. Develop an Initial Simplex Tableau
 Steps in developing initial simplex tableau:
I. List the variables in the model across the top of
the tableau
II. Next fill-in the parameters of the model in the
appropriate rows and columns
III. Add two columns to the left side of the tableau.
The first column is a list of variables called Basis.
IV. The C at the top second column indicates that
the values in that column and the values in the
top row are objective function coefficients.
 Cont…
V. The last column at the right is called the
quantity column. It refers to the right hand
side values (RHS) of the constraints.
VI. There are two more rows at the bottom of the
tableau. The first raw is a Z-row. For each
column the Z – value is obtained by
multiplying each of the number of the column
by their respective row coefficient in column C.
VII. The last raw is Cj-Z row. The values in this row
are also calculated column by column. For
each Column, the value in row Z is subtracted
form the C value in the top row.
 Cont…
3. Determining the Entering Variable:
 For a maximization problem; the entering variable is
identified as the one which has the largest positive value in
Cj-Z row.
 This column corresponding to the entering variable is called
pivot column.
 In a minimization problem, the entering variable is the one
which has the largest negative Cj-Z row value in the simplex
tableau.
4. Determining the Leaving Variable:
 The leaving variable is identified as the one with the smallest
non-negativity ratio for quantity divided by respective
positive pivot columnar entries.
 The row of the leaving variable is pivot row.
 Cont...

5. Drive the Revised Tableau for

Improved Solution
A. Divide each element of the pivot row (including
quantity) by the pivot element to get the
corresponding value in the new tableau. The
divided raw values is called the replacement
row.
B. For each raw other than the pivot raw;
 New row element = old row element – (row
element in pivot column X corresponding
replacement value.)
 Cont…
6. Check for Optimality
 Remark:
 A simplex solution for a maximization
problem is optimal if and only if cj – z row
contains only zeros and negative value (i.e. if
there are no positive values in the cj – z row).
 The simplex solution for a minimization

problem is optimal if Cj-Z row contains only

zero and positive values (Cj-Z ≥ 0).
Note: if the solution is not optimal the steps will
be repeated again and again until the optimal
solution is obtained!
 1. Maximization
Problems
Example: Solve the problem using simplex
method.
 Max Z = 60X +50X
1 2
 Subject to: 4X1+10X2 ≤100
2X1+ X2 ≤ 22
3X1+ 3X2 ≤ 39
 Where; X1, X2 > = 0
 2. Minimization
Problems
 The Big-M Method is a technique, which is used in
removing artificial variables from the basis
 In this method; we assign coefficients to artificial
variables, undesirable from the objective function
point of view
 If objective function Z is to be minimized, then a very
large positive price (called penalty) is assigned to
each artificial variable
 Example
 Minimize Z = 7X1+9X
 Subject to 3X1+6X >= 36
8X1+4X2 > = 64
Where; X1, X2 > = 0
Step 1: Write in Standard Form
 We subtract surplus and add artificial variables
into both constraints and write as follows
Minimize Z = 7X1+9X + 0S1+0S2+MA1+MA2
Subject to 3X1+6X - S1 + A1= 36
8X1+4X2 –S2+A2 = 64
X1, X2 > = 0
Step 2: Initial Tableau
Cj 7 9 0 0 M M
Basic V. X1 X2 S1 S2 A1 A2 Quantity
A1 M 3 6 -1 0 1 0 36
A2 M 1 4 0 -1 0 1 64
Zj 11M 10M -M -M M M 100M
Cj-Zj 7-11M 9-10M M M 0 0
 Step 3: Determine the
Entering and Leaving
Variables
 The entering variable is identified as the
one which has the largest negative Cj-Z row
value in the simplex tableau
 The leaving variable is the smallest positive

ratio in quantity column

 The artificial variables in a minimization

problem will be expressed in the objective

function with a large positive coefficient so
that they are quickly eliminated as we
proceed with the solution
Step 4: Develop Second
Tableau
Cj 7 9 0 0 M
Basic V. X1 X2 S1 S2 A1 Quantity
A1 M 0 9/2 -1 3/8 1 12
X1 7 1 ½ 0 -1/8 0 8
Zj 7 7/2+9/2M -M 3/8M-7/8 M 56+12M
Cj-Zj 0 11/2-9/2M M 7/8-3/8M 0
 Step 5: Develop Third
Tableau
Cj 7 9 0 0
Basic V. X1 X2 S1 S2 Quantity
X2 9 0 1 -2/9 1/12 8/3
X1 7 1 0 1/9 -1/6 20/3
Zj 7 9 -11/9 -5/12 212/3
Cj-Zj 0 0 11/9 5/12
 Step 6: Check of
Optimality
 The third tableau represents a final
tableau since it is the optimal
solution with entirely zeros and non-
negative values in the Cj-Zj row

 Therefore, the optimal solution is: X1

= 20/3 and X2 = 8/3 and value of
objective function is 212/3
 Summary of Extra Variables

Coefficient of Extra Variables Presence of

Types of in the Objective Function variables in the
Extra Variables to be Initial Solution Mix
Constraint
added
Max Z Min Z
<= Add only slack variable (S) 0 0 Yes
>= Subtract surplus variable 0 0 No
(S) and add artificial
variable (A) -M +M Yes
= Add artificial variable (A) -M +M Yes
Special Issues in
Simplex Solution
 1. Non-feasible Solution/ Infeasibility

Example: Minimization Case

C5 8 0 0 M
Basic V. X1 X2 S1 S2 A2 Quantity
X1 5 1 1 -2 3 0 200
X2 8 0 1 1 2 0 100
A2 M 0 0 0 -1 1 20
Z 5 13 2 31-M M 1800 +
C-Z 0 -5 -2 -31 +M 0 200M

Even though all Cj - Zj are positive or 0(i.e. the criterion for an optimal solution in a
minimization case), no feasible solution is possible because an artificial variable (A2) remains
in the solution mix.
 2. Unbounded Solution
Example: Maximization case

C 6 9 0 0
Basic V. X1 X1 S1 S2 Quantity
X2 9 -1 1 2 0 30 30/-1 = -30
S2 0 -2 0 -1 1 10 10/-2 = -5
Z -9 9 18 0 270
C-Z 15 0 -18 0

 The entire ratios turn out to be

negative or undefined, it indicates
that the problem is unbounded.
 3. Degeneracy: Tie for Leaving and
Entering Variables

Example: Tie for Leaving Variables

C 5 8 2 0 0 0
Basic V. X1 X2 X3 S1 S2 S3 Quantity Ratio
X2 8 ¼ 1 1 -2 0 10 10/1/4 = 40
S2 0 4 0 1/3 -1 1 20 20/4 = 5
S3 0 2 0 2 2/5 0 10 10/2 = 5
Z 2 8 8 16 0 0 80
C-Z 3 0 -6 -16 0 0
 Cont…
 If a tie of two entering Variables,
use following rules:
 If there is a tie between two decision
variables, select arbitrary
 If there is a tie between a decision
variable and a slack (or surplus)
variable, select the decision variable to
enter into basis first
 If there is a tie between slack or surplus
variable, select arbitrary
 4. Multiple Optimum
Solution
Example: Maximization problem

C 3 2 0 0
Basic V. X1 X2 S1 S2 Quantity
X2 2 3/2 1 1 0 6
S2 0 1 0 ½ 1 3
Z 3 2 2 0 12
C-Z 0 0 -2 0

 The Cj - Zj value of the non-basic variable (X1)

is 0. Thus, this shows the existence of
alternative optimal solution.
THANK YOU!