Big M Method: Linear Programming with Artificial Variables & Infeasibility Handling

SECTION 01

Introduction

Why Do We Need the Big M Method?

Standard simplex method requires an obvious initial basic feasible solution
Easy when all constraints are \(\leq\) type (use slack variables)
Problem arises with \(\geq\) and \(=\) constraints

Example: Problematic Constraints

\(x_1 + 2x_2 \geq 8\) (need surplus + artificial variables)
\(3x_1 + x_2 = 12\) (need artificial variables)
No obvious initial BFS available

The Challenge

How do we find an initial basic feasible solution when we can’t use slack variables alone?

SECTION 02

The Big M Method Concept

Core Idea

Add artificial variables to create an obvious initial BFS
Assign a very large penalty (\(M\)) to artificial variables in the objective function
Force artificial variables out of the optimal solution
If any artificial variable remains positive in the final solution, the original problem is infeasible

Key Insight

\(M\) is assumed to be so large that any solution with artificial variables will be worse than any solution without them.

SECTION 03

When to Use Big M Method

Use Big M When:

\(\geq\) constraints present
Equality constraints present
Mixed constraint types
No obvious initial BFS

Don’t Need Big M When:

All constraints are \(\leq\) type
Can use slack variables only
Obvious initial BFS exists

SECTION 04

Big M Method Procedure

Step-by-Step Procedure

Convert to standard form
- Add slack variables for \(\leq\) constraints
- Add surplus and artificial variables for \(\geq\) constraints
- Add artificial variables for \(=\) constraints
Modify objective function
- Subtract \(M \times\) (artificial variables) for maximization
- Add \(M \times\) (artificial variables) for minimization
Solve using simplex method
Interpret results

SECTION 05

Converting Different Constraint Types

\(\leq\) Constraint

\(2x_1 + 3x_2 \leq 10\)

\(\Rightarrow 2x_1 + 3x_2 + s_1 = 10\), where \(s_1 \geq 0\)

\(\geq\) Constraint

\(x_1 + 2x_2 \geq 8\)

\(\Rightarrow x_1 + 2x_2 - s_2 + a_1 = 8\), where \(s_2, a_1 \geq 0\)

\(=\) Constraint

\(3x_1 + x_2 = 12\)

\(\Rightarrow 3x_1 + x_2 + a_2 = 12\), where \(a_2 \geq 0\)

SECTION 06

Objective Function Modification

Maximization Problem

Original: \(\max z = c_1x_1 + c_2x_2\)

With artificial variables \(a_1, a_2\):

\(\max z = c_1x_1 + c_2x_2 - Ma_1 - Ma_2\)

Penalty for artificial variables

Minimization Problem

Original: \(\min w = c_1x_1 + c_2x_2\)

With artificial variables \(a_1, a_2\):

\(\min w = c_1x_1 + c_2x_2 + Ma_1 + Ma_2\)

Penalty for artificial variables

SECTION 07

Detailed Example

Example Problem Setup

Example (Complete Big M Example)

Maximize \(z = 3x_1 + 2x_2\)

Subject to:

\[\begin{aligned} x_1 + x_2 &\geq 4 \\ 2x_1 + x_2 &\leq 8 \\ x_1 + 3x_2 &= 9 \\ x_1, x_2 &\geq 0 \end{aligned}\]

Challenge

Mixed constraint types
Cannot use slack variables alone for initial BFS
Need Big M method to handle \(\geq\) and \(=\) constraints

SECTION 08

Step 1: Convert to Standard Form

\(s_1\): surplus variable for constraint 1
\(a_1\): artificial variable for constraint 1
\(s_2\): slack variable for constraint 2
\(a_2\): artificial variable for constraint 3

SECTION 09

Step 2: Modify Objective Function

Modified: \(\max z = 3x_1 + 2x_2 + 0s_1 + 0s_2 - Ma_1 - Ma_2\)

Initial Basic Variables

Basic variables: \(a_1, s_2, a_2\) (form identity matrix)
Non-basic variables: \(x_1, x_2, s_1\) (set to zero)
Initial BFS: \(a_1 = 4, s_2 = 8, a_2 = 9\)
Initial objective: \(z = -M(4) - M(9) = -13M\)

SECTION 10

Step 3: Initial Simplex Tableau

Basic	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(a_1\)	\(a_2\)	RHS
\(z\)	\(-3\)	\(-2\)	\(0\)	\(0\)	\(M\)	\(M\)	\(0\)
\(a_1\)	\(1\)	\(1\)	\(-1\)	\(0\)	\(1\)	\(0\)	\(4\)
\(s_2\)	\(2\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(8\)
\(a_2\)	\(1\)	\(3\)	\(0\)	\(0\)	\(0\)	\(1\)	\(9\)

Problem!

Basic variables \(a_1\) and \(a_2\) have non-zero coefficients in the \(z\)-row. We need to eliminate them first!

SECTION 11

Step 4: Eliminate Artificial Variables from Z-row

Row 0: \(z - 3x_1 - 2x_2 + Ma_1 + Ma_2 = 0\)
Row 1: \(a_1 = 4 - x_1 - x_2 + s_1\)
Row 3: \(a_2 = 9 - x_1 - 3x_2\)

Substitute:

\[\begin{aligned} z &= 3x_1 + 2x_2 - M(4 - x_1 - x_2 + s_1) - M(9 - x_1 - 3x_2) \\ &= 3x_1 + 2x_2 - 4M + Mx_1 + Mx_2 - Ms_1 - 9M + Mx_1 + 3Mx_2 \\ &= (3 + 2M)x_1 + (2 + 4M)x_2 - Ms_1 - 13M \end{aligned}\]

New \(z\)-row: \(z - (3 + 2M)x_1 - (2 + 4M)x_2 + Ms_1 = -13M\)

SECTION 12

Corrected Initial Tableau

Basic	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(a_1\)	\(a_2\)	RHS
\(z\)	\(-(3+2M)\)	\(-(2+4M)\)	\(M\)	\(0\)	\(0\)	\(0\)	\(-13M\)
\(a_1\)	\(1\)	\(1\)	\(-1\)	\(0\)	\(1\)	\(0\)	\(4\)
\(s_2\)	\(2\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(8\)
\(a_2\)	\(1\)	\(3\)	\(0\)	\(0\)	\(0\)	\(1\)	\(9\)

Ready for Iterations

Most negative coefficient: \(-(2+4M)\) for \(x_2\)
Since \(M\) is very large, \(2+4M\) is the largest coefficient
\(x_2\) enters the basis

SECTION 13

Iteration 1: Pivot Selection

Ratio test for leaving variable:

Row 1: \(4/1 = 4\)
Row 2: \(8/1 = 8\)
Row 3: \(9/3 = 3\) \(\leftarrow\) minimum

Leaving variable: \(a_2\) (row 3) Pivot element: \(3\) (intersection of \(x_2\) column and \(a_2\) row)

Basic	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(a_1\)	\(a_2\)	RHS
\(z\)	\(-(3+2M)\)	\(-(2+4M)\)	\(M\)	\(0\)	\(0\)	\(0\)	\(-13M\)
\(a_1\)	\(1\)	\(1\)	\(-1\)	\(0\)	\(1\)	\(0\)	\(4\)
\(s_2\)	\(2\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(8\)
\(a_2\)	\(1\)	\(\boxed{3}\)	\(0\)	\(0\)	\(0\)	\(1\)	\(9\)

SECTION 14

Iteration 1: Pivot Operations

\(R_3' = R_3 \div 3\): \((1/3, 1, 0, 0, 0, 1/3, 3)\)

Step 2: Make other elements in \(x_2\) column = 0

\(R_0' = R_0 + (2+4M) \times R_3'\)

\(R_1' = R_1 - 1 \times R_3'\)

\(R_2' = R_2 - 1 \times R_3'\)

Basic	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(a_1\)	\(a_2\)	RHS
\(z\)	\(-(7/3+2M)\)	\(0\)	\(M\)	\(0\)	\(0\)	\((2+4M)/3\)	\(6-4M\)
\(a_1\)	\(2/3\)	\(0\)	\(-1\)	\(0\)	\(1\)	\(-1/3\)	\(1\)
\(s_2\)	\(5/3\)	\(0\)	\(0\)	\(1\)	\(0\)	\(-1/3\)	\(5\)
\(x_2\)	\(1/3\)	\(1\)	\(0\)	\(0\)	\(0\)	\(1/3\)	\(3\)

SECTION 15

Iteration 2: Continue Process

Ratio test:

Row 1: \(1 \div (2/3) = 3/2 = 1.5\)
Row 2: \(5 \div (5/3) = 3\)
Row 3: \(3 \div (1/3) = 9\)

Leaving variable: \(a_1\) (minimum ratio = 1.5)

After pivot operations:

Basic	\(x_1\)	\(x_2\)	\(s_1\)	\(s_2\)	\(a_1\)	\(a_2\)	RHS
\(z\)	\(0\)	\(0\)	\(M-7/2\)	\(0\)	\((7/2+2M)\)	\(1/2\)	\(21/2\)
\(x_1\)	\(1\)	\(0\)	\(-3/2\)	\(0\)	\(3/2\)	\(-1/2\)	\(3/2\)
\(s_2\)	\(0\)	\(0\)	\(5/2\)	\(1\)	\(-5/2\)	\(1/2\)	\(5/2\)
\(x_2\)	\(0\)	\(1\)	\(1/2\)	\(0\)	\(-1/2\)	\(1/2\)	\(5/2\)

SECTION 16

Final Solution and Interpretation

Optimality Check

All coefficients in \(z\)-row are non-negative:

\(M - 7/2 > 0\) (since \(M\) is very large)
\(7/2 + 2M > 0\)
\(1/2 > 0\)

Solution is optimal!

Optimal Solution

\(x_1 = 3/2 = 1.5\)
\(x_2 = 5/2 = 2.5\)
\(s_2 = 5/2 = 2.5\) (slack in constraint 2)
\(z = 21/2 = 10.5\)

Key Observation

Both artificial variables (\(a_1\) and \(a_2\)) are non-basic with value 0. This confirms the original problem has a feasible solution.

SECTION 17

Interpretation of Results

Possible Outcomes of Big M Method

Case 1: Optimal Solution Found (Our Example)

All artificial variables are non-basic (value = 0)
Finite optimal value obtained
Original problem has optimal solution

Case 2: Unbounded Solution

Ratio test yields no finite minimum
Objective can be increased indefinitely
Same as regular simplex method

Case 3: Infeasible Solution

One or more artificial variables remain basic with positive values
Optimal value contains \(-M\) terms
Original problem has no feasible solution

SECTION 18

Detecting Infeasibility

Consider the modified problem:

\[\begin{aligned} \text{Maximize } z &= x_1 + x_2 \\ \text{Subject to: } x_1 + x_2 &\geq 5 \\ x_1 + x_2 &\leq 3 \\ x_1, x_2 &\geq 0 \end{aligned}\]

Clearly infeasible: cannot have \(x_1 + x_2 \geq 5\) and \(x_1 + x_2 \leq 3\) simultaneously
Big M method would terminate with artificial variable(s) in the basis
Final objective value would contain negative \(M\) terms

SECTION 19

Advantages and Disadvantages

Advantages of Big M Method

Versatility: Handles any type of constraint ( \(\leq\), \(\geq\), \(=\))
Single-phase approach: No need for separate phases
Conceptually simple: Easy to understand penalty concept
Detects infeasibility: Clearly identifies infeasible problems
Standard implementation: Works with regular simplex tableau

SECTION 20

Disadvantages of Big M Method

Numerical issues: Large \(M\) values can cause computational problems
Round-off errors: Floating-point arithmetic complications
\(M\) value selection: How large should \(M\) be?
Computational overhead: Extra variables increase problem size
Interpretation complexity: Final tableau may have \(M\) terms

Practical Consideration

In computer implementations, choose \(M\) large enough to ensure dominance but not so large as to cause numerical instability.

SECTION 21

Comparison with Two-Phase Method

Big M vs Two-Phase Method

Big M Method

Single phase
Uses penalty parameter \(M\)
Can have numerical issues
Simpler conceptually
Direct approach

Two-Phase Method

Two separate phases
No penalty parameter
More numerically stable
More complex procedure
Systematic approach

When to Use Which?

Big M: Hand calculations, educational purposes, simple problems
Two-Phase: Computer implementations, large problems, numerical stability concerns

SECTION 22

Practice Problems

Practice Problem 1

Example:

Minimize \(w = 2x_1 + 3x_2\)

Subject to:

\[\begin{aligned} x_1 + x_2 &\geq 3 \\ 2x_1 + x_2 &\geq 4 \\ x_1, x_2 &\geq 0 \end{aligned}\]

Your Task

Convert to standard form using Big M method
Set up initial tableau
Identify the entering and leaving variables for first iteration
What would indicate infeasibility in this problem?

SECTION 23

Practice Problem 2

Example:

Maximize \(z = x_1 + 2x_2\)

Subject to:

\[\begin{aligned} x_1 + x_2 &= 4 \\ x_1 - x_2 &\leq 2 \\ x_1, x_2 &\geq 0 \end{aligned}\]

Key Questions

How many artificial variables are needed?
What is the initial basic feasible solution?
How do you modify the objective function?

SECTION 24

Additional Practice

Practice Problem 3

Example:

Maximize \(z = 2x_1 + x_2\)

Subject to:

\[\begin{aligned} x_1 + 2x_2 &\leq 6 \\ 3x_1 + x_2 &\geq 9 \\ x_1 + x_2 &= 4 \\ x_1, x_2 &\geq 0 \end{aligned}\]

Mixed Constraints Challenge

This problem contains all three constraint types
Identify which variables are needed for each constraint
How would you set up the initial tableau?

SECTION 25

Summary

Key Takeaways

Purpose: Big M method handles problems without obvious initial BFS
Mechanism: Artificial variables with large penalties
Process: Standard form \(\to\) modify objective \(\to\) solve \(\to\) interpret
Outcomes: Optimal, unbounded, or infeasible
Critical: Artificial variables must be eliminated from final solution

Success Criteria

All artificial variables non-basic in final solution
Finite optimal value without \(M\) terms
Satisfies original constraints

SECTION 26

Implementation Checklist

Convert all constraints to standard form correctly
Add appropriate artificial variables
Modify objective function with correct \(M\) signs
Eliminate artificial variables from \(z\)-row initially
Apply simplex method systematically
Check final solution for artificial variables
Interpret results correctly (optimal/unbounded/infeasible)

Common Mistake

Forgetting to eliminate artificial variable coefficients from the initial \(z\)-row!

← Previous: Revised Simplex Method Next: The Two-Phase Method →