Sensitivity Analysis

Consider the following linear Linear Programming Problem:
Minimize z = -30 x1 - 6 x2 + 5 x3 - 18 x4
   subject to:
      x1+ 2 x3+ x4 < = 20
 - 2 x1+   x2 - x4 < = 15
   6 x1+ 2 x2- 3 x3 < = 54
       x1, x2, x3, x4 > = 0
The initial and final tableaux of the Primal problem are as follows:

A b
cz
x1x2x3 x4
x5 x6 x7
 b
x5
x6
x7
1 0 2 1
-2 1 0 -1
6 2 -30
1 0 0
0 10
0 0 1
20
15
54
C
-30 -6 5 -18
000
0
A* b*
c*z*
x1 x2 x3 x4
x5 x6 x7
 b*
x4*
x6*
x2*
1 0 2 1
-4 0 7/2 0
3 1 -3/2 0
1 0 0
1 1 -1/2
0 0 1/2
20
8
27
C*
6 0 32 0
18 0 3
522
Inititial Tableau Final Tableau
Notice that in the final tableau, the identity matrix
I3 = [ A4* , A6* , A2* ].
In the initial tableau, we use A4 , A6 and A2 to create the matrix
B = [ A4 , A6 , A2 ] = [   1    0    0
-1    1    1
  0    0    2 		]

Since B-1 I3 = B-1, we conclude that the inverse of B is obtain from A5* , A6* , A7* in the final tableau. Thus
B-1 = [ A5* , A6* , A7* ] = [ 1     0      0
1     1   -1/2
0     0     1/2 		]

Note that B-1 A = A*, so B-1 Aj = A*j ; and also B-1 b = b*.
From the vector c = ( c1 , c2 , c3 , c4 , c5 , c6 , c7 ) = (-30 , -6 , 5 , -18 , 0 , 0 , 0 ), we define the vector
cB = ( c4 , c6 , c2) = ( -18 , 0 , -6 ), then
c* = c - cB B-1 A = c - cB A*
z* = z - cB B-1 b = z - cB b*
Hence the final tableau is
A* = B-1 A b* = B-1 b
c* = c - cB B-1 Az* = z - cB B-1 b

Changes in the Objective Function
The changes in the objective vector c can induce changes only in c* and z*, and in fact the new c* can be determined using
c* = c - cB B-1 A. If the modified c* remains nonnegative, X* would remain an optimal solution; if not, more iterations of the simplex algorithm may be necessary to complete the modified problem.

Changes in the Constant Column Vector
Changing the original column vector b into b' will affect b* and z* of the final tableau, but not c* and A*.
The modified b'* = B-1 b' can be calculated. If the entries remain nonnegative, since c* > = 0, the optimal solution to the modified problem will have the same optimal solution as the original problem, with values given by b'*; and z'* = z - cBb'*.
If some entries of b'* are negative, then to resolve this problem we use the Dual Simplex Algorithm on this new tableau.

Addition of a New Variable
Suppose that now we wish to add another variable in the formulation of the original problem. Let xn+1 be the new variable, with the objective coefficient cn+1 and the column vector of coefficients for the constraining equations An+1. Then the expanded, modified problem in canonical form is to minimize z' = c' X' subject to A' X' = b, X' > = 0, where

c = ( c1 , c2 , . . . , cn , cn+1 ),     X' = ( x1 , x2 , . . . , xn , xn+1 )t,     and     A' = [ A1 , A2 , . . . , An , An+1 ]

Now X* is still a basic feasible solution to the new problem if we simply set the value of the nonbasic variable xn+1 equal to 0. Moreover, this point will provide an optimal solution if cn+1* = cn+1 - cB B-1 An+1 > = 0; if not, we just use the simplex algorithm on the new tableau by using the n+1th column as a pivot column.

Addition of a Constraint
Suppose after solving the problem we wish to alter the original problem by the addition of a new constraint. Now it could be that X* satisfies this new constraint. If this is the case, X* is also optimal for the expanded problem, because clearly, by this addition of a constraint, we have not changed the objective function nor increased the set of feasible solutions to the system of constraints. On the other hand, if X* does not satisfy this new constraint, we must find a new optimal solution. Under certain circumstances, however, this problem may be resolved quite easily by creating a new canonical tableau ( the new costant column b' may contain some negative entries) from the final tableau solution to the original problem and the application of the Dual Simplex Algorithm.