Linear Programming Lecture Notes

Linear Programming: Penn State Math 484 Lecture Notes

Version 1.8.3

Christopher Griffin 2009-2014

Licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License

With Contributions By: Bob Pakzad-Hurson Greg Ference Veselka Kafedzhieva Michael Cline Akinwale Akinbiyi Ethan Wright Richard Benjamin Douglas Mercer

Contents

List of Figures

v

Preface

ix

Chapter 1. Introduction to Optimization

1

1. A General Maximization Formulation

2

2. Some Geometry for Optimization

4

3. Gradients, Constraints and Optimization

10

Chapter 2. Simple Linear Programming Problems

13

1. Modeling Assumptions in Linear Programming

14

2. Graphically Solving Linear Programs Problems with Two Variables (Bounded

Case)

16

3. Formalizing The Graphical Method

17

4. Problems with Alternative Optimal Solutions

18

5. Problems with No Solution

20

6. Problems with Unbounded Feasible Regions

22

Chapter 3. Matrices, Linear Algebra and Linear Programming

27

1. Matrices

27

2. Special Matrices and Vectors

29

3. Matrices and Linear Programming Expression

30

4. Gauss-Jordan Elimination and Solution to Linear Equations

33

5. Matrix Inverse

35

6. Solution of Linear Equations

37

7. Linear Combinations, Span, Linear Independence

39

8. Basis

41

9. Rank

43

10. Solving Systems with More Variables than Equations

45

11. Solving Linear Programs with Matlab

47

Chapter 4. Convex Sets, Functions and Cones and Polyhedral Theory

51

1. Convex Sets

51

2. Convex and Concave Functions

52

3. Polyhedral Sets

53

4. Rays and Directions

56

5. Directions of Polyhedral Sets

57

6. Extreme Points

59

7. Extreme Directions

62

iii

8. Caratheodory Characterization Theorem

64

Chapter 5. The Simplex Method

69

1. Linear Programming and Extreme Points

69

2. Algorithmic Characterization of Extreme Points

70

3. The Simplex Algorithm?Algebraic Form

71

4. Simplex Method?Tableau Form

78

5. Identifying Unboundedness

81

6. Identifying Alternative Optimal Solutions

84

7. Degeneracy and Convergence

86

Chapter 6. Simplex Initialization

91

1. Artificial Variables

91

2. The Two-Phase Simplex Algorithm

95

3. The Big-M Method

98

4. The Single Artificial Variable Technique

102

5. Problems that Can't be Initialized by Hand

103

Chapter 7. Degeneracy and Convergence

109

1. Degeneracy Revisited

109

2. The Lexicographic Minimum Ratio Leaving Variable Rule

111

3. Bland's Rule, Entering Variable Rules and Other Considerations

116

Chapter 8. The Revised Simplex Method and Optimality Conditions

117

1. The Revised Simplex Method

117

2. Farkas' Lemma and Theorems of the Alternative

121

3. The Karush-Kuhn-Tucker Conditions

126

4. Relating the KKT Conditions to the Tableau

132

Chapter 9. Duality

137

1. The Dual Problem

137

2. Weak Duality

141

3. Strong Duality

142

4. Geometry of the Dual Problem

145

5. Economic Interpretation of the Dual Problem

148

6. The Dual Simplex Method

152

Bibliography

157

iv

List of Figures

1.1 Goat pen with unknown side lengths. The objective is to identify the values of

x and y that maximize the area of the pen (and thus the number of goats that

can be kept).

2

1.2 Plot with Level Sets Projected on the Graph of z. The level sets existing in R2

while the graph of z existing R3. The level sets have been projected onto their

appropriate heights on the graph.

5

1.3 Contour Plot of z = x2 + y2. The circles in R2 are the level sets of the function. The lighter the circle hue, the higher the value of c that defines the level set. 6

1.4 A Line Function: The points in the graph shown in this figure are in the set

produced using the expression x0 + vt where x0 = (2, 1) and let v = (2, 2).

6

1.5 A Level Curve Plot with Gradient Vector: We've scaled the gradient vector

in this case to make the picture understandable. Note that the gradient is

perpendicular to the level set curve at the point (1, 1), where the gradient was

evaluated. You can also note that the gradient is pointing in the direction of

steepest ascent of z(x, y).

8

1.6 Level Curves and Feasible Region: At optimality the level curve of the objective

function is tangent to the binding constraints.

11

1.7 Gradients of the Binding Constraint and Objective: At optimality the gradient

of the binding constraints and the objective function are scaled versions of each

other.

12

2.1 Feasible Region and Level Curves of the Objective Function: The shaded region

in the plot is the feasible region and represents the intersection of the five

inequalities constraining the values of x1 and x2. On the right, we see the optimal solution is the "last" point in the feasible region that intersects a level

set as we move in the direction of increasing profit.

16

2.2 A Bounded Set: The set S (in blue) is bounded because it can be entirely

contained inside a ball of a finite radius r and centered at some point x0. In this example, the set S is in R2. This figure also illustrates the fact that a ball in R2

is just a disk and its boundary.

18

2.3 An example of infinitely many alternative optimal solutions in a linear programming problem. The level curves for z(x1, x2) = 18x1 + 6x2 are parallel to one face of the polygon boundary of the feasible region. Moreover, this side contains the points of greatest value for z(x1, x2) inside the feasible region. Any

v

combination of (x1, x2) on the line 3x1 + x2 = 120 for x1 [16, 35] will provide

the largest possible value z(x1, x2) can take in the feasible region S.

20

2.4 A Linear Programming Problem with no solution. The feasible region of the linear programming problem is empty; that is, there are no values for x1 and x2 that can simultaneously satisfy all the constraints. Thus, no solution exists. 21

2.5 A Linear Programming Problem with Unbounded Feasible Region: Note that

we can continue to make level curves of z(x1, x2) corresponding to larger and

larger values as we move down and to the right. These curves will continue

to intersect the feasible region for any value of v = z(x1, x2) we choose. Thus,

we can make z(x1, x2) as large as we want and still find a point in the feasible

region that will provide this value. Hence, the optimal value of z(x1, x2) subject

to the constraints +. That is, the problem is unbounded.

22

2.6 A Linear Programming Problem with Unbounded Feasible Region and Finite Solution: In this problem, the level curves of z(x1, x2) increase in a more "southernly" direction that in Example 2.10?that is, away from the direction in which the feasible region increases without bound. The point in the feasible region with largest z(x1, x2) value is (7/3, 4/3). Note again, this is a vertex. 23

3.1 The feasible region for the diet problem is unbounded and there are alternative

optimal solutions, since we are seeking a minimum, we travel in the opposite

direction of the gradient, so toward the origin to reduce the objective function

value. Notice that the level curves hit one side of the boundary of the feasible

region.

49

3.2 Matlab input for solving the diet problem. Note that we are solving a

minimization problem. Matlab assumes all problems are mnimization problems,

so we don't need to multiply the objective by -1 like we would if we started

with a maximization problem.

50

4.1 Examples of Convex Sets: The set on the left (an ellipse and its interior) is

a convex set; every pair of points inside the ellipse can be connected by a line

contained entirely in the ellipse. The set on the right is clearly not convex as

we've illustrated two points whose connecting line is not contained inside the

set.

52

4.2 A convex function: A convex function satisfies the expression f (x1+(1-)x2)

f (x1) + (1 - )f (x2) for all x1 and x2 and [0, 1].

53

4.3 A hyperplane in 3 dimensional space: A hyperplane is the set of points satisfying

an equation aT x = b, where k is a constant in R and a is a constant vector

in Rn and x is a variable vector in Rn. The equation is written as a matrix

multiplication using our assumption that all vectors are column vectors.

54

4.4 Two half-spaces defined by a hyper-plane: A half-space is so named because any

hyper-plane divides Rn (the space in which it resides) into two halves, the side

"on top" and the side "on the bottom."

54

4.5 A Ray: The points in the graph shown in this figure are in the set produced

using the expression x0 + d where x0 = [2, 1]T and d = [2, 2]T and 0.

56

vi

4.6 Convex Direction: Clearly every point in the convex set (shown in blue) can be

the vertex for a ray with direction [1, 0]T contained entirely in the convex set.

Thus [1, 0]T is a direction of this convex set.

57

4.7 An Unbounded Polyhedral Set: This unbounded polyhedral set has many

directions. One direction is [0, 1]T .

58

4.8 Boundary Point: A boundary point of a (convex) set C is a point in the set

so that for every ball of any radius centered at the point contains some points

inside C and some points outside C.

59

4.9 A Polyhedral Set: This polyhedral set is defined by five half-spaces and has

a single degenerate extreme point located at the intersection of the binding

constraints

3x1

+ x2

120,

x1

+ 2x2

160

and

28 16

x1

+ x2

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download