Chapter Two

Linear programing (LP)

infotesfish@gmail.com
 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.
 DEFINITION

 Linear Programming(LP) is a field of

management science or OR 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

 Constraints
– a less than or equal to constraint : f(X1 , X2 , X3 , … , Xn) < b
– a greater than or equal to constraint : f(X1 , X2 , X3 , … , Xn) > b
– an equal to constraint : f(X1 , X2 , X3 , … , Xn) = b

 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 objective 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 of certain common
components and characteristics.

 Components of LPM:

 Decision variables,

 Objective function 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
SYNERGY 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
$40X1= profit from bowls
$50X2= profit from mugs
 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

$3x2 = cost of bags of Crop-quick

 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
 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 constraint < and shading above

the line for the constraint > type).

 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 Total
P1 P2
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 < 48
x1, x2 > 0 non-negativity condition.
 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 X2
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
X1 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 zero ∴ Z=O

At point A x2=12, x1=0 ∴ Z=12x6=72

At point D x1=15, x2=0 ∴ Z=15x8=120

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)
SNERGY 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):
Required:
Resource Requirements
formulate linear
model, solve
product Labor (hr/unit) Clay (lb/unit) Profit/unit graphically, find
Bowl 1 4 40 the optimum
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 50 60
10 20 30 40
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

(30, 40) 0
X1
10 20 30 40 50 60
 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

30
4X1+3X2=120
A
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

30
4X1+3X2=120 Optimum solution
A
20 The optimal solution is
the best feasible solution.
10
B 1X1+2X2=40

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

 A minimization problem minimizes the value of the

objective function rather than maximizing it.
Minimization problems generally involve finding 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 E x1=80,x2=0 therefore Z= 4000

From 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 X2 X1 X2
0 14 X1 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

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.

 For application 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: represents the linear relationships of objective

function and constraints, making RHS of constraints as equal
produces standard form,

involves converting inequality situation (canonical form) into

standard form

2. Slack and Artificial Variables:

are 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.

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'.

9. Iteration: 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.
 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. . . . .ainxn < bi ; i = 1,2,. .m(Canonical form)

 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

≥ subtract a surplus variable and add

an artificial variable
 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 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 Cj 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 Zj-row. For each column the Zj – 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-Zj 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

tableau.
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 by the
corresponding new element of the revised row at (b) above.]
(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
 The structure of most algorithms has the following
steps as a main framework

Formulate Put In Put In Execute

Problem Standard Tableau Simplex
as LP
Form Form Method
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

zero values) Hence, S1 = 200, S2 = 125, S3 = 900 and Z=0
 This can be written as initial simplex table 1

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

0 S1 200 1 1 1 0 0 200/1=200
0 S2 125 0 1 0 1 0 125/1=125 LV

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 X 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

row (6x125)=150
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 X 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)

row 150 =0
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.
 Home work
 Maximize 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= 46,000/11
 Class work
Maximise Z = 10x1 + 15 x2 + 20 x3
S.T.
10 x1+ 5x2 + 2x3 ≤ 2,700
5x1 + 10x2 + 4x3 ≤ 2,200
1x1 + 1x2 + 2x3 ≤ 500 and
All 1x,x2 andx3 are ≥ 0

Maximise Z = 10x1 + 15 x2 + 20 x3 +0S1+0S2+0S3

S.T
10 x1+ 5x2 + 2x3 +S1 = 2700 Solution ; S1 1600
5x1 + 10x2 + 4x3 + S2 = 2200 X2= 150
1x1 + 1x2 + 2x3+S3 = 500
x1, x2 and x3 all ≥ 0 X2= 174.4
Profit= 5738
 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 surplus and artificial variables.

 Surplus 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 surplus
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, x1 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, x1 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= Q X1 X2 S1 S2
2 0 5/3 -1 0
2/5/3 0/5/3 5/3/5/3 -1/5/3 0/5/3
new row= 6/5 0 1 -3/5 0
 New row= old row – corresponding coefficient new tableau
in pivot column X row value

row X1, Q= 1-(1/3x6/5) = 9/15 S2, Q= 2-(5/3x6/5)= 0

X1= 1-(1/3x0)= 1 X1= 0-(5/3x0)= 0
X2= 1/3-(1/3x1)= 0 X2= 5/3-(5/3x1)= 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= 6/5
S2= 0, 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
problems with constraints with negative quantity values.
 Multiple optimal solution

40

Profit @ corner B
30

A and C is equal
20

(1200)
10

B
FR
C
10 20 30 40 50
An infeasible solution
 Multiple optimal 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 C
6

B
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 in formulating
10

the model
8

The objective function is

6
4

shown to increase without

2

FR bound; thus, the solution is

2 4 6 8 10 never reached
Sensitivity analysis (post
optimality)
 Carried out after the optimal solution is found

 Is begins with the final simplex tableau

 Its purpose is to explore how change in any of the

parameters of a problem i.e. coefficient of the constraints,
coefficient of the objective function, quantity or RHS
values
Example: 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 Z-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. This tells us that if the amount

of assembly time was increased by one hour, there would

be no effect on profit; if the inspection time was increased

by one hour, the effect would be to increase profit by $ 10,

and if storage space was increased by one cubic foot, profit

would increase by $40/3.

 In the above problem, the optimal solution was given by
the intersection of inspection time and storage space
constraints. Thus, the shadow prices in the final simplex
tableau will remain the same so long as the same
constraints give the intersection for the optimal solution.
For what range of changes in the RHS value of those
constraints the current shadow prices remain valid? This is
answered by range of feasibility.
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)
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= undefined 4/-1= -4 4/2/3= 6
 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 18-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 affecting the current
profit level.
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.
 Range of insignificance
S1= below zero
S2= (0-10)
S3= (0-40/3)
 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• Duality
 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.

 for example, 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

decrease.
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)

Upper limit= the original value + negative ratio

Lower limit= the original value – positive ratio Closest

For both max and to zero
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= undefined 4/-1= -4 4/2/3= 6
 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 affecting the current
profit level.
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
insignificant for S2
50 X2 4 0 1 0 -1 2/3
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

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

• Upper limit= 60+40= 100 ∞ ∞ ∞ 10 -20

• Lower limit= 60-10= 50 • Upper limit= 50+10= 60

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

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

30-60
 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


 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: 2y1+ 3y2 ≤3

3X1+ 2X2 ≥50 4y2+ 2y2 ≤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.
The END!