Simplex Algorithm (NSA) (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
on the Reduced Cost and Node Potential).
·NSA has 4 main steps:
¨Step 0: Initialization (Generate a Basic Feasible spanning
¨While (The Current Solution is not
§Step 1: Select an Entering arc to add the spanning tree (a Non-Basic
§Step 2:Select aLeaving
arc (one Basic arc has to be removed ).
the two arcs (Pivoting)
·Searching Methods/Rules for violated arcs determine speed of the algorithm.