Linear Programming Lecture Notes

1 Linear Programming : Penn State Math 484 Lecture NotesVersion Griffin 2009-2014 Licensed under a Creative Commons Attribution-Noncommercial-Share Alike United States LicenseWith Contributions By:Bob Pakzad-HursonGreg FerenceVeselka KafedzhievaMichael ClineAkinwale AkinbiyiEthan WrightRichard BenjaminDouglas MercerContentsList of FiguresvPrefaceixChapter 1. Introduction to Optimization11. A General maximization Formulation22. Some Geometry for Optimization43. Gradients, Constraints and Optimization10 Chapter 2. Simple Linear Programming Problems131. Modeling Assumptions in Linear Programming142.

2 Graphically Solving Linear Programs Problems with Two Variables (BoundedCase)163. Formalizing The Graphical Method174. Problems with Alternative Optimal Solutions185. Problems with No Solution206. Problems with Unbounded Feasible Regions22 Chapter 3. Matrices, Linear Algebra and Linear Programming271. Matrices272. Special Matrices and Vectors293. Matrices and Linear Programming Expression304. Gauss-Jordan Elimination and Solution to Linear Equations335. Matrix Inverse356. Solution of Linear Equations377. Linear Combinations, Span, Linear Independence398.

3 Basis419. Rank4310. Solving Systems with More Variables than Equations4511. Solving Linear Programs with Matlab47 Chapter 4. Convex Sets, Functions and Cones and Polyhedral Theory511. Convex Sets512. Convex and Concave Functions523. Polyhedral Sets534. Rays and Directions565. Directions of Polyhedral Sets576. Extreme Points597. Extreme Directions62iii8. Caratheodory Characterization Theorem64 Chapter 5. The Simplex Method691. Linear Programming and Extreme Points692. Algorithmic Characterization of Extreme Points703. The Simplex Algorithm Algebraic Form714.

4 Simplex Method Tableau Form785. Identifying Unboundedness816. Identifying Alternative Optimal Solutions847. Degeneracy and Convergence86 Chapter 6. Simplex Initialization911. Artificial Variables912. The Two-Phase Simplex Algorithm953. The Big-M Method984. The Single Artificial Variable Technique1025. Problems that Can t be Initialized by Hand103 Chapter 7. Degeneracy and Convergence1091. Degeneracy Revisited1092. The Lexicographic Minimum Ratio Leaving Variable Rule1113. Bland s Rule, Entering Variable Rules and Other Considerations116 Chapter 8.

5 The Revised Simplex Method and Optimality Conditions1171. The Revised Simplex Method1172. Farkas Lemma and Theorems of the Alternative1213. The Karush-Kuhn-Tucker Conditions1264. Relating the KKT Conditions to the Tableau132 Chapter 9. Duality1371. The Dual Problem1372. Weak Duality1413. Strong Duality1424. Geometry of the Dual Problem1455. Economic Interpretation of the Dual Problem1486. The Dual Simplex Method152 Bibliography157ivList of pen with unknown side lengths. The objective is to identify the values ofxandythat maximize the area of the pen (and thus the number of goats thatcan be kept).

6 With Level Sets Projected on the Graph ofz. The level sets existing inR2while the graph ofzexistingR3. The level sets have been projected onto theirappropriate heights on the Plot ofz=x2+y2. The circles inR2are the level sets of the lighter the circle hue, the higher the value ofcthat defines the level Line Function: The points in the graph shown in this figure are in the setproduced using the expressionx0+vtwherex0= (2,1) and letv= (2,2). Level Curve Plot with Gradient Vector: We ve scaled the gradient vectorin this case to make the picture understandable. Note that the gradient isperpendicular to the level set curve at the point (1,1), where the gradient wasevaluated.

7 You can also note that the gradient is pointing in the direction ofsteepest ascent ofz(x,y). Curves and Feasible Region: At optimality the level curve of the objectivefunction is tangent to the binding of the Binding Constraint and Objective: At optimality the gradientof the binding constraints and the objective function arescaled versions of Region and Level Curves of the Objective Function: The shaded regionin the plot is the feasible region and represents the intersection of the fiveinequalities constraining the values ofx1andx2. On the right, we see theoptimal solution is the last point in the feasible region that intersects a levelset as we move in the direction of increasing Bounded Set: The setS(in blue) is bounded because it can be entirelycontained inside a ball of a finite radiusrand centered at some pointx0.

8 In thisexample, the setSis inR2. This figure also illustrates the fact that a ball inR2is just a disk and its example of infinitely many alternative optimal solutions in a linearprogramming problem. The level curves forz(x1,x2) = 18x1+ 6x2areparallelto one face of the polygon boundary of the feasible region. Moreover, this sidecontains the points of greatest value forz(x1,x2) inside the feasible region. Anyvcombination of (x1,x2) on the line 3x1+x2= 120 forx1 [16,35] will providethe largest possible valuez(x1,x2) can take in the feasible Linear Programming Problem with no solution.

9 The feasible region of thelinear Programming problem is empty; that is, there are no values forx1andx2that can simultaneously satisfy all the constraints. Thus, no solution Linear Programming Problem with Unbounded Feasible Region: Note thatwe can continue to make level curves ofz(x1,x2) corresponding to larger andlarger values as we move down and to the right. These curves will continueto intersect the feasible region for any value ofv=z(x1,x2) we choose. Thus,we can makez(x1,x2) as large as we want and still find a point in the feasibleregion that will provide this value.

10 Hence, the optimal value ofz(x1,x2) subjectto the constraints + . That is, the problem is Linear Programming Problem with Unbounded Feasible Region and FiniteSolution: In this problem, the level curves ofz(x1,x2) increase in a more southernly direction that in Example that is,awayfrom the directionin which the feasible region increases without bound. The point in the feasibleregion with largestz(x1,x2) value is (7/3,4/3). Note again, this is a feasible region for the diet problem is unbounded and there are alternativeoptimal solutions, since we are seeking a minimum, we travel in the oppositedirection of the gradient, so toward the origin to reduce the objective functionvalue.