INTRODUCTION TO LINEAR PROGRAMMING

By -
The development of linear programming has been ranked among the most important scientific advances of the mid-20th century, and we must agree with this assessment.

Its impact since just 1950 has been extraordinary. Today it is a standard tool that has saved many thousands or millions of dollars for many companies or businesses of even moder- ate size in the various industrialized countries of the world, and its use in other sectors of society has been spreading rapidly. A major proportion of all scientific computation on computers is devoted to the use of linear programming. Dozens of textbooks have been written about linear programming, and published articles describing important applica- tions now number in the hundreds.

What is the nature of this remarkable tool, and what kinds of problems does it address? You will gain insight into this topic as you work through subsequent examples. However, a verbal summary may help provide perspective. Briefly, the most common type of application involves the general problem of allocating limited resources among competing activities in a best possible (i.e., optimal) way. More precisely, this problem involves selecting the level of certain activities that compete for scarce resources that are necessary to perform those activities. The choice of activity levels then dictates how much of each resource will be consumed by each activity. The variety of situations to which this description applies is diverse, indeed, ranging from the allocation of production facilities to products to the allocation of national resources to domestic needs, from portfolio selection to the selection of shipping patterns, from agricultural planning to the design of radiation therapy, and so on. However, the one common ingredient in each of these situations is the necessity for allocating resources to activities by choosing the levels of those activities.

Linear programming uses a mathematical model to describe the problem of concern. The adjective linear means that all the mathematical functions in this model are required to be linear functions. The word programming does not refer here to computer programming; rather, it is essentially a synonym for planning. Thus, linear programming involves the planning of activities to obtain an optimal result, i.e., a result that reaches the specified goal best (according to the mathematical model) among all feasible alternatives.

Although allocating resources to activities is the most common type of application, linear programming has numerous other important applications as well. In fact, any prob- lem whose mathematical model fits the very general format for the linear programming model is a linear programming problem. (For this reason, a linear programming problem and its model often are referred to interchangeably as simply a linear program, or even as just an LP.) Furthermore, a remarkably efficient solution procedure, called the simplex method, is available for solving linear programming problems of even enormous size. These are some of the reasons for the tremendous impact of linear programming in recent decades.

Because of its great importance, we devote this and the next seven chapters specifically to linear programming. After this chapter introduces the general features of linear program- ming, Chaps. 4 and 5 focus on the simplex method. Chapters 6 and 7 discuss the further analysis of linear programming problems after the simplex method has been initially applied. Chapter 8 presents several widely used extensions of the simplex method and introduces an interior-point algorithm that sometimes can be used to solve even larger linear programming problems than the simplex method can handle. Chapters 9 and 10 consider some special types of linear programming problems whose importance warrants individual study.

You also can look forward to seeing applications of linear programming to other areas of operations research (OR) in several later chapters.

We begin this chapter by developing a miniature prototype example of a linear pro- gramming problem. This example is small enough to be solved graphically in a straight- forward way. Sections 3.2 and 3.3 present the general linear programming model and its basic assumptions. Section 3.4 gives some additional examples of linear programming applications. Section 3.5 describes how linear programming models of modest size can be conveniently displayed and solved on a spreadsheet. However, some linear programming problems encountered in practice require truly massive models. Section 3.6 illustrates how a massive model can arise and how it can still be formulated successfully with the help of a special modeling language such as MPL (its formulation is described in this section) or LINGO (its formulation of this model is presented in Supplement 2 to this chapter on the book’s website).

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more