A Computer Technique for Sensitivity Analysis in Linear Programs

Abstract

Sensitivity Analysis is a systematic study of how sensitive solutions are to (small) changes in the
data. In our paper, we develop a computer oriented method for analyzing sensitivity. This method
shows the changes in optimal solution of a Linear Programming problem for a small change in data
values. A numerical example is illustrated to demonstrate our algorithm.

I. Introduction b2, … , bm) be any non-singular sub-matrix of

A and xB be the vector of variables associated
Sensitivity Analysis (SA) is one of the great
with the columns of B.
successes to emerge from operations research
and management science. It is well developed The general properties and solution
and widely used. Linear Programming (LP) procedures of LP problems can be found in
problems in practice are often based on Kambo [5], Hasan [2]. We will now
numerical data that represent rough concentrate our discussion into SA.
approximations of quantities that are
Revised Simplex Method
inherently difficult to estimate. Because of
this, most LP-based studies include a post In real life the LP matrices are thin and sparse
optimality investigation of how a change in (there are usually more columns than rows).
the data affects the solution. SA is the most According to the characteristic of the LP
helpful tool for this purpose. problems and the way Simplex Method (SM)
works, it can easily be shown that a
Linear Programs
significant amount of redundant information
We first briefly discuss the general LP is generated at each step. This necessitates
problems. Consider the standard LP problem extra computational effort and computer
as follows, storage. To overcome the drawback of the
standard method of pivoting, a
Maximize Z = cx (1.1)
computationally more efficient procedure
subject to Ax = b (1.2)
Revised Simplex Method (RSM) is presented.
x 0 (1.3)
The RSM is an implementation of the
Where A = (a1, a2, … , am, am+1, … , an) is an
standard SM that uses an abbreviated table,
m × n matrix, b∈ Rm, x, c ∈ Rn. Let B = (b1,
reconstructing only that data from the
complete simplex tables absolutely necessary imprecise, forcing us to approximate data
to perform the steps of the SM. RSM (more values. For this reason Sensitivity Analysis is
efficient for computing) is now used in all needed to apply in real life models.
commercially available packages (e.g. IBM
The basic idea is to be able to give answers to
MPSX, CDC APEX III).
the changes:
Sensitivity Analysis
Changing the Objective Function
Once the optimal solution to an LP problem Coefficient of a Nonbasic Variable.
has been attained, it may be desirable to study Changing the Objective Function
how the current solution changes when the Coefficient of a Basic Variable.
parameters of the problem are changed. The Changing the Right-Hand Side of a
change in parameter of the problem may be Constraint.
discrete or continuous. The study of the effect Changing the Column of a Nonbasic
of discrete changes in parameters on the Variable.
optimal solution is called SA. In analyzing Adding a New Activity.
output, SA is used to explore how changes in
Some Definitions
the problem data might change the solution to
an LP, for example, how a change in Objective Function
production costs or demand projections might
The linear function z = = c1x1 + c2x2
affect a production schedule. Because large-
+ … … … + cnxn which is to be maximized
scale planning efforts often rely on large
(or minimized) is called objective function of
amounts of data, much of which represents
the LP problem.
best-guess estimates, the ability to undertake
such SA is critical to the acceptance of the Constraints
methodology. Indeed, people who are
The set of equations or inequalities is called
uncertain about data elements are often
the constraints of the general LP problem. Ax
advised to use SA to resolve the impact of
( , =, ) b is the set of constraints in the LP.
uncertainty. When we use a mathematical
model to describe reality we must make Feasible Solution
approximations. The world is more
Any solution to an LP which also satisfies the
complicated than the kinds of optimization
nonnegative restrictions of the problem is
problems that we are able to solve. Our
called a feasible solution to the LP.
knowledge of the relevant technology may be
Basic Solution Basis Matrix

A basic solution is a solution obtained by Basis matrix B is the matrix, whose elements
setting (n-m) variables equal to zero and are the original columns corresponding to the
solving for the remaining m variables, basic variables.
provided the determinant of the coefficient of
II. Algorithm
these m variables are non-zero. The m
variables are called basic variables. In this section, we present the algorithm of
our computer oriented method.
Basic Feasible Solution
Start
A basic feasible solution is a basic solution
which also satisfies the nonnegative Input type of problem d, number of
restrictions xj 0; that is all basic variables variables n, number of constraints m, cost
are nonnegative. coefficients c[i], cost coefficients of basic
variables cBV, basis matrix B, columns of
Optimal Solution
variables a[i], right hand side vector b.
Any feasible solution which optimizes
Step 1 calculate B-1 and B-1b.
(minimizes or maximizes) the objective
function of an LP is called optimal solution to Step 2 for i m, x = solve equation B-1b = 0
the LP.
if x ≠ φ, solve inequality B-1b 0
Cost/Profit Coefficient
Print inequality solution.
The vector c (c1, c2, … … , cn)T which is
Step 4 calculate cBVB-1, for i n
formed by the coefficients of the objective
function is called cost/profit coefficient. if d = 1, calculate cj[i] = cBVB-1a[i] –
c[i]
Right Hand Side Constant

T
else, calculate cj[i] = c[i] – cBVB-1a[i]
The vector b (b1, b2, … … , bn) which is
formed by the right hand side values of the Step 6 for i n, M = 0, x = solve equation
constraints is called right hand side constant. cj[i] = 0, clear the value of M

if x ≠ φ, solve inequality cj[i] 0

Print inequality solution.

Step 7 calculate cBVB-1b. method can be applied to analyze the
sensitivity of the solution of the solved
Output B-1b, cBVB-1b, cj[i].
problem. Our computer oriented program is
Stop. presented as follows:

III. Mathematica Codes << LinearAlgebra`MatrixManipulation`

Now, we present our computer codes of << Algebra`InequalitySolve`

Mathematica for SA. We have written the d = Input["d"]; n = Input["n"]; m = Input["m"]; i

propram in Mathematica 4 for student = 1;

version, but it will run on any version of Do[c[i] = Input["c"], {i, 1, n}]; z = Input["z"]; B =
Mathematica. In this program we have used Input["B"];
some mathematica codes like as,
i = 1; Do[a[i] = Input["a"], {i, 1, n}]; b =
Input["b"];
Solve[equations, vars] attempts to solve
equations for vars. IB = Inverse[B]; IBb = IB.Transpose[b]; i = 1;

Take[lst, {m, m}] returns a list consisting of While[i <= m, x = Solve[Take[IBb, {i, i}] == 0];

the mth object of lst. If[x != {{}} && x != {}, Print[N[InequalitySolve[

InequalitySolve[inequality, vars] attempts to (Take[IBb, {i, i}].{1}).{1} >= 0, p]]]]; i++];

solve inequality for vars.
zB = z.IB; i = 1;

If[condition, true, false] evaluates condition If[d == 1, Do[ca[i] = ((zB.Transpose[a[i]]) - c[i]), {i,
and executes true if condition is True and 1, n}],
executes false if condition is False.
Do[ca[i] = (c[i] - (zB.Transpose[a[i]])), {i, 1, n}]];

Do[expr,{i, imin, imax}] evaluates expr with i = 1; While[i <= n, M = 0; x = Solve[ca[i] == 0];
the value of i changing from imin to imax in Clear[M]; If

increments of 1.
[x != {{}} && x != {},
Print[N[InequalitySolve[(ca[i].{1}).{1} >= 0,
While[condition, expr] evaluates condition,
then expression, repetitively, until condition is p]]]]; i++]; zBb = zB.Transpose[b];

False.
Print[N[MatrixForm[IBb]] // Simplify]; Print[
N[zBb] // Simplify]; Print[
For our program we need an LP problem
which is solved by any method. Then our Array[ca, n] // Simplify // N];
We have generalized and designed the + 7/3 X3 + X5 = 3\n\n X1, X2, X3, X4, X5 >= 0"], {i,

previous program for general use. We have 1, n}];

used an example in the input box, so that one z = Input["Input the cost coefficents of Basic
can easily understand which data values he variables. Example:

has to enter in the each input boxes. It makes {{2,3}} in\n\n Z = 2 X1 + 3 X2 + X3\n\n 1/3 X1 + 1/3
the program so easy that any one can use this X2 + 1/3 X3 +
program to analyze the sensitivity of any LP
X4 = 1\n 1/3 X1 + 4/3 X2 + 7/3 X3 + X5 = 3\n\n X1,
problem. The generalized form of the main X2, X3, X4, X5 >= 0"];
program is given below:
B = Input["Input the Matrix B. Example:
<< LinearAlgebra`MatrixManipulation` {{1/3,1/3},{1/3,4/3}} \n in\n\n

<< Algebra`InequalitySolve` Z = 2 X1 + 3 X2 + X3\n\n 1/3 X1 + 1/3 X2 + 1/3 X3 +

X4 = 1\n 1/3 X1 +
d = Input["Input Maximization or Minimization
Problem.\n If Max then input: 4/3 X2 + 7/3 X3 + X5 = 3\n\n X1, X2, X3, X4, X5 >=
0"];
1\n If Min then input: -1"];
i = 1; Do[a[i] = Input["Input the column of variable
n = Input["Input the number of variables.
in constraints.
Example:
Example: {{1/3,1/3}} in \n\n Z = 2 X1 + 3 X2 +
5 \n in\n\n Z = 2 X1 + 3 X2 + X3\n\n 1/3 X1 + 1/3
X3\n\n 1/3 X1 +
X2 + 1/3 X3 + X4 =
1/3 X2 + 1/3 X3 + X4 = 1\n 1/3 X1 + 4/3 X2 + 7/3 X3
1\n 1/3 X1 + 4/3 X2 + 7/3 X3 + X5 = 3\n\n X1, X2,
+ X5 =
X3, X4, X5 >= 0"];
3\n\n X1, X2, X3, X4, X5 >= 0"], {i, 1, n}]
m = Input["Input the number of constraints.
Example: 2 \n in\n\n Z = 2 X1 b = Input["Input the right hand side column b of
constraints. Example:
+ 3 X2 + X3\n\n 1/3 X1 + 1/3 X2 + 1/3 X3 + X4 = 1\n
1/3 X1 + 4/3 X2 {{1,3}} in\n\n Z = 2 X1 + 3 X2 + X3\n\n 1/3 X1 + 1/3
X2 +
+ 7/3 X3 + X5 = 3\n\n X1, X2, X3, X4, X5 >= 0"];
1/3 X3 + X4 = 1\n 1/3 X1 + 4/3 X2 + 7/3 X3 + X5 =
i = 1; Do[c[i] = Input["Input the cost coefficent.
3\n\n

Example: 2 \n in\n\n Z = 2 X1 + 3 X2 + X3\n\n 1/3

X1, X2, X3, X4, X5 >= 0"];
X1 +
Print["\n## Optimal Solution:" ]; Print["The range
1/3 X2 + 1/3 X3 + X4 = 1\n 1/3 X1 + 4/3 X2
of p is: "];
IB = Inverse[B]; IBb = IB.Transpose[b]; Now if we run the program an input box will

i = 1; While[i <= m, x = Solve[Take[IBb, {i, i}] == appear like below:

0];

If[x != {{}} && x != {}, Print[N[InequalitySolve[

(Take[IBb, {i, i}].{1}).{1} >= 0, p]]]]; i++];

zB = z.IB; i = 1;

If[d == 1, Do[ca[i] = ((zB.Transpose[a[i]]) - c[i]), {i,

1, n}],

Do[ca[i] = (c[i] - (zB.Transpose[a[i]])), {i, 1, n}]];

One need to input some data values in

i = 1; While[i <= n, M = 0; x = Solve[ca[i] == 0];
Clear[M]; If different input boxes one after another. They
are type of the problem, number of variables,
[x != {{}} && x != {},
number of constraints, cost coefficients, cost
Print[N[InequalitySolve[(ca[i].{1}).{1} >= 0,
coefficients of basic variables, basis matrix B,
p]]]]; i++]; zBb = zB.Transpose[b];
column of constraints, and right hand side of
Print["The right hand side column of optimal constraints.
tableau is: ",
After inputting all the data values we find the
MatrixForm[IBb] // Simplify // N]
optimal table of the given LP. Now, if we
Print["The Optimum value is: z = ", N[zBb] // change any value of the problem by the
Simplify]
variable p, our program will show the range
Print["The Zero Row is: ", Array[ca, n] // Simplify of p for which the solution will still remain
// N]; optimal with the changed values in optimal
table.

In the following section we will illustrate our

technique with a numerical example.
IV. Numerical Illustrations x1, x2, x3 0
Solving by usual simplex method we get the
In this section, we take an LP problem as
optimal solution as, x1 = 33.33, x2 = 66.67,
follows,
x3 = 0, x4 = 0, x5 = 0, x6 = 100 and Z = 733.33.
max z = 10x1 + 6x2 + 4x3 x4, x5 and x6 are slack variables.
s.t. x1 + x2 + x3 ≤ 100 (labor)
Now if we run our program for this particular
10x1 + 4x2 + 5x3 ≤ 600 (material)
problem then the output of our program will
2x1 + 2x2 + 6x3 ≤ 300 (administration)
be as below,

Output 1

## Optimal Solution:
33.3333
The right hand side column of optimal tableau is: 66.6667
100.
The Optimum value is: z 733.333
The Zero Row: 0. , 0. , 2.66667 , 3.33333 , 0.666667 , 0.

Changing the Objective Function change the coefficient of x3 in the objective

Coefficient of Nonbasic Variable function within the range -∞ p 6.66667,
our solution will be still optimal. We can
In example, x3 (the daily production level of
afford the changes in the unit profit value of
product 3) is a nonbasic variable. The unit
product 3 from -∞ to 6.6667. But it will not
profit on product 3 in the objective function is
change our maximum profit value. If the unit
c[3] = 4. Now if we replaced c[3] in the
profit of product 3 decreases, it will not affect
objective function by p in our program then
the optimality of our previous optimal table,
the output of the program is as like Output 2.
but if increases, the solution will remain
In output 2, only the coefficient of x3 in the optimal to the unit profit value 6.66667. If it
optimal row is changed. All other values of increases more then 6.66667, then our
optimal table remain same. The range of p is solution will lose its optimality.
p 6.66667 with no lower bound. So, if we
 Output 2
## Optimal Solution:
The range of p is:
p 6.66667
33.3333
The right hand side column of optimal tableau is: 66.6667
100.
The Optimum value is: z 733.333
The Zero Row: 0. , 0. , 6.66667 1. p , 3.33333 , 0.666667 , 0.

Changing the Objective Function optimal row and the value of z are changed.
Coefficient of Basic Variable The ranges of p in output 3 are like as p - 6,
p 15 and p 6. So the minimum range will
x1, the variable for the daily production level
be 6 p 15. By this we can say that the
of product 1 is a basic variable in this
solution will be optimal if we change the
example. The coefficient of x1 in the objective
value of c[1] by any value in this range.
function is c[1] = 10. If we replace c[1] by p
Hence in order to maximizing the profit we
in our program then the output of the program
can afford the changes in the profit value of
will be as like below Output 3. In Output 3,
product 1 from 6 to 15.
the right hand side is same as before. Only the

Output 3
## Optimal Solution:
The range of p is:
p 6.
p 15.
p 6.
33.3333
The right hand side column of optimal tableau is: 66.6667
100.
The Optimum value is: z 400. 33.3333 p
The Zero Row: 0. , 0. , 0.166667 6. p , 10. 0.666667 p , 0.166667 6. p , 0.
By the same way, we can show the sensitivity 3. D. C. Aucamp and D. I. Steinberg
of the optimal solution of this particular (June 1982), “The Computation of
factory problem for the other changes of data Shadow Prices in Linear
values. Programming”, “The Journal of the
Operational Research Society”, Vol.
V. Conclusion
33, No. 6, pp. 557-565.
In our paper, we have developed a computer
4. W. L. Winston, “Operation Research,
oriented method for analyzing sensitivity of
Application and Algorithms, 3rd
the optimal solution for any changes of data
edition”.
and for any kind of LP problem. And we have
showed sensitivity of the optimal solution of a 5. Kambo, N.S., 1984, “Mathematical
particular factory problem for some changes programming technique,” Affiliated
in data values. Our program is capable of East-West Press Pvt. Ltd., New Delhi.
handling any number of constraints and any
6. G. B. Dantzig, “Linear Programming
number of variables. This method can also be
and extension”, Princeton university
extended for solving any kind of LP
press, Princeton, N.J (1962).
problems. We concluded that our technique is
more efficient for performing sensitivity 7. Ravindran, Phillips and Solberg,
analysis. “Operation Research Principles and
Practice.”
……………..
8. Eugene D., “Schaum’s outlines-
1. J. L. Higle & S. W. Wallace (July-
Mathematica”, Mc-Graw-Hill.
August 2003), “Sensitivity Analysis
and Uncertainty in Linear 9. H. A. Taha, “Operations Research: An
Programming”, Interfaces © 2003 introduction, 6th edition”, Prentice Hill
Informs, Vol. 33, No. 4, pp. 53–60. of India, PVT. LTD., New Delhi
(1997).
2. M. B. Hasan, A. F. M. K. Khan and
M. A. Islam (2001), “Basic Solution 10. Saul I. Gass, “Linear Programming,
of Linear System of Equations through Methods and Applications, third
Computer Algebra”, “Ganit: J. edition”, World Systems Laboratories,
Bangladesh Math”, Soc. 21, pp. 1-7. Inc. The American University.