Recall SEF

The solution of any LP must either be infeasible, unbounded, or optimal (Fundamental theorem of linear programming)

Normal simplex algorithm

Let’s say we’re given a typical optimization problem $(P)$ $\max\{c^Tx:Ax=b,x≥0\}$

Recall canonical form on the right:

  1. $c_B=0$
  2. $A_B = I$

Note that you can delay computing the constraints until after step 5.

Canonical Form. $y$ should be multiplied additionally by $c_B$; the SS is wrong.

Canonical Form. $y$ should be multiplied additionally by $c_B$; the SS is wrong.

Repeat the following process:

  1. Choose a basis $B$. Recall that $N$ is everything not in $B$.
  2. Convert $(P)$ to canonical form for $B$ with BFS $\overline{x}$.
  3. If $c_N≤0$, stop. $\overline{x}$ is optimal.
  4. Select $k∈N$ with $c_k>0$.
  5. If $A_k≤0$, stop. $(P)$ is unbounded.
  6. Pick an index $i$ where $t=\left\{\frac{b_i}{A_{ik}} : A_{ik} > 0\right\}$ is minimized.
  7. Add $k$ (from step 4) and remove $B_i$ from $B$.

Bland’s rule mod

  4. Choose first $k$ with $c_k>0$.
  6. Pick the first $r ∈ B$ with $A_{rk}>0$ and $\frac{b_r}{A_{rk}}=t$.

Two phase simplex algorithm

Let’s say we’re given a typical optimization problem

$c^Tx:Ax=b,x≥0$ where $A$ has $m$ rows and $n$ columns

$2×3$ matrix in the example

<aside> 💡 If the right side $b$ has any negatives, just multiply both sides of the row by $-1$

</aside>

Phase 1: find a feasible solution for original by finding the optimal solution for the auxiliary problem

Example

Example

Then our auxiliary problem is given by adding the identity matrix to the right of $A$

Note that the obj. function also changes to minimizing the sum of the new variables

To convert to canonical, just add all constraints to the obj. function

Auxiliary Problem

Auxiliary Problem

The obj. value in the example is $x_4 + x_5$

  1. If this is 0, then $(x_1, \ldots, x_n)^T$ is a solution
  2. Otherwise, the original problem is infeasible

The obj. value is bounded above by $0$ for every iteration of phase 1