advertisement

ISM 206 Lecture 3 The Simplex Method Announcements Outline • LP so far • Why we can look only at basic feasible solutions • Optimality conditions • The simplex method • The step from one bfs to the next • Tableu method • Phase I: Finding an initial BFS LP so far • Formulated LP’s in various contexts • Transform any LP into a standard form LP • Intuition of simplex method: Find the best corner point feasible solution • Math required: – Corner point Feasible or basic feasible solutions correspond to a set of n active constraints – Any set of active constraints corresponds to a basis from the matrix A – The basis is a set of linearly independent columns Standard Form max c1 x1 c2 x2 ... cN xN subject to a11x1 a12 x2 ... a1N xN b1 a21 x1 a22 x2 ... a2 N x N b2 ... aM 1 x1 aM 2 x2 ... aMN x N bM x j 0, j 1..N max cx Concise version: subject to Ax b x0 A is an m by n matrix: n variables, m constraints Standard Form to Augmented Form max c1 x1 c2 x2 ... cN xN max c1 x1 c2 x2 ... c N x N subject to subject to a11x1 a12 x2 ... a1N xN b1 a21 x1 a22 x2 ... a2 N x N b2 ... aM 1 x1 aM 2 x2 ... aMN x N bM x j 0, j 1..N max cx subject to Ax b x0 A is an m by n matrix: n variables, m constraints a11x1 a12 x2 ... a1N xN x1 b1 a21x1 a22 x2 ... a2 N x N x2 b2 ... aM 1 x1 aM 2 x2 ... aMN x N xN bM x j , xi 0, j 1..N , i 1..m max cx x subject to [ A, I ] b x x0 Solutions, Extreme points and bases • Key fact: – If a LP has an optimal solution, then it has an optimal extreme point solution (proved today) • Basic Feasible solution (Corner Point Feasible): – The vector x is an extreme point of the solution space iff it is a bfs of Ax=b, x>=0 • If A is of full rank then there is at least one basis B of A – B is set of linearly independent columns of A • B gives us a basic solution – If this is feasible then it is called a basic feasible solution (bfs) or corner point feasible (cpf) Optimal basis theorem Theorem If a LP in standard form has a finite optimal solution then it has an optimal basic feasible solution Proof Requires the representation theorem… Simplex Method • Checks the corner points • Gets better solution at each iteration 1. Find a starting solution 2. Test for optimality – If optimal then stop 3. Perform one iteration to new CPF (BFS) solution. Back to 2. Simplex Method: basis change • One basic variable is replaced by another • The optimality test identifies a non-basic variable to enter the basis – The entering variable is increased until one of the other basic variables becomes zero – This is found using the minimum ratio test – That variable departs the basis Idea of simplex iterations • New matrix A is an m by n matrix – m constraints – n variables • Z = objective value (another variable) • m+1 constraints, n variables – We can rearrange m+1 equations, trying to • Maximize Z • Keeping x >=0 • Consider basic solutions – m x-variables are nonzero – All others are zero The simplex method • Example • Table version Questions and Break A basic feasible solution • B=basis of A. • Write LP in terms of basis A [B N ] Ax Bx B NxN b xB m , x N n m xN 0, xB B 1b X is a basic solution of the LP X is a basic feasible solution if it is feasible! (example) max c' x s.t. Ax b x0 Optimality of a basis We want to test of a basic feasible solution is optimal Use the basic notation from before Bx B NxN b xB B 1 (b NxN ) c' x cB ' xB c N ' x N cB ' B 1 (b NxN ) c N ' x N cB ' B 1b cB ' B 1 NxN c N ' x N z0 ( z j c j )x j j z0 cB ' B 1b z j cB ' B 1 A. j j N max cB ' xB cN ' xN s.t. Bx B NxN b xB , x N 0 Optimality test max c' x z0 ( z j c j )x j j Test : z j c j 0 j N Finding an initial bfs • The ‘phase 1’ approach • The ‘big M’ method