Introduction to Mathematical Programming - English Version

Author: Russell C. Walker
Publisher:
Publish Date: 2005-06-01
Features: Introduction This textbook is designed for business administration students and assumes a background in mathematics. Readers should have a strong interest in knowledge beyond mere application. Students who have completed a calculus course equivalent to that for science and engineering majors can read this book. Only a basic understanding of differential calculus is required for this book, with key principles of calculus used in optimization reviewed in Chapter 5. The background knowledge of vectors and matrices needed is introduced in Chapter 2. This book contains enough material for a two-semester course and can be used as a textbook for various courses (e.g., linear programming, optimization, quantitative management methods, or operations research). Software can be used to enhance efficiency in solving many of the problems in this book. Examples of using optimization software packages LINDO and LINGO are provided in several chapters and Appendix A. Symbolic mathematics software package Maple is also used in chapters related to vectors and matrices and nonlinear optimization. Appendix B introduces Maple and explains how to use it in curve fitting, network problem solving, and solving linear programming problems. Appendix C introduces Texas Instruments graphing calculators TI-82 and TI-92.
Objectives The primary objective of this book is to provide the necessary background knowledge for beginning to use mathematical programming as a tool. Although the main focus is on management applications, it can be demonstrated that mathematical methods are useful in many fields. The key step is to make people recognize that mathematical models are accepted when they may be useful. Even for those who do not intend to use mathematical programming themselves, understanding the underlying ideas is undoubtedly beneficial when working with or supervising others who engage in problem analysis. Thus, the ultimate goal is to identify the potential of the various methods introduced, delve deeper into them, and enhance the ability to apply them. The second objective of this book is to provide an understanding and familiarity with mathematical methods related to applied techniques. This refers to certain proofs and occasionally involves topics such as basic graph theory, linear algebra, mathematical analysis, algorithmic properties, and combinatorics. While these subsidiary topics may be ignored by those interested only in applications, they are worth mentioning and discussing in detail for instructors who plan to focus on the mathematical aspects of the course. The following overview of each chapter explains the key applications and mathematical highlights.
Chapter 1: Introduction to Problems This chapter provides an overview of problem types, introducing possible applications and the tools studied from an early perspective. In some cases, the key to solving a problem for an organization lies in identifying the relationship between these techniques. Section 3 introduces the linear structures considered in most models and some issues related to model representation. The final section introduces a graphical method for solving two-variable linear programming, introducing a key management tool and promoting the study of algebraic methods for solving multivariable problems.
Chapter 2: Vectors and Matrices This chapter introduces the concepts needed to handle linear problems and serves two purposes. First, it covers the prerequisite knowledge for learning linear programming; second, it provides an independent introduction to matrix algebra. Students or instructors can skip certain sections based on their objectives. For example, matrix inversion is discussed in two places: Section 2.4 briefly discusses the inversion of 2×2 matrices, while Section 2.7 provides a more detailed discussion of n×n matrices. Outside of Chapter 2, matrix inversion is only needed in Exercise 3.3. Therefore, readers who are not particularly interested in matrix inversion can skip Section 2.7. Section 2.6 is an important one because the row operations used there are also needed in the simplex algorithm discussed later. Section 2.5 is also important because the set of linearly independent vectors corresponds to each basic solution in the simplex algorithm. We use the discussion of linear independence to explore some basic mathematical reasoning that every student learning mathematics should understand. These ideas are then used to prove several propositions involving linear independence.
Chapter 3: Linear Programming The central theme of this chapter is linear programming. Sections 3.2 and 3.3 discuss the simplex algorithm. Section 3.4 proves the correctness of the simplex algorithm. Section 3.5 discusses the formulation of problems, which is particularly important for most problems that arise from applications. Section 3.6 extends the simplex algorithm to problems with non-standard constraints. Section 3.7 discusses the solution of minimization problems, where a related maximization problem is used. Example 3.7.8 illustrates the ability of linear programming as a management tool and helps introduce the discussion of sensitivity analysis in Section 3.8.
Chapter 4: Network Models This chapter covers four network problems: transportation problems, critical path problems, shortest path problems, and minimum spanning tree problems. This chapter provides sampling models used in LINGO and LINDO. The discussion of shortest paths and minimum spanning trees requires some basic knowledge of graph theory. This chapter also discusses the effectiveness and correctness of algorithms, with a discussion of the minimum spanning tree algorithm.
Chapter 5: Unconstrained Optimization This chapter discusses classical optimization techniques, requiring some knowledge of differential calculus. The convexity related to economic order quantity problems and inventory management is discussed. Section 5.5 is devoted to the application of least squares curve fitting. The theoretical foundations of optimization are discussed, and Maple is introduced for solving optimization problems.
Chapter 6: Constrained Optimization This chapter extends the discussion from the previous chapter to problems where solutions are constrained. The key theorem for solving convex problems is the Karush-Kuhn-Tucker theorem. The main applications introduced in this chapter include minimizing the cost of a card box, maximizing utility, minimizing equipment replacement costs, and selecting an investment portfolio to achieve attractive returns with low risk. The chapter concludes with a review of linear programming, treating it as a special case of convex programming.
Chapter 7: Integer Programming After discussing the dual simplex algorithm, integer programming is introduced. For linear programming problems that already have an optimal solution without needing to be solved, the dual simplex algorithm is used to add constraints, forming the branch and bound method for solving integer programming problems. This chapter considers the knapsack problem to introduce the branch and bound method, then proposes the general branch and bound algorithm. Next, various integer programming models are discussed, concluding with a method for solving the traveling salesman problem.
Chapter 8: Introduction to Dynamic Programming The solutions to certain problems can be defined by a series of reachable operational steps using dynamic programming. The first example introduced is the longest path problem, which is very similar to the earliest time determined in the critical path method (CPM). Two extended problems are then considered: the fixed-charge transportation problem and the cargo loading problem derived from the knapsack problem. We return to the traveling salesman problem and highlight some computational challenges posed by such problems. Dynamic programming relies on recursion, so the main ideas related to recursive functions need to be introduced. This briefly introduces readers to the Towers of Hanoi, Fibonacci numbers, and binomial expansions.
Chapter 9: Case Studies This chapter introduces several problems that are far from being solved, suitable for longer assignments and group projects. Instructors can obtain solutions to the cases and hints for classroom use.
Appendix A: Introduction to LINGO and LINDO The linear programming software package LINDO is extremely useful for solving linear programming problems introduced in Chapter 3, integer programming models in Chapter 7, and the critical path problem in Section 4.3. This appendix introduces the examples used and the usage of basic commands. Examples of using LINDO are found in Sections 3.5, 3.8, 4.3, 7.1, and 9.1. This appendix also provides a brief introduction to LINGO, a software package for solving nonlinear problems. As a modeling language, LINGO is particularly useful for effectively representing problems with repetitive constraints. Examples of using LINGO are found in Sections 4.3 and 4.5, where Section 4.3 is used to solve the critical path problem and Section 4.5 to determine the minimum spanning tree. LINGO is also used in Chapter 6 to solve nonlinear optimization problems.
Appendix B: Introduction to Maple The symbolic computation software package Maple is very useful, especially for solving classical optimization problems introduced in Chapters 5 and 6, as well as matrix computations, curve fitting, solving linear programming problems, and network models. Brief introductions to Maple are also found in Sections 2.7, 5.4, and 5.6.
Appendix C: Introduction to Texas Instruments Graphing Calculators For certain problems, this may be the most valuable computational software. A significant example is solving an equation to determine critical points, and the second example is curve fitting discussed in Section 5.5 and dynamic programming in Chapter 9. This appendix provides a brief introduction to TI-82, TI-92, and their usage in such applications, including a sample program for solving the cargo loading problem.
Appendix D: Selected Solutions and Hints This appendix provides answers to many exercises, primarily for odd-numbered problems. For some exercises, only hints are given without answers. While solutions to some exercises are useful, students should still strive to verify the correctness of their own solutions.
Suggestions for Instructors At Carnegie Mellon University, a course in mathematical methods for business majors has been changed from a calculus course for science and engineering majors, with a focus on business and economic applications. Therefore, Chapters 2 and the topics in Chapters 5 and 6 are placed in the next course for business majors, where additional calculus material is supplemented. The second course also discusses compound interest calculations, laying the mathematical foundation for future work in statistics and economics. The third course is application-oriented, typically including most of Chapters 1, 3 (with only a brief mention of Section 3.4), most of Chapter 4, and parts of Sections 7.1, 7.2, 7.6, and 7.7. For instructors interested in the connection between mathematics and applications, some time should be spent teaching mathematical reasoning methods and their application in the discussion of linear independence in Section 2.5. Subsequently, the indirect proof method used in the discussion of extreme points and basic solutions in Section 3.4 is taught, which is again used when discussing trees in Section 4.5. Additionally, algorithmic effectiveness and correctness are discussed in Sections 4.4 and 4.5; convexity proofs and an introduction are included in Chapters 5 and 6; and recursion, combinations, permutations, and binomial expansions are introduced in Section 8.1. Instructors focusing on algorithmic research should emphasize Sections 3.4, 4.4, and 4.5, as mentioned above, while paying attention to the branch and bound method introduced in Sections 7.2–7.5 and 7.7. Additionally, the dual simplex algorithm discussed in Section 7.3 and the analysis of dynamic programming methods for the traveling salesman problem in Section 8.4 should be taught.
Chapter Summaries Each chapter provides a list of specific learning objectives. For most objectives, an illustrative example and a typical exercise are provided. This makes it very simple to describe the content of exams. It is clear that exams will include a set of specific objectives.
Dependencies Between Topics The topics in each chapter are organized in such a way that later topics are largely independent of earlier ones, allowing for various course content selections. The only fundamental topic is linear programming. To guide the selection of topics from this textbook, we first identify linear programming as the fundamental topic and then discuss the material needed for each subsequent topic. A basic introduction to linear programming should include some material from the first three sections of Chapter 1 to understand the methods and scope of application discussed in the book. Then Section 4 introduces graphical solution methods. To transition to the simplex algorithm, Sections 2.4–2.6 of Chapter 2 are needed. For courses that do not focus on the mathematical foundation of the methods, most of the section on linear independence can be omitted. Chapter 3 covers the basics of linear programming. If the simplex algorithm is not to be validated, Section 3.4 can be omitted. In Section 3.5, LINDO is first used to solve a linear programming problem. In subsequent discussions, we will consider Sections 1.2–1.4, 2.4–2.6, and 3.1–3.7 as the core material. Chapter 4 covers network models and can be discussed after the basic core material on linear programming. The material in Sections 3.6 and 3.7 is particularly important due to equality constraints and duality. The discussion of classical nonlinear optimization in Chapters 5 and 6 is largely unrelated to any previous material, although the concepts of constrained optimization and feasible solutions introduced in the linear programming discussion are certainly beneficial. A background in differential calculus is also essential for these chapters.
Chapter 7 discusses integer programming, and several approaches can be used when selecting topics. In addition to the basic core material, it is helpful to first teach Sections 4.1 and 4.2, which introduce networks and use the transportation algorithm as an example, where the integer values of variables are automatically generated. One approach is to consider only the knapsack problem and the traveling salesman problem. For courses interested only in problem representation and relying on software packages for solutions, Sections 7.3–7.5 on the branch and bound process can be omitted. Teaching the entire Chapter 7 provides an introduction to both models and solution processes.
Chapter 8 reviews the models established from a dynamic perspective. This chapter is based on the transportation problem discussed in Section 4.2, the knapsack problem discussed in Section 7.2, and the traveling salesman problem discussed in Section 7.7.
Chapter 9 introduces case studies that require different background knowledge, although for most people, having read Chapters 3 and 4 and having the ability to use linear programming software packages is sufficient.
Web Site Additional information about this book is provided on the author's website at http://www.math.cmu.edu/rwlk/. This includes data files for some exercises and various links helpful to readers.
Features of the Book This book provides the background knowledge necessary for using mathematical programming as a tool and discusses mathematical methods related to applied techniques. It covers linear programming, integer programming, dynamic programming, classical optimization techniques, the application of symbolic software package Maple in vector and matrix operations and nonlinear optimization, curve fitting using Maple, solving network and linear programming problems, examples of using optimization software packages LINDO and LINGO, and the use of Texas Instruments graphing calculators TI-82 and TI-92. This book is suitable as a textbook for majors in management science and operations research, as well as for MBA programs.
Book Features
● Includes examples of using optimization software packages LINDO and LINGO.
● Introduces Texas Instruments graphing calculators TI-82 and TI-92.
● Contains a large number of examples and exercises to help deepen readers' understanding of mathematical programming.
● Provides solutions to many currently challenging problems.