MODULE 7 - MANSCI

• Prelude for the next module, which is CPM and PERT. These network techniques are used primarily for project analysis.
• Network Flow Models


  A larger class of LP problems known as NETWORK FLOW PROBLEMS
• Network


  • An arrangement of paths connected at various points, through which one or more items move from one point to another
  • Enables the manager to visually interpret the system and thus enhances the manager's understanding
  • Many real-life systems can be modeled as networks, which are relatively easy to conceive and construct
• Nodes


  Denoted by circles, represent junction points connecting branches
• Branches


  Represented as lines, connect nodes and show flow from one point to another
• The Shortest Route Problem

  1. Determine the shortest distance between an origin point and various destination points

  2. Start at the origin node and determine the shortest time to directly connected nodes

  3. Repeat the process to determine the shortest route to all nodes
• Stagecoach Shipping Company


  • Transporting oranges by six trucks from Los Angeles to six cities in the West and Midwest
• The shipping company manager wants to determine the best routes (in terms of the minimum travel time) for the trucks to reach their destinations
• Steps of the Shortest Route Problem

  1. Select the node with the shortest direct route from the origin

  2. Establish a permanent set with the origin node and the node that was selected in step 1

  3. Determine all nodes directly connected to the permanent set nodes

  4. Select the node with the shortest route (branch) from the group of nodes directly connected

  5. Repeat steps 3 and 4 until all nodes have joined the permanent set
• Computer Solution Of The Shortest Route Problem using QM for Windows
• Minimal Spanning Tree Problem


  Objective is to connect all the nodes in the network so that the total branch lengths are minimized as well as the resulting network spans (connects) all the points in the network at a minimum total distance (or length)
• Steps of the Minimal Spanning Tree Problem

  1. Start with any node in the network and select the closest node to join the spanning tree

  2. Repeat the process of selecting the closest node to the present spanning tree
• Steps of the Minimal Spanning Tree Problem

  1. Select any starting node

  2. Select the node closest to the starting node to join the spanning tree

  3. Select the closest node not presently in the spanning tree

  4. Repeat until all nodes have joined the spanning tree
• The minimal spanning tree network shows how to connect all nodes so that the total distance (length) is minimized
• Maximal flow problem


  To maximize the amount of flow of items from an origin to a destination
• Examples of maximal flow problems

  • Flow of water, gas, or oil through a network of pipelines
  • Flow of forms through a paper processing system
  • Flow of traffic through a road network
  • Flow of products through a production line system
• Steps of the Maximal Flow Problem

  1. Arbitrarily select any path in the network from origin to destination

  2. Adjust the capacities at each node by subtracting the maximal flow for the path selected

  3. Add the maximal flow along the path in the opposite direction at each node

  4. Repeat until there are no more paths with available flow capacity

  5. Recompute the branch flow in both directions
• Maximal flow problems can have multiple optimal solutions
• Steps to design a rail system that will connect all six communities with the minimum amount of track


  Develop a minimal spanning tree for this problem