Catálogo de publicaciones - libros

The purpose of this chapter is to introduce to the reader the basic concepts of linear algebra whose knowledge is mandatory for the understanding of the material covered in the succeeding chapters. We have taken it out of the main part of the book so as not to interrupt the flow of our arguments and to let those who are familiar with the concepts discussed here, skip them and jump ahead to the Introduction in Chapter 1. With some modifications, the material in this Chapter is largely taken from Eiselt and Sandblom (2004). For a full treatment, see any text on linear algebra, e.g., Bretscher (1997) or Nicholson (2006).

Solving a mathematical problem will require calculations. Whether such calculations are performed manually or on a computer, we will be interested in the effort it will take to perform these calculations. Since the days of the abacus, the slide rule, and the mechanical calculating machine, our ability to handle vast amounts of calculations has developed to an extraordinary extent. However, at the same time, the need for ever more complex and large-scale computations has soared, at times outperforming the increase of computational capability. It is therefore interesting to study the science of how much calculation effort our numerical problems require. This is the topic of this chapter. The treatment in this chapter is based on material from Eiselt and Sandblom (2000). For an original and comprehensive treatment of computational complexity, readers are referred to the classical book by Garey and Johnson (1979).

This chapter will first outline some of the major developments that have led to the field that is now known as linear programming. We will then summarize the structure and the main assumptions made in linear programming. The third section describes the modeling process in some detail. Section 4 discusses the main three phases in optimization, and the last section in this chapter solves a small linear programming problem and interprets a computer printout.

This chapter will provide a number of classes of applications of linear programming problems. We should note that these are mere sample problems that are designed to give readers a flavor of the application, rather than a model that includes all of the bells and whistles usually found in real applications. We have already discussed an example of the first large class of applications in the Introduction, , production problems. Readers may recall that the simple model formulated in the introduction has its decision variables defined in terms of the number of quantity units of a product that are made and sold. Much more frequently, such variables will have to be decomposed into variables that measure the number of units that are made, while other variables express the number of units that are sold, with the unsold units being left in inventory. A sizeable production — inventory problem is presented as a mini case study in Section 10 of this Chapter.

Being not only the traditional and best-known method but also the standard solution technique for the solution of linear programming problems, we devote this chapter entirely to the simplex method.

Linear programming is based on the theory of duality. In essence, to each linear programming problem P, we can assign a linear programming problem PD. This chapter formulates and discusses number of relations between the primal and dual problems that are not only essential to establish optimality conditions, but also provide insight into the problems and a meaningful economic interpretation of the optimization model. In particular, post optimality analyses depend almost entirely on the understanding of duality.

This chapter will introduce a number of extensions to the standard (primal) simplex method discussed in Chapter 3 of this volume. The first section introduces a technique that allows variables to be constraint by upper bounds without introducing these bounds in the tableau explicitly, thus keeping the tableaus small. The second section describes the column-generation technique, another method that has proven to be an invaluable tool for large-scale problem. Finally, the chapter concludes with the description of the dual simplex method, a technique that works on the primal problem but proceeds differently from the primal simplex method, in that it retains dual feasibility at all times, while trying to achieve primal feasibility. This technique is used extensively in integer programming as well as in methods that add constraints during the solution process.

As discussed in Chapter 1 of this volume, one of the assumptions in linear programming is that all parameters are deterministic, i.e., assumed to be known with certainty. Clearly, this assumption will rarely be satisfied in practice. One popular way to get around the problem, i.e., dealing with uncertainty while keeping the simple structure and efficient solution methods of linear programming, are sensitivity analyses. In essence, sensitivity (sometimes also called “what...if?”) analyses deal with the effects of parameter changes on the optimal solution. Typical examples include analyses regarding the effects of price changes on a cutting plan, changes in the demand structure on the allocation of resources, and technological changes (such as faster throughputs in some machines) on a production schedule.

So far, we have concentrated on the simplex method as the solution technique of choice for linear programming problems. While being extremely successful in practice for the last half century, the simplex method is by no means the only solution method for linear programming. Interestingly enough, the first alternative solution technique to the simplex method, a method by Brown and Koopmans (1951), was published in the same volume in which Dantzig presented his simplex method in 1951.

This section investigates a number of scenarios that do not obviously fall into the realm of linear programming. These include specifications of variables, types of constraints, and objective functions that differ from the linear programming formulations in standard and canonical form as defined in Chapter 3.2. This chapter is divided into three sections. The first (short) section discusses that do not fit into the standard and canonical forms, the second section deals with , and the third, and arguably most important, section considers a number of that do not appear to lend themselves to linear programming.