Linear Programming - Simplex Computational Procedure, Geometric Interpretation, Revised Simplex Method, Duality, Degeneracy, Perturbation Techniques

1. Introduction to Linear Programming

Linear Programming (LP) is a mathematical technique used to optimize a linear objective function, subject to a set of linear constraints. It's widely used in various fields like operations research, economics, engineering, and management to make optimal decisions in resource allocation, production planning, scheduling, and more. The core idea is to find the best possible outcome (maximum profit, minimum cost) when the relationship between variables is linear.

An LP problem can be formulated as: Maximize (or Minimize) $ Z = c_1x_1 + c_2x_2 + ... + c_nx_n $ Subject to: $ a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n \le (\text{or} \ge, =) b_1 $ $ a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n \le (\text{or} \ge, =) b_2 $ ... $ a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n \le (\text{or} \ge, =) b_m $ And $ x_1, x_2, ..., x_n \ge 0 $ (Non-negativity constraints)

Here, $ Z $ is the objective function, $ x_i $ are decision variables, $ c_i $ are coefficients of the objective function, $ a_{ij} $ are coefficients of the constraints, and $ b_i $ are the right-hand side values of the constraints.

2. Geometric Interpretation of Linear Programming

For problems with two decision variables ($ x_1 $ and $ x_2 $), the feasible region can be visualized graphically. Each linear constraint defines a half-plane, and the intersection of all these half-planes (including the non-negativity constraints) forms the feasible region. This region is a convex polygon (or polyhedron in higher dimensions).

The objective function $ Z = c_1x_1 + c_2x_2 $ can be represented by a family of parallel lines (isoprofit or isocost lines). The optimal solution lies at one of the corner points (vertices) of the feasible region. To find the optimum, we move the objective function line parallel to itself in the direction of optimization (upwards for maximization, downwards for minimization) until it touches the last point(s) of the feasible region. This last point will be the optimal solution.

Example: Maximize $ Z = 3x_1 + 2x_2 $ Subject to: $ x_1 + x_2 \le 4 $ $ 2x_1 + x_2 \le 6 $ $ x_1, x_2 \ge 0 $ The feasible region is a polygon. The vertices are (0,0), (3,0), (2,2), and (0,4). Evaluating Z at each vertex: (0,0): $ Z = 0 $ (3,0): $ Z = 9 $ (2,2): $ Z = 3(2) + 2(2) = 6 + 4 = 10 $ (0,4): $ Z = 3(0) + 2(4) = 8 $ The maximum value of Z is 10 at ($ x_1=2, x_2=2 $).

3. Simplex Computational Procedure

The Simplex method is an algebraic algorithm for solving LP problems, especially those with many variables and constraints where graphical methods are impractical. It systematically moves from one feasible corner point to an adjacent one, improving the objective function value at each step until the optimal solution is reached.

3.1 Standard Form of an LP Problem

Before applying the Simplex method, the LP problem must be converted into standard form: 1. Objective Function: All problems are converted to maximization. If it's minimization, multiply the objective function by -1. 2. Constraints: All constraints must be equalities. * For ' $ \le $' constraints, add a non-negative 'slack variable'. * For ' $ \ge $' constraints, subtract a non-negative 'surplus variable' and add an artificial variable. * For '=' constraints, add an artificial variable. 3. Right-Hand Side (RHS): All RHS values ($ b_i $) must be non-negative. If any $ b_i < 0 $, multiply the entire constraint by -1 (reversing the inequality sign if necessary). 4. Non-negativity: All variables must be non-negative. If a variable can be negative, replace it with the difference of two non-negative variables.

Example Conversion: Minimize $ Z = 2x_1 - 3x_2 $ Subject to: $ x_1 + x_2 \le 7 $ $ 2x_1 + x_2 \ge 3 $ $ x_1, x_2 \ge 0 $ Convert to maximization: Maximize $ Z' = -Z = -2x_1 + 3x_2 $ Add slack variable $ s_1 \ge 0 $ to the first constraint: $ x_1 + x_2 + s_1 = 7 $ Subtract surplus variable $ s_2 \ge 0 $ and add artificial variable $ a_1 \ge 0 $ to the second constraint: $ 2x_1 + x_2 - s_2 + a_1 = 3 $ The problem becomes: Maximize $ Z' = -2x_1 + 3x_2 + 0s_1 - 0s_2 - Ma_1 $ (M is a very large positive number in the Big M method) Subject to: $ x_1 + x_2 + s_1 = 7 $ $ 2x_1 + x_2 - s_2 + a_1 = 3 $ $ x_1, x_2, s_1, s_2, a_1 \ge 0 $

3.2 The Simplex Tableau

The Simplex method uses a table called a tableau to organize the calculations. The initial tableau is set up based on the standard form of the problem. Key components of a tableau: * Basic Variables (BV): Variables that form an identity matrix in the current tableau (initially, slack variables). * Coefficients of Objective Function ($ c_j $): Coefficients of the variables in the objective function. * $ Z_j $ Row: Calculated for each column $ j $ as the dot product of the $ c_j $ of the basic variables and the column $ j $ values. $ Z_j = \sum_{i} c_{Bi} a_{ij} $. * $ C_j - Z_j $ Row (or $ Z_j - C_j $ for minimization): The difference between the objective function coefficients and the $ Z_j $ values. For maximization, if all $ C_j - Z_j \le 0 $, the current solution is optimal. * RHS Column: The current values of the basic variables (solution vector). * Iteration Number: Keeps track of the steps.

3.3 Steps of the Simplex Method (Maximization)

1. Initialization: Convert the LP problem to standard form. Set up the initial Simplex tableau. If artificial variables are used, employ the Big M method or the Two-Phase method.
2. Optimality Check: Examine the $ C_j - Z_j $ row. If all entries are less than or equal to zero ($ C_j - Z_j \le 0 $), the current solution is optimal. Stop.
3. Entering Variable Selection: If optimality is not reached, select the variable to enter the basis. Choose the column with the most positive value in the $ C_j - Z_j $ row. This column is the 'pivot column'. The variable corresponding to this column is the 'entering variable'.
4. Leaving Variable Selection: Calculate the 'minimum ratio' for each row $ i $ by dividing the RHS value by the corresponding element in the pivot column ($ \theta_i = \frac{RHS_i}{a_{ik}} $), where $ a_{ik} $ is the element in row $ i $ and pivot column $ k $. Ignore rows where the pivot column element is zero or negative. The row with the minimum non-negative ratio corresponds to the 'leaving variable' (the basic variable in that row). The element at the intersection of the pivot column and the minimum ratio row is the 'pivot element'.
5. Pivoting: Perform row operations to make the pivot element '1' and all other elements in the pivot column '0'. This transforms the tableau to represent the new basic feasible solution.
6. Iteration: Repeat steps 2-5 until the optimal solution is found.

3.4 Handling Artificial Variables (Big M Method)

If artificial variables are introduced, they are penalized heavily in the objective function: * For maximization, assign a large negative coefficient (-M). * For minimization, assign a large positive coefficient (+M). The goal is to drive these artificial variables to zero in the optimal solution. If any artificial variable remains in the basis with a positive value at the end of the optimization (and the original problem had a feasible solution), then the original LP problem has no feasible solution.

4. Duality in Linear Programming

Every linear programming problem, called the 'primal problem', has an associated linear programming problem called the 'dual problem'. The dual problem provides valuable insights into the primal problem, particularly concerning the sensitivity of the optimal solution to changes in the constraints.

4.1 Forming the Dual Problem

Given a primal LP problem: Maximize $ Z = c_1x_1 + ... + c_nx_n $ Subject to: $ A_{m \times n} \mathbf{x} \le \mathbf{b} $ $ \mathbf{x} \ge 0 $ The dual problem is formed as follows: Minimize $ W = b_1y_1 + ... + b_my_m $ Subject to: $ A^T \mathbf{y} \ge \mathbf{c} $ $ \mathbf{y} \ge 0 $ Where $ A^T $ is the transpose of matrix A, $ \mathbf{y} $ are the dual variables, and $ \mathbf{c} $ and $ \mathbf{b} $ are vectors.

Rules for Forming the Dual:

• If Primal is Max, Dual is Min. If Primal is Min, Dual is Max.
• The number of constraints in the Primal equals the number of variables in the Dual, and vice versa.
• The objective function coefficients of the Primal become the RHS of the Dual constraints.
• The RHS of the Primal constraints become the objective function coefficients of the Dual.
• The constraint matrix of the Dual is the transpose of the Primal's constraint matrix.
• Inequality signs are reversed ( $ \le $ in Primal Max becomes $ \ge $ in Dual Min).
• Variable types: If Primal variables are unrestricted in sign, the corresponding Dual constraints are equalities. If Primal constraints are equalities, the corresponding Dual variables are unrestricted.

4.2 Duality Theorems

1. Weak Duality Theorem: For any feasible solution $ \mathbf{x} $ of the Primal problem and any feasible solution $ \mathbf{y} $ of the Dual problem, $ Z(\mathbf{x}) \le W(\mathbf{y}) $. This means the objective value of the Primal is always less than or equal to the objective value of the Dual.
2. Strong Duality Theorem: If both the Primal and Dual problems have feasible solutions, then their optimal objective values are equal: $ Z_{optimal} = W_{optimal} $.
3. Complementary Slackness Theorem: If $ \mathbf{x}^* $ and $ \mathbf{y}^* $ are optimal solutions to the Primal and Dual problems, respectively, then for each $ i $ and $ j $:
   • $ y_i^* (A_i \mathbf{x}^* - b_i) = 0 $ (Primal constraint $ i $ is non-binding or Dual variable $ y_i^* $ is zero)
   • $ x_j^* ( (A^T)_j \mathbf{y}^* - c_j ) = 0 $ (Dual constraint $ j $ is non-binding or Primal variable $ x_j^* $ is zero)
   In simpler terms: If a primal variable is positive, its corresponding dual constraint must be binding (equal). If a primal constraint is non-binding, its corresponding dual variable must be zero.

5. Degeneracy in Linear Programming

Degeneracy occurs in an LP problem when, at a basic feasible solution, one or more basic variables have a value of zero. This typically happens when the minimum ratio test in the Simplex method results in a tie (multiple rows have the same minimum non-negative ratio).

5.1 Causes and Consequences

Causes:

• A tie in the minimum ratio test during the Simplex procedure.
• The feasible region has redundant constraints or multiple constraints are binding at a vertex.

Consequences:

• Cycling: The Simplex method might cycle, meaning it repeats a sequence of basic feasible solutions without reaching the optimum. This is rare in practice but theoretically possible.
• Slow Convergence: The algorithm might take more iterations than necessary.
• Zero Value Basic Variables: A basic variable having a value of zero means that increasing or decreasing it slightly might violate a constraint or make another variable non-basic.

5.2 Detecting Degeneracy

Degeneracy is detected when, during the minimum ratio calculation, two or more basic variables yield the same minimum non-negative ratio.

5.3 Handling Degeneracy (Perturbation Techniques)

To prevent cycling and ensure the Simplex method terminates, perturbation techniques are used. The most common is **Bland's Rule** (or lexicographical method).

5.4 Bland's Rule

Bland's Rule modifies the selection criteria for entering and leaving variables:

1. Entering Variable: Instead of choosing the column with the most positive $ C_j - Z_j $, choose the column with the smallest index $ j $ among those with positive $ C_j - Z_j $.
2. Leaving Variable: If there's a tie in the minimum ratio test, choose the row corresponding to the basic variable with the smallest index among the tied rows.

By systematically choosing the variable with the smallest index, Bland's rule ensures that the algorithm never repeats a basis and thus terminates.

Another perturbation technique involves slightly altering the RHS values. For a degenerate basic solution, replace the RHS vector $ \mathbf{b} $ with $ \mathbf{b}' = \mathbf{b} + \epsilon \mathbf{d} $, where $ \epsilon $ is a very small positive number and $ \mathbf{d} $ is a vector chosen such that $ \mathbf{b}' $ is always positive and the minimum ratio test yields unique minimums. This effectively breaks ties in the ratio test. For example, if the original constraints are $ A\mathbf{x} = \mathbf{b} $, we consider $ A\mathbf{x} = \mathbf{b}^{(k)} $, where $ \mathbf{b}^{(0)} = \mathbf{b} $ and $ \mathbf{b}^{(k+1)} $ is obtained by perturbing $ \mathbf{b}^{(k)} $.

6. Revised Simplex Method

The standard Simplex method involves a tableau that can become very large for problems with many variables and constraints. The Revised Simplex method is an alternative computational procedure that recomputes the necessary components of the Simplex tableau directly, rather than updating the entire tableau. It's often more efficient computationally, especially when using computers.

6.1 Basic Principles

The Revised Simplex method works with the fundamental relationships derived from the Simplex tableau. It focuses on updating the basis inverse ($ B^{-1} $) and related vectors. Consider the LP in standard form: Maximize $ Z = \mathbf{c}_B \mathbf{x}_B + \mathbf{c}_N \mathbf{x}_N $ subject to $ B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b} $, $ \mathbf{x}_B, \mathbf{x}_N \ge 0 $. The basic solution is $ \mathbf{x}_B = B^{-1}\mathbf{b} $. The objective function value is $ Z = \mathbf{c}_B \mathbf{x}_B = \mathbf{c}_B B^{-1} \mathbf{b} $. The optimality condition requires checking the reduced costs ( $ C_j - Z_j $) for non-basic variables. The reduced cost for a non-basic variable $ x_j $ is $ \bar{c}_j = c_j - \mathbf{c}_B B^{-1} \mathbf{a}_j $, where $ \mathbf{a}_j $ is the column corresponding to $ x_j $ in the original constraint matrix.

6.2 Algorithm Steps

1. Initialization: Find an initial basic feasible solution and the corresponding basis matrix $ B $. Calculate $ B^{-1} $ and the initial solution $ \mathbf{x}_B = B^{-1}\mathbf{b} $. Set up the initial objective function coefficients for basic variables $ \mathbf{c}_B $.
2. Calculate Dual Variables ( $ \pi $ vector): Compute the vector $ \boldsymbol{\pi} = \mathbf{c}_B B^{-1} $. This vector represents the dual prices.
3. Check Optimality: For each non-basic variable $ x_j $, calculate its reduced cost: $ \bar{c}_j = c_j - \boldsymbol{\pi} \mathbf{a}_j $. If all $ \bar{c}_j \le 0 $ (for maximization), the current solution is optimal. Stop.
4. Select Entering Variable: Choose the non-basic variable $ x_k $ with the most positive reduced cost ($ \bar{c}_k = \max_{j \in N} \{ \bar{c}_j \} $). This is the entering variable.
5. Calculate Update Vector: Compute $ \mathbf{y}_k = B^{-1} \mathbf{a}_k $, where $ \mathbf{a}_k $ is the column of $ x_k $ in the original constraint matrix.
6. Select Leaving Variable: Perform the minimum ratio test: $ \theta = \min_{i} \{ \frac{x_{B_i}}{y_{ik}} \} $ for all $ y_{ik} > 0 $. The minimum occurs at row $ r $, identifying the leaving basic variable $ x_{B_r} $.
7. Update Basis Inverse: Update $ B^{-1} $ to reflect the change in basis. The new basis matrix $ B_{new} $ replaces column $ r $ of $ B $ with $ \mathbf{a}_k $. $ B_{new}^{-1} $ can be computed efficiently using the formula for matrix inversion.
8. Update Solution: Calculate the new basic feasible solution $ \mathbf{x}_{B_{new}} = B_{new}^{-1}\mathbf{b} $.
9. Repeat: Go back to step 2.

The Revised Simplex method can be implemented in two main forms: the **Product Form of the Inverse** (where $ B^{-1} $ is stored as a product of elementary matrices) and the **Inverse Matrix Form** (where $ B^{-1} $ is updated directly). The product form is generally preferred for large-scale problems.

7. Perturbation Techniques (Revisited in context of Simplex)

Perturbation techniques are primarily used to handle degeneracy and prevent cycling in the Simplex method. While Bland's Rule is a rule-based approach, other perturbation methods involve modifying the problem slightly.

7.1 Lexicographical Method (Bland's Rule)

As discussed earlier, Bland's Rule addresses degeneracy by systematically choosing the entering and leaving variables based on their indices. This ensures that the sequence of bases generated is unique and finite.

7.2 Perturbing RHS Values

This method involves adding a small, positive parameter $ \epsilon $ to the RHS values in a specific way. If the standard form is $ A\mathbf{x} = \mathbf{b} $, we consider the modified system $ A\mathbf{x} = \mathbf{b}' $, where $ \mathbf{b}' $ is a vector derived from $ \mathbf{b} $ and powers of $ \epsilon $. For example, if the original RHS is $ \mathbf{b} = (b_1, b_2, ..., b_m)^T $, the perturbed RHS might be $ \mathbf{b}' = (b_1 + \epsilon, b_2 + \epsilon^2, ..., b_m + \epsilon^m)^T $.

When performing the minimum ratio test, instead of comparing simple ratios $ \frac{x_{B_i}}{y_{ik}} $, we compare lexicographically the vectors $ ( \frac{x_{B_1}}{y_{1k}}, \frac{x_{B_2}}{y_{2k}}, ..., \frac{x_{B_m}}{y_{mk}} ) $. The perturbation ensures that ties in the ratio test are broken, and the algorithm progresses uniquely. After the optimal solution is found for the perturbed problem, we can substitute $ \epsilon = 0 $ to get the optimal solution for the original problem. This method guarantees termination but can be computationally more intensive to implement correctly.

Example of Perturbation in Ratio Test: Suppose in a tie, row 1 gives ratio 2 and row 3 gives ratio 2. Using standard Simplex, we might pick either. With perturbation, we compare vectors: Row 1: $ (2, 2^2, ...) $ Row 3: $ (2, 3^2, ...) $ Lexicographically, $ (2, 2^2, ...) < (2, 3^2, ...) $, so row 1 is chosen as the leaving variable.