4/4/2006

Slide: 12

Copyrights (H.Rashidi)

Network
Simplex Algorithm (NSA)

(A complete algorithm)

(A complete algorithm)

· NSA is **the fastest** algorithm to solve the MCF problem

· NSA maintains the solution feasibility and
moves towards optimality.

· Each connected graph has a **spanning tree**. At each stage, the arcs in the graph divided into two sets; **(1)**** Basic** Arcs: This set makes the **spanning tree;** (2) **Non-Basic** Arcs: This set may **violate
the ***optimality
condition **(based
on the **Reduced Cost and Node Potential)*.

·NSA has 4 main steps:

§**Step 1**: **Select an Entering arc** to add the spanning tree (a Non-Basic
arc).

§**Step 2****:** **Select a Leaving
arc** (one *Basic* arc has to be removed ).

§**Step 3**: **Exchanging**
the two arcs (Pivoting)

· **Searching Methods/Rules** for violated arcs **determine speed** of the algorithm.