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

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

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

Google Online Preview   Download