In-Depth Notes on Sensitivity Analysis and Linear Programming

Sensitivity Analysis

• Definition: Sensitivity analysis studies how changes in a linear programming (LP) model's parameters affect its optimal solution.

• Changes in Constraints:

  • Example: If the constraint $30x<em>1 + 10x</em>2 \leq 600$ changes to $30x<em>1 + 10x</em>2 \leq 610$, sensitivity analysis helps determine the impact on the optimal objective value and decision variables.

• Changes in Objective Function Coefficients:

  • Example: If the coefficient of $x1$ in the objective function $100x1 + 75x_2$ changes to 200, sensitivity analysis evaluates the effect on the solution.

• Importance: It enables decision-makers to understand the robustness of their solutions against changes in constraints and coefficients.

Binding and Non-Binding Constraints

• Binding Constraints:

  • Definition: A constraint is binding if it must be satisfied as an equality at the optimal solution (i.e., $g_i(x) = 0$).
  • Example in context: In the LP with $x1^* = 15$ and $x2^* = 15$, both constraints are binding since they equal the resource limits.

• Non-Binding Constraints:

  • Definition: A constraint is non-binding if there's a strict inequality (i.e., $g_i(x) > 0$) at the optimal solution.
  • Affect on Sensitivity Analysis: Changes to the right-hand side of non-binding constraints typically do not affect the optimal solution unless they become binding.

Example 2: Microbrewer Problem

• Setup: Producing four types of beer: Light, Dark, Ale, Premium.

• Decision Variables: Amount produced for each type denoted as $x{Light}, x{Dark}, x{Ale}, x{Premium}$.

• Objective Function: Maximize total revenue:
  $R = 6x<em>{Light} + 5x</em>{Dark} + 3x<em>{Ale} + 7x</em>{Premium}$

• Constraints:

  • Non-negativity:
    $x<em>{Light}, x</em>{Dark}, x<em>{Ale}, x</em>{Premium} \geq 0$
  • Malt Inventory:
    $x<em>{Light} + x</em>{Dark} + 3x_{Premium} \leq 50$
  • Hops Inventory:
    $2x<em>{Light} + x</em>{Dark} + 2x<em>{Ale} + x</em>{Premium} \leq 150$
  • Yeast Inventory:
    $x<em>{Light} + x</em>{Dark} + x<em>{Ale} + x</em>{Premium} \leq 80$

• Solver Solution: All constraints are binding; changes to their right-hand sides will likely affect the optimal solution.

Shadow Price Analysis

• Definition: The shadow price of a resource represents the improvement in the objective function if the constraint is relaxed by one unit.
• Example with Malt Constraint:
  • Allowable increase: If the malt constraint increases from 50 to 50+a (where $0 \leq a \leq 30$), the objective value increases by $3a$.
  • Allowable decrease: Reducing the malt constraint from 50 to 50-a (where $0 \leq a \leq 40$) decreases the objective value by $3a$.
  • If changes exceed these limits, re-solving the LP is necessary.

Example 3: Software Sales Manager Problem

• Setup: Dispatch representatives to three conventions; 6 representatives available in two branches.
• Objective: Formulate an LP that minimizes airfares given constraints on the number of representatives sent to each location.
  • Decision Variables: Number of representatives sent to each location.
  • Objective Function: Minimize total fare costs based on selected routes.
  • Constraints: At least 2 to Los Angeles, 5 to Saint Louis, and 4 to Detroit.

Issues in LP Solutions

• Infeasible Solutions: Occur when no feasible set exists. Example:
  $\text{Maximize } 2x<em>1 + x</em>2 \text{ subject to } x<em>1 + x</em>2 \leq 10 \text{ and } 2x<em>1 + x</em>2 \geq 22$

• Unbounded Solutions: Occur when an optimal solution expands infinitely. Example:
  $\text{Maximize } 2x<em>1 + x</em>2 \text{ subject to } x<em>1 + x</em>2 \geq 10$

Key Notes

• Sensitivity analysis is crucial for understanding the effects of changes in linear programming models.
• Binding constraints have significant impacts on the optimal solutions and shadow prices, while non-binding constraints typically do not unless they become binding.