Chapter Two

LP
 Introduction

 Linear programming- developed by Kantorovich in 1939 and

extended by G. Dantzig in 1947
 The original name, "programming in a linear structure," which
was later shortened to "linear programming.“
 Programming- “planning or optimization”
 LP- Planning with linear models
 Meaning of LP
 LP is a mathematical technique for choosing the best

alternative from the a set of feasible alternatives.

– It is the most commonly applied form of constrained

optimization, which is harder than uncontained

optimization
 ….

 Linear Programming (LP) is a field of

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

Optimization
 LP is the favorites tools of OR’s
 Simple: easy to manipulate
 Easy to understand: easy to explain
 Robust: strong (good enough for every thing)
 THE UNDERLYING ASSUMPTIONS of LP
1. Proportionality: value of each term is strictly proportional to
the value of variable in the term
– Exists in the objective function and the constraints inequalities

2. Additively: prohibited 5X1X2

3. Divisibility/Continuity: deals with integer number but fractional

values can be utilized

4. Certainty: all parameter values are known with certainty

5. Finite choices: There should be finite feasible solution.

However sometimes there may be infinite solution
 Main elements LP
 Decision variables –value of unknown variables
Goal- to find values of the variable that provide a best value of the objective function

 Objective function- mathematical expression that combines the variables to express

your goal.
•Represent profit, efficiency, yield, cost etc

•Requirement: maximize or Minimize objective function

 Constraints- a mathematical expression that combine the variables to express limits

on the possible solutions

 Variable bound- Right hand side (rhs) or quantity, budget

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) Z : f(X X X …, X )
1, 2, 3, n
Mathematical formulation of an optimization
problem

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

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

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

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

note : n variables, m 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

Example 1
Assume a firm that produces two products p and q using two
row materials in order to maximize monthly profit
Max monthly
p q available of row
materials
Profit
$5 $10 -
contribution
Row material one 4units 5units 200units

Row material two 5units 6units 400units

No more than 20 units of p should be produced per month

Formulate LPM
10/19/24 Mgmt, JU
Example 2:
A firm makes two types of furniture chairs and tables. The
profit contribution for each product as calculated by the
accounting department is birr20 per chair and birr30 per
table. Both products are processed on three machines
M1, M2 and M3. The time required in hours by each
product and total times available per week on each
machine are as follows:
Machines Chairs Tables Available hours per week

M1 3hours 3hours 36hours

M2 5hours 2hours 50hours

M3 2hours 6hours 60hours

Formulate the linear programming model.

10/19/24 Mgmt, JU
 Example
 An electronic firm is undecided at the most profitable mix for
its products. The products manufactured are transistors,
resistors and carbon tubes with a profit of (per 100 units) $
10, $6 and $4 respectively. To produce a shipment of
transistors containing 100 units requires 1 hour of
engineering, 10 hours of direct labor and 2 hours of
administrative service. To produce 100 units of resistors
requires 1 hour, 4 hours and 2 hours of engineering, direct
labor and administrative time respectively. For 100 unit of
carbon tubes it needs 1 hour, 6 hours and 5 hours of
engineering, direct labor and administrative time
respectively. There are 100 hours of engineering time, 600
hours of direct labor and 300 hours of administrative time
available. Formulate the corresponding LPP.
 Solution
 Let X1- 100 units of transistors
 X2- 100 units of resistors
 X3- 100 units of carbon tubes
Z= 10X1+6X2+4X3
each product will requires
X1+X2+X3
10X1+4X2+6X3
2X1+2X2+5X3
But the total time available for engineering, direct labour and
administrative services is 100, 600 and 300 hours respectively.
formulated LPP is
Example1
 The agricultural Research institute has suggested to a farmer
to spread out at least 4800 kg of a special phosphate
fertilizer and no less than 7200 kg of a special nitrogen
fertilizer to raise productivity of crops in his fields. There
are two resources for obtaining these mixtures A and B.
Both of these are available in bags weighing 100 kg each
and they cost Birr 40 and Birr 24 respectively. Mixture A
contains phosphate and nitrogen equivalent of 20 kg and 80
respectively, while mixture B contains these ingredients
equivalent of 50 kg each. Formulate LPM
10/19/24 Mgmt, JU
 Class work
A Farmer is mixing two types of food, Brand X
and Brand Y, for his cattle. If each serving is
required to have 60 grams of protein and 30 grams
of fat, where Brand X has 15 grams of protein and
10 grams of fat and costs 80 cents per unit, and
Brand Y contains 20 grams of protein and 5 grams
of fat and costs 50 cents per unit. Formulate LPM
Solution
 Home work
1. DeReal international, 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.
2. 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.
 LP:
Graphical 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 the 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.

NB: an optimum solution to the LP is always at corner point.

 Example 1

Max z = 3x1+ 2x2

st: 2x + x ≤100
1 2

x1+ x2 ≤80

x1 ≤40

x1, x2 >0

Solve the problem graphically.

 Example 2
Min z = 4x1+ 6x2
st: x+x >8
1 2

6x1+ x2 > 12

x1, x2 >0
 Class work

Minimize C= 50x1 + 20x­2

Subject to
2x1 – x2> 0
x1 + 4x2 > 80
0.9x1 + 0.8x2 >40
x1 ,x2 > 0
 Simplex
Algorithm
 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 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 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.
 formulated by G. Dantzig in 1947.
 CONDITIONS TO USE SIMPLEX

• 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.
 Basic terms and Definitions
 Standard Form:
Changing the canonical form(inequalities) in to equalities form

 Slack and Artificial Variables:

designated as S1, S2 . . . . etc. and A1, A2 etc. respectively.

– slack variables indicate spare capacity of the constraints,

– artificial variables are imaginary variables added for standard form.

Surplus Variable:
 A variable subtracted from the left hand side of a greater than or equal to constraint to convert the
constraint into equality.
 amount of resource over and above the minimum required level.
 slack variable in the case of maximization.
 Cont’d
 Basic Solution:
– There may be n variables and m constraints in a LPP. 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".
 Basic Feasible Solution: When a basic solution satisfies even the non-negativity
requirement is called Basic Feasible Solution (bfs). a bfs corresponds to a corner point
of the feasible region.

 Simplex Table: A table used for calculations during various iterations of the simplex
procedure

 Variable Mix: The values of the column that contains all the variables in the solution.
 Cont’d

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

 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.
 Cj Row: It is the row containing the coefficients of all the variables
(decision variables, slack or artificial variables) in the objective
function.

 Constraints: Restrictions on the problem solution arising from

limited resources.

 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.
 Cont’d

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

Pivot Row: When we work out the ratio of quantities rhs/Q or 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.

 Pivot Element:
The element at the point of intersection of the key column and the key row is called the Pivot
element.

 Optimal Solution: The best of all feasible solutions.

 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 = I, 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. . . . .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 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 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 – zj 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 Q or 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!

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
Home work
 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

Class work
Mixed constraints
Mixed constraints
 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)
B
10

FR
C
10 20 30 40 50
An infeasible solution
 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 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
Z=
8

4X

The objective function is

6

1+
2X
2 4

shown to increase without

2

FR bound; thus, the solution is

2 4 6 8 10
never reached
 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.
 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?

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):
PROBLEM: animals feeding farm.

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. formulate LPM

. 2. Minimize the cost of meeting the nutrient requirements.

3. Solve the problem graphically

HAVE
GOOD
DAY
 post optimality analysis
Carried out after the optimal solution is
found
• Is begins with the final simplex tableau
 DUALTY
 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
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.

 Therange 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

For both max and min problems
Determine the range of feasibility for each of the constraints
in the ff LPP, whose final tableau
 Solution
1. Recall the original value of the resources
Original value constraints S1 S2 S3
100 S1 1 6 -16/3
101 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

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.

 Cont…
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

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
 Example

Determine the range of insignificant for S2

 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.
 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.
 2.10.1 How to Convert Primal in to Dual
1.If primal is of maximization type then its dual is
minimization type
 2.profit/cost constants Cj in primal is replaced by
resource (capacity) constants bm.
 3.all signs “<” in primal is replaced by sign “>”
and vice versa.
 4.in primal, constraint inequities are positioned
from left to right ie
The primal dual relationship
 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.

 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.
 Home work
 Maximize Z= 6x1 + 5x2+10x3
 s/t 4x1+ 5x2 + 7x3 < 5
 3x1 + 7x3 < 10
 2x1+ x2 + 8x3 = 20
 2x2+ 9x3 > 5
END OF
CHAPTER
TWO