Chapter 4 The Simplex Algorithm Part I Based on Introduction to Mathematical Programming Operations Research Volume 1 4th edition by Wayne L Winston and Munirpallam Venkataramanan Lewis Ntaimo L Ntaimo c 2005 INEN420 TAMU 1 Introduction Modeling LPs Solving 2 variable LPs graphically Most real life LPs have many variables So a method is needed to solve LPs with more that 2 variables So we will study the simplex algorithm which is used to solve LPs with thousands of constraints and variables Your linear algebra skills will now come into play Chapter 2 L Ntaimo c 2005 INEN420 TAMU 2 4 5 Converting an LP to Standard Form Before the simplex algorithm can be used to solve an LP the LP must be converted into a problem where all the constraints are equations and all variables are nonnegative An LP in this form is said to be in standard form Steps 1 If the ith constraint is a constraint then we convert it to an constraint by adding a slack variable si and the sign restriction si 0 2 If the ith constraint is a constraint then we convert it to an constraint by subtracting an excess variable ei and the sign restriction ei 0 3 If the variable xi is unrestricted in sign urs or free replace xi in both the objective and constraints by x i x i where x i 0 and x i 0 L Ntaimo c 2005 INEN420 TAMU 3 4 5 Converting an LP to Standard Form Consider the following example Leather Limited manufactures two types of leather belts the deluxe model and the regular model Each type requires 1 square yard of leather A regular belt requires 1 hour of skilled labor and a deluxe belt requires 2 hours of skilled labor Each week 40 square yards of leather and 60 hours of skilled labor are available Each regular belt contributes 3 profit and each deluxe belt 4 Write an LP to maximize profit L Ntaimo c 2005 INEN420 TAMU 4 4 5 Converting an LP to Standard Form The decision variables are x1 number of deluxe belts produced weekly x2 number of regular belts produced weekly the appropriate LP is max z 4x1 3x2 s t x1 x2 40 2x1 x2 60 x1 x2 0 leather constraint labor constraint To convert the leather and labor constraints to equalities we define for each constraint a slack variable si si slack variable for the i th constraint A slack variable is the amount of the resource unused in the i th constraint L Ntaimo c 2005 INEN420 TAMU 5 4 5 Converting an LP into Standard Form The LP not in standard form is max z 4x1 3x2 s t x1 x2 40 2x1 x2 60 x1 x2 0 leather constraint labor constraint The same LP in standard form is max z 4x1 3x2 s t x1 x2 s1 40 2x1 x2 s2 60 x1 x2 s1 s2 0 L Ntaimo c 2005 INEN420 TAMU 6 4 5 Converting an LP to Standard Form Convert the following LP Dorian Auto to standard form min z 50 x1 100x2 s t 7x1 2x2 28 2x1 12x2 24 x1 x2 0 L Ntaimo c 2005 INEN420 TAMU 7 4 5 Converting an LP to Standard Form Transforming the Dorian Auto LP to standard form yields min z 50 x1 100x2 s t 7x1 2x2 e1 2x1 12x2 e2 xi ei 0 i 1 2 28 24 L Ntaimo c 2005 INEN420 TAMU 8 4 5 How to Convert an LP to Standard Form Convert the following LP Financial Planning to standard form Original LP LP in Standard Form max z 20x1 15x2 max z 20x1 15x2 s t s t x1 100 x2 100 s1 x1 x2 50x1 35x2 6000 50x1 35x2 20x1 15x2 2000 20x1 15x2 x1 x2 0 100 s2 100 s3 6000 e4 2000 x1 x2 s1 s2 s3 e4 0 L Ntaimo c 2005 INEN420 TAMU 9 4 5 Converting an LP to Standard Form Consider the following problem A baker has 30 oz of flour and 5 packages of yeast Baking a loaf of bread requires 5 oz of flour and 1 package of yeast Each loaf of bread can be sold for 30 cents The baker may purchase additional flour at 4 cents oz or sell leftover flour at the same price Formulate an LP to help the baker maximize profits revenues costs L Ntaimo c 2005 INEN420 TAMU 10 4 5 Converting an LP to Standard Form The decision variables are x1 number of loaves of bread baked x2 number of oz by which flour supply is increased by cash transactions The appropriate LP is max z 30x1 4x2 s t 5x1 x2 30 flour 5 yeast x1 x1 0 x2 urs Note x2 0 x2 oz of four were purchased x2 0 x2 oz of four were sold x2 0 no flour was bought or sold L Ntaimo c 2005 INEN420 TAMU 11 4 5 Converting an LP to Standard Form Original LP LP in Standard Form max z 30x1 4x2 s t 5x1 x2 30 5 x1 x1 0 x2 urs max z 30x1 4x 2 4x 2 s t 5x1 x 2 x 2 s1 30 x1 s2 5 x1 x 2 x 2 s1 s2 0 L Ntaimo c 2005 INEN420 TAMU 12 4 5 Preview of the Simplex Algorithm General form for an LP Suppose an LP with m constraints and n variables has been converted into standard form The from of such an LP is max or min z c1x1 c2x2 cnxn s t a11x1 a12x2 a1nxn b1 a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm xi 0 i 1 2 n L Ntaimo c 2005 INEN420 TAMU 13 4 5 Preview of the Simplex Algorithm If we define a11 a 21 A am1 a12 a22 am 2 a1n a2 n amn x1 x 2 x xn b1 b 2 b bm The constraints may be written as a system of equations Ax b Consider a system Ax b of m linear equations in n variables where n m A basic solution to Ax b is obtained by setting n m variables equal to 0 and solving for the remaining m variables This assumes that setting the n m variables equal to 0 yields a unique value for the remaining m variables or equivalently the columns for the remaining m variables are linearly independent L Ntaimo c 2005 INEN420 TAMU 14 4 5 Preview of the Simplex Algorithm To find a basic solution to Ax b we choose a set of n m variables the nonbasic variables or NBV and set each of these variables equal to 0 Then we solve for the values of the n n m m variables the basic variables or BV that satisfy Ax b Different choices of nonbasic variables will lead to different basic solutions L Ntaimo c 2005 INEN420 TAMU 15 4 5 Preview of the Simplex Algorithm Consider the basic solutions to the following system of 2 equations x1 x2 3 x2 x3 1 The number of nonbasic variables 3 2 1 Setting for example …