Introduction to Mathematical Programming

Introduction to Mathematical Programming by Russell C. Walker
View this page in Romanian courtesy of azoft

This text is a soft cover, spiral bound, custom published version of the hard cover text of the same name. It or its hardcover predecessor have been used in the Business Administration program at Carnegie Mellon for more than 10 years. It is the sole text for Models and Methods for Optimization and one of the texts for Multivariate Analysis.

There have been several improvements in the custom version which is now in its third edition:

Two sections on the matrix interpretation of the simplex algorithm have been added. These lead to an increased understanding of the simplex algorithm and the ability to add a variable to a linear program when the optimal tableau is known without having to re-solve the problem.
A section on numerical search for a maximum has been added.
Exercises have been added.
An adaptation of the transportation model to solve a transhipment problem has been added.
A discussion of alternative constraints with an application to job sequencing has been added.
An appendix on the use of Solver in Excel has replaced the one on graphing calculators.
Errors have been corrected and the formatting improved.
The appendix with solutions to the odd problems has been completed.
The supplement containing the solutions to the even numbered problems and the case studies in Chapter 10 has been completed and is available from the author as a 125 page pdf file.

The text can be ordered by contacting the author: rw1k AT andrew DOT cmu DOT edu or from Amazon.

The table of contents and chapter summaries:

Chapter 1: Introduction to the Problems Section 1.1 Introduction p. 1 Section 1.2 Types of problems to be considered p. 3 Section 1.3 Sample problems p. 6 Section 1.4 Graphical solution of linear programs p. 17 Section 1.5 Summary and objectives p. 26	The first chapter provides a survey of problem types to be considered to indicate the possible applications. In some cases the contribution of the solution to an organization is indicated to emphasize the relevance of these skills. The sample problems in the third section suggest the linear structure involved in most models we consider and issues associated with model formulation. The concluding section presents a graphical approach to solving two variable linear programs.

Chapter 2: Vectors and Matrices Section 2.1 Introduction p. 28 Section 2.2 Vectors p. 29 Section 2.3 The span of a set of vectors p. 34 Section 2.4 Matrices p. 38 Section 2.5 Linear independence p. 48 Section 2.6 Systems of equations p. 54 Section 2.7 The inverse of a matrix p. 68 Section 2.8 Summary and objectives p. 77	This chapter develops the matrix algebra needed to treat linear problems. Section 2.5 is important since there is a linearly independent set of vectors corresponding to each basic solution in the simplex algorithm. The discussion of linear independence includes some principles of basic mathematical reasoning which should be understood by any student who has studied mathematics. These ideas are then used in proving propositions concerning linear independence. The section on systems of equations is important because the row operations used there are the same as those needed later in the simplex algorithm. Matrix inverses are discussed but are needed only in the Exercises of Section 3.3 and in Sections 4.4 and 4.5.

Chapter 3 Linear Programming Section 3.1 Introduction p. 81 Section 3.2 Slack variables p. 83 Section 3.3 The simplex algorithm p. 89 Section 3.4 Basic feasible solutions and extreme points p. 101 Section 3.5 Formulation examples p. 112 Section 3.6 General constraints and variables p. 128 Section 3.9 Summary and objectives p. 142	The central topic in the text is linear programming. Sections 3.2 and 3.3 develop the simplex algorithm. In Section 3.4 we establish that the simplex algorithm is correct. Section 3.5 discusses the formulation of problems and is of particular importance to those most motivated by applications. Section 3.6 extends the simplex algorithm to problems with nonstandard constraints or unsigned variables.

Chapter 4 Duality and Post Optimal Analysis Section 4.1 Introduction p. 144 Section 4.2 The dual and minimizing problems p. 1445 Section 4.3 Sensitivity analysis p. 166 Section 4.4 The matrix setting for the simplex algorithm p. 186 Section 4.5 Adding a variable p. 192 Section 4.6 Summary and objectives p. 198	Section 4.2 discusses the solution of minimization problems by using the associated dual maximization problem. The power of linear programming as a managerial tool is shown in an example which helps to motivate the discussion of sensitivity analysis in Section 4.3. Section 4.4 takes a closer look at the linear algebra involved in the simplex algorithm, and in Section 4.5 that linear algebra is used to show that a variable can be added to a solved linear program without having to re-solve it.

Chapter 5 Network Models Section 5.1 Introduction p. 200 Section 5.2 The transportation problem p. 206 Section 5.3 The critical path method p. 231 Section 5.4 Shortest path models p. 254 Section 5.5 Minimal spanning trees p. 261 Section 5.6 The maximum flow problem p. 276 Section 5.7 Summary and objectives p. 284	Chapter 5 treats six network problems: the transportation problem, the transhipment problem, the critical path method, the shortest path problem, minimal spanning trees, and maximum flow. Sample models in LINGO and LINDO are provided. The discussions of shortest paths and minimal spanning trees require some introduction to graph theory. The effectiveness and correctness of an algorithm are also introduced and considered for minimal spanning tree algorithms.

Chapter 6 Unconstrained Extrema Section 6.1 Introduction p. 287 Section 6.2 Locating extrema p. 288 Section 6.3 The economic lot size model and convexity p. 294 Section 6.4 Location of extrema in two variables p. 307 Section 6.5 Least squares approximation p. 317 Section 6.6 The n-variable case p. 323 Section 6.7 Numerical search p. 329 Section 6.8 Summary and objectives p. 337	In this chapter we discuss classical optimization techniques. Some knowledge of differential calculus is required. Convexity is discussed in connection with the economic order quantity problem and inventory management. A section is devoted to the application of least squares curve fitting. There is a discussion of the theory underlying optimization and also an introduction to the use of Maple to solve optimization problems. Numerical search techniques are also introduced.

Chapter 7 Constrained Extrema Section 7.1 Introduction p. 339 Section 7.2 Two variable problems p. 346 Section 7.3 More variables; more constraints p. 352 Section 7.4 Problems having inequality constraints p. 362 Section 7.5 The convex programming problem p. 372 Section 7.6 Linear programming revisited p. 389 Section 7.7 Summary and objectives p. 392	This chapter extends the discussion begun in the previous one to problems in which the solution is subject to constraints. The key theorem is the Karush-Kuhn-Tucker theorem for solving convex problems. The main applications presented are the minimization of the cost of a cardboard box, the maximization of utility, the minimization of the cost of equipment replacement, and choosing an investment portfolio to achieve an acceptable return at minimum risk. The chapter concludes with a look back at linear programming as a special case of convex programming.

Chapter 8 Integer Programming Section 8.1 Introduction p. 394 Section 8.2 The knapsack problem p. 397 Section 8.3 The dual simplex algorithm p. 406 Section 8.4 Adding a constraint p. 415 Section 8.5 Branch and bound for integer programs: p. 422 Section 8.6 Basic integer programming models p. 429 Section 8.7 The traveling salesman problem p. 452 Section 8.8 Summary and objectives p. 466	Branch-and-bound algorithms are central to this topic. The knapsack problem is considered first to introduce the branch-and-bound method. The dual simplex algorithm is discussed next, and then employed to re-optimize a solved problem after a constraint has been added. This then forms the basis of a branch-and-bound approach to solving integer programs. A variety of integer programming models is then discussed, and the chapter concludes with a branch-and-bound approach to the traveling salesman problem.

Chapter 9 Introduction to Dynamic Programming Section 9.1 Introduction to recursion p. 468 Section 9.2 The longest path p. 476 Section 9.3 A fixed cost transportation problem p. 479 Section 9.4 More examples p. 484 Section 9.5 Summary and objectives p. 491	Problems for which a solution can be obtained through a succession of independent decisions can often be solved by dynamic programming. Dynamic programming requires an introduction to recursion. This leads to a brief excursion through the Towers of Hanoi, Fibonacci numbers, and the binomial expansion. Applications discussed are the longest path problem, which is similar to the determination of earliest times in the CPM model, the fixed cost transportation problem, and the cargo loading problem. We also return to the traveling salesman problem and investigate the computational challenge of that problem.

Chapter 10 Case Studies Section 10.1 Tweaking Widget's production p. 494 Section 10.2 A furniture sales opportunity p. 501 Section 10.3 Building storage lockers p. 502 Section 10.4 The McIntire farm p. 503 Section 10.5 Cylinders for beverages p. 504 Section 10.6 Books by the holidays p. 506 Section 10.7 Into a blind trust p. 508 Section 10.8 Max's taxes p. 509 Section 10.9 A supply network p. 510	Chapter 10 presents several more open-ended problems suitable for longer assignments and group projects. Solutions to the cases and suggestions for their class use are available for instructors in the solutions manual from the author. Methods required for their solution are linear programming, integer programming, critical path management, and non-linear optimization.

Appendix A Brief Introductions to LINDO and LINGO Section A.1 LINDO p. 512 Section A.2 LINGO p. 516	The LINDO program is extremely useful in solving linear programs including those with integer constraints. Examples of its use are presented along with the use of the basic commands. LINGO is a related package allowing the solution of nonlinear problems. As a modelling language, LINGO is particularly useful for its ability to efficiently express problems with repetitive constraints.

Appendix B A Brief Introduction to Maple Section B.1 The basics p. 521 Section B,2 Using packages p. 525	The symbolic computation software Maple can be very useful, particularly in solving classical optimization problems such as are presented in Chapters 5 and 6 as well as in doing matrix computations, curve fitting, solving linear programs, and solving network models.

Appendix C Using Excel Solver Section C.1 A basic example p. 533 Section C.2 Two network examples p. 539 Section C.3 Two nonlinear examples p. 543	The Excel spreadsheet includes the Solver add-in which is extremely useful in linear optimization problems. A brief introduction to Solver with several examples of its use is provided.

Appendix D Selected Answers and Hints p. 546	The answers to all odd problems are provided here. Solutions to the even numbered problems are available from the author in a pdf file.

References p. 585

Index p. 588