4.4 Revised simplex method

The revised simplex method is a game-changer for solving big linear programming problems. It's like upgrading from a bicycle to a sports car – faster, more efficient, and better at handling complex situations. This method cuts down on data storage and reduces errors, making it a go-to for tackling large-scale optimization challenges.

At its core, the revised simplex method uses smart matrix operations to find the best solution. It's all about maintaining the right information, updating it efficiently, and making calculated decisions at each step. This approach not only speeds up the process but also opens doors to advanced techniques for even better performance.

Revised Simplex Method Motivation

Computational Efficiency and Data Management

• Revised simplex method improves computational efficiency for large-scale linear programming problems
• Reduces data storage requirements by maintaining only essential information (basis inverse and objective row)
• Significantly reduces round-off errors accumulating in standard simplex method
  • Particularly beneficial for problems with many variables and constraints
• Allows efficient handling of sparse matrices common in large-scale optimization problems
• Facilitates implementation of advanced techniques for selecting entering variables
  • Partial pricing
  • Steepest-edge pricing

Advanced Update Procedures

• Provides framework for implementing sophisticated update procedures
  • Product Form of the Inverse (PFI)
  • Bartels-Golub update
• Enables more efficient matrix operations and updates throughout optimization process

Applying the Revised Simplex Method

Matrix Operations and Variable Selection

• Uses matrix operations to compute necessary information at each iteration
• Maintains and updates basis inverse ($B^{-1}$) throughout optimization process
• Calculates reduced costs for non-basic variables using formula $c_j - c_B^T B^{-1} A_j$
• Selects entering variable based on most negative reduced cost (maximization) or most positive reduced cost (minimization)
• Computes pivot column ($a_q = B^{-1} A_q$) to determine leaving variable using minimum ratio test

Optimality and Solution Calculation

• Reaches optimality when all reduced costs are non-negative (maximization) or non-positive (minimization)
• Obtains final optimal solution by computing $x_B = B^{-1} b$ and setting all non-basic variables to zero
• Iteratively improves solution until optimality criteria are met

Basis Matrix Updates and Operations

Efficient Update Methods

• Updates basis inverse ($B^{-1}$) at each iteration using efficient update formulas
• Employs Product Form of the Inverse (PFI) method to update $B^{-1}$
  • Multiplies $B^{-1}$ with elementary matrices representing row operations
• Utilizes Bartels-Golub update as alternative method
  • Maintains factorization of basis matrix
  • Often leads to improved numerical stability

Matrix Operations and Numerical Stability

• Implements efficient methods for solving systems of linear equations
  • LU decomposition
  • Sherman-Morrison formula
• Applies partial pricing or multiple pricing to reduce computational effort in selecting entering variables
• Employs sparse matrix storage and manipulation techniques for handling large-scale problems
• Considers numerical stability through techniques like LU factorization with partial pivoting
  • Maintains accuracy in matrix operations

Revised vs Standard Simplex Methods

Computational Approach and Efficiency

• Revised simplex method reduces storage requirements compared to standard simplex method
  • Especially beneficial for large-scale problems with many variables and constraints
• Computes only necessary information at each iteration, unlike standard method maintaining entire tableau
• Exhibits better numerical stability and accuracy, particularly for problems prone to round-off errors
• Requires more complex implementation, involving sophisticated programming techniques

Advanced Features and Problem Suitability

• Provides natural framework for implementing advanced pivot selection rules and pricing strategies
  • More challenging to implement in standard simplex method
• Both methods follow fundamental principles of moving between basic feasible solutions
• Revised simplex method preferred for solving large-scale linear programming problems
• Standard simplex method sufficient for smaller problems or educational purposes (classroom demonstrations)