2.3 Simplex Method and Sensitivity Analysis

Linear programming is a powerful tool in operations research for optimizing resource allocation. The Simplex Method, a cornerstone algorithm, efficiently solves these problems by iteratively improving solutions. This topic explores its mechanics and the crucial role of sensitivity analysis in understanding solution robustness.

Mastering these concepts equips industrial engineers to tackle complex optimization challenges. By learning to interpret results and perform sensitivity analysis, you'll gain insights into resource valuation and decision-making under varying conditions, essential skills for effective operations management.

Linear Programming in Standard Form

Converting Constraints and Objective Function

Top images from around the web for Converting Constraints and Objective Function

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

1 of 3

Top images from around the web for Converting Constraints and Objective Function

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

• 

  3.3c. Examples – Simplex Method | Finite Math View original

  Is this image relevant?

1 of 3

• Standard form requires all constraints expressed as equalities with non-negative right-hand sides
• Add slack variables to inequality constraints converting them into equalities
• Introduce surplus variables and artificial variables for greater-than-or-equal-to constraints
• Convert objective function to maximization form by multiplying minimization problems by -1
• Replace variables without sign restrictions with the difference of two non-negative variables
• Ensure coefficient matrix of constraints has full row rank for unique solution

Example of Standard Form Conversion

• Original constraint: 2x + 3y ≤ 10
  • Standard form: 2x + 3y + s = 10 (s is a non-negative slack variable)
• Original objective: Minimize z = 4x - 5y
  • Standard form: Maximize z = -4x + 5y
• Variable without sign restriction: x (unrestricted)
  • Standard form: x = x₁ - x₂ (x₁ and x₂ are non-negative)

Simplex Algorithm for Optimization

Iterative Process and Basic Concepts

• Simplex method moves from one basic feasible solution to another, improving objective function value
• Obtain initial basic feasible solution by setting non-basic variables to zero and solving for basic variables
• Select entering variable based on most negative reduced cost in objective function row
• Determine leaving variable using minimum ratio test to maintain feasibility
• Perform pivot operations to update simplex tableau and move to next basic feasible solution
• Reach optimality when all reduced costs in objective function row are non-negative for maximization problems
• Degeneracy occurs when multiple basic variables are zero, potentially causing cycling in algorithm

Simplex Tableau and Pivot Operations

• Construct initial simplex tableau with objective function coefficients, constraint coefficients, and right-hand side values
• Identify pivot element at intersection of entering variable column and leaving variable row
• Update tableau rows using row operations ($\text{New Row} = \text{Old Row} - \text{Multiple of Pivot Row}$)
• Continue pivoting until optimality conditions are met or infeasibility/unboundedness is detected
• Example pivot operation:
  • Pivot element: 2
  • Old row: [1 2 3 4]
  • Pivot row: [0 2 1 6]
  • New row: [1 0 2.5 -2]

Optimal Solutions and Shadow Prices

Interpreting the Final Simplex Tableau

• Read optimal solution directly from final tableau, with basic variables' values in right-hand side column
• Identify reduced costs in final tableau indicating rate of change in objective function for non-basic variables
• Find shadow prices (dual variables) in bottom row of final tableau, corresponding to original constraints
• Locate objective function value in bottom-right cell of final tableau
• Identify binding constraints by non-zero shadow prices in final tableau
• Determine slack and surplus variables' values, indicating whether constraints are binding or have slack

Economic Interpretation of Shadow Prices

• Shadow prices represent marginal value of resources in constraints
• Positive shadow price indicates potential improvement in objective function by relaxing constraint
• Zero shadow price suggests non-binding constraint with no immediate impact on objective value
• Example: Shadow price of $5 for raw material constraint means objective value increases by$5 for each additional unit of raw material

Sensitivity Analysis of Parameters

Ranges of Optimality and Feasibility

• Examine how changes in coefficients affect optimal solution without re-solving entire problem
• Determine range of optimality for objective function coefficients before optimal solution changes
• Calculate range of feasibility for right-hand side values before current basis becomes infeasible
• Analyze dual prices (shadow prices) representing rate of change in objective function value per unit change in right-hand side of constraint
• Apply 100% rule for simultaneous changes in right-hand side values to determine if optimal basis remains unchanged
• Re-solve problem or use dual simplex method for sensitivity analysis of new variables or constraints

Examples of Sensitivity Analysis

• Objective coefficient range: Coefficient of x₁ can vary from 2 to 5 without changing optimal solution
• Right-hand side range: Resource 1 can increase by 10 units or decrease by 5 units without affecting optimal basis
• Simultaneous changes: Increase Resource 1 by 3 units and Resource 2 by 2 units (total percentage change: 60% < 100%, optimal basis unchanged)

Duality in Linear Programming

Primal-Dual Relationships

• Every linear programming problem (primal) has associated dual problem with reciprocal relationship
• Dual problem provides economic interpretation of primal problem's constraints and variables
• Weak duality theorem states any feasible dual solution provides bound on optimal objective value of primal
• Strong duality theorem asserts if either primal or dual has optimal solution, both do, with equal optimal values
• Complementary slackness conditions relate primal and dual solutions, indicating binding constraints
• Dual simplex method solves dual problem implicitly by working with primal tableau, useful for sensitivity analysis and re-optimization
• Duality principles fundamental in developing solution methods and understanding economic implications of linear programming problems

Constructing and Interpreting Dual Problems

• Primal constraints become dual variables
• Primal variables become dual constraints
• Objective function coefficients and right-hand side values swap positions
• Inequality directions reverse (≤ becomes ≥, and vice versa)
• Example:
  • Primal: Maximize 3x₁ + 2x₂ subject to x₁ + x₂ ≤ 4, 2x₁ + x₂ ≤ 5, x₁, x₂ ≥ 0
  • Dual: Minimize 4y₁ + 5y₂ subject to y₁ + 2y₂ ≥ 3, y₁ + y₂ ≥ 2, y₁, y₂ ≥ 0