Chapter 3. The simplex algorithmOverview of LectureSlide 3Linear Programs in Standard FormConverting Inequalities into Equalities Plus Non-negativesConverting “” constraintsMore TransformationsThe Last Transformations (for now)PowerPoint PresentationAnother ExamplePreview of the Simplex AlgorithmSlide 12LP Canonical Form = LP Standard Form + Jordan Canonical FormLP Canonical FormFor each constraint there is a basic variableSlide 16Optimality Conditions PreviewThe current basic feasible solution (bfs) is not optimal!Optimality ConditionsLet x2 = D. How large can D be? What is the solution after changing x2?Slide 21Pivoting to obtain a better solutionSummary of Simplex AlgorithmOK. Let’s iterate again.Slide 25A Digression: What if we had a problem in which D could increase to infinity?End Digression: Perform another pivotCheck for optimalitySummary of Simplex Algorithm AgainPerforming a “Pivot”. Towards a shortcut.More on performing a pivotNext LectureMIT and James Orlin © 20031Chapter 3. The simplex algorithmPutting Linear Programs into standard formIntroduction to Simplex AlgorithmMIT and James Orlin © 20032Overview of LectureGetting an LP into standard formGetting an LP into canonical formOptimality conditionsImproving a solutionA simplex pivotRecognizing when an LP is unboundedOverview of what remainsMIT and James Orlin © 20033Overview of LectureGetting an LP into standard formMIT and James Orlin © 20034Linear Programs in Standard FormWe say that a linear program is in standard form if the following are all true:1. Non-negativity constraints for all variables.2. All remaining constraints are expressed as equality constraints.3. The right hand side vector, b, is non-negative.maximize 3x1 + 2x2 - x3 + x4 x1 + 2x2 + x3 - x4  5;-2x1 - 4x2 + x3 + x4  -1; x1  0, x2  0 An LP not in Standard Formnot equalitynot equalityx3 may be negativeMIT and James Orlin © 20035s1 is called a slack variable, which measures the amount of “unused resource.” Note that s1 = 5 - x1 - 2x2 - x3 + x4.Converting Inequalities into Equalities Plus Non-negativesTo convert a “” constraint to an equality, add a slack variable. x1 + 2x2 + x3 - x4 +s1 = 5s1  0 AfterBeforex1 + 2x2 + x3 - x4  5MIT and James Orlin © 20036Converting “” constraintsConsider the inequality -2x1 - 4x2 + x3 + x4  -1;Step 1. Eliminate the negative RHS 2x1 + 4x2 - x3 - x4  1Step 2. Convert to an equality 2x1 + 4x2 - x3 - x4 – s2 = 1 s2  0The variable added will be called a “surplus variable.”To covert a “” constraint to an equality, subtract a surplus variable.MIT and James Orlin © 20037More TransformationsHow can one convert a maximization problem to a minimization problem?Example: Maximize 3W + 2PSubject to “constraints”Has the same optimum solution(s) as Minimize -3W -2P Subject to “constraints”MIT and James Orlin © 20038The Last Transformations (for now)Transforming x1: replace x1 by y1 = -x1; y1  0.One can recover x1 from y1. max -3 y1 + 4x2 +5 x3 -2 y1 -5 x2 +2 x3 =7 y1  0, x2 is unconstrained in sign, x3  0Transforming variables that may take on negative values.maximize 3x1 + 4x2 + 5 x3subject to 2x1 - 5x2 + 2x3 = 7 other constraints x1 0, x2 is unconstrained in sign, x3  0MIT and James Orlin © 20039 max -3 y1 + 4(y3 - y2) +5 x3 -2 y1 -5 y3 +5 y2 +2 x3 =7 all vars  0 max -3 y1 + 4x2 +5 x3 -2 y1 -5 x2 +2 x3 =7 y1  0, x2 is unconstrained in sign, x3  0Transforming variables that may take on negative values.Transforming x2: replace x2 by x2 = y3 - y2; y2  0, y3  0.One can recover x2 from y2, y3.e.g., y1 = 1, x2 = -1, x3 = 2 is feasible.e.g., y1 = 1, y2 = 0, y3 = 1 x3 = 2 is feasible.MIT and James Orlin © 200310Another ExampleExercise: transform the following to standard form (maximization):Minimize x1 + 3x2Subject to 2x1 + 5x2   12x1 + x2  1 x1  0 Perform the transformation with your partnerMIT and James Orlin © 200311Preview of the Simplex Algorithmx1x2x4x3-z=-3 3 1 600-3 2 001=0maximize z = -3x1 + 2x2 subject to -3x1 + 3x2 +x3 = 6 -4x1 + 2x2 + x4 = 2 x1, x2, x3, x4  02-4 2 0 10=MIT and James Orlin © 200312Overview of LectureGetting an LP into standard formGetting an LP into canonical formMIT and James Orlin © 200313-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 simplex method starts with an LP in LP canonical form (or it creates canonical form at a preprocess step.)z is not a decision variable1 00 100x4x3MIT and James Orlin © 200314-3 2 001-3 3 1 0-4 2 0 100-3 3 1 0-4 2 0 100-3 2 001LP Canonical Form ==26x1x2x4x3-z=0The basic feasible solution is x1 = 0, x2 = 0, x3 = 6, x4 = 2(set the non-basic variables to 0, and then solve)The 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 © 200315-3 3 1 0-4 2 0 1For each constraint there is a basic variable==26x2x4x3-3 2 00-z001=0Constraint 1: basic variable is x3 Constraint 1Constraint 2: basic variable is x4 Constraint 2The basis consists of variables x3 and x4x1-3 3 1 0 60-4 2 0 1 20MIT and James Orlin © 200316Overview of LectureGetting an LP into standard formGetting an LP into canonical formOptimality conditionsMIT and James Orlin © 200317x1-3 3 1 0-4 2 0 1Optimality Conditions Preview==26x2x4x3-3 2 00-z001=0Obvious Fact: If one can improve the current basic feasible solution x, then x is not optimal.Idea: assign a small value to just one of the non-basic variables, and then adjust the basic variables.Note: z = -3x1 + 2x2MIT and James Orlin © 200318x1-3 3 1 0-4 2 0 1The current basic feasible solution (bfs) is not optimal!==26x2x4x3-3 2 00-z001=0Increase x2 to > 0. Let x1 stay at 0.x3 = 6 - 3. x4 = 2 - 2. z = 2.x1-3-4-3If there is a positive coefficient in the z row, the basis is not optimal**Recall: z = -3x1 + 2x2What happens to x3, x4 and z? .MIT and James Orlin © 200319-3 3 1 0-4 2 0 1Optimality Conditions ==26x2x4x3-2 -4 00-z001=-8z = -2x1 - 4x2 + 8. Therefore z  8