Simplex Method ContinuedToday’s LectureLP Canonical Form = LP Standard Form + Jordan Canonical FormTowards: writing an LP in general form. This notation is useful for the text AMP.Towards: writing an LP in general formSlide 6Basic VariablesReview of the NotationThe basic feasible solutionOptimality Conditions (maximization)Slide 11Pivoting and the min ratio ruleSlide 13Minimum Ratio RulePivoting to obtain a better solutionAlternative Optima (maximization)Slide 17Slide 18UnboundednessReview of notationSimplex Method (Max Form)Preview of what is to comeDegeneracySlide 24Slide 25A degenerate pivotNon-degeneracy leads to strict improvementTheorem. If every basic feasible solution is non-degenerate, the simplex method is finite.Handling DegeneracyAn LP before perturbationAn example of a perturbed initial bfsSome Remarks on Degeneracy and Alternative OptimaSimplex Algorithm: getting startedA naïve suggestion: just choose the variables and then pivot to get into canonical form.A suggestion that sounds dumb, but almost works: let’s create an artificial basis.Trying to make artificial bases workSo, how can we modify x5 and x6 so that they won’t be in an optimal solution?Getting into canonical form3 pivots laterThe Big M methodAn alternative approach: The Phase 1 methodObservation 1: if all we want is a basic feasible solution, then we can select any objective function.Next: add in the artificial variables, creating a basic feasible solution to the new problemThe phase 1 problem: almost in canonical formThe phase 1 problem: now in canonical formTwo pivots later, we have an optimal solution to the phase 1 problem.Recovering a bfs for the original problemSlide 48Slide 49Phase 2. And one pivot laterSummaryThe following are extra slidesCreating a Phase 1 ProblemSlide 54Slide 55Slide 56Slide 57Creating a bfs from the phase 1 solutionSlide 59Slide 60Slide 61Potential DifficultiesSlide 63Phase 1: obtaining an initial bfsSlide 65How does one obtain an initial bfs?Reducing to a Previously Solved ProblemMaria’s ProblemSlide 69Juan’s ProblemMaria’s Problem in Tableau FormMaria’s Problem in Canonical FormThe optimal basis for Maria’s ProblemMIT and James Orlin © 20031Simplex Method ContinuedMIT and James Orlin © 20032Today’s LectureReview of the simplex algorithm.Formalizing the approachDegeneracy and Alternative Optimal SolutionsIs the simplex algorithm finite? (Answer, yes, but only if we are careful)MIT and James Orlin © 20033-3 2 001-3 3 1 0-4 2 0 100-3 3 1 0-4 2 0 100-3 2 001LP Canonical Form = LP Standard Form + Jordan Canonical Form==26x1x2x4x3-z=0The basic feasible solution is x1 = 0, x2 = 0, x3 = 6, x4 = 2The basic variables are x3 and x4.The non-basic variables are x1 and x2.z is not a decision variable1 00 100x4x3MIT and James Orlin © 20034-3 2 001-3 3 1 0-4 2 0 100-3 3 1 0-4 2 0 100-3 2 001Towards: writing an LP in general form. This notation is useful for the text AMP.==26x1xsx4x3-z=0Use aij to denote the constraint matrix coefficients.Use cj to denote the cost coefficientsUse bi to denote the RHS coefficients1 00 100x4x3c1c2b1b2a11a12a21a22The bar indicates that it is the coefficient after some pivots-z0c3c4a13a14a23a24MIT and James Orlin © 20035-3 2 001-3 3 1 0-4 2 0 100-3 3 1 0-4 2 0 100-3 2 001Towards: writing an LP in general form==26x1x2x4x3-z=0Let r denote the index of the row with the leaving variable. Let s denote the index of the entering variable.1 00 100x4x3c1c2b1b2a11a12a21a22csa1sa2sbrarsar1We pivot on coefficientars-z0Usually, we write the basic variables as unit vectorsMIT and James Orlin © 20036-3 2 001-3 3 1 0-4 2 0 100-3 3 1 0-4 2 0 100-3 2 001Towards: writing an LP in general form==26x1x2x4x3-z=0(2) the number of variables (columns) is n. (1) the number of equality constraints (rows) is m1 00 100x4x3c1c2b1b2a11a12a21a22csa1sa2sbrarsar1To do next: rewrite the LP so that:-z0MIT and James Orlin © 20037Basic Variablesx1x2xm+1xm1 010-z00xrxn0a1,m+1a2,m+1000a1,na2,nb1b2==xsa1,sa2,s000ar,m+101ar,nbr=ar,s000am,m+110am,nbm=am,s0001cm+100cn-z0=cs0CVm constraints, n variablesNon-basic VariablesMIT and James Orlin © 20038Review of the Notationn number of variablesm number of constraintss index of entering variabler index of pivot row–note: the rth basic variable leaves the basisThe original data is cj, aij, bi After performing pivots we represent the revised coefficients as cj, aij, biMIT and James Orlin © 20039The basic feasible solutionThe current values are all non-negative.–This is needed for canonical formThere is a basic variable associated with each constraint.–in this case, the basic variable associated with constraint i is xi. There are n-m nonbasic variables.–In this case, the nonbasic variables are xm+1, … xn.This bfs is as follows: x1 =b1, … , xm =bm. All other variables are 0.MIT and James Orlin © 200310-3 3 1 0-4 2 0 1Optimality Conditions (maximization) ==26x2x4x3-2 -4 00-z001=-8This basic feasible solution is optimal!What are the optimality conditions, expressed in terms of c ?x1MIT and James Orlin © 200311-3 3 1 0-4 2 0 1Optimality Conditions (maximization) ==26x2x4x3-2 -4 00-z001=-8This basic feasible solution is optimal!What are the optimality conditions, expressed in terms of c ?x1c1c2-z0MIT and James Orlin © 200312x1-3 3 1 0-4 2 0 1Pivoting and the min ratio rule==26x2x4x3-3 2 00-z001=01x1 = 0 x2 = x3 = 6 - 3 x4 = 2 - 2 z = 2x3 = 0 when = 6/3 x4 = 0 when = 2/2.63x3x4BV-z2 2 is set to the min(6/3, 2/2) = min (b1 /a1s , b2 /a2s). Pivot in variable xs, where cs > 0.32232MIT and James Orlin © 200313x1-3 3 1 0-4 2 0 1Pivoting and the min ratio rule==26x2x4x3-3 2 00-z001=01x1 = 0 x2 = x3 = 6 - 3 x4 = 2 - 2 z = 2x3 = 0 when = 6/3 x4 = 0 when = 2/2.63x3x4BV-z2 2 is set to the min(6/3, 2/2) = min (b1 /a1s , b2 /a2s). Express the min ratio rule using general coefficientsPivot in variable xs, where cs > 0.32232b1b2a1sa2sThe constraint with a changed basic variable is constraint r, where r = argmin (b1 /a1s , b2 /a2s) = 2. Min ratio rule.MIT and James Orlin © 200314Minimum Ratio RulePivot out the basic variable in row r,
View Full Document