Network Optimization Models

Chapter 8Network Optimization ModelsPart 2 Deterministic Decision ModelsLearning ObjectivesState why network models are important tools for problem solving.Describe the kinds of problems that can be solved using the shortest-route algorithm and use the algorithm to solve typical shortest-route problems.Formulate the shortest-route problem as a linear programming problem.Solve the shortest-route problem using Excel.After completing this chapter, you should be able to:2Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Learning Objectives (cont’d)Describe the kinds of problems that can be solved using the minimal-spanning-tree algorithm and use the algorithm to solve typical minimal-spanning-tree problems.Describe the kinds of problems that can be solved using the maximal-flow algorithm and use the algorithm to solve typical maximal-flow problems.Formulate the maximal-flow problem as a linear programming problem.Solve the maximal-flow problem using Excel.After completing this chapter, you should be able to:3Copyright © 2007 The McGraw-Hill Companies. All rights reserved. NetworksNetworkA set of nodes and connecting arcs or branches. Can be useful in representing various systems, such as distribution systems, production systems, and transportation systems.Network models are an important approach for problem solving because:They can be used to model a wide range of problems.They are relatively simple to work withThey provide a visual portrayal of a problem.4Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Frequently Used AlgorithmsShortest-Route AlgorithmUsed for determining the shortest time, distance, or cost from an origin to a destination through a network.Minimum Spanning Tree AlgorithmUsed in determining the minimum distance (cost, time) needed to connect a set of locations into a single system.Maximal Flow AlgorithmUsed for determining the greatest amount of flow that can be transmitted through a system in which various branches, or connections, have specified flow capacity limitations.5Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–1 A Simple Network Diagram6Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-1Labeling ProcedureA label is developed for each node. The labels consist of two numbers separated by a comma: The first number refers to the distance from Node 1 to the labeled node along a certain path, while the second number refers to the node that immediately precedes this node along that path.7Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-1 (cont’d)8Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-1 (cont’d)9Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–2 Network for Tri-State Shipping Company Shortest-RouteProblem10Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8-1 Input Worksheet for the Tri-State Shipping Company Shortest-Route Problem (Beginning Node 1, Ending Node 7)11Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8-2 Parameter Specification Screen for the Tri-State Shipping Company Shortest-Route Problem (Beginning Node 1, Ending Node 7)12Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–3 Output Worksheet for the Tri-State Shipping CompanyShortest-Route Problem (Beginning Node 1, Ending Node 7)X13Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–4 Output Worksheet for the Tri-State Shipping CompanyShortest-Route Problem (Beginning Node 1, Ending Node 6)14Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–5 Parameter Specification Screen for the Tri-State Shipping Company Shortest-Route Problem (Beginning Node 1, Ending Node 6)15Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–3 Network for Oil Pipeline ProblemNote: Arc lengths are not precisely proportional to the distances shown on the arcs.16Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-317Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-3 (cont’d)18Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Example 8-3 (cont’d)19Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–4 A Flow Network20Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–5 Updated Flow Network21Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–6 Second Revision of the Network22Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–7 Third Revision of Flow Network23Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–8 Final Solution for Flow Network Example24Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–9 Flow Network for Demonstration of Reverse Flow25Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–10 Flow Network for Demonstration of Reverse Flow26Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–11 Revised Flow Network27Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 8–1 Branches of the Network and Flow Capacities of the Branches for the Turkmen Oil Ltd. Maximal Flow Problem28Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Figure 8–12 Network Diagram for the Maximal Flow Problem for TurkmenOil Ltd.29Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–6 Input Worksheet for the Turkmen Oil Ltd. Maximal Flow Problem30Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–7 Parameter Specification Screen for the TurkmenOil Ltd. Maximal Flow Problem31Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–8 Output Worksheet for the Turkmen Oil Ltd. Maximal Flow Problem32Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Table 8–2 Summary of the Optimal Flow Quantities for Turkmen Old Ltd.33Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–9 Worksheet for Solved Problem 1, the Shortest-Route Problem(Beginning Node 1, Ending Node 5)34Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–10 Parameter Specification Screen for Solved Problem 1, the Shortest-Route Problem (Beginning Node 1, Ending Node 5)35Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–11 Worksheet for Solved Problem 3, the Maximal Flow Problem36Copyright © 2007 The McGraw-Hill Companies. All rights reserved. Exhibit 8–12 Parameter Specification Screen for Solved Problem 3, the Maximal Flow Problem37Copyright © 2007 The McGraw-Hill Companies. All rights reserved.