Simplex Method: Solving Linear Programming Problems

TAKEAWAYS:

• The Simplex Method solves linear programming problems by moving along the feasible region’s boundary to find the optimal solution.
• Standard form requires all constraints to be equalities (≤ or ≥ converted to =) with slack/surplus variables and a non-negative objective function.
• Simplex tables organize coefficients to iteratively improve the objective function until optimality is reached (no negative coefficients in the bottom row).
• Pivoting selects the entering and leaving variables based on the minimum ratio test and most negative coefficient in the objective row.
• The method guarantees the optimal solution if one exists, but may fail for unbounded or infeasible problems.
• Real-world applications include resource allocation (e.g., factory production), transportation logistics (e.g., Daraz delivery routes), and financial planning (e.g., Ncell’s budget optimization).

1. Introduction to the Simplex Method

The Simplex Method is an algorithmic approach to solve Linear Programming (LP) problems graphically or algebraically. While the graphical method works for 2-variable problems, the Simplex Method extends this to n variables by using simplex tables to systematically improve the objective function.

Why Use Simplex?

• Handles complex constraints (e.g., ≥, ≤, =) with slack/surplus variables.
• Efficient for large-scale problems (e.g., NEPSE stock portfolio optimization).
• Provides exact solutions (unlike approximation methods).

Key Terms

2. Standard Form of Linear Programming Problems

Before applying Simplex, convert the problem into standard form:

1. Objective function: Maximize $Z=c_1{x}_1+c_2{x}_2+...+c_n{x}_n$.
2. Constraints:
   • All ≤ constraints become equalities by adding slack variables ($s_i\ge 0$).
   • All ≥ constraints become equalities by subtracting surplus variables ($s_i\ge 0$).
   • All variables (including slack/surplus) must be non-negative.

Example: Converting to Standard Form

Problem: Maximize $Z=3x_1+2x_2$ Subject to:

• $x_1+x_2\le 100$ (≤ constraint)
• $2x_1-x_2\ge 20$ (≥ constraint)
• $x_1,x_2\ge 0$

Solution:

1. Add slack variable $s_1$ to the first constraint: $x_1+x_2+s_1=100$.
2. Subtract surplus variable $s_2$ from the second constraint: $2x_1-x_2-s_2=20$.
3. Rewrite the objective function (no change needed): $Z-3x_1-2x_2=0$.

Final Standard Form: Maximize $Z=3x_1+2x_2$ Subject to:

• $x_1+x_2+s_1=100$
• $2x_1-x_2-s_2=20$
• $x_1,x_2,s_1,s_2\ge 0$

3. Constructing the Initial Simplex Table

The simplex table organizes coefficients to perform iterations. Steps:

1. Write the objective function in terms of slack variables (if maximizing, subtract from $Z$).
2. List all constraints and the objective row.
3. Identify the basic variables (slack/surplus variables initially) and non-basic variables (set to 0).

Example: Initial Simplex Table

Using the previous problem: Maximize $Z=3x_1+2x_2$ Subject to:

• $x_1+x_2+s_1=100$
• $2x_1-x_2-s_2=20$

Initial Table:

Key Observations:

• The bottom row (Z-row) shows coefficients of non-basic variables.
• Negative coefficients in the Z-row indicate potential improvements (here, $-3$ and $-2$).
• Basic variables are $s_1$ and $s_2$ (corresponding to slack/surplus).

4. Iterative Process: Pivoting to Optimality

The Simplex Method improves the solution in iterations until no negative coefficients remain in the Z-row.

Step 1: Select the Entering Variable

• Choose the most negative coefficient in the Z-row (here, $-3$ for $x_1$).

Step 2: Select the Leaving Variable (Minimum Ratio Test)

• Divide the RHS by the positive coefficients in the entering variable’s column.
• Ratios: $100/1=100$, $20/2=10$.
• The minimum ratio is $10$ (for $s_2$), so $s_2$ leaves the basis.

Step 3: Pivot and Update the Table

• Pivot element: The intersection of the entering ($x_1$) and leaving ($s_2$) rows/columns (here, $2$).
• Row operations:
  1. Divide the pivot row by the pivot element: New $s_2$ row: $[1,-0.5,0,-0.5|10]$.
  2. Eliminate other entries in the $x_1$ column:
     • Subtract $1\times$ (new $s_2$ row) from the $s_1$ row.
     • Add $3\times$ (new $s_2$ row) to the Z-row.

Updated Table:

Step 4: Check for Optimality

• The Z-row has no negative coefficients ($1,1.5$ are positive).
• Optimal solution reached:
  • $x_1=10$, $x_2=0$, $Z=30$.

5. Handling Special Cases

Case 1: Unbounded Problem

• If all ratios in Step 2 are negative or no positive coefficients exist in the entering column, the problem is unbounded (objective can increase infinitely).
• Example: If the entering column has no positive entries, the solution grows without limit.

Case 2: Infeasible Problem

• If a negative RHS appears in the final table or no feasible solution exists, the problem is infeasible.
• Example: Constraints may conflict (e.g., $x_1\ge 10$ and $x_1\le 5$).

Case 3: Degeneracy

• If a ratio in Step 2 is zero, the problem is degenerate (multiple optimal solutions may exist).
• Example: A constraint like $x_1=0$ may lead to ties in the minimum ratio test.

flowchart TD
    A["Start"] --> B{"All Z-row coefficients ≥ 0?"}
    B -->|"Yes"| C["Optimal Solution Found"]
    B -->|"No"| D["Select entering variable (most negative Z-row)"]
    D --> E["Select leaving variable (minimum ratio test)"]
    E --> F["Pivot and update table"]
    F --> B
    C --> G["End"]
    E --> H{"All ratios negative or no positive entries?"}
    H -->|"Yes"| I["Unbounded Problem"]
    H -->|"No"| F

6. Dual Simplex Method (Brief Overview)

The Dual Simplex Method is used when:

• The initial solution is infeasible (some RHS values are negative).
• The Z-row is optimal, but the constraints are not satisfied.

Steps:

1. Start with an infeasible basic solution.
2. Select the most negative RHS (leaving variable).
3. Select the entering variable (most negative in the leaving row).
4. Pivot and repeat until feasibility is restored or optimality is confirmed.

In the Real World

The Simplex Method is widely used in Nepalese and global businesses to optimize resources, reduce costs, and maximize profits. Here’s how:

1. Daraz (E-commerce Logistics)

   • Problem: Optimizing delivery routes to minimize fuel costs while meeting delivery deadlines.
   • Simplex Use: Daraz uses LP to determine the optimal number of delivery vehicles and routes for each warehouse, reducing operational costs by 15-20%.
   • Example: Suppose Daraz has two warehouses (A and B) with limited trucks. The Simplex Method helps decide how many trucks to allocate from each warehouse to minimize total delivery time while satisfying demand constraints.

2. Ncell (Telecom Network Planning)

   • Problem: Allocating spectrum bandwidth to different services (calls, data, SMS) to maximize customer satisfaction without exceeding network capacity.
   • Simplex Use: Ncell uses LP to optimize bandwidth allocation across towers, ensuring no service is overloaded while minimizing costs.
   • Example: If Ncell has constraints like:
     • Total bandwidth ≤ 1000 MHz,
     • Calls require 5 MHz per user, data requires 10 MHz,
     • Maximize profit from calls and data. The Simplex Method finds the optimal mix of call and data users to maximize revenue.

3. Nepal Rastra Bank (Financial Portfolio Optimization)

   • Problem: Investing in different assets (bonds, stocks, gold) to maximize returns while adhering to risk limits.
   • Simplex Use: Banks use LP to diversify portfolios efficiently. For example, if NRB has:
     • Budget constraint: ≤ Rs. 500 million,
     • Risk limits: ≤ 30% in stocks,
     • Return rates: Bonds (5%), Stocks (12%), Gold (8%). The Simplex Method determines the optimal allocation to maximize returns.

Worked Example: Daraz Delivery Optimization

Problem: Daraz has two warehouses:

• Warehouse A: Can send up to 100 orders/day, costs Rs. 500/order.
• Warehouse B: Can send up to 150 orders/day, costs Rs. 400/order.
• Demand: Kathmandu needs 120 orders, Pokhara needs 80 orders.
• Constraints:
  • Warehouse A can send ≤ 60 orders to Pokhara (limited road capacity).
  • Warehouse B can send ≤ 50 orders to Kathmandu (traffic delays).
• Goal: Minimize total delivery cost.

Formulation: Let:

• $x_1$ = orders from A to Kathmandu,
• $x_2$ = orders from A to Pokhara,
• $x_3$ = orders from B to Kathmandu,
• $x_4$ = orders from B to Pokhara.

Objective: Minimize $Z=500x_1+500x_2+400x_3+400x_4$.

Constraints:

1. $x_1+x_2\le 100$ (Warehouse A capacity),
2. $x_3+x_4\le 150$ (Warehouse B capacity),
3. $x_1+x_3\ge 120$ (Kathmandu demand),
4. $x_2+x_4\ge 80$ (Pokhara demand),
5. $x_2\le 60$ (A to Pokhara limit),
6. $x_3\le 50$ (B to Kathmandu limit),
7. $x_1,x_2,x_3,x_4\ge 0$.

Solution: Convert to standard form (add slack/surplus variables):

• $x_1+x_2+s_1=100$,
• $x_3+x_4+s_2=150$,
• $-x_1-x_3+s_3=-120$,
• $-x_2-x_4+s_4=-80$,
• $x_2+s_5=60$,
• $x_3+s_6=50$.

Initial Simplex Table:

Iterations:

1. First Pivot: Entering variable $x_3$ (most negative in Z-row), leaving $s_6$ (minimum ratio: 50/1 = 50).
2. Second Pivot: Entering $x_1$, leaving $s_3$.
3. Third Pivot: Entering $x_2$, leaving $s_5$.

Final Table:

Optimal Solution:

• $x_1=50$ (A to Kathmandu),
• $x_2=60$ (A to Pokhara),
• $x_3=50$ (B to Kathmandu),
• $x_4=50$ (B to Pokhara).
• Total Cost: Rs. 72,000.

Exam Tip

What Examiners Look For

1. Correct Standard Form Conversion:

   • Ensure all constraints are equalities with slack/surplus variables.
   • Common Mistake: Forgetting to include slack/surplus variables or misplacing signs.

2. Simplex Table Construction:

   • Label basis variables clearly.
   • Common Mistake: Incorrectly identifying entering/leaving variables.

3. Pivoting Steps:

   • Show all row operations (including intermediate steps).
   • Common Mistake: Skipping the minimum ratio test or miscalculating pivot rows.

4. Interpretation of Results:

   • State whether the solution is optimal, unbounded, or infeasible.
   • Common Mistake: Stopping early without checking the Z-row.

5. Real-World Application:

   • Examiners may ask to formulate a business problem (e.g., production, logistics) using Simplex.
   • Tip: Always define variables clearly and justify constraints.

High-Scoring Strategies

• Draw the Simplex table neatly (use borders for clarity).
• Show all iterations (even if some are trivial).
• Explain degeneracy/unboundedness if encountered.
• Relate to business scenarios (e.g., "This solution minimizes Daraz’s delivery cost by...").

Common Pitfalls to Avoid

• Ignoring non-negativity constraints: Always ensure $x_i\ge 0$.
• Arithmetic errors: Double-check row operations.
• Premature termination: Always verify optimality (no negative Z-row).

Feasible region for a 2-variable LP problem (Image: en:User:Jacj, Public domain, via Wikimedia Commons)