MASTERS OF BUSINESS

ADMINISTRATION
OPERATIONS RESEARCH
(MBA641)
CHAPTER 2 - LINEAR MATHEMATICAL PROGRAMMING

1
 LINEAR MATHEMATICAL PROGRAMMING
2.Linear Programming Models
Unit Objectives:
 Recognize problems that can be solved using LP
models.
 Formulate a LP model in mathematical terms.
 Solve Linear Programming Problems (LPP) using
both graphic and simplex approach.
 Explain special cases in both graphic and simplex
techniques.
 Formulate the dual of a problem, read and
interpret the solution to a dual problem, and relate
the dual solution to the prime solution
 Perform sensitivity analysis 2
 LINEAR PROGRAMMING
 Developed by Denting in 1940 for determining solutions to
problems that involved the optimal allocation of scarce
resources.
 LP: is a mathematical process that has been developed to
help management in decision making involving the efficient
allocation of scarce resources to achieve a certain objective.
 LP: is a mathematical technique designed to aid managers
in allocating scarce resources (such as labor, capital, or
energy) among competing activities
 The term linear implies that all the mathematical
relations used in the problem are linear or straight-line
relations, while the term programming refers to the
method of determining a particular program or plan of 3
action.
LINEAR MATHEMATICAL PROGRAMMING
 Linear programming: refers to a family of mathematical
techniques for choosing the best alternative from a set of
feasible alternative, in situations in which the objective
function as well as the constraints can be expressed as
linear mathematical function.
 LP: is a branch of mathematical programming which is
designed to solve optimization problems where all the
constraints as well as the objectives are expressed as linear
function.
 The linear programming technique can be said to have a
linear objective function that is to be optimized (either
maximized or minimized) subject to linear equality or
inequality constraints and sign restrictions on the variables
4
 LINEAR PROGRAMMING
LINEAR PROGRAMMING MODELS
 Linear programming models are mathematical
representations of LP problems. Linear programming models
have certain characteristics in common.
 COMPONENTS OF LP MODELS
 Objective function,
 Decision variables,
 Constraints and
 Parameters.
 ASSUMPTIONS OF LP MODELS
• Linearity (proportionality)
• Divisibility (Continuity)
• Certainty
• Additivity
• Non-negativity 5
LINEAR MATHEMATICAL PROGRAMMING

1) Objective and Objective Function

 The objective in problem solving is the criterion by
which all decisions are evaluated. It provides the
focus for problem solving.
2) Decision variables:
 They represent unknown quantities to be solved for.
The decision maker can control the value of the
objective, which is achieved through choices in the
levels of decision variables.
• For example, how much of each product should be
produced in order to obtain the greatest profit?

6
LINEAR MATHEMATICAL PROGRAMMING

3) Constraints:
 The decision variables in an LP problem is subject to
certain restrictions or limits coming from a variety of
sources. The restrictions may reflect
 Availabilities of resources (e.g., raw materials, labor time,
etc.),
 Legal or contractual requirements (e.g., product
standards, work standards,),
 Technological requirements (e.g., necessary compressive
strength or stretchable strength) or they may reflect other
limits based on forecasts, customer orders, company
policies, and so on.
7
 LINEAR MATHEMATICAL PROGRAMMING
 In LP model, the restrictions are referred to as constraints. Only
solutions that satisfy all constraints in a model are acceptable and
are referred to as feasible solutions.
 The optimal solution will be the one that provides the best value
for the objective function.
 Generally speaking, a constraint has four elements:
 A right hand side (RHS) quantity that specifies the limit for
that constraint. It must be a constant, not a variable.
 An algebraic sign that indicates whether the limit is an upper
bound that cannot be exceeded, a lower bound that is the
lowest acceptable amount, or an equality that must be met
exactly.
 The decision variables to which the constraint applies.
 The impact that one unit of each decision variable will have8
on the right-hand side quantity of the constraint.
 LINEAR MATHEMATICAL PROGRAMMING
 Constraints can be arranged into three groups:
 System constraints – involve more than one decision
variable,
 Individual constraints – involve only one variable, and
 Non-negativity constraints – specify that no variable will be
allowed to take on a negative value. The non-negativity
constraints typically apply in an LP model, whether they are
explicitly stated or not.
4) Parameters
 The objective function and the constraints consist of symbols
that represent the decision variables (e.g., X1, X2, etc.) and
numerical values called parameters.
 The parameters are fixed values that specify the impact that one
unit of each decision variable will have on the objective and on
any constraint it pertains to as well as the numerical value of 9
each constraint
LINEAR MATHEMATICAL PROGRAMMING

ASSUMPTIONS OF LP MODELS
Linearity (proportionality)
 The linearity requirement is that each decision variable has a
linear impact on the objective function and in each constraint
in which it appears.
Divisibility (Continuity)
 The divisibility requirement pertains to potential values of
decision variables. It is assumed that non-integer values are
acceptable.
Certainty
 This requirement involves two aspects of LP models. One
aspect relates to the model parameters, i.e., the numerical
values. It is assumed that these values are known and constant.
 The other aspect is the assumption that all relevant constraints
have been identified and represented in the model. 10
LINEAR MATHEMATICAL PROGRAMMING
Additivity
 The value of the objective function and the total
amount of each resource used (or supplied), must be
equal to the sum of the respective individual
contributions (profit or cost) by decision variables.
Non-negativity
 It assumes that negative values of variables are
unrealistic and, therefore, will not be considered in
any potential solutions. Only positive values and zero
will be allowed and the non-negativity assumption is
inherent in LP models.

11
LINEAR MATHEMATICAL PROGRAMMING
FORMULATING LP MODELS
 Linear programming algorithms (solution techniques) are widely
used and understood and computer packages are readily available
for solving LP problems.
Steps in formulating LP models:
1. Problem definition:
 involves the determination of the specific objective of the linear
programming problem. It is necessary to decide the problem is
maximization or minimization.
2. Identify the decision variables:
 involves the representation of unknown quantity by the letter
3. Formulate the objective function:
 All the decision variable are represented in the objective function
 All terms in the objective function must be inclusive with variables
 The unit of measurement of all coefficients in the objective function
must be the same. 12
LINEAR MATHEMATICAL PROGRAMMING
4. Identify and formulate the constraint:
 Find a mathematical expression that represents any limited
resources or constraints of unknowns.
 Determine appropriate values for the parameters, and determine
whether an upper limit, lower limit, or equality is called for.
 Include any additional constraints on the unknowns that are not
explicitly stated in the problem but are implicitly from the
context of the problem.
 Indicate the non-negativity constraints.
5. Building and validating the model
 Potential sources of information include historical records,
interviews with managers and staff, and data collection.
Validating the model will involve a critical review of the output,
perhaps under a variety of inputs, in order to decide if the
results are reasonable. 13
LINEAR MATHEMATICAL PROGRAMMING

General form of LPM

 The general LPM with n decision variables and m
constraints can be stated in the following form.
Max (Min) Z= c1x1+c2x2+…+cnxn-----objective function
Subject to
a11x1+a12x2+…+a1nxn.(≤ = ≥) b1
a21x1+a22x2+…+a2nxn.(≤ = ≥) b2
 
am1x1+am2x2+…+amnxn.(≤ = ≥) bm
14
x ,x ,x … x ≥ 0 non-negativity
EXAMPLE 1. A firm that assembles computer and computer equipment is
about to start production of two new microcomputers. Each type of
microcomputer will require assembly time, inspection time, and storage space.
The amount of each of these resources that can be devoted to the production of
the micro computers is limited. The manager of the firm would like to
determine the quantity of each microcomputer to produce in order to maximize
the profit generated by the sales of these microcomputers. The manager has
collected the following information from design and manufacturing personnel.
  Type I Type II
Profit per unit $60 $50
Assembly time per unit 4 hours 10 hours
Inspection time per unit 2 hours 1 hours
Storage space per unit 3 cubic feet 3 cubic feet
The manager also has acquired information on the availability of company
resources. The weekly amount are;
Resources Amount available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet
Note: all of the two types of microcomputer that can be produced can be sold. Formulate
15
LPM
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
 The firm wants to maximize their profit by producing the two
type of micro-computer. Therefore, the objective is profit
maximization.
Step2. Identify decision variables
 Based on the statement, the manager would like to determine the
quantity of each microcomputer to produce. The decision
variable are the quantity of each type of computer. thus,
 X1 = quantity of type one mc to produce.
 X2 = quantity of type two mc to produce.
Step3. Determine Objective Function
 The profit per unit of type1 is $60, and type 2 is $50. so the
appropriate objective function is:
Max Z= 60X1 + 50X2
 This is because, each unit of X1 contributes $60 and X2 16
contributes $50 to objective function
 LINEAR MATHEMATICAL PROGRAMMING
Step 4. Identify and formulate the constraints
 Here we have two constraints: structural and non-negativity
constraints. There are three structural constraint of resources with
limited availability: assembly time, inspection time, and storage space.
4X1 + 10X2 ≤ 100 ---------- assembly time
2X1 + X2 ≤ 22 --------------- inspection time
3X1 + 3X2 ≤ 39 ------------- storage space
X1, X2 ≥ 0 -------------------- non-negativity
Step 5. Building and validating the model
Max Z= 60X1 + 50X2
Subject to
4X1 + 10X2 ≤ 100
2X1 + X2 ≤ 22
3X1 + 3X2 ≤ 39 17
LINEAR MATHEMATICAL PROGRAMMING

Example2:
 The agriculture research institute suggested to a
farmer to spread out at least 4800kg of a special
phosphate fertilizer and not less than 7200kg of a
special nitrogen fertilizer to raise productivity of
crops in his field. There are two sources for obtaining
these- mixtures A and B. both of these are available
in bags weighing 100kg each and they cost birr 40
and birr 24 respectively. Mixture A contains
phosphate and nitrogen equivalent of 20kg and 80kg
respectively, while mixture B contains these
ingredients equivalent of 50kg each. Formulate LPM
18
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
 The farmer wants to attain the requirement suggested by
agriculture institute at minimum cost. Therefore, the objective is
cost minimization
Step2. Identify decision variables
 Based on the statement, the farmer would like to determine the
quantity of mixture A and B to be purchase. The decision
variable are the quantity of mixture A and B. thus,
 X1 = quantity of mixture A to purchase.
 X2 = quantity of mixture B to purchase.
Step3. Determine Objective Function
 The cost per unit of mixture A is 40, and mixture B is 24. so
the appropriate objective function is:
Minimize cost= 40X1 + 24X2
 This is because, each unit of X1 costs 40 and X2 Costs 24 to
19
objective function
LINEAR MATHEMATICAL PROGRAMMING
Step 4. Identify and formulate the constraints
 Here we have two constraints: structural and non-negativity
constraints. There are two structural constraint of minimum
requirements suggested by the agriculture institute: Phosphate and
Nitrogen requirement .
20X1 + 50X2 ≥ 4800 -------- Phosphate requirement
80X1 + 50X2 ≥ 7200 -------- Nitrogen requirement
Step 5. Building and validating the model
X1, X2 ≥ 0 -------------------- non-negativity
Min C= 40X1 + 24X2
Subject to:
20X1 + 50X2 ≥ 4800
80X1 + 50X2 ≥ 7200
X1, X2 ≥ 0 20
LINEAR MATHEMATICAL PROGRAMMING
2.1.3 Solving LP Model
 An optimal, as well as feasible solution to an LP problem is
obtained by choosing from several values of decision variables
x1,x2…xn , the one set of values that satisfy the given set of
constraints simultaneously and also provide the optimal
(maximum or minimum) values of the given objective function.
Graphical approach/methods
 Graphical linear programming is a relatively straightforward
for determining the optimal solution to certain linear
programming problems involving only two decision variables.
 Graphical method has the following advantages:
 It is simple
 It is easy to understand, and
21
 It saves time.
Example: Solve the following LPM using graphic approach
Max Z= 60X1 + 50X2
Subject to
AT: 4X1 + 10X2 ≤ 100
IT : 2X1 + X2 ≤ 22
SS: 3X1 + 3X2 ≤ 39
NN: X1, X2 ≥ 0
Graphical solution method involves the following steps.
Steps in graphic solution
1. Plot each of the constraint on the graph
 1st plotting the non-negativity of constraints, the area feasibility for
these two constraint has been shaded in order to plot the remaining
constraint;
 Convert the inequalities in to an equality
 Set x1 = 0, and find the value for x2
 Set x2 = 0, and find the value for x1
 plot the line to the graph 22
Step 2. Identify the feasible region:
 The feasible region is the solution space that satisfies all
the constraints simultaneously. It is the intersection of
the entire region represented by all constraints of the
problem. We shade in the feasible region depending on
the inequality sign.
 If the inequality sign is less than or equal to, it represents
the region of the plane below the plotted line. If the
inequality sign is greater than or equal to, it represents
the region of the plane above the plotted line
Step 3. Locate the optimal solution:
 The feasible region contains an infinite number of points
that would satisfy all the constraints of the problem.
Point that will make the objective function optimum will
be our optimal solution. This point is always found
among the corner points of the solution space.
23
Once the constraints are plotted and feasible region is determined,
we use either of the two graphic methods of Graphic approach to
find a solution for LP model consisting of only two decision
variables: i) The extreme point enumeration method ii) The
objective (Iso-profit or cost) function line approach

24
1)The extreme point approach
 It states that for problems that have a single optimal solution, a
solution will occur at one of the extreme, or corner point. If it has
multiple optimal solutions, at least one will occur at the corner
point.
Steps to be followed
 Graph the possible problem
 Identify the feasible area
 Determine the value of decision variables at each corner point in the
feasible solution space. Some times this can be done by inspection
(observation), usually it is done using simultaneous equation.
 Substitute the values of the decision variable at each corner point in
the objective function to obtain its value at each corner point.
 Select the one with the highest value of the objective function for
maximization problem or the lowest value for minimization problem
at the optimal solution.
25
 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.
 what are the values of decision variables at each corner point?
(Hint: Solve simultaneously those lines which intersected each
other). Can you mention some of the characteristics of the LP
26
graphs consisting of sign? ≤
Example 2: given the LPM:
Min C = 20X1 + 30X2
Subject to:
6X1 + X2 ≥ 12
7X1 + 7X2 ≥ 49
3X1 + 11X2 ≥ 33
X1, X2 ≥ 0
A. Find the optimal values of the decision variables and minimum
cost using both the objective function approach and the extreme
point approach.
B. Determine the amount of surplus associated with each constraint.
Note: surplus is the amount by which the optimal solution causes a
greater than or equal to constraint to exceed the required minimum
amount. It is the amount by which the left-hand side of a constraint
exceeds the right hand side.
27
 Graphical approach/methods
Exercise: solve graphically the following LPM
Minimize C= 3X1 + 5X2
Subject to :
-3X1 + 4X2 ≤ 12
2X1 + 3X2 ≥ 12 Minimize = 40X + 24X ----------Total cost
1 2

2X1 – X2 ≥ -2 Subject to:

20X + 50X ≥ 4800 -------- Phosphate requirement
X1 ≤ 4 : X2 ≥ 2
1 2
80X + 50X ≥ 7200 -------- Nitrogen requirement
1 2

X1, X2 ≥ 0 X, X ≥0
1 2

Maximize Z = 10X1 + 15X2

Subject to :
2X1 + X2 ≤ 26
2X1 + 4X2 ≤ 56
X1 – X2 ≥ -5
X1, X2 ≥ 0 28
 2. The Simplex Method
 The applicability of the graphical method is very limited
in scope. This is due to the fact that it is quite simple to
identity all the corner points & then tests them for
optimality-in the case of a two-variable problem.
 As a result, the graphical method cannot be always
employed to solve the real-life practical Linear
programming models which involve more than two
decision-variables.
 The Simplex method is an iterative or “step by step”
method or repetitive algebraic approach that moves
automatically from one basic feasible solution to another
basic feasible solution improving the situation each time
until the optimal solution is reached at. 29
2. The simplex method
A.Maximization problem with all ≤ constraints
 The simplex method is an algebraic procedure that starts
with a feasible solution that is not optimal and
systematically moves from one feasible solution to
another until an optimal solution obtained.
Steps in solving LPP using simplex method
1. Formulation the LPM of the real world problem
2. Express the mathematical model of LPP in the standard
form by adding slack variables in the left hand side of
the constraints and assign a zero coefficient to these in
the objective function.
3. Design the initial feasible solution. An initial basic
feasible solution is obtained by setting the decision 30
variable to zero.
 2. The simplex method
4. Set up the initial simplex tableau:
List the variables across the top of the table and write the
objective function coefficient of each variable just above it.
There should be one row in the body of the table for each
constraint. list the slack variable in the basic column, one
per row.
In the Cj column, enter the objective function coefficient of
zero for each slack variable.
Compute values for row Zi
Compute values for Cj - Zi; index row/net evaluation row,
used to determine whether or not the current solution is
optimal or not.
31
2. The simplex method
5. Test if the current solution is optimal or not. If the entire element in the
Cj – Zi row (index row) is negative or zeros, then the current solution is
optimal. If there exist some positive number, the current solution can be
further improved.
 Determine the entering variable: identifying the column with the largest
value in the Ci –Zi row of the simplex table. The column with the largest
possible entry in the Cj – Zi row is called key/pivot column. The non-
basic variable at the top of the key column is entering variable that will
replace a basic variable.
 Determine the departing/leaving variable: dividing each number in the
quantity column by the corresponding number in the key/pivot column
selected as entering variable. The row with the minimum positive ratio is
key row/pivot row. The corresponding variable in the key row (the
departing variable) will leave the basis.
 Identify the key/pivot element, the number that lies at the intersection of
the pivot column and pivot row of a given simplex tableau. 32
2. The simplex method
6. Evaluate the new solution by constructing a second
simplex tableau. After identifying the entering and departing
variable, find the new basic feasible solution by constructing
a new simplex tableau from the current one.
7. If any of the numbers in Cj – Zi row are positive, repeat
the steps (5-6) again until an optimal solution has been
obtained.

33
SLACK VERSUS SURPLUS
Slack
 It 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.
Surplus
 IT 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 objective34
function by using coefficients of zero like wise.
Solve the following LPM using simplex method

1. Max Z= 60X1 + 50 X2
Subject to
AT: 4X1 + 10X2 ≤ 100
IT : 2X1 + X2 ≤ 22
SS: 3X1 + 3X2 ≤ 39
NN: X1, X2 ≥ 0
 2. Max Z = 40X1 + 35X2------- Profit
Subject to:
2X1 + 3X2 ≤ 60-------Row material constraint
4X1 + 3X2 ≤ 96-------Labor hours constraint
X1, X2 ≥ 0

35
2. The simplex method
. Max Z= 60X + 50 X +0S +0S +0S
1 2 1 2 3
Subject to
AT: 4X1 + 10X2 +S1 =100
IT : 2X1 + X2 +S2 =22
Initial table SS: 3X1 + 3X2 +S3 =39
NN: all variable ≥ 0
Basic V Cj 60 50 0 0 0 Quantity

X1 X2 S1 S2 S3

S1 0 100
4 10 1 0 0
S2 0 22
36
39
S 0
2. The simplex method
Second table
Basic V Cj 60 50 0 0 0 Quantity

X1 X2 S1 S2 S3

S1 0 56
0 8 1 -2 0
11
X1 60
6
S3 0 1 1/2 0 1/2 0 37
2. The simplex method
Third table
Basic V Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3

S1 0 24
0 0 1 6 -16/3
X1 60 9
1 0 0 1 -1/3
4
X2 50 0 1 0 -1 2/3

Zi 740
60 50 0 10 40/3
Cj-Zi  

0 0 0 -10 -40/3 38