Trabajo De Sadoi

Linear Programming: Theory and Applications
Catherine Lewis May 11, 2008

1

Contents
1 Introduction to Linear Programming 1.1 What is a linear program? . . . . . . . . . . . . . . . . . . . . . . 1.2 1.3 1.4 1.5 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Manipulating a Linear Programming Problem . . . . . . . . . . . The Linear Algebra of Linear Programming . .. . . . . . . . . . Convex Sets and Directions . . . . . . . . . . . . . . . . . . . . . 3 3 5 6 7 8

2 Examples from Bazaraa et. al. and Winston 11 2.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 17 17 19 20

3 The Theory Behind Linear Programming 3.1 3.2 Definitions . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . The General Representation Theorem . . . . . . . . . . . . . . .

4 An Outline of the Proof

5 Examples With Convex Sets and Extreme Points From Bazaara et. al. 22 6 Tools for Solving Linear Programs 23 6.1 Important Precursors to the Simplex Method . . . . . . . . . . . 23 7 The Simplex Method In Practice 8 What if there is no initial basis in theSimplex tableau? 8.1 8.2 The Two-Phase Method . . . . . . . . . . . . . . . . . . . . . . . The Big-M Method . . . . . . . . . . . . . . . . . . . . . . . . . . 25 28 29 31

33 9 Cycling 9.1 The Lexicographic Method . . . . . . . . . . . . . . . . . . . . . 34 9.2 9.3 9.4 Bland’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theorem from [2] . . . . . . . . . . . . . . . . . . .. . . . . . . . Which Rule to Use? . . . . . . . . . . . . . . . . . . . . . . . . . 37 37 39

10 Sensitivity Analysis 39 10.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 10.1.1 Sensitivity Analysis for a cost coefficient . . . . . . . . . . 1 40

10.1.2 Sensitivity Analysis for a right-hand-side value . . . . . .

41

11 Case Study: Busing Children to School41 11.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 11.2 The Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.2 Objective Function . . . . . . . . . . . . . . . . . . . . . . 11.2.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 The Complete Program . . .. . . . . . . . . . . . . . . . . . . . 11.4 Road Construction and Portables . . . . . . . . . . . . . . . . . . 11.4.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . 11.4.2 Portable Classrooms . . . . . . . . . . . . . . . . . . . . . 11.5 Keeping Neighborhoods Together . . . . . . . . . . . . . . . . . . 11.6 The Case Revisited . . . . . . . . . . . . . . . . . . . . . . . . . .11.6.1 Shadow Prices . . . . . . . . . . . . . . . . . . . . . . . . 11.6.2 The New Result . . . . . . . . . . . . . . . . . . . . . . . 12 Conclusion 42 42 43 43 47 49 49 50 55 56 56 57 57

2

1

Introduction to Linear Programming

Linear programming was developed during World War II, when a system with which to maximize the efficiency of resources was of utmost importance. New war-relatedprojects demanded attention and spread resources thin. “Programming” was a military term that referred to activities such as planning schedules efficiently or deploying men optimally. George Dantzig, a member of the U.S. Air Force, developed the Simplex method of optimization in 1947 in order to provide an efficient algorithm for solving programming problems that had linear structures. Since then,experts from a variety of fields, especially mathematics and economics, have developed the theory behind “linear programming” and explored its applications [1]. This paper will cover the main concepts in linear programming, including examples when appropriate. First, in Section 1 we will explore simple properties, basic definitions and theories of linear programs. In order to illustrate some...