Range For The Coefficients of Basic Decision Variables

Range for the coefficients of basic decision variables
The range of optimality: is the range over which a basic decision variable coefficient in the
objective function can change without changing the optimal solution mix. However, this change will
change only the optimal value of the objective function. (The profit figure)
Example:
Given the final tableau of the microcomputers problem, determine the range of optimality.
Solution
The final simplex tableau for the problem is repeated here for convenience
B C 60 50 0 0 0 Q
X1 X2 S1 S2 S3
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
C- Z 0 0 0 -10 - 40/3
Analysis of X1
Steps:
a. Take the C – Z row of the optimal solution.
b. Take the X1 row values.
c. C – Z row
X1 row
Column X1 X2 S1 S2 S3
C – Z row 0 =0 0 =und 0 =und -10 =-10 -43/3 =+40
X1 row 1 0 0 1 -1/3
The positive ratio is +40. Therefore, the coefficients of X 1 can be increased by 40 without changing
the optimal solution. The upper end of its range of optimality is this amount added to its current
(original) value. Thus its upper end is 60+ 40 = 100. Also, the smallest negative ratio is -10;
therefore the x1 coefficient can be decreased by as much as 10 from its current value, making the
lower end of the range equal to 60-10= 50
Analysis of X2
Steps:
a. Take the C – Z row of the optimal solution
a. Take the X2 row values.
b. C – Z row
X1 row
Column X1 X2 S1 S2 S3
C – Z row 0 =und 0 =0 0 =und -10 =10 -43/3 =-20
X2 row 0 1 0 -1 2/3
The smallest positive ratio is + 10. This tells us that the X 2 coefficient in the objective function could
be increased by 10 to 50+ 10 = 60. The smallest negative ratio is -20, which tells us that x 2
coefficient could be decreased by 20 to 50-20 =30. Hence the range optimality for the objective
function coefficient of x2 is 30 to 60.
Example:
Max Z=5x1 +4.5x2 +x3
Subject to:
15 x1+15.8x2 < 150
5x1+6.4x2+15x3 < 77
2.8x2+11.8x3 < 36
x 1 , x 2 , x3 > 0
The optimal tableau for this solution is:

B C 5 4.5 1 0 0 0 Q
X1 X2 X3 S1 S2 S3
X1 5 1 1.053 0 0.067 0 0 10
X3 1 0 0.67 1 -0.022 0.067 0 1.8
S3 0 0 1.924 0 0.258 -0.773 1 15.12
Z 5 5.342 1 0.311 0.067 0 51.8
C–Z 0 -0.842 0 -0.311 -0.067 0
Determine the range of optimality for the coefficients of the basic-decision variables.
Solution:
Analysis of basic decision variable
The analysis will be conducted on products on X1 and X3 which are in the basic solution. Divide each C -
Z row entry for variables not in the solution (for instance, by X2, S1 and S2 values) the remaining values
result undefined so we can skip it
I. Analysis of X1
Steps:
a. Take the C – Z row of the optimal solution of the non-basic variables
b. Take the X1 row of the non-basic variables
c. C – Z row
X1 row
 Upper Limit
The smallest positive number in the C- Z row tells how much the profit of
X1
X1 can be increased before the solution is changed.
Upper Limit= C (for X1) +the smallest positive value of C - Z row
=5+∞=∞ X1 row
Note: C (for X1) =5(Look in the OF of the LP problem)
X2 S1 S2
C – Z row -0.842 -0.311 -0.067
 Lower Limit
X1 row 1.053 0.067 0
The C - Z row -0.8 -4.64 -∞ smallest
X1 row
negative
ratio (the
number closest negative amount closest to 0)
Lower Limit= C (for X1) +The largest negative value of C - Z row
=5+ (-0.8) = 4.2 X1 row
Therefore, the range of optimality for the coefficient of X1 is 4.2< C (for X1) < ∞
(The coefficient of X1 in the objective function can change between 4.2 and ∞ without changing the optimal
solution mix X1=10, X3=1.8 and S3=15.12)
II. Analysis of X3
Upper Limit= C (for X3) +The smallest positive value of C - Z row

=1- (1) =0 X1 row
Note: C (for X3) =5(Look in the OF of the LP problem
 Lower Limit= C (for X3 )+The largest negative value of C- Z row

=1+ (14.13) = 15.13 X1 row
Therefore, the range of optimality for the coefficient of X3 is 0 < C (for X3) < 15.13 (The
coefficient of X3 in the objective function can change between 0 and 15.13 without changing the optimal
solution mix X1=10, X3=1.8 and S3=15.12).However, this change will change only the optimal value of the
objective function (i.e. Max Z will change)
X2 S1 S2
C- Z row -0.842 -0.311 -0.067
X3 row 0.67 -0.022 0.067
C - Z row -1.26 14.13 -1
X1 row
Exercise:
Subject to: Max Z=50x1 +120x2
2 x1+4x2 < 80
3x1+x2< 60
x1, x2 > 0
Required: Determine the range of optimality for the coefficient of the basic variables for
the given problem.
Optimal Solution
B C 80 60 0 0 Q
X1 X2 S1 S2
S2 0 5/2 0 -1/4 1 20
X2 60 3/2 1 1/2 0 40
Z 90 60 30 0 $2,400
C–Z -10 0 -30 0
Ans: The range of optimality for X2’s profit coefficient is: $66.6 < C (for X2) < ∞
The range of insignificance is the range over which Cj rates for non-basic variables can
vary without causing a change in the optimal solution mix (variable) is called the range of
insignificance
If the profit contribution of X2 is greater than 5.342, then X2 will be included in the solution.
Thus, ∞< C (new for X2)< 5.342 is the range of insignificance for X2.
C (profit contribution) for X2 can vary with in the given range without causing a change in the
optimal solution mix.

Range For The Coefficients of Basic Decision Variables

Uploaded by

Copyright:

Available Formats

Range For The Coefficients of Basic Decision Variables

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Range For The Coefficients of Basic Decision Variables

Uploaded by

Copyright:

Available Formats

Range for the coefficients of basic decision variables

The optimal tableau for this solution is:

Note: C (for X1) =5(Look in the OF of the LP problem)

Upper Limit= C (for X3) +The smallest positive value of C - Z row

Note: C (for X3) =5(Look in the OF of the LP problem

 Lower Limit= C (for X3 )+The largest negative value of C- Z row

You might also like