KEMBAR78
Sensitivity Analysis: How Changes in An LP's Parameters Affect The LP's Optimal Solution | PDF | Variable (Mathematics) | Theoretical Computer Science
Scribd
Upload
93 views15 pages

Sensitivity Analysis: How Changes in An LP's Parameters Affect The LP's Optimal Solution

Sensitivity analysis examines how changes to an linear program's (LP's) parameters affect its optimal solution. It determines if small changes to objective function coefficients or right-hand sides result in the current basis remaining optimal or a new basis becoming optimal. Sensitivity analysis is important because it allows the optimal solution to be determined without re-solving the LP if a parameter changes within a determined range. Key formulas express an LP's optimal tableau and constraints in terms of its original parameters using the inverse of the basis matrix.

Uploaded by

sirkiber
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
93 views15 pages

Sensitivity Analysis: How Changes in An LP's Parameters Affect The LP's Optimal Solution

Sensitivity analysis examines how changes to an linear program's (LP's) parameters affect its optimal solution. It determines if small changes to objective function coefficients or right-hand sides result in the current basis remaining optimal or a new basis becoming optimal. Sensitivity analysis is important because it allows the optimal solution to be determined without re-solving the LP if a parameter changes within a determined range. Key formulas express an LP's optimal tableau and constraints in terms of its original parameters using the inverse of the basis matrix.

Uploaded by

sirkiber
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 15

Sensitivity Analysis

Sensitivity analysis is concerned with how changes in an LP’s


parameters affect the LP’s optimal solution.

How would changes in the problem’s objective function


coefficients or right-hand sides change this optimal solution?
Sensitivity Analysis
Graphical Analysis of the Effect of a Change
in an Objective Function Coefficient

Let c1 be the contribution to profit by each soldier. For what


values of c1 does the current basis remain optimal?

If the isoprofit lines are flatter than the carpentry constraint
and the current basis is no longer optimal,
A(0,80) will be optimal instead

If the isoprofit lines are steeper than the finishing constraint
and the current basis is no longer optimal,
C(40,20) will be optimal instead.
Therefore, the current basis remains optimal for
Graphical Analysis of the Effect of a Change in a
Right-Hand Side on the LP’s Optimal Solution

The current basis


remains optimal for
Effect of a Change in a Right-Hand Side on the LP’s
Optimal Solution
•As long as the current basis remains optimal, it is a routine matter to
determine how a change in the right-hand side of a constraint
changes the values of the decision variables.

•let b1 = number of available finishing hours. If we change b1 to


100 + Δ, for -20 ≤ Δ ≤ 20

Thus, an increase in the number of available finishing hours results


in an increase in the number of Product X produced and a decrease
in the number of product Y produced.
•Similarly
,
Importance of Sensitivity Analysis

1. The values of an LP’s parameters may change


If a parameter changes, sensitivity analysis often makes it
unnecessary to solve the problem again

For Example,
if the profit contribution of product X increased to $3.50, we
would not have to solve the ChomA problem again because the
current solution remains optimal.
Some Important Formulas

•Assume that we are solving a max LP problem that has m


constraints and n variables.

•we use our knowledge of matrices to show how an LP’s optimal


tableau can be expressed in terms of the LP’s parameters.
Some Important Formulas

Consider this
LP problem for
illustration

Let BVi = basic variable for row i of the optimal tableau. Also
define BV = {BV1, BV2, . . . , BVm} to be the set of basic variables in
the optimal tableau, and define the m x 1 vector

Let NBV = the set of non-basic variables in the optimal tableau


xNBV = (n m) x 1 vector listing the non-basic variables
Some Important Formulas
Some Important Formulas

NBV ={x2, s2, s3}


Some Important Formulas
Expressing the Constraints in Any Tableau
in Terms of B-1 and the Original LP
Expressing the Constraints in Any Tableau
in Terms of B-1 and the Original LP
Multiplying the constraints by B-1, we obtain

These are the constraints for the problem’s optimal tableau


Expressing the Constraints in Any Tableau
in Terms of B-1 and the Original LP

let be the coefficient of xj in the optimal tableau’s row 0;


and cj be coefficient for xj in cNBV
Expressing the Constraints in Any Tableau
in Terms of B-1 and the Original LP

the optimal tableau’s basic variables (x1, x3, and s1) will have zero
coefficients in row 0

You might also like