15.082J and 6.855J and ESD.78J November 4, 2010 The Network Simplex AlgorithmOverview first 1/3 of the lecture Quick Review of Linear Programming: • some geometry • extreme points (corner points) • an overview of the simplex algorithm Networks • extreme points • basic feasible solutions The Network Simplex Algorithm 2A Two Variable Linear Program z = 3x + 5yobjective 2x + 3y ≤ 10 x + 2y ≤ 6 x ≤ 4 y ≤ 3 x, y ≥ 0 (1) (2) (3) (4) (5) Constraints 3Graphing the Feasible Region Graph the Constraints: y 5 4 3 2 1 2x+ 3y ≤ 10 (1) x ≥ 0 , y ≥ 0. (5) 2x + 3y = 10 x 1 2 3 4 5 6 4Add the Constraint: y 1 2 3 4 5 x + 2y ≤ 6 (2) x + 2y = 6 x 1 2 3 4 5 6 5Add the Constraints: yx ≤ 4; y ≤ 3 5 4 3 2 1 1 2 3 4 5 6 We have now graphed the feasible region. x 6The geometrical method for optimizing 3x + 5y y 3 2 1 x Graph points such that 3x + 5y = p for various values of p. 3x + 5y = 11 Choose p maximal 3x + 5y = 8 Isocost lines 1 2 3 4 7y 1 2 3 Find the maximum value p such that there is a feasible solution with 3x + 5y = p. Move the line with profit p parallel as much as possible. 3x + 5y = 8 3x + 5y = 11 3x + 5y = 16 The optimal solution occurs at an extreme point. x 1 2 3 4 8Extreme Points (Corner Points) An extreme point (also called n corner point) of the feasible region is a point that is not the midpoint of two other points of the feasible region. Where are the extreme points of this feasible region? 9The Simplex Method 1 2 3 4 5 y Start at any feasible extreme point. Move along an edge (or extreme ray) in which the objective value is continually improving. Stop at the next extreme point. (If moving along an extreme ray, the objective value is unbounded.) Continue until no adjacent extreme point has a better objective value. Max z = 3 x + 5 y 3 x + 5 y = 19 x 10 1 2 3 4 5 6 10Comments about the simplex algorithm Each step is called a pivot. • Pivots are carried out using linear algebra • Pivots for network flow problems can be carried out directly by changing flows in arcs. Typically, the simplex method finds the optimal solution after a “small” number of pivots (but can be exponential in the worst case). The simplex algorithm is VERY efficient in practice. 11Back to networks We will work with the arcs of the original network (not the residual network) We will soon describe extreme flows. Connection between spanning tree flows and extreme flows. 121 Networks: sending flow around a cycle -1 2 3 +1 C 4-1 +1 Arcs (1,2) and (4, 1) are forward arcs. Arcs (3, 2) and (4, 3) are backward arcs. Assume that cycles are oriented in a direction. The forward arcs of the cycle are the arcs in the same orientation. The backward arcs are in the opposite direction. A flow of 1 unit around C refers to a flow of 1 unit in the forward arcs and a flow of -1 units in the arcs in the backward arcs. 13What is an extreme point solution of a network flow problem? Let x be a feasible flow for a minimum cost flow problem. An arc (i, j) is called free if 0 < xij < uij. One can increase or decrease the flow in a free arc by a small amount and still satisfy bound constraints. Theorem. A feasible flow x is an extreme point solution if and only if there is no (undirected) cycle of free arcs. Proof. Suppose that C is a free cycle. We will show that x is not extreme. Let yC be a flow of 1 unit around C. 1 2 3 5 C Since all arcs of C are free wrt x, there is some ε > 0 so that x’ = x + ε yC is a feasible flow and so that x” = x – ε yC is feasible. x is the midpoint of x’ and x”. 14Proof continued Suppose that x is not an extreme point. Suppose that x = (x’ + x”)/2 and for feasible flows x’ and x”. We will show that there is a free cycle. Consider arc (i, j). = (x’ij + x”ij)/2.xij if xij = 0 then x’ij = x”ij = 0 (Otherwise x’ij < 0 or x”ij < 0). If xij = uij then x’ij = x”ij = uij (Otherwise x’ij > uij or x”ij > uij). So, x differs from x’ and x” on free arcs. 1 2 3 5 C x’ – x is a circulation, and so it is expressible as the sum of flows around cycles. It follows that there is a cycle of free arcs. 15Basic feasible solutions A basis structure consists of a spanning tree T, a set L of arcs, and a set U of arcs, such that T∪ L ∪ U = A. For each (i,j) ∈ L, xij = 0. For each (i,j)∈ U, xij = uij. The arc flows in T are selected so that each node satisfies its supply/demand constraint. The basis structure is feasible if the arc flows also satisfy the upper and lower bounds. (Not all basis structures are feasible.) The feasible flow is called basic. 16Calculating A Spanning Tree Flow A tree with supplies and demands. (Assume that all 3 other arcs have a flow of 0) What is the flow in arc (4,3)? 1 3 6 4 5 2 7 1 -6 -4 1 2 3 See the animation: slide 2 17What would happen if the flows in non- tree arcs were not 0? 1 3 6 4 5 2 7 1 -6 -4 1 2 3 1 3 Suppose that non-tree arcs had a non-zero flow. How 3 would this change the computations? 2 18What would happen if the flows in non- tree arcs were not 0? Adjust the supplies/demands. 3 6 They will be interpreted as excesses and deficits. 2 4 The compute flows as in the previous method; e.g., what is the flow in (4,3)? 1 3 6 4 5 2 7 1 -6 -4 1 2 3 1 3 0 2 19What would happen if the flow were negative? If the direction of (4,3) were reversed, the flow in (3,4) would be negative. A spanning tree flow is guaranteed to satisfy the supply/demand constraints. It may violate an upper or lower bound. A spanning tree flow is called feasible if it satisfies its upper and lower bound. Otherwise, it is infeasible. 1 3 6 4 5 2 7 1 3 -6 -4 1 2 3 -2 3 6 4 4 3 20Another way of calculating flows in arcs Case 1. If (i, …