Introduction to Mathematical Programming (English Version)

Author: (American) Walker
Publisher:
Publish Date: 2005-06-01
Features:
Introduction This textbook is designed for business administration students. Readers should have a mathematical background and a strong interest in knowledge beyond just applications. After completing a calculus course equivalent to that for science and engineering majors, students can read this book. Learning this book only requires readers to understand differential calculus, and the key principles of calculus used in optimization are 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, etc.). For solving many of the problems in the book, software can be used to improve efficiency. Several examples of using optimization software packages LINDO and LINGO are provided in a few chapters and Appendix A. In the chapters related to vectors and matrices and nonlinear optimization, the symbolic mathematics software package Maple is also used. Appendix B introduces Maple and explains how to use it for curve fitting, network problem solving, and solving linear programming problems. Appendix C introduces the Texas Instruments graphing calculator software 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 very 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, it is undoubtedly beneficial to understand the underlying ideas when working with or supervising others who are involved in problem analysis. Therefore, 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 gain 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 whose interest is solely in applications, they are worth mentioning and discussing in detail for instructors who plan to focus on the mathematical aspects of the course. Below is an overview of each chapter, highlighting both key applications and mathematical focuses.
Chapter 1: Introduction to Problems This chapter provides an overview of the types of problems, presenting 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 certain issues related to model representation. The final section introduces a graphical method for solving two-variable linear programming, which introduces a key management tool and promotes 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 of this chapter based on their objectives. For example, matrix inversion is discussed in two places: Section 2.4 briefly describes 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 in it 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, which any 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: the transportation problem, the critical path problem, the shortest path problem, and the minimum spanning tree problem. This chapter provides sampling models used in LINGO and LINDO. The discussion of the shortest path and minimum spanning tree requires some basic knowledge of graph theory. This chapter also discusses the effectiveness and correctness of algorithms and provides a discussion of the minimum spanning tree algorithm.
Chapter 5: Unconstrained Optimization This chapter discusses classical optimization techniques, which require some knowledge of differential calculus. The convexity related to economic order quantity problems and inventory management is discussed. Section 5.5 is dedicated 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 desirable returns with minimal 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 solve them, the dual simplex algorithm is used to add constraints, which constitutes the branch and bound method for solving integer programming. 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, and the chapter concludes 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 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 models from Chapter 3, integer programming models from Chapter 7, and the critical path problem from Section 4.3. This appendix introduces the examples used and the usage of basic commands. Examples of using LINDO can be 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 can be found in Sections 4.3 and 4.5, where Section 4.3 is used for solving the critical path problem and Section 4.5 for determining the minimum spanning tree. LINGO is also used in Chapter 6 for solving nonlinear optimization problems.
Appendix B: Introduction to Maple The symbolic computation software package Maple is very useful, especially for solving classical optimization problems such as those introduced in Chapters 5 and 6, as well as matrix computations, curve fitting, solving linear programming problems, and network models. Brief introductions to Maple can also be found in Sections 2.7, 5.4, and 5.6.
Appendix C: Introduction to Texas Instruments Graphing Calculator For certain problems, this may be a valuable computational tool. A significant example is solving an equation to determine a critical point, and the second example is curve fitting discussed in Section 5.5 and dynamic programming in Chapter 9. This appendix briefly introduces the TI-82 and TI-92 and their usage in such applications, including a sample program for solving the 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 the 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 calculus is supplemented from another textbook. 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 and typically includes most of Chapters 1, 3 (with only a brief mention of Section 3.4), most of Chapter 4, and most of Sections 7.1, 7.2, 7.6, and 7.7. For instructors interested in the connection between mathematics and applications, it is helpful to spend some time teaching basic 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 also used when discussing trees in Section 4.5. Additionally, algorithmic effectiveness and correctness are discussed in Sections 4.4 and 4.5; Sections 5 and 6 include several proofs of convexity and an introduction; and Section 8.1 introduces recursion, combinations, permutations, and binomial expansions. Instructors focusing on algorithmic research should emphasize Sections 3.4, 4.4, and 4.5, as mentioned above, while also focusing on 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 the dynamic programming method for the traveling salesman problem in Section 8.4 should be taught.
Chapter Summaries Each chapter summary lists 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 cover a specific set of 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 multiple ways to select course content. 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 foundations 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 basic core. Chapter 4 covers network models and can be discussed after the basic core material on linear programming. Due to the presence of equality constraints and duality, the material in Sections 3.6 and 3.7 is particularly important.
Chapters 5 and 6 discuss classical nonlinear optimization, which is largely unrelated to any previous material, although the concepts of constrained optimization and feasible solutions introduced in the discussion of linear programming are certainly beneficial. Knowledge of differential calculus also forms the foundation for these two chapters.
Chapter 7 discusses integer programming, and several approaches can be adopted 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 that are only interested in representing problems and rely on software packages for solutions, Sections 7.3–7.5, which discuss 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 in previous chapters. 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, reading Chapters 3 and 4 and having the ability to use linear programming software packages are sufficient.
Web Site On the author's website at http://www.math.cmu.edu/rwlk/, supplementary information for this book is provided, including data files for some exercises and various links helpful to readers.
This book provides the necessary background knowledge 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 the symbolic software package Maple in vector and matrix operations and nonlinear optimization, curve fitting using Maple, solving network and linear programming problems, examples of applying optimization software packages LINDO and LINGO, and the use of Texas Instruments graphing calculator software 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.
Features● Includes examples of using optimization software packages LINDO and LINGO.
● Introduces Texas Instruments graphing calculator software 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.