289. Simplex Cheatsheet

1. Convert to standard form

Objective Function

Constraints

Negative/Free Variables

2. Partition

Constraints:

3. Basic Feasible Solution

4. Reduced Costs

• If ${\overline{𝑐}}_{𝑗}>0$: ${𝑥}_{𝑗}$ can enter the basis
• If ${\overline{𝑐}}_{𝑗}\le 0$: optimal

5. Choose Entering Variable

Select ${𝑥}_{𝑗}\in 𝑁$ with the largest ${\overline{𝑐}}_{𝑗}$.

If there’s a tie, pick the smallest index (Bland’s rule).

6. Pivot / Ratio Test

Let $𝑑={𝐵}^{-1}{𝐴}_{𝑗}$ be the column of the entering variable expressed in basic coordinates Only ${𝑑}_{𝑖}>0$ maintain feasibility

${𝜃}_{𝑖}=\frac{{\left({𝐵}^{-1}𝑏\right)}_{𝑖}}{{𝑑}_{𝑖}},{𝑑}_{𝑖}>0$

• The smallest ${𝜃}_{𝑖}$ identifies the leaving variable ${𝑥}_{{𝐵}_{𝑖}}$.
• If all ${𝑑}_{𝑖}\le 0$: the LP is unbounded