Models

Distribution Example

 Distribution Example The logistics manager has the problem of shipping materials in warehouses to customer locations as illustrated in Fig. 1. Warehouses are in Phoenix, Austin and Gainesville, the gray nodes in the figure. The supplies available are indicated in the brackets adjacent to the nodes with a positive number indicating a supply of the material. Customers are in Chicago, Los Angeles, Dallas, Atlanta and New York. The negative numbers adjacent to these nodes are the demands. Possible air shipping links are the directed arcs between the nodes. The numbers adjacent to the arcs are unit shipping costs. The flow on each link is restricted to a maximum of 200 units. Dallas and Atlanta are hubs that, in addition to their own demands, can transship material to other customers. The problem is to determine an optimum shipping plan that minimizes the total cost of shipping while meeting all customer demands with available supplies.

Figure 1. Distribution Problem.

Arc lower bounds 0 and upper bound 200.

Pure Network Model

This problem is ready made for a network flow model, and we use Figure 1 to describe the several components of this model type. The network model is graphical in that it is presented as a collection of the nodes and arcs drawn in the figure. The nodes represent the cities of this problem, and we name them with the shortened names of the supply and demand cities. Arcs are the directed line segments of the figure. The nodes at its ends identify an arc. One arc in the figure originates at node Phoenix and terminates at node Chicago.

Flow is associated with the network, entering and leaving at the nodes and passing through the arcs. Flows entering or leaving a node from external sources are called external flows and are shown adjacent to the nodes in the square brackets. A positive external flow is a supply, flow that enters the network, and a negative external flow is a demand, flow that leaves the network. Flow is conserved at each node, implying that the total flow entering a node, either from arcs or external supplies, must equal the total flow leaving the node, either to arcs or to external demands. The arc flows are the decision variables for the network flow programming model.

Flow is limited in an arc by the lower and upper bounds on flow. In this example we specify 0 as the lower bound for all arcs and 200 as the upper bound. Sometimes the term capacity refers to the upper bound on flow. Within the restrictions imposed by conservation of flow for each node and the bounds on flow for each arc, there are usually many feasible flows (a flow is an assignment of an arc flow to each arc). The problem is to find a feasible flow, if one exists, and an optimal flow from the set of feasible flows.

The criterion for optimality is cost. Associated with each arc is a cost per unit of flow (the number in the parenthesis). If a flow x passes through the arc with unit cost c, a cost cx is incurred. The total cost for the network is the sum of the arc costs, and the goal of optimization is to find the feasible flow that minimizes this measure.

We call the model of this section a pure network flow model because the flow entering an arc at its origin node is equal to the flow leaving the arc at its terminal node. This is contrasted later to the generalized network flow model that does not have this limitation. The pure model has the important feature of integral optimum solutions. Whenever all node external flows and all arc upper and lower bounds are integer, the flow solution to the pure model is also integer. As we will see, this has important ramifications.

The model defined in Fig. 1 can be solved to find the optimum flows. The solution is shown on the next page.

Linear Programming Model

Every network flow model has a linear programming model, that is a model with algebraic linear expressions describing the objective function and constraints. We explain here the model for the specific case above, and will provide in the Vocabulary Section, the general model.

For construction of the model, it is convenient to number the nodes and arcs for reference as in Fig. 2.

Figure 2. Representation for Linear Programming Model.

The linear programming model is an algebraic description of the objective to be minimized and the constraints to be satisfied by the variables. The variables are the flows in each arc designated by through . The network flow problem is to minimize total cost while satisfying conservation of flow at each node. The variables must also satisfy the simple upper and lower bounds on arc flow.

Solving the Model

A network model may be solved with either special purpose network flow programming algorithms or with general purpose linear programming algorithms. The solution, shown in Fig. 3, has the feature of integrality of flows. All pure network flow models have integer solutions.

Figure 3. Optimum flow solution. Total Cost = \$5300.

Operations Research Models and Methods
Internet
by Paul A. Jensen