Big M Method for Linear Programming

Overview

This lecture explains how to solve linear programming minimization problems with "greater than or equal to" constraints using the Big M method, a modification of the Simplex method.

Introduction to Big M Method

• Big M method extends the Simplex method to handle ≥ constraints by introducing surplus and artificial variables.
• For ≥ constraints, subtract a surplus variable (−S) and add an artificial variable (+A).
• Artificial variables are assigned a large penalty (M) in the objective function to ensure their removal from the final solution.

Problem Setup

• Objective: Minimize Z = 7X₁ + 15X₂ + 20X₃
• Subject to:
  • 2X₁ + 4X₂ + 6X₃ ≥ 24
  • 3X₁ + 9X₂ + 6X₃ ≥ 30
  • X₁, X₂, X₃ ≥ 0
• Adjust constraints by subtracting surplus variables (S₁, S₂) and adding artificial variables (A₁, A₂).

Forming the Initial Table

• Construct initial Simplex table with variables X₁, X₂, X₃, S₁, S₂, A₁, A₂.
• Artificial variables A₁, A₂ have coefficients M in the objective function.
• Fill table rows using the adjusted constraints and objective function coefficients.

Iterative Procedure

• Calculate Zj (sum of products of basic variable coefficients and their column values).
• Compute Cj − Zj for optimality check.
• If any Cj − Zj is negative (for minimization), select the most negative as key column.
• Find key row by computing the minimum positive ratio (solution value/key column value).
• Pivot to swap basic and non-basic variables (entering/leaving variable), update rows using Simplex formulas.
• Repeat iterations: update tables, recalculate Zj and Cj − Zj, and check for optimality.

Reaching the Optimal Solution

• When all Cj − Zj values are zero or positive, the solution is optimal.
• Final variable values: X₁ = 0, X₂ = 6/5, X₃ = 16/5, Z = 82.

Key Terms & Definitions

• Simplex Method — an algorithm for solving linear programming problems.
• Surplus Variable (S) — variable subtracted to convert ≥ constraints to equations.
• Artificial Variable (A) — additional variable introduced for ≥ constraints to start the Simplex process.
• Big M — a large positive number used as a penalty in the objective function for artificial variables.
• Cj — coefficient of a variable in the objective function.
• Zj — calculated value used to check optimality in Simplex.
• Pivot — operation to change basic variables during iteration.

Action Items / Next Steps

• Practice solving similar minimization problems using the Big M method and Simplex iterations.
• Review the steps of forming and updating Simplex tables for problems with artificial variables.