Introduction to Sensitivity Analysis
    Introduction to Sensitivity Analysis
    Sensitivity analysis means determining effects of changes 
    in parameters on the solution. It is also called What if analysis, 
    Parametric analysis, Post optimality analysis, etc,. It is not 
    restricted to LP problems. Here is an example using Data Table.
                               We will now discuss LP and 
                               sensitivity analysis..
   LP: Sensitivity Analysis          BU.520.601                              2
    Primal dual relationship                                              10x +        8x     Max 
     Primal dual relationship                                                 1           2
                                                                         0.7x +         x ≤ 630
    Consider the LP problem shown. We will call                               1           2
                                                                        (½) x + (5/6) x ≤ 600
    this as a “primal” problem. For every primal                              1           2
                                                                             x + (2/3) x ≤ 708
    problem, there is always a corresponding LP                               1           2
    problem called the “dual” problem.                                (1/10) x + (1/4) x ≤ 135
                                                                              1           2
    630y + 600y + 708y +             135y - 150y            Min             -x -        x ≤ -150
          1         2          3           4         5                        1           2
     0.7y + (½)y             y     (1/10)y         -y ≥     10                     x1 ≥ 0,  x2  ≥ 0
          1         2          3           4         5
         y + (5/6)y + (2/3)y +        (1/4) -       y ≥      8       Note the 
          1         2          3           4         2
                          y  ≥ 0,  y  ≥ 0, y  ≥ 0, y  ≥ 0, y  ≥ 0    following
                            1        2       3      4       5
     • Any one of these can be called “primal”;                                 Min
       the other one is “dual”.
     • If  one is  of the size m x n, the other is of                 optimal
       the size n x m.
     • If we solve one, we implicitly solve the                                 Max
       other.
     • Optimal solutions for both have identical 
       value for the objective function (if an 
    LP: Sensitivity Analysis                                                                       3
       optimal solution exists).
                                                 BU.520.601
   The Simplex Method
    The Simplex Method
   Consider a simple two product example 
   with three resource constraints. The 
   feasible region is shown. 
     Maximize 15x +10x = Z 
                   1     2
                 2x +   x ≤ 800
                   1     2
                  x + 3x ≤ 900
                   1     2
                    +   x ≤ 250
                         2
                    x1 ≥ 0,  x2  ≥ 0
    We now add slack variables  MaxZ  - 15x + 10x                   =    0 
    to each constraint to convert              1      2
                                            2x +     x + S          = 800
    these in equations.                        1      2   1
                                              x +  3x      +S       = 900
                                               1      2        2
                              Primal - dual     +    x          +S = 250
                  Maximize 15 x  + 10 x               2            3
                                   1        2
     Minimize 800 y  + 900 y + 250 y
                       1          2         3
   LP: Sensitivity Analysis                                               4
                                     BU.520.601
    The Simplex Method: Cont…
     The Simplex Method: Cont…
    Start with the tableau for Maximize 15 x1 + 10 x2
    Z x x S S S
         1   2   1   2   3
    1 -15 -10    0   0   0      0    Initial solution: 
                                     Z = 0, x1 = 0, x2 = 0, 
    0   2   1    1   0   0    800    S = 800, S  = 900 
                                       1         2
    0   1   3    0   1   0    900    and S = 250. 
    0   0   1    0   0   1    250           3 
                                   After many iterations (moving from one 
    Z x x S S S                    corner to the next) we get the final answer.
         1   2   1   2    3
    1   0   0    7    1   0 6500        Optimal solution: 
                                        Z = 6500, x1 = 300, x2 = 200 and S3 = 50. 
    0   1   0 3/5-1/5     0    300      Z = 15 * 300 + 10 * 200 = 6500
    0   0   1 -1/5 -2/5   0    200
    0   0   0    0    0   1     50   Notice 7, 1, 0 in the objective row. 
    These are the values of dual variables, called shadow prices.
    Minimize 800 y  + 900 y + 250 y  gives 800*7 +  900*1 + 250*0 = 6500
                    1       2        3
    LP: Sensitivity Analysis                                                         5
                                          BU.520.601
                                             Maximize 10 x  + 8 x = Z 
    Solver                                                    1       2 
    Solver              Consider the                 7/10 x   +      x    630
    “Answer                                                 1       2
    “Answer             Golf Bag       1/2 x1  + 5/6 x2  600                         
    Report”             problem.                          x1  + 2/3 x2  708
    Report”
                                     1/10 x   + 1/4 x   135                         
                                             1       2
                                       x1 ≥ 0, x2 ≥ 0            x1  +      x2 ≥ 150
               Optimal solution: x  = 540, x = 252.  Z = 7416
                                   1           2
                   Binding constraints: constraints intersecting at 
                    the optimal solution. ,
                           Nonbinding constraint? , and 
                                       Now consider the 
                                       Solver solution.
                                                       
   Linear Optimization               BU.520.601                             6