Chapter 4 The Simplex Algorithm and Goal Programming4.1 How to Convert an LP to Standard FormExample 1: Leather LimitedExample 1: SolutionSlide 64.2 Preview of the Simplex AlgorithmSlide 84.3 Direction of UnboundednessSlide 104.4 Why Does LP Have an Optimal bfs?4.5 The Simplex AlgorithmExample 2: Dakota Furniture CompanyEx. 2 - continuedExample 2: SolutionEx. 2: Solution continuedSlide 17Slide 18Slide 19Slide 20Ex. 2: Solution continuedSlide 22Slide 23Slide 24Ex. 2: Solution continuedSlide 26Ex. 2: Solution continuedSlide 28Slide 294.6 Using the Simplex Algorithm to solve Minimization ProblemsSlide 31Slide 32Slide 33Slide 344.7 Alternate Optimal Solutions4.8 – Unbounded LPs4.9 The LINDO Computer PackageSlide 38Slide 39Slide 40Slide 41Slide 424.10 Matrix Generators, LINGO and Scaling LPsSlide 444.11 Degeneracy and the Convergence of the Simplex AlgorithmSlide 46Slide 474.12 The Big M MethodExample 4: BevcoExample 4: SolutionEx. 4 – Solution continuedEx. 4 – Solution continuedSlide 53Slide 54Slide 55Slide 56Slide 57Slide 584.13 The Two-Phase Simplex MethodSlide 604.14 Unrestricted-in-Sign VariablesSlide 624.15 Karmarkar’s Method for Solving LPs4.16 Multiattribute Decision Making in the Absence of Uncertainty: Goal ProgrammingExample 10: Burnit Goal ProgrammingEx. 10 - continuedExample 10: SolutionEx. 10 – Solution continuedSlide 69Slide 70Slide 71Slide 724.17 Using the Excel Solver to Solve LPsChapter 4The Simplex Algorithm and Goal Programmingto accompanyOperations Research: Applications and Algorithms 4th editionby Wayne L. WinstonCopyright (c) 2004 Brooks/Cole, a division of Thomson Learning, Inc.24.1 How to Convert 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.3Example 1: Leather Limited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.4 Example 1: Solution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 + 3x2s.t. x1 + x2 ≤ 40 (leather constraint) 2x1 +x2 ≤ 60 (labor constraint) x1, x2 ≥ 05 To convert a ≤ constraint to an equality, define for each constraint a slack variable si (si = slack variable for the ith constraint). A slack variable is the amount of the resource unused in the ith constraint.If a constraint i of an LP is a ≤ constraint, convert it to an equality constraint by adding a slack variable si to the ith constraint and adding the sign restriction si ≥ 0.6 To convert the ith ≥ constraint to an equality constraint, define an excess variable (sometimes called a surplus variable) ei (ei will always be the excess variable for the ith ≥ constraint. We define ei to be the amount by which ith constraint is over satisfied.Subtracting the excess variable ei from the ith constraint and adding the sign restriction ei ≥ 0 will convert the constraint.If an LP has both ≤ and ≥ constraints, apply the previous procedures to the individual constraints.74.2 Preview of the Simplex Algorithm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. Any basic solution in which all variables are nonnegative is called a basic feasible solution (or bfs).8 The following theorem explains why the concept of a basic feasible solution is of great importance in linear programming.Theorem 1 The feasible region for any linear programming problem is a convex set. Also, if an LP has an optimal solution, there must be an extreme point of the feasible region that is optimal.94.3 Direction of UnboundednessConsider an LP in standard form with feasible region S and constraints Ax=b and x ≥ 0. Assuming that our LP has n variables, 0 represents an n-dimensional column vector consisting of all 0’s.A non-zero vector d is a direction of unboundedness if for all xS and any c≥0, x +cdS10 Theorem 2 Consider an LP in standard form, having bfs b1, b2,…bk. Any point x in the LP’s feasible region may be written in the formwhere d is 0 or a direction of unboundedness and =1 and i ≥ 0.Any feasible x may be written as a convex combination of the LP’s bfs.kiiii1bdxkiii1114.4 Why Does LP Have an Optimal bfs?Theorem 3 If an LP has an optimal solution, then it has an optimal bfs.For any LP with m constraints, two basic feasible solutions are said to be adjacent if their sets of basic variables have m – 1 basic variables in common.The set of points satisfying a linear inequality in three (or any number of) dimensions is a half-space.The intersection of half-space is called a polyhedron.124.5 The Simplex AlgorithmThe simplex algorithm can be used to solve LPs in which the goal is to maximize the objective function.Step 1 Convert the LP to standard formStep 2 Obtain a bfs (if possible) from the standard formStep 3 Determine whether the current bfs is optimalStep 4 If the current bfs is not optimal, determine which nonbasic variable should become a basic variable and which basic variable should become a nonbasic variable to find a bfs with a better objective function value.Step 5 Use EROs to find a new bfs with a better objective function value. Go back to Step 3.13Example 2: Dakota Furniture CompanyThe Dakota Furniture company manufactures desk, tables, and chairs. The manufacture of each type of furniture requires lumber and two types of skilled labor: finishing and carpentry. The amount of each resource needed to make each type of furniture is given in the table below.Resource Desk Table ChairLumber 8 board ft