Introduction This is a text written for an audience of business students with the mathematical background and the interest to appreciate an occasional departure from a main emphasis on applications. A student can begin this text following a calculus course at a level comparable to that taught for engineering and science students. Only differential calculus is required, and the key elements of calculus needed for optimization are recalled at the beginning of Chapter 5. The needed background on vectors and matrices is found in Chapter 2.
There is enough material for a two semester course. It could serve as the text for a variety of courses with titles such as linear programming, optimization, quantitative methods for management, or operations research.
Software can be used productively in solving many of the problems proposed. Examples using the optimization packages LINDO and LINGO appear in several chapters as well as in Appendix A. The symbolic mathematics package Maple is also used in the chapters on vectors and matrices and on nonlinear optimization. An appendix on Maple indicates how to use it to do curve fitting, solve network problems, and to solve linear programs. There is also an appendix introducing the TI-82 and TI-92 graphing calculators.
Objectives The first objective is to provide the needed background to begin to employ mathematical programming as a tool. While managerial applications are the primary focus, mathematical techniques can prove useful in many areas. The key step is to acquire the mind-set that allows one to recognize when a mathematical model can be useful. Even for a person who does not expect to use mathematics him or herself, it is certainly desirable to be familiar with the ideas when working with or supervising others who do the actual analysis of problems. So the ultimate objective is to acquire an attitude that appreciates the potential of the methods to be presented, and then to develop an understanding and ability to apply them.
The second objective is to achieve some appreciation and understanding of the mathematics associated with the applied techniques. There are some proofs here and there, and also an occasional excursion into topics such as basic graph theory, linear algebra, analysis, properties of algorithms, and combinatorics. While these side-trips can be largely ignored by those solely interested in applications, they could also be pointed out and amplified by the instructor who wants a course that emphasizes the mathematics.
Chapter 1: Introduction to the Problems
The first chapter provides a survey of problem types to be considered to give an early view of the applications possible with the tools to be studied. In some cases the effect of the solution of a problem on 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 some of the issues associated with model formulation. The concluding section presents a graphical approach to solving two variable linear programs. This introduces a key managerial tool and also motivates the need for algebraic methods to solve problems involving more variables.
Chapter 2: Vectors and Matrices
This chapter develops the ideas needed to treat linear problems and serves two purposes. First, it contains the prerequisite material for the study of linear programming. Second, it can be viewed as a brief introduction to matrix algebra in its own right. The reader or instructor might choose to omit certain sections depending upon his or her goal.
For instance, matrix inverses are discussed twice: a brief introduction of the $2\times2$ case in Section 2.4 and a more detailed discussion including the $n\times n$ case in Section 2.7. Beyond Chapter 2, inverses are actually needed only in the Exercises of Section 3.3. Hence, Section 2.7 could be omitted if the reader is not specifically interested in inverses.
Section 2.6 is the key section because the row operations used there are the same as those needed later in the simplex algorithm.
Section 2.5 is important later because of the linearly independent set of vectors corresponding to each basic solution in the simplex algorithm. We take advantage of the discussion of linear independence to discuss some basic mathematical reasoning which should be understood by any student who has studied mathematics. These ideas are then used in proving several propositions concerning linear independence.
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 therefore of particular importance to those most motivated by applications. Section 3.6 extends the simplex algorithm to problems with nonstandard constraints. Section 3.7 discusses the solution of minimization problems by using an associated maximization problem. Example 3.7.8 illustrates some of the power of linear programming as a managerial tool, and helps to motivate the coming discussion of sensitivity analysis in Section 3.8.
Chapter 4 treats four network problems: the transportation problem, the critical path method, the shortest path problem, and minimal spanning trees. Sample models in LINGO or 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 5: Unconstrained Extrema
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.
Chapter 6: Constrained Extrema
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 7: Integer Programming
Integer programming is introduced after first discussing the dual simplex algorithm. The dual simplex algorithm is needed to facilitate the addition of a constraint to a linear program for which an optimal solution has been obtained without having to resolve the problem. This then forms the basis of a branch-and-bound approach to solving integer programs. The chapter considers the knapsack problem to introduce the branch-and-bound method, and then develops a general branch-and-bound algorithm. A variety of integer programming models is then discussed, and the chapter concludes with an approach to the traveling salesman problem.
Chapter 8: Introduction to Dynamic Programming
Certain problems to which a solution can be defined through a succession of steps are approachable by dynamic programming. The first example is the longest path problem, which is quite similar to the determination of earliest times in the CPM method. We then consider two extensions of problems considered earlier--the fixed cost transportation problem and a variation of the knapsack problem called the cargo loading problem. We also return to the traveling salesman problem and indicate some of the computational challenge of such problems. Dynamic programming relies on recursion, so it is necessary to introduce some of the key ideas associated with recursive functions. This leads the reader on a brief excursion through the Towers of Hanoi, Fibonacci numbers, and the binomial expansion.
Chapter 9 presents several more open-ended problems suitable for longer assignments and possibly group projects. Solutions to the cases and suggestions for their class use are available for instructors.
Appendix A: Introductions to LINDO and LINGO
The linear programming package LINDO is extremely useful in solving the linear programs formulated in Chapter 3 as well as the integer programming models of Chapter 7 and the critical path problems of Section 4.3. Examples of its use are presented here along with the use of the basic commands. Other examples of the use of LINDO can be found in Sections 3.5, 3.8, 4.3, 7.1, and 9.1.
Appendix A also contains a brief introduction to LINGO, a related package allowing the solution of nonlinear problems. As a modeling language, LINGO is particularly useful for its ability to efficiently express problems with repetitive constraints. Examples of its use can be found in Section 4.3 in conjunction with critical paths and in Section 4.5 where it is used to determine a minimal spanning tree. It is also used in Chapter 6 in conjunction with nonlinear optimization.
Student versions of LINDO and LINGO for Windows can be downloaded from the LINDO Systems Home Page.
Appendix B: Introduction to Maple
The symbolic computation package 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. Maple is also briefly introduced in Sections 2.7, 5.4, and 5.6.
For more information on Maple, go to the Waterloo Maple Home Page.
Appendix C: Introduction to Texas Instruments Graphing Calculators
A calculator can be of great value in some of the problems to be considered. Solving an equation to determine a critical point is an obvious example. Less obvious are curve fitting discussed in Section 5.5 and dynamic programming in Chapter 9. This appendix provides brief introductions to the TI-82 and TI-92 and their use for such applications. A sample program to solve a cargo loading problem is included.
For additional information on these and other calculator models from Texas Instruments, go to the Texas Instruments site.
Appendix D: Selected Answers and Hints
The answers to many of the problems, chiefly the odd ones, are provided here. In some cases a hint is provided instead of the answer. While it is useful to have answers to some of the problems, students should also seek to develop their ability to monitor the correctness of their own work.
Solutions to the Chapter 9 Cases
The cases in Chapter 9 are designed to give the student a richer problem soliving experience than is provided in the exercises at the end of sections. This supplement provides detailed solutions to all eight cases. Each solution involves the use of software. LINDO, LINGO, and Maple are all used. This supplement for adopters of the text is available from Prentice Hall.
Compound interest is not a normal topic for inclusion in a text on mathematical programming, but on the other hand, managers can scarcely ignore the notion of compound interest. The financial aspects of some of the problems considered in other chapters are explored here. The reader should note that this material is also critical to one's personal financial affairs since nearly everyone borrows and invests money. This supplement is available from the author, or a printer ready postscript version can be downloaded in the two files below.
Cover page and table of contents. (58K)
Compound Interest Chapter. (457K)