CPU- BUSINESS AND INFORMATION TECHNOLOGY

COLLEGE

ANALYTICAL DECISION MODELING FOR BUSINESS DECISION

CHAPTER TWO : LINEAR PROGRAMING (LP)

BY ; Shewayirga Assalf ( Asst. Prof.)

April,2022
 HISTORY
OF LP

 LP was developed by the Russian mathematician L. V.

Kantorovich in 1939 and extended by the American
mathematician G. B. Dantzig in 1947 at air force.
 The original name for this technique, "programming in a linear
structure," which was later shortened to "linear programming."
 Meaning of LP
 LP is a mathematical technique for choosing the best
alternative from the a set of feasible alternatives.
 Linear programming (LP) problems are optimization problems
where the objective function and the constraints of the
problem are all linear.

 Linear programming is the subject of studying and solving

linear programs.
 Introduction

 Linear Programming(MP) is field of

management
a science or operations research
that finds most efficient way of using
limited resources to achieve the objectives
of a business.

Optimization
Characteristics of Optimization Problems
 One or more decisions

 Restrictions or constraints

e.g. Determining the number of products to

manufacture a limited amount of raw materials

a limited amount of labor

 Objective

– The production manager will choose the mix of

products that

maximizes profits

– Minimizing the total cost

 Expressing optimization problems
mathematically

 Decision variables
X1 , X2 , X3 , … , Xn
e.g. the quantities of different
products
Index n = the number of
product types
f(X1 , X2 , X3 , … , Xn) < b
 Constraints f(X1 , X2 , X3 , … , Xn) > b
– a less than or equal to constraint :
f(X1 , X2 , X3 , … , Xn) = b
– a greater than or equal to constraint :
– an equal to constraint :
 Objective

– MAX(or MIN) : f(X1 , X2 , X3, …,

Xn)
 Mathematical formulation of an
optimization problem

MAX(or MIN) : f(X1 , X2 , X3 , … , Xn)

Subject to:
f(X1 , X2 , X3 , … , Xn) < bm

f(X1 , X2 , X3 , … , Xn) > bm

f(X1 , X2 , X3 , … , Xn) = bm

note : n variables , m
constraints
 Requirements For Application Of Linear Programming

1.The aim or object should be clearly identifiable in mathematical

terms.

2. The activities involved should be represented in quantitative terms.

3. Limited availability/ constraints should be clearly spelt out.

4.The relationships between the objective function and the resource

limitation consideration must be linear in nature.

5.Feasible alternative courses of action should be available to the

decision makers that are determined by the resources constraints.
ASSUMPTIONS UNDERLYING LINEAR PROGRAMMING

1. Proportionality

2. Additivity

3. Continuity

4. Certainty

5. Finite choices

6. Non-negativity
 ADVANTAGES OF LINEAR PROGRAMMING

1. LP helps a decision maker to ensure effective use of

scarce resources

2. LP techniques improve the quality of decision making.

3. It generates large number of alternate solutions

4. This technique can also cater for changing situations. The

changed conditions can be used to readjust the plan decided for
execution and so on.
 Model formulation
 A linear programming model consists certain common
of components and characteristics.
 Components of LPM:
 decision variables,
 an objective function, and which consists d/t DV and parameters

 model constraints,

Decision variables are mathematical symbols that represent levels of

activity by the firm.
 Contd

 The objective function is a linear relationship that reflects

the objective of an operation.
 The objective function always consists of either
maximizing or minimizing some value (e.g., maximize
the profit or minimize the cost of producing items).
 A constraint is a linear relationship that represents a
restriction on decision making.
 Parameters are numerical values that are included in the
objective functions and constraints.
 STEPS IN FORMULATION OF LP PROBLEMS

There are three basic steps in formulation of LPM

Step 1 : define the decision variables

how many x1, x2, x3……xn to produce

Step 2 : define the objective function

maximize profit or minimize a cost

Step 3 : define the constraints

resources available to produce

something
 A maximization model example
X Company is a small crafts operation run by an American natives. The
company employs skilled artisans to produce clay bowls and mugs with
authentic Native America designs and colors. The two primary resources used
by the company are special pottery clay and skilled labor. Given these limited
resources, the company desires to know how many bowls and mugs to produce
each day in order to maximize profit.
The two products have the following resource requirements for production and
profit per item produced (i.e., the model parameters):
Resource Requirements
Required:
formulate
product Labor (hr/unit) Clay (lb/unit) Profit/unit
linear model
Bowl 1 4 40
Mug 2 3 50
There are 40 hours of labor and 120 pounds of clay available each day for
production.
 Summary of LP Model Formulation Steps
Step 1. Define the decision variables

How many bowls and mugs to produce

Step 2. Define the objective

function Maximize profit

Step 3. Define the constraints

The resources (clay and labor) available

 Solution
o Decision Variables

how many bowls and mugs to produce

X1: numbers of bowls to produce

X2: numbers of mugs to produce

o The Objective Function

maximize total profit

maximize Z
= $40x1 +
50x2
Where,
Z= total profit
per day
 Contd
 Class work
 DeReal wood co., produces wooden soldiers and trains. Each soldier sells
for $27, uses $10 of raw materials and takes $14 of labor& overhead costs.
Each train sells for $21, uses $9 of raw materials, and takes $10 of
overhead costs. Each soldier needs 2 hours finishing and 1 hour carpentry;
each train needs 1 hour finishing and 1 hour carpentry. Raw materials are
unlimited, but only 100 hours of finishing and 80 hours of carpentry are
available each week. Demand for trains is unlimited; but at most 40 soldiers
can be sold each week. How many of each toy should be made each week
to maximize profits.
 Answer
 Decision variables completely describe the decisions to be
made (in this case, by DeReal). DeReal must decide how
many soldiers and trains should be manufactured each
week. With this in mind, we define:
 x1= the number of soldiers produced per week,
 x2= the number of trains produced per week,
 Contd
 Objective function: maximizing the total weekly profit (z).

Here, profit equals to (weekly revenues) – (raw material

purchase cost) – (other variable costs).
 Weekly profit from soldiers toys: 27-(10+14)= 3
 Weekly profit from Train: 21-(9+10)= 2

Hence DeReal’s objective function is:

Max z = 3x1+ 2x2

 Cont
 Constraints: Here there are three
constraints:

 Finishing time per week

 Carpentry time per week
 Weekly demand for soldiers

non-negative values: (DeReal can not manufacture

negative number of soldiers or trains!)
 Contd
 The complete Linear Programming (LP) problem

Max z = 3x1+ 2x2 (The Objective function)

st: 2x1+ x2 ≤100 (Finishing

constraint) x1+ x2 ≤80(Carpentry

constraint)
x1 ≤40 (Constraint on
demand for soldiers)

x1, x2 >0 (Sign

restrictions)
 A minimization model example
 A farmer is preparing to plant a crop in the spring and needs to
fertilize a field. There are two brands of fertilizer to choose from,
Super-gro and Crop-quick. Each brand yields a specific amount of
nitrogen and phosphate per bag, as follows:
Chemical contribution
Brand Nitrogen (lb/bag) Phosphate (lb/bag)
super-gro 2 4
Crop-quick 4 3

The farmer's field requires at least 16 pounds of nitrogen and 24 pounds of

phosphate. Super-gro costs $6 per bag, and Crop-quick costs $3. The farmer
wants to know how many bags of each brand to purchase in order to minimize
the total cost of fertilizing.
Summary of LP Model Formulation Steps
Step 1. Define the decision variables

How many bags of Super-gro and Crop-quick to buy

Step 2. Define the objective

function Minimize cost

Step 3. Define the constraints

The field requirements for nitrogen and phosphate

 Contd
 Decision Variables

x1 = bags of Super-gro

x2 = bags of Crop-quick
The Objective
Function

minimize Z = $6x1 + 3x2

where

$6x1 = cost of bags of

Super-gro
 Contd

 Class work
 DeReal makes luxury cars and jeeps for high-income men and
women. It wishes to advertise with 1 minute spots in comedy
shows and football games. Each comedy spot costs 50birr and is
seen by 7M high-income women and 2M high-income men.
Each football spot costs 100birr and is seen by 2M high-income
women and 12M high-income men. How can DeReal reach
28M high-income women and 24M high-income men at the
least cost.
 Answer:
 The decision variables are

x1 = the number of comedy spots

x2 = the number of football spots.

 Giving the problem
 min z = 50x1 + 100x2

St:7x1 + 2x2 ≥ 28

2x1 + 12x2 ≥

24

x1, x2 ≥ 0
 Home work
 A company is making two products A and B. The cost of
producing one unit of product A and B is $ 60 and $ 80
respectively. As per the agreement, the company has to supply at
least 200 units of product B to its regular customers. One unit of
product A requires one machine hours whereas product B has
machine hours available abundantly within the company. Total
machine hours available for product A are 400 hours. One unit of
each product A and B requires one labour hour each and total of
500 labour hours are available. The company wants to minimise
the cost of production by satisfying the given requirement.
Formulate the problem as a linear programming problem.
 LP:
Graphical method
Solution of Linear Programming Problems

 The linear programming problems can be

solved to determine optimum strategy by
two methods- Graphical and Simplex
method.
 GRAPHICAL METHOD

 Graphical method is suitable when there are only two

decision variables. Models with three decision variables
can be graphed in three dimensions, but the process is
quite cumbersome, and models of four or more decision
variables cannot be graphed at all.
 STEPS IN GRAPHICAL METHOD

Step I. Formulate the LP Problem as explained in previous class.

Step II. Convert the inequalities in to equalities to obtain

graphical form of the constraints. (Draw the line of each

constraint, first putting x1=0 to find the value of x2 and then

putting x2=0 to find the value of x1.

 Then draw the line for the values of x1 and x2 which represents

the particular constraint. Once the lines are drawn for all

the constraints, identify the

feasible polygon (area) by shading the area below the line for the
 Contd

Step III. Identify the extreme points of the feasible polygon and
name the Corners.

Step IV. Evaluate the objective function Z or C for all points of

feasible region.

Step V. In case of maximizing objective function Z, the corner

point of feasible region giving the maximum value of Z becomes
the value of decision variables. Similarly in minimizing case, the
point of minimum value of C gives the answer.
 Example 1 (problem of Maximizing Z)

 Two commodities P1 and P2 are to be produced. The profit Margin on P1

is $ 8 and on P2 is $ 6. Both the commodities are required to be

processed through two different machines. Sixty hours of time are

available on I machine and forty eight hours of time are available on II

machine. One unit of P1 requires 4 hours of time in machine I and 2

hours of time on machine II. Similarly, one unit of P2 requires 2 hours of

time on machine I and 4 hours of time on machine II. Determine the

number of units of P1 and P2 to be produced in order to maximize the

profits using graphical method?

 solution
Step I. Formulate LP Problem.
The information available can be put into structural matrix form as
follow. Commodities
Requirement Tota
P1 P2
l
Machine I 4 2 60
Machine II 2 4 48
Profit $ per unit 8 6 -

Let x1 be number of units to be produced for P1

DV
Let x2 be number of units to be produced for

P2 X1 and X2 are unknown decision variables.

Max Z= 8x1 + 6x2 Objective Function
st: 4x1 + 2x2 < 60
Resource constraints
2x1 + 4x2 <
48x1, x2 > 0 non-negativity
 contd
Step II. Convert constraint inequalities in to equalities, draw respective lines
and

determine feasible polygon (area).

 Taking constraint (i)

4x1 + 2x2 = 60 ∴ 4x1= 60 or x1 =15
X1 X 2
0 30
∴ 2x2 = 60 or x2 = 30
15 0
By these coordinates (15,30) we get line BD in graph. Similarly, taking constraint
(ii).

2x1 + 4x2 = 48 X 1 X2
∴ 2x1= 48 or x1 =24
0 12
24 0 ∴ 4x2 = 48 or x2 = 12

 By these coordinates (24,12) we get line AE in

graph.
 contd

 Now, any point on line BD satisfies (i) constraint and

any point on line AE satisfies (ii) constraint. The
constraints cannot be violated, they must be satisfied.
Any solution which satisfies all the know constraints is
called optimal solution. Since both the constraints are of
the type < hence any point on the right hand side (RHS)
of BD or AE becomes infeasible area/solution for which
we are not concerned.
 Contd

Feasible
region
 contd
 Step III. Both the constraints are to be satisfied
simultaneously, therefore, OACD becomes the region of
feasible solution. This is also known as feasible polygon.
 On line OA, point A give maximum profit, on line OD, point
D gives maximum profit.
 contd

Step IV. Evaluate the objective function Z= 8x1 + 6x2 for all points of
feasible region i.e. O,A,C,D.
At point O profit is ∴ Z=O
zero
∴ Z=12x6=72
At point A x2=12, x1=0
∴ Z=15x8=120
At point D x1=15, x2=0
∴
At point C x1=12, x2=6 Z=12x8+6x6=132

(from graph)
Step V. Z is maximizing objective function, hence the point with maximum
value of Z is the optimal solution point.

Therefore at point C (Z=132) with x1=12 and x2=6 is the optimal point.
 A maximization model (class work)
X Company is a small crafts operation run by an American natives. The
company employs skilled artisans to produce clay bowls and mugs with
authentic Native America designs and colors. The two primary resources used
by the company are special pottery clay and skilled labor. Given these limited
resources, the company desires to know how many bowls and mugs to produce
each day in order to maximize profit.
The two products have the following resource requirements for production and
profit per item produced (i.e., the model parameters):
Resource Requirements Required:
formulate linear
model,
product Labor (hr/unit) Clay (lb/unit) Profit/unit graphically solve
Bowl 1 4 40 ,
the optimum
find
point
Mug 2 3 50
There are 40 hours of labor and 120 pounds of clay available each day for
production.
 answer

 Contd X2
The labor constraint area

60

50
 Letting X1 and solving for X2
40
Let’s first consider labor constraint line first
30
1(0)+2X1=40 20
X2= 20 10

1X1+2(0)=40 X1
0 60
10 20 30 40 50
X1=40 (40,20) X2
The constraint area for clay
Then, let’s consider clay constraint 60

4(0)+3X2=120 50

40
X2=40
30
4X1+3(0)= 120 20
X1=30 10

( 0
X1
10 20 60
3 30 40 50
 Contd
The feasible solution area is an area on the graph that
is bounded by the constraint equations.
X2

60

50

40
Common area to both constraints
30

20

10
X1
0 10 20 30 40 50 60
 The Optimal Solution Point

 After plotting the graph, the next step in graphical solution

method is locate the point in the feasible solution are that will
result in the greatest total profit.
 Contd
Let’s assign letters to each corner

X2 0ABC are the feasible region

60

50

40

4X1+3X2=120
A
30

20

10
B 1X1+2X2=40

C X1
0 10 20 30 40 50 60
Calculate the value of each corner (O, A, B and C) to get
the optimal solution

 Max Z= $40X1+$50X2
 At point 0, Profit is 0 (substitute both X1 and X2 by 0 in the OF)
 At point A, profit is 1000 (substitute X1 by 0 and X2 by 20)
 At point B, profit is 1360 (substitute X1 by 24 and X2 by 8)
 At point C, profit is 1200 (substitute X1 by 30 and X2 by 0)
 Thus the optimal solution is point be (the firm should produce
24 bowls and 8 mugs so as to meet its objective).
 Contd
Let’s assign letters to each corner

X2 0ABC are the feasible region

60

50

40

4X1+3X2=120 Optimum solution

A
30

20 The optimal solution is

10
B 1X1+2X2=40
the best feasible solution.

C X1
0 10 20 30 40 50 60
 LP: Cost Minimization

 A minimization problem minimizes the value of

objective function rather the maximizing
than
Minimization problems generally involve finding it.
the least-
cost way to meet a set of requirements.
 Problem of Minimizing C

Minimize C= 50x1 + 20x2

Subject to
2x1 – x2> 0
x1 + 4x2 > 80 0.9x1 + 0.8x2
>40
Where x1 ,x2 > 0 non-
negativity condition.
 Solution:

 The first step is skipped as LP problem is already

formulated. We will follow other steps simultaneously. In
constraint (i) 2x1 –x2 > 0 there is no constant value, hence
it must pass through the origin. First convert it into
equality.

2x1 –x2 > 0 . Now give x1 any arbitrary value.

When x1 =0, x2=0

x1 =1, x2=2

x1 =2, x2=4 and so on.

 contd

 We draw the line with these coordinates and get line I drawn in the graph
passing through origin.
 Now, convert constraint (ii) in equality
x1 + 4x2 = 80
When x1 =0, x2=20
X2 =0, x1=80
 We draw the line II (80, 20) as shown
in graph.
 Now, convert constraint (iii) in equality
0.9x1 + 0.8x2 =40
 When x1 =0, x2=50
X2 =0, x1=44.4
 We draw line III (44.4, 50) as shown in
graph.
contd
 contd

 For feasible area we need to examine all the there constraints

equations (Note, all are > type)

 In equation (i) if we move vertically upward, meaning x1=o and

x2 increasing, the equation becomes negative or less than, which
is not permitted. Hence feasible area should be on RHS.
 In equation (ii), the feasible area should be above the line
because it is greater than the sum of x1 and x2.

 Similarly in equation (iii) it is on the RHS therefore feasible area

(region) is indicated by three rows or shading and extends upto
infinity.
 Contd
 Now we have to find out different values of Z at different corner
points, B,C,E by finding out their coordinates (x1, x2) then putting
them in objective function Z. The point which gives the
minimum value is the answer.
At corner B x1=16,x2=32 therefore Z= 1440

At corner C x1=34.4,x2=11.4 therefore Z= 1948

At corner x1=80,x2=0 therefore Z= 4000

From
E the above we can see that minimum value of Z is at point B
where x1=16 and x2 =32 and hence it is the answer.
 Class exercise
feeding farm animals.

 Animals need:

 14 units of nutrient A, 12 units of nutrient B, and 18 units of nutrient

C.

Two feed grains are available, X and Y.

 A bag of X has 2 units of A, 1 unit of B, and 1 unit of C.

 A bag of Y has 1 unit of A, 1 unit of B, and 3 units of C.

 A bag of X costs $2. A bag of Y costs $4.

 Required: 1. Minimize the cost of meeting the nutrient requirements.

2. Solve the problem graphically

3. Find the optimal solution in the graph

 Answer

Feed Nutrients cost
grains A B C

X 2 1 1 2
Y 1 1 3 4
Total 14 12 18
needs
 Change inequalities in to equalities

X1 X 2 X1 X2
0 14 X 1 X2
0 12
7 0 12 0 0 6
18 0

(7, 14) (12, 12) (18, 6)

 Plot the graph
X2
14 A 2X1+X2= 14

12

10
2X1+X2= 14
B
8

4 C
2X1+X2= 14
2
D
0 X1
2 4 6 8 7 10 12 14 16
18
 Optimum solution

 Special Cases in Graphical solution
1. Redundant Constraint
• If a constraint when plotted on a graph doesn’t
form part of the boundary making the feasible
region of the problem that constraint is said to be
redundant.
• Example:
 Cont..
2. Multiple optimal Solutions
• /Alternative optimal solutions/
• -This is a situation where by a LPP has more than one optimal
solution.
• Multiple optimal Solutions will be found if two corers give optimal
solution, then the line segment joining these points will be the
solution.
 Contd….
• ==>We have unlimited number of optimal solution with out increasing or decreasing
the objective function.
•  
• Example:
• The information given below is for the products A and B.
• _____________________________________________________________________
Machine hours per week Maximum available
• Department Product A Product B per week
• _____________________________________________________________________
•  Cutting 3 6 900
• Assembly 1 1 200
• Profit per unit $8 $16
• _____________________________________________________________________
• Assume that the company has a marketing constraint on selling products B and
therefore it can sale a maximum of 125units of this product.
 Contd…
• Required:
a. Formulate the LPP of this problem
b. Find the optimal solution
Solution:
• Let X1 =The No of units f product A produced
per week
• X2 =The No of units f product B produced per
week
• The LPP Model of the problem is:
 
Contd…
 contd…..
Corners Coordinates MaxZ=8 X1 + 16X2
A (0, 0) 0 
B (0, 125) 2000
C (50, 125) 2400 
D (100, 100) 2400
E (200, 0) 1600 
Interpretation:
Both C and D are optimal solutions. Any point on the line segment CD will also lead to the same optimal solution.
==>Multiple optimal solutions provide more choices for management to reach their objectives.  

3. Infeasible Solution
A solution is called feasible if it satisfies all the constraints and the constraints and non-negativity condition.
However, it is sometimes possible that the constraints may be inconsistent so that there is no feasible solution to the
problem. Such a situation is called infeasibility.
Example:
MaxZ=20X1+30X2
St:
2X1+X2< 40
4X1+X2< 60
X1 > 30
X1, X2 > 0
Solution:
contd……
Simplex

method
 Simplex method of solving LP
 When a large number of variables (more than 2) are involved
in a problem, the solution by graphical method is difficult/ not
possible.
 The simplex method provides an efficient technique which
can be applied for solving LPPs of any magnitude, involving
two or more decision variables.
 In this method, the objective function is used to control the
development and evaluation of each feasible solution of the
problem.
 The simplex Algorithm is an iterative procedure for
finding, in a systematic manner, the optimal solution that
comes from the corner points of the feasible region.
 Simplex algorithm considers only those feasible solutions
which are provided by the corner points and that too not all
of them.
 It is very efficient algorithm.
 The technique also has the merit to indicate whether a
given solution is optimal or not.
 Was formulated by G.B. Dantzig in 1947.
 Forapplication of simplex method, following conditions must
be satisfied.
• Right Hand Side (RHS) of each constraint should be non-negative.

In case of negative RHS, the whole solution (inequality) to be

multiplied by-1.
• Each of the decision variables of the problem should be non-

negative. In case of ‘unrestricted’ variables it is treated as the

difference of two non-negative variables-such as xl, x2 > 0, x3
unrestricted can be written as xl, x2, x4, x5 > 0, where x3 = x4 –x5 ,
After the solution is reached, we substitute difference of x4 and x5 as

x3.
 Basic Definitions
Before using the simplex method, let us examine and understand certain
basic terms involved in the procedure.

1.Standard Form: This has already been clarified in the initial part of this
chapter. With linear relationships of objective function and constraints,
making RHS of constraints as equal produces standard form, whereas the
inequality situation is called canonical form.

2.Slack and Artificial Variables: These have also been explained under
an appropriate heading. Their physical significance have also been
clarified. These are generally designated as S1, S2 . . . . etc. and A1, A2 etc.
respectively. Whereas the slack variables indicate spare capacity of the
constraints, artificial variables are imaginary variables added for
standard form.
3. Surplus Variable: A variable subtracted from the left hand side of a greater
than or equal to constraint to convert the constraint into equality. Physical
sense or interpretation of the surplus variable is that it is amount of resource
over and above the minimum required level. In case the constraint inequality
is of the type "less than or equal to", then it is called slack variable.

4. Basic Solution: There may be n variables and m constraints in a linear

programming problem. When we evaluate the solution of this problem by
setting (n - m) of the variables to zero and solve the other m variable
equations, we obtain a unique solution. It is called "Basic Solution".
 5. Basic Feasible Solution: When a basic solution satisfies even the non-
negativity requirement is called Basic Feasible Solution. Since it has to be
within the feasible region as explained in the graphical method, a basic
feasible solution corresponds to a corner point of the feasible region.
6.Simplex Table: A table used for calculations during various iterations of the
simplex procedure, is called Simplex table.

7.Variable Mix: The values of the column that contains all the variables in the
solution.
8. Basis: The set of variables which are not set to zero and
figure in the column of "Product Mix" are said to be in the
'Basis'. Other than these figuring in the product mix column
are termed as non basic variables.

9. Iteration: Since the simplex procedure is that of constant

improvement type from one basic feasible solution to another,
these steps of moving from one solution to another to reach
optimal solution are called Iterations.
10. Cj Row: It is the row containing the coefficients of all the variables
(decision variables, slack or artificial variables) in the objective function.

11. Constraints: Restrictions on the problem solution arising from limited

resources.

12.Cj - Zj = ∆j or Index Row: The row containing net profit or loss resulting
from introducing one unit of the variable in that column in the solution. A
positive number in the ∆j row would indicate an algebraic reduction or
increment in the objective function if one unit of the variable of that column is
introduced in the basis.
13.Pivot -Column: The column with the largest positive number in Cj - Zj row
in a maximization problem or the smallest number in a minimization problem
is called Pivot column. This indicates the variable entering the solution in the
next iteration by replacing an appropriate variable.

14.Pivot Row: When we work out the ratio of quantities bi's and the elements
of the Pivot column, we get the last column of the simplex table. The
outgoing variable to be replaced by the entering variable (decided by the
key row) would be the one with the smallest positive value of the ratio
column.
15. Pivot Element: The element at the point of intersection of
the key column and the key row is called the Pivot element.

16: Optimal Solution: The best of all feasible solutions.

17: Linear Function: A mathematical expression in which a

linear relationship exists amongst various variables.
 Standard form of LP Problem:

 In order to develop a general procedure for solving any linear

programming (LP) problem, we first introduce the standard
form. Let us assume the decision variables as x1, x2, x3 . . . xn
such that the objective function (Linear) of these variables
assumes an optimum value, when operated under the given
constraint of resources. Thus, the standard form of LPP can be
written as follows.
Objective Function
 Optimise (Maximise or minimise) Z = C1 x1 + C2 x2 + . . .+ Cn xn

 where Cj (j = 1,2,. . . . . . . . . n) are called cost coefficients.

 Constraints (linear)
St: a11 x1 + a12 x2 + a1n xn = b1

a21 x1 + a22 x2 + a2n xn = b2

.........................

aml x1+ am2 x2 + amm xn = bm.

Where bi (i = 1, 2…m) are resources constraints and constants aij (i =

l,2,….m; j = 1,2,…..n ) are called the input output coefficients.
The decision variables are required to be non-negative so that they can
contribute towards the optimum objective function, which is either
maximization or minimization type.
 Slack and Artificial variables :
Normally constraints are in the form of inequalities or equalities, when constraints
are in the inequality form, we use imaginary variables to remove these inequalities
and convert the constraint to equation form to bring in deterministic nature of
resources.

 When the constraints are of the type < bi, then to convert the it into equality we
need adding some variable (not constant) this is normally done by adding
variables such as S1, S2. . . . . Sn, which are called slack variables. In physical
sense, these slack variables represent unused resources, the slack variables
contribute nothing towards the objective function and hence their coefficients in
the objective function are to be zeros.
  Thus, to illustrate the above concept,

 Constraints ailxl + ai2x2. . . . < bi ; i = 1,2,.

.m(Canonical form)
.ainxn

 Can be written as ail x1….ain xn + Si = bi ; i = 1,2,. .

m(Standard form)

And the objective function can be written as

 Max. or Min. Z = c1 x1 + c2 x2 + . . . . . cn xn + 0S1 + 0S2 + ......
 Similarly for the constraints of the type ≥, the addition of slack variables has to
be in the form of subtraction. Thus, equation of constraints can be written as
 ai1 x1 + ai2 x2 +….ain xn - Si = b I ; i = 1,2,…….m

 To bring it to the standard form, we add another variable called artificial

variable (Ai), as follows:

 ai1 x1 +ai2 x2 +. . . . . . . ainxn- Si + Ai = bi ; i = 1, 2, 3,. . . . . . . . m

 This is done to achieve unit matrix for the constraints. But artificial variables
can not figure in the solution as there are artificially added variables and have
no significance for the objective function. These variables, therefore, are to be
removed from the solution.
 Standardization/Tableau Form/

Types of constraint Standard form

≤ Add a slack variable

= Add an artificial
≥ variable
an artificial variable subtract a surplus
variable and add
 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
2. Develop an initial simplex tableau

Steps in developing initial simplex

i. tableau:
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.

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. The last row is Cj-Z row.
 The values in this row are also calculated column by
column. For each Column, the value in row Zj is subtracted
form the Cj value in the top row.
3. Interpreting the initial simplex tableau

4. 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. The column
which corresponds to the entering variable in the simplex tableau
is

called pivot column.

In a minimization problem, the entering variable is identified as the

one which has the largest negative Cj-Z row value in the
simplex
5.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.

6.Make the entering variable basic and the leaving non- basic by
applying elementary row operations of matrix algebra.
7. Iteration for improved solution:

(a)Replace outgoing variable with the entering variable

and enter relevant coefficients in Zj column.

(b)Compute the, Pivot row with reference to the newly entered

variable by dividing the old row quantities by the key element.

(c)new values for the other rows. In the revised simplex table,
all the other rows are recalculated as follows.

New row elements= Elements in the old row

[corresponding key column element -
multiplied
corresponding new element of the revised row at (b) above.]
by the
(d)The same procedure is followed for modification to bi
column also.

(e)Having obtained the revised simplex table, evaluate ∆j =

Cj -Zj and test for optimality as per step 3 above.
8. 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).
(a) Obtaining Optimal Solution- If the table indicates
optimality level by examining ∆j or index row, the iteration
stops at this point and values of bi's for corresponding
variables in the product mix column will indicate the values of
the variables contributing towards the objective function. The
value of the objective function can be then worked out by
substituting these Values for corresponding decision variables.
 (b) If the solution is not optimal, proceed to Step 9.
9. Revise or improve the Solution-For this purpose, we repeat
Step 4 to Step 7 till optimality conditions are fulfilled and
solution is obtained.
 Rule for Ties. Whenever two similar values are
encountered in index row or ratio column, we select any
column or ratio, but to reduce computation effort,
following can be helpful.
(a) For key column, select the left most tie element.
(b) For ratio, select nearest to the top.
 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.

Note that: if the solution is not optimal the steps will be

repeated again and again until the optimal solution is
obtained!
 Simplex Algorithm-
Maximization Problem
A. Simplex Algorithm-Maximization Problem
Solve the following problem by simplex method.
Max. Z = 8x 1 + 16x2
Subject to, x1 + x2 < 200
x2 < 125
3x1 + 6x2 < 900
x1, x2 > 0
 Solution
 We convert the inequality into equations by adding slack variables. Above
statements can thus be written as follows.
x1 + x2 + S1 = 200
x2 + S2 = 125
3x1 + 6x2 + S3 = 900 and
x1, x2, S1, S2, S3 > 0.
where S1,S2, S3 are slack variables and objective
function is re-written as:
Max. Z = 8x1 + 16x2 + 0S1 + 0S2 + 0S3

Now there are five variables and three equations and hence to obtain the
solution, any two variables will have to be assigned zero value. Moreover, to get
a feasible solution, all the constraints must be satisfied.
 To start with, let us assign x1 = 0; x2 = 0 (Both decision variables are assigned
 This can be written as initial simplex table 1

Unit Cj 8 16 0 0 0 Ratio
profi
t BV Q X1 X2 S1 S2 S3 Q/aij
(Zj)

0 S1 200 1 1 1 0 0 200/1=200 LV
0 S2 125 0 1 0 1 0 125/1=125
0 S3 900 3 6 0 0 1 900/6= 150
Zj 0 0 0 0 0 0
Cj-Zj 8 16 0 0 0
EV
Key No.
Where: EV= entering variable (Key
column) LV= leaving variable (key
row)
 Entering variable

Since Cj - Zj is maximum at 16, i.e., profit is more for each unit for x2
variable, we introduce x2 into the solution. It is the marked as key column and
x2 becomes the entering variable. Dividing Quantities (bi's) by the
corresponding key elements of each row, we obtain the ratio (Q/aij) column
such as for row S1, it is 200 ÷ 1 = 200, S2= 125 and S3=150.

 Leaving variable

The leaving variable is, the row which has least ration (Q/aij), here, S2 has 125
ratio which small compare to other BV, it will be replaced by X2.
  Now each of the elements of the Key row is divided by Key element to
get x2 row in the new table. Thus we get the key row as follows:
Unit profit Q X1 x2 S1 S2 S3
16 125/1 0/1 1/1 0/1 1/1 0/1
125 0 1 0 1 0

In order to obtain the corresponding values of the table, we follow

the relationship as follows:
New row= old row – corresponding coefficient new tableau
in pivot column

row value
Q X1 X2 S1 S2 S3

For S1, 200- 1-(1x0)=1 1-(1x1)=0 1-(1x0)=1 0-(1x1)=-1 0-(1x0)=0

row (1x125)=75

For S3 900- 3-(6x0)=3 6-(6x1)=0 0-(6x0)=0 0-(6x1)=-6 1-(6x0)=0

Arranging these values into the simplex table, we obtain:

revised simplex table II

Zj Cj 8 16 0 0 0
variable Q x1 x2 s1 s2 S3
0 S1 75 1 0 1 -1 0
16 X2 125 0 1 0 1 0

0 S3 150 3 0 0 -6 1
Zj 2000 0 16 0 16 0
Cj-Zj 8 0 0 -16 0

Since the Cj-Zj row is contains positive value it is not

optimal, as a result we have to revise the tableau to reach
the optimal solution
 Lets identify the Ev and Lv
Zj Cj 8 16 0 0 0 Q/aij
variable Q x1 x2 s1 s2 S3
0 S1 75 1 0 1 -1 0 75/1=75
16 X2 125 0 1 0 1 0 125/0=∞

Key row
0 S3 150 3 0 0 -6 1 150/3=50
Zj 200 0 16 0 16 0
0
Cj-Zj 8 0 0 -16 0

Key
column
  Now each of the elements of the Key row is divided by Key element to
get x2 row in the new table. Thus we get the key row as follows:
Unit profit Q X1 x2 S1 S2 S3
8 150/3 3/3 0/3 0/3 -6/3 1/3
50 1 0 0 -2 1/3

In order to obtain the corresponding values of the table, we follow

the relationship as follows:
New row= old row – corresponding coefficient new tableau
in pivot column

row value
Q X1 X2 S1 S2 S3

For S1, 75-(1x50)=25 1-(1x1)=0 0-(1x0)=0 1-(1x0)=1 -1-(1x-2)=1 0-(1x1/3)=

row -1/3

For X2 125-(0x50)= 0-(0x0)=0 1-(0x1)=1 0-(0x0)=0 0-(0x-2)=0 0-(0x1/3)

Arranging these values into the simplex table, we obtain:

revised simplex table III

Zj Cj 8 16 0 0 0
variable Q x1 x2 s1 s2 S3
0 S1 25 0 0 1 1 -1/3
16 X2 125 0 1 0 1 0

8 X1 50 1 0 0 -2 1/3
Zj 2400 8 16 0 0 8/3
Cj-Zj 0 0 0 0 -8/3
Now, all the values of ∆j being zero or negative, suggesting that the
solution is optimal and Z = 2,400 for x1 = 50 and x2 = 125. S1 indicates
surplus.
 Class work
 Maximise Z = 30x1 + 40x2
Subject to, 60x1 + 120x2 < 12,000
8x1 + 5x2 < 600
3x1 + 4x2 < 500
x1, x2 > 0
Answer
X = 200/11
1

X =1000/11
2

Profit=
 Simplex Algorithm-
Minimization problem
 B. Simplex Algorithm- Minimization problem
 Some of the important aspects of minimization problem

1. Artificial variables have no economic significance

• Introduced only to bring in the standard form of simplex method.
• Need be removed from the solution as soon as they become non-
basic.

2. Since these variables are added for computation purpose only,

• ensure their zero value in the optional solution.
• This can be done by assigning very large penalty (+M) for a
minimisation problem, so that these do not enter the solution.
3.If artificial variables cannot be removed from the solution,
then the solution so obtained is said to be Non-Feasible. This
would indicate that the resources of the system are not
sufficient to meet the expected demand.

4. Equality Constraints also can be handled by using artificial

variables to obtain initial solution.
 Big M-Method
 In this method, we assign the coefficients of the artificial
variables, as a very large positive penalty i.e., +M
therefore called Big M-method.
 The Big M-method for solving LP problem can be adopted
as follows:

Step 1 : The standard simplex table can be obtained

by
adding slack and artificial variables.
 Slack variables are assigned zero coefficients and artificial
variables assigned +M coefficients in the objective
function.

Step 2: We obtain initial basic feasible solution by assigning

zero value to the decision and slack variables.
Step 3: Initial basic feasible solution is obtained in the form
of the simplex table as above and then values of ∆j = Cj - Zj
are calculated.
 If ∆j ≥0, then the optimal solution has been obtained.
 If ∆j< 0, then we select the largest negative value of ∆j and
this column becomes the key column indicating the
entering variable.
Step 4: Determine the key row as in case of maximisation
problem i.e., selecting the lowest positive value of the ratio Q
or bi/aij, obtained by dividing the value of quantity bi by
corresponding element of the key column.
 Step 5: Repeat steps 3 and 4 to ensure optimal solution
with no artificial variable in the solution. If at least one
artificial variable is present in the basis with zero value and
coefficient of M in each Cj - Zj values is negative, the LP
problem has no solution. This basic solution will be
treated as degenerate.
 A tie for the pivot row is broken arbitrarily and can
lead to
degeneracy.
 If at least one artificial variable is present in the basis
with positive value, and coefficient of M in each Cj - Zj
values is non-negative, then LP problem has no optimal
basic feasible solution. It is called pseudo-optimum
solution.
 Example
 Food A contains 20 units of vitamin X and 40 units of
vitamin Y per gram. Food B contains 30 units each of
vitamin X and Y. The daily minimum human requirements
of vitamin X and Y are 900 and 1200units respectively.
How many grams of each type of food should be
consumed so as to minimise the cost, if food A costs 60
cents per gram and food B costs 80 cents per gram.
 Solution:

 LPP formulation is as follows

Min. Z = 60x1+ 80x2 (Total Cost)

Subject to, 20x1 + 30x2 > 900 (Vitamin X Constraint)

40x1 + 30x2 > 1,200 (Vitamin Y Constraint)

and x1, x2 > 0
 Adding slack and artificial variables, we get

Min. Z = 60x1 + 80x2 + 0S1 + 0S2 + MA1 + MA2

Subject to, 20x1 + 30x2 – S1 + A1 = 900

40x1 + 30x2 - S2 + A2 = 1,200

and x1, x2, S1, S2, A1,
A2 > 0
 Initial non-optimal solution is written as follows:

simplex table I
Zj Cj 60 80 0 0 M M Ratio
BV Q x1 x2 s1 s2 A1 A2
M A1 900 20 30 -1 0 1 0 45
M A2 1200 40 30 0 -1 0 1 30

Zj 2100M 60M 60M -M -M M M

Cj-Zj 60-60M 80-60M M M 0 0

Since ∆j = 60 – 60M is the lowest, x 1 becomes the

entering variable, similarly Ratio bi/aij = 30 is
lowest positive value, hence it goes out.
 Simplex table II
Zj Cj 60 80 0 0 M Ratio
BV Q x1 x2 s1 s2 A1 Q/aij
M A1 300 0 15 -1 1/2 1 20
60 X1 30 1 3/4 0 -1/40 0 40

Zj 1800+300M 60 45+15M -M -3/2+1/2M M

Cj-Zj 0 35-15M M (3-M)/2 0

Since ∆j = 35 – 15M is the lowest, x 1 becomes the

entering variable, similarly Ratio bi/aij = 20 is
lowest positive value, hence it goes out.
Initial non-optimal solution is written as follows:
Simplex table III

Zj Cj 60 80 0 0
BV Q x1 x2 s1 s2
80 X2 20 0 1 -1/15 1/30
60 X1 15 1 0 1/20 -1/20

Zj 2500 60 80 -7/3 -1/3

Cj-Zj 0 0 7/3 1/3

Since ∆j = zero and positive value, hence this the

solution.
 Class work

 Mixed constraints

 Mixed constraints

 Initial non-optimal solution is written as follows:

simplex table I
Zj Cj 4 2 0 0 M M Ratio
BV Q x1 x2 s1 s2 A1 A2
M A1 3 3 1 0 0 1 0 1
M A2 6 4 3 -1 0 0 1 6/4
0 S2 3 1 2 0 1 0 0 3
Zj 9M 7M 4M -M 0 M M
Cj-Zj 4-7M 2-4M M 0 0 0
 X1= Q X1 X2 S1 S2 A2
3 3 1 0 0 0
3/3 3/3 1/3 0/3 0/3 0/3
new row= 1 1 1/3 0 0 0
 New row= old row – corresponding coefficient new tableau
in pivot column X row value

row A2, Q= 6-(4x1) = 2 S2, Q= 3-(1x1)= 2

X1= 4-(4x1)=0 X1= 1-(1x1)=0
X2= 3-(4x1/3)=5/3 X2= 2-(1x1/3)=5/3
S1= -1-(4x0)= -1 S1= 0-(1x0)=0
S2= 0-(4x0)= 0 S2= 1-(1x0)=1
A2= 1-(4x0)= 1 A2= 0-
(1x0)=0
 Revised simplex table II

Zj Cj 4 2 0 0 M Ratio
BV Q x1 x2 s1 s2 A2
4 X1 1 1 1/3 0 0 0 3
M A2 2 0 5/3 -1 0 1 6/5
0 S2 2 0 5/3 0 1 0 6/5
Zj 4+2M 4 4/3+5/3M -M 0 M
Cj-Zj 0 2-5M/3 M 0 0

Select near to
the top
 X2= X1 X2 S1 S2
Q 0 5/3 -1 0
2 0/ 5/3/5/3 - 0
2/5/3 5/ 1/5/3 /
 new
New row= old row –3 corresponding
row= 1 coefficient 5
6/5 0 in pivot column
-3/5 /
3
X
0
row X1, Q= 1-(1/3x6/5) = 9/15 S2, Q= 2-(5/3x6/5)= 0 new tableau
X1= 1-(1/3x0)= 1 X1= 0-(5/3x0)= row value
X2= 1/3-(1/3x1)= 0 X2= 5/3-(5/3x1)= 0
0
S1= 0-(1/3x-3/5)= 1/5 S1= 0-(5/3x-3/5)=1
S2= 0-(1/3x0)= 0 S2= 1-(5/3x0)= 1
 Optimal solution simplex table
III
Zj Cj 4 2 0 0
BV Q x1 x2 s1 s2
4 X1 9/15 1 0 1/5 0
2 X2 6/5 0 1 -3/5 0
0 S2 0 0 0 1 0
Zj 72/15 4 2 -2/5 0
Cj-Zj 0 0 0 0

This is the optimal solution, with X1= 3/5

X2= 2/5
S1= 2/5, and
total cost= 24/5
 Irregular types of LPP
 The basic simplex solution of typical maximization and
minimization problems has been shown in this chapter. However,
there are several special types of atypical linear programming
problems.
 For irregular problems the general simplex procedure does
not
always apply.

These special types include problems with more than one optimal
solution, infeasible problems, problems with unbounded solutions,
problems with ties for the pivot column or ties for the pivot row, and
 Multiple optimal solution


40

Profit @ corner B
30

A and C is equal
20

(1200)
B
10

FR
C
10 20 30
40 50
An infeasible solution
The three constraints do not overlap to form a feasible solution area.
Because no point satisfies all three constraints simultaneously, there is no
solution to the problem.

X1= 4
8

X2=6
6

B C
4

4X1+2X2=8
2

A
C
2 4 6 8 10
 An unbounded problem

 In some problems the feasible solution area formed by the

model constraints is not closed. In these cases it is possible
for the objective function to increase indefinitely without ever
reaching a maximum value because it never reaches the
boundary of the feasible solution area.
 In an unbounded problem the objective function can increase
indefinitely because the solution space is not closed.
 An unbounded solution
But unlimited profits are
not possible in the real
world; unbounded
solution, like an infeasible
solution, atypically
reflects an error in
defining the problem or
10

in
theformulating
model
8

The objective function is

6
4

shown to increase without

2

FR bound; thus, the solution is

2 4 6 8 never reached
10
 Duality
 The mirror image of LPP
 A given LPP has two forms
1. The Primal: the original LP Model
2. The Dual: alternative
How to convert the primal to its dual and vice versa?
Maximization objective of the primal=
minimization objective of the Dual.
 The primal dual relationship


2
 Example:
 The doctor advises a patient visited him that the patient is weak in

his health due to shortage of two vitamins, i.e., vitamin X and

vitamin Y. He advises him to take at least 40 units of vitamin X and

50 units of Vitamin Y everyday. He also advises that these vitamins

are available in two tonics A and B. Each unit of tonic A consists of

2 units of vitamin X and 3 units of vitamin Y. Each unit of tonic B

consists of 4 units of vitamin X and 2 units of vitamin Y. Tonic A

and Bare available in the medical shop at a cost of ETB 3 per unit of

A and ETB 2.50 per unit of B. The patient has to fulfill the need of

vitamin by consuming A and B at a minimum cost.

 If we solve and get the solution of the primal problem, we
can read the answer of dual problem from the primal
solution.

Primal problem: Dual Problem:

Min C= 3X1+ 2.5X2 Max Z= 40Y1+ 50Y2

st: 2X1+ 4X2 ≥40 St: 2x+ 3y ≤3

3X1+ 2X2 ≥50 4x+ 2y ≤2.50

X1, X2≥0 Y1, Y2 ≥0.

 Solution to primal (minimization)
CJ 3 2.5 0 0 M M
Zj Bv Q X1 X2 S1 S2 A1 A2
2.5 X2 5/2 0 1 -3/8 1/4 3/8 -1/4
3 X1 15 1 0 1/4 -1/2 -1/4 1/2
Zj 51.25 3 2.5 -3/16 -7/8 3/16 7/8
Cj-Zj 0 0 3/16 7/8 M-3/16 M-7/8

Answer: X1= 15 X2= 2.5 cost= 51.25

Solution to dual (maximization)

CJ 40 50 0 0
Zj Bv Q Y1 Y2 S1 S2
50 Y2 7/8 0 1 1/2 -1/4
40 Y1 3/16 1 0 -1/4 3/8
Zj 51.25 3 2.5 15 5/8
Cj-Zj 0 0 -15 -5/2

Answer: Y1= 3/16 Y2= 7/8 profit= 51.25

 The patient has to minimize the cost by purchasing vitamin
X and Y and the shopkeeper has to increase his returns by
fixing competitive prices for vitamin X and Y. Minimum
cost for patient is ETB 51.25 and the maximum returns for
the shopkeeper is ETB 51.25. The competitive price for
tonics is ETB 3 and ETB 2.50. Here we can understand the
concept of shadow price or economic worth of Resources
clearly. If we multiply the original elements on the right
hand side of the constraints with the net evaluation
elements under slack or surplus variables we get the values
equal to the minimum cost of minimization problem or
maximum profit of the maximization problem.
post optimality analysis

• Carried out after the

optimal solution is found
• Is begins with the final simplex
• Sensitivity analysis
tableau D u al i t y
•
 Sensitivity analysis
 Examination of the impacts of changes of
parameters on the optimal solution.
 i.e. change of coefficient of the constraints, change
of coefficient of the objective function, change of
quantity or RHS values
 Starts with the final tableau of the LPP (simplex
tableau)
Example: 1. a change in the RHS
of a constraints
 Change in RHS or Q of one constraint is considered at a time
 Consider shadow price
 Shadow price: is a marginal value; it indicates the impact that a
one unit change in the value of the constraint would have on the
value of the objective function.
 Shadow prices are the values in the Zj-row of slack columns
 The LPM of the micro computer
problem above is:
Max Z: 60x1+50x2

Subject to:

Assembly time: 4X1+10x2≤100

Inspection time: 2x1+x2≤22

Storage space: 3x1+3x2≤39

x1, x2≥0
Basis Cj 60 50 0 0 0 Quantit
X1 X2 S1 S2 S3 y
S1 0 0 0 1 6 -16/3 24
X1 60 1 0 0 1 -1/3 9
X2 50 0 1 0 -1 2/3 4
Z 60 50 0 10 40/3 740

Cj-Z 0 0 0 10 -40/3

Shadow price
 From the above tableau; the shadow prices are $ 0 for S1, $10

for S2 and $40/3 for S3.

 forexample, an increase of S1 by one unit will

resulted

increment of objective value by $10.

 Similarly the opposite is true, i.e. decrease of 1 unit of S1 will

be resulted in reduction of objective value by $10.

 But to what extent this change hold true?

 Because we can’t increase or decrease the constraint infinitely,

there are upper and lower limits, i.e. allowable increase and
Range of Feasibility (Right hand side
range)

 The range of feasibility is the range over which the RHS

value of a constraint can be changed and still have the
same shadow prices.
Range of feasibility

 The range within which resources/constraints can changed

having the proportionate change in objective value
 Steps
Step 1. compute the ratio (feasibility ratio) quantity

respective slack value = Q/S

both –ve and +ve ratio are considered

Step 2. identify the smallest +ve ratio

and –ve ratio closest to zero

Step 3. find the upper

limit or allowable increase and lower limit
or allowable decrease (range of
feasibility)
Lower Closest
limit= the original value – positive ratio
tovalue +
For both max and Upper limit= the original
negative ratio
Determine the range of feasibility for each of the constraints
in the ff LPP, whose final tableau

Cj 60 50 0 0 0
Zj Bv Q X1 X2 S1 S2 S3
0 S1 24 0 0 1 6 -16/3
60 X1 9 1 0 0 -1 -1/3
50 X2 4 0 1 0 -1 2/3
Zj 740 60 50 0 10 40/3
Cj-Zj 0 0 0 -10 -40/3
 Solution
1. Recall the original value of the resources
Original value constraints S1 S2 S3
100 S1 1 6 -16/3
22 S2 0 -1 -1/3
39 S3 0 -1 2/3
2. ratio = Q/respective slack values
S1= 24/1= 24 S2= 24/6= 4 S3= 24/-16/3= -4.5
9/0= undefined 9/-1= -9 9/-1/3= -27
4/0= 4/-1= 4/2/3= 6
undefined
-4
 3. Find the range of feasibility

Constrai Origina Lower limit Upper limit Range of

nts l value feasibility
S1 100 100-24= 76 100+∞ 76-∞
S2 22 22-4= 18 22+4= 26 11-26
S3 39 39-6 = 39+4.5= 43.5 33-43.5
33
Therefore:

Constraint one (assembly line): 100-24 up to 100+∞= 76-∞

Constraint two (inspection time): 22-4 up to 22-4= 18-26

Constraint three (storage space): 39-6 up to 39+4.5= 33-43.5

 Interpretation
First constraint:
Each hour decrease in assembly time will decrease the
current profit by Birr 0 (i.e no effect- indicated by shadow
price) as long as the decrease is up to 24 hours. But if the
assembly time decreases by more than 24 hours (or if the
total available assembly time is lower than 76 hours), the
current shadow price will no longer be valid. That is, the
profit will be affected. But available assembly time can
increase indefinitely (=allowable increase is ∞ ) without
Second constraint:
Similarly, Each hour increase or decrease in inspection time
will increase or decrease the current profit by $10,
respectively as long as the total inspection time is between 18
and 26 hours. Out side the range of feasibility, the current
shadow price ($10) will not be valid.
Third constraint:
Each cubic feet increase or decrease in storage space results
in an increase or decrease, respectively, of profit by $13.33
(i.e 40/3) as long as the total storage space is between 33 and
43.5 cubic feet.
 Example 2. A change of coefficient of objective function
 Two cases
1. Range of insignificance
the range over which the non basic variables objective function
coefficient can change without making these variables entering in
the solution
2.Range of optimality
the range over which the objective function coefficient of basic
variables can change without changing the optimal values i.e.
without changing basic and non basic variables but change the
optimal function value.
 Steps for range of optimality

For both max and min

problems
 Example
Cj 60 50
Zj BV Q X1 X2 S1 S2 S3 Solution
0 S1 24 0 0 1 6 -16/3
• Range of
60 X1 9 1 0 0 1 -1/3
50 X2 4 0 1 0 -1 2/3 insignificant for S2
Zj 740 60 50 0 10 40/3 = -∞ up to 10
Cj-Zj 0 0 0 -10 -40/3
• S3= ?

 Determine the range of insignificant for S2 and the

range of optimality for decision variables
 Solution


X1 Cj-Zj 0 0 0 -10 -40/3
X1 values in the
tableau
1 0 0 1 -1/3 X2 Cj-Zj 0 0 0 -10 -40/3

∞ ∞ ∞ -10 40 0 1 0 -1 2/3

• Upper limit= 60+40= 100 ∞ ∞

∞ 10
• Lower limit= 60-10= 50 -20

• Range of optimality of X1(1st DV)= 50-100 • Lower 50-20= 30

Upper limit= 50+10= 60

• Range of optimality of X2(2nd DV)=

30-60
The END!