| 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. 127
Section 3.9 Summary and objectives p. 140
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. 143
Section 4.2 The dual and minimizing problems p. 144
Section 4.3 Sensitivity analysis p. 165
Section 4.4 The matrix setting for the simplex algorithm p. 183
Section 4.5 Adding a variable p. 189
Section 4.6 Summary and objectives p. 195
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. 195
Section 5.2 The transportation problem p. 203
Section 5.3 The critical path method p. 225
Section 5.4 Shortest path models p. 248
Section 5.5 Minimal spanning trees p. 255
Section 5.6 The maximum flow problem p. 270
Section 5.7 Summary and objectives p. 276
Chapter 5 treats five network problems: the transportation problem, the critical
path method, the shortest path problem, minimal spanning trees, and maximum flow.
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 6 Unconstrained Extrema
Section 6.1 Introduction p. 280
Section 6.2 Locating extrema p. 281
Section 6.3 The economic lot size model and convexity p. 287
Section 6.4 Location of extrema in two variables p. 300
Section 6.5 Least squares approximation p. 310
Section 6.6 The n-variable case p. 316
Section 6.7 Numerical search p. 322
Section 6.8 Summary and objectives p. 330
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. 332
Section 7.2 Two variable problems p. 339
Section 7.3 More variables; more constraints p. 345
Section 7.4 Problems having inequality constraints p. 355
Section 7.5 The convex programming problem p. 365
Section 7.6 Linear programming revisited p. 382
Section 7.7 Summary and objectives p. 385
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. 387
Section 8.2 The knapsack problem p. 390
Section 8.3 The dual simplex algorithm p. 399
Section 8.4 Adding a constraint p. 408
Section 8.5 Branch and bound for integer programs: p. 415
Section 8.6 Basic integer programming models p. 422
Section 8.7 The traveling salesman problem p. 440
Section 8.8 Summary and objectives p. 454
The knapsack problem is considered first to introduce
the branch-and-bound method. 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.
A variety of integer programming models is then discussed, and the chapter concludes
with an approach to the traveling salesman problem.
| |
| Chapter 9 Introduction to Dynamic Programming
Section 9.1 Introduction to recursion p. 456
Section 9.2 The longest path p. 464
Section 9.3 A fixed cost transportation problem p. 467
Section 9.4 More examples p. 472
Section 9.5 Summary and objectives p. 479
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. 482
Section 10.2 A furniture sales opportunity p. 489
Section 10.3 Building storage lockers p. 490
Section 10.4 The McIntire farm p. 491
Section 10.5 Cylinders for beverages p. 492
Section 10.6 Books by the holidays p. 494
Section 10.7 Into a blind trust p. 496
Section 10.8 Max's taxes p. 497
Section 10.9 A supply network p. 498
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.
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. 500
Section A.2 LINGO p. 505
The LINDO program is extremely useful in solving
linear programs as well as integer programs. 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. 510
Section B,2 Using packages p. 514
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.
| |
| Appendix C Using Excel Solver
Section C.1 A basic example p. 522
Section C.2 Two network examples p. 528
Section C.3 Two nonlinear examples p. 532
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 are provided.
| |
| Appendix D Selected Answers and Hints
| The answers to all odd problems are provided here. Solutions to the even numbered problems are available from the
author. |
| References
|
| Index
|
