Linear Programming – Simplex MethodLinear Programming - ReviewLinear Programming – ReviewSlide 4Linear Programming – Simplex AlgorithmSlide 6Slide 7Linear Programming – Simplex Method: Computational ProblemsSlide 9Simplex Method – Finding an Initial Basic Feasible SolutionSlide 11Simplex Method – Solve Using Big-M MethodLinear Programming – Simplex MethodLinear Programming - ReviewGraphical Method:• What is the feasible region?• Where was optimal solution found?• What is primary limitation of graphical method?Conversion to Standard Form:---Linear Programming – ReviewSolving Systems of Linear Equations:• What is a basic solution?• How did we obtain a basic solution?• What is a basic feasible solution?Relationship between graphical and algebraic representation of the feasible region:corner point basic solutionLinear Programming – ReviewFundamental insight – the optimal solution to a linear program, if it exists, is also a basic feasible solution.Naïve approach – solve for all basic solutions and find the feasible solution with the largest value (maximization problem).What is the problem with this approach? – there are possible basic solutions, where m is the number of constraints and n is the number of variables.)!(!!mnmnmnLinear Programming – Simplex AlgorithmStep 1 Convert the LP to standard form.Step 2 Obtain a bfs (if possible) from the standard form.Step 3 Determine whether the current bfs is optimal.Step 4 If the current bfs is not optimal, then determine which nonbasic basic variable should become a basic variable and which basic variable should become a nonbasic variable to find a new bfs with a better objective function value. (pivot operation)Step 5 Use EROs to find the new bfs with the better objective function value. Go back to step 3.Operations Research, Wayne L. WinstonLinear Programming – Simplex MethodReview Simplex HandoutsLinear Programming – Simplex MethodMinimization Problems:Min Z = cx  (-) Max Z = -cxEx. Min 2x1 – 3x2 + x3 s.t. x1 + 2x2 < 5 2x1 - 3x3 > 10 x1, x2, x3 > 0(-)Max -2x1 + 3x2 - x3 s.t. x1 + 2x2 < 5 2x1 - 3x3 > 10 x1, x2, x3 > 0Linear Programming – Simplex Method: Computational ProblemsBreaking Ties in Selection of Non-Basic Variable – if tie fornon-basic variable with largest relative profit ( ), arbitrarily select incoming variable.Ties in Minimum Ratio Rule (Degeneracy) – if more than onebasic variable have same minimum ratio, select either variableto leave the basis. This will result in a basic variable taking ona value of 0. When this occurs, the solution is referred to asa degenerate basic feasible solution. When this occurs, you may transition through more than one simplex tableau with the same objective (Z) value. jCLinear Programming – Simplex Method: Computational ProblemsUnbounded Solutions – if when performing the minimum ratiorule, none of the ratios are positive, then the solution isunbounded (e.g Max Z = or Min = - ).Simplex Method – Finding an Initial Basic Feasible SolutionMin Z = -3x1 + x2 + x3s.t. x1 – 2x2 + x3 <= 11 -4x1 + x2 +2x3 >= 3 2x1 - x3 = -1 x1, x2, x3 >= 0Standard Form:(-) Max Z = 3x1 - x2 - x3 s.t. x1 – 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 -x5 = 3 -2x1 + x3 = 1 x1, x2, x3, x4, x5 >= 0Simplex Method – Finding an Initial Basic Feasible Solution(-) Max Z = 3x1 - x2 - x3 s.t. x1 – 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 -x5 = 3 -2x1 + x3 = 1 x1, x2, x3, x4, x5 >= 0Only x4 is basic.Introduce artificial variables. s.t. x1 – 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 -x5 + x6 = 3 -2x1 + x3 + x7 = 1 x1, x2, x3, x4, x5, x6, x7 >= 0Simplex Method – Solve Using Big-M MethodLet M be an arbitrarily large number, then:(-) Max Z = 3x1 - x2 - x3 + 0x4 + 0x5 – Mx6 – Mx7 s.t. x1 – 2x2 + x3 + x4 = 11 -4x1 + x2 +2x3 -x5 + x6 = 3 -2x1 + x3 + x7 = 1 x1, x2, x3, x4, x5, x6, x7 >= 0Note: If the simplex algorithm terminates with one of the artificial variables as a basic variable, then the original problem has no feasible