155x Filetype PPTX File size 0.53 MB Source: home.ubalt.edu
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
no reviews yet
Please Login to review.