Network Optimization Models

By -

Networks arise in numerous settings and in a variety of guises. Transportation, electrical, and communication networks pervade our daily lives. Network representations also are widely used for problems in such diverse areas as production, distribution, project planning, facilities location, resource management, supply chain management and financial planning— to name just a few examples. In fact, a network representation provides such a powerful visual and conceptual aid for portraying the relationships between the components of systemsthat it is used in virtually every field of scientific, social, and economic endeavor.

One of the most exciting developments in operations research (OR) in recent decades, has been the unusually rapid advance in both the methodology and application of network optimization models. A number of algorithmic breakthroughs have had a major impact, as have ideas from computer science concerning data structures and efficient data manipulation. Consequently, algorithms and software now are available and are being used to solve huge problems on a routine basis that would have been completely intractable three decades ago.

Many network optimization models actually are special types of linear programming problems. For example, both the transportation problem and the assignment problem dis- cussed in the preceding chapter fall into this category because of their network representations presented in Figs. 9.3 and 9.5.

One of the linear programming examples presented in Sec. 3.4 also is a network optimization problem. This is the Distribution Unlimited Co. problem of how to distribute its goods through the distribution network shown in Fig. 3.13. This special type of linear programming problem, called the minimum cost flow problem, is presented in Sec. 10.6. We shall return to this specific example in that section and then solve it with network methodology in the following section.

In this one chapter we only scratch the surface of the current state of the art of net- work methodology. However, we shall introduce you to five important kinds of network problems and some basic ideas of how to solve them (without delving into issues of data structures that are so vital to successful large-scale implementations). Each of the first three problem types—the shortest-path problem, the minimum spanning tree problem, and the maximum flow problem—has a very specific structure that arises frequently in applications.

The fourth type—the minimum cost flow problem—provides a unified approach to many other applications because of its far more general structure. In fact, this structure is so general that it includes as special cases both the shortest-path problem and the maxi- mum flow problem as well as the transportation problem and the assignment problem from

Chap. 9. Because the minimum cost flow problem is a special type of linear programming problem, it can be solved extremely efficiently by a streamlined version of the simplex method called the network simplex method. (We shall not discuss even more general network problems that are more difficult to solve.)

The fifth kind of network problem considered here involves determining the most economical way to conduct a project so that it can be completed by its deadline. A technique called the CPM method of time-cost trade-offs is used to formulate a network model of the project and the time-cost trade-offs for its activities. Either marginal cost analysis or linear programming then is used to solve for the optimal project plan.

The first section introduces a prototype example that will be used subsequently to illustrate the approach to the first three of the problem types mentioned above. Section 10.2 presents some basic terminology for networks. The next four sections deal with the first four problem types in turn, and Sec. 10.7 then is devoted to the network simplex method. Section 10.8 presents the CPM method of time-cost trade-offs for project management. (Chapter 22 on the website also uses network models to deal with a variety of project management problems.)

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