9.3. Simplex Algorithm

Max-Flow Min-Cut Theorem

Let $S$ - $T$ cut be a set of edges whose removal disconnects any path between $S$ and $T$:

What is the relationship between max-flow and min-cut?

Simplex: Prime

Maximize p = 0x1 + x2 + 0x3 + x4 subject to
x1 <= 4
x2 <= 2
x3 <= 3
x4 <= 2
x2 - x1 <= 0
x4 - x3 <= 0

Maximize p = 0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + x7 + x8  subject to
x1 <= 4
x2 <= 2
x3 <= 3
x4 <= 2
x5 <= 3
x6 <= 1
x7 <= 2
x8 <= 4
x3 - x1 <= 0
x4 + x5 - x2 - x6 <= 0
x6 + x7 - x3 - x4 <= 0
x8 - x5 <= 0

Simplex: Dual

Minimize p = 4x1 + 2x2 + 3x3 + 2x4 + 0y1 + 0y3  subject to
x1 + y1 >= 1
x3 + y3 >= 1
x2 - y1 >= 0
x4 - y3 >= 0

Minimize p = 4x1 + 2x2 + 3x3 + 2x4 +
3x5 + x6 + 2x7 + 4x8 + 0y1 + 0y2 + 0y3 + 0y4  subject to
x1 + y1 >= 1
x2 + y2 >= 1
x3 - y1 + y3 >= 0
x4 - y2 + y3 >= 0
x5 - y2 + y4 >= 0
x6 - y3 + y2 >= 0
x7 - y3 >= 0
x8 - y4 >= 0