Simplex Method

Iterates Basic Feasible Point (BFP) until one that fulfills KKT (Karush–Kuhn–Tucker) Conditions is found.

Can be divided into two phases (since finding an initial BFP can be quite hard).

1. Find Basic Feasible Point (BFP)
2. Solve LP

A method for solving Lecture 4&5 - Linear Programming (LP) problems.

---

One step of Simplex-Algorithm Example of Simplex Method

Theorem 13.4

• If an LP is bounded and non degenerate, the simplex method terminates at a Basic Optimal Point (BOP)

Notation

• $x:$ Basic Feasible Point (BFP)
• $B=[A_i{]}_{i\in \mathcal{B}(x)}$
• $N=[A_i{]}_{i\in \mathcal{N}(x)}$
• $x_b$
• $x_n$
• …