Difference between revisions of "Network flow problem"

From optimization
Jump to: navigation, search
Line 36: Line 36:
 
         <math>\Sigma</math>x<math>_{ij}\geq</math>D<math>_{j}</math> For All ''j'' <math>\in</math> D (C)  
 
         <math>\Sigma</math>x<math>_{ij}\geq</math>D<math>_{j}</math> For All ''j'' <math>\in</math> D (C)  
 
         x<math>_{ij}\geq</math>0 For All ''i'' <math>\in</math>S <math>\in</math>D (D)
 
         x<math>_{ij}\geq</math>0 For All ''i'' <math>\in</math>S <math>\in</math>D (D)
 +
 +
Equation (A) is the minimization of the product of cost and amount of product, which gives the total price.  The total price is subject to the constraints of equations (B) and (C), where (B) is the condition that the sum of the products transported from source to demand is not greater than the total supply.  Equation (C) is the constraint that the demand is not greater than the total amount of product shipped.  Constraint (D) is to ensure that there is indeed a product shipped since otherwise all minimization problems would have an answer of zero.  This situation can be solved by a software program such as GAMS.
  
 
==Conclusion==
 
==Conclusion==

Revision as of 22:25, 25 May 2014

Authors: Blake Alexander, Aaron Frank, and Joshua Lee (ChE 345 Spring 2014)


Contents

Introduction

Network Flow Optimization problems form the most special class of linear programming problems. Transportation, electric, and communication networks are clearly common applications of Network Optimization. These types of problems can be viewed as minimizing transportation problems. This Network problem will include cost of moving materials through a network involving varying demands, parameters, and constraints depending on the locations that the materials are being brought to. Problems of these type are characterize Network Flow Optimization. The consideration of the connections between different parts of the Network is what makes these problems difficult, but extremely important and applicable.

A network consists of two types of of objects, which are, nodes and arcs (1). Node sets will be denoted by “N” with m being the number of nodes. These nodes are connected by arcs. These arcs are defined and direct, meaning that the arc that connects nodes 1 and 2 is not the same as the arc that connects nodes 3 and 4. It is therefore intuitive to denote arcs by their direction [i.e. arc (1,2), arc (3,4), (i.j)]. Knowing this, we can denote the set of all arcs in the network with “A.” The following expression is the subset of the set of all possible arcs (1):

  A \subset { (i, j):i, j \in N, i\neqj}.

The pair (N, A) is called a network. To specify a network flow problem, we need to specify the supply/demand of a material into a node. So for each i\inN, let b_{i} be the supply/demand to the node to the network at Node i. Depending on whether the amount of material moved to each node is negative or positive differentiates supply or demand. Thus, one can assume (1):

  \Sigmab_{i}= 0 for i\inN

To guide the solver in solving the paths, we assume that for each arc, there is an associated cost c_{i}_{j}, for moving material. Furthermore, x_{i}_{j} is the quantity shipped down a certain arc.

With this information, the objective of the network flow problem is simple. The objective, or problem, is minimizing total cost of moving supplies while meeting demands (1):

  minimize  \Sigmac_{i}x_{i} for (i.j)\inA

As stated earlier, Network Flow Optimization problems are limited by constraints. Depending on the circumstances of the problem, these constraints can have some variation.


Example

A basic example of the Network Flow Optimization problem is one based around transportation. There are three source nodes denoted S1, S2, and S3, and three demand nodes denoted D1, D2, and D3. Each source node can deliver its product to any demand node, and overall all products produced are consumed by the demand nodes. Each supply node has a different amount of product it can produce, and each demand node requires a different amount of product. The shipping costs from each supply node to each demand node are different which gives rise to how to distribute products so that demand is met at the lowest cost.

Network Flow Problem.jpg

Strategies to Solve the Problem

  minimize  \Sigmac_{i}x_{i} (A)
  s.t. \Sigmax_{ij}\leqS_{i} For All i \in S (B)
       \Sigmax_{ij}\geqD_{j} For All j \in D (C) 
       x_{ij}\geq0 For All i \inS \inD (D)

Equation (A) is the minimization of the product of cost and amount of product, which gives the total price. The total price is subject to the constraints of equations (B) and (C), where (B) is the condition that the sum of the products transported from source to demand is not greater than the total supply. Equation (C) is the constraint that the demand is not greater than the total amount of product shipped. Constraint (D) is to ensure that there is indeed a product shipped since otherwise all minimization problems would have an answer of zero. This situation can be solved by a software program such as GAMS.

Conclusion

Network Flow problems are useful for minimizing different issues that arise when considering many different situations, but especially transportation, electric, and communications problems. The complex connections between nodes and arcs can be applied to problems of varying magnitude.

Sources

(1) R.J. Vanderbei, Linear Programming: Foundations and Extensions. Springer, 2008.


Steward: Dajun Yue, Fengqi You

Date Presented: Apr. 10, 2014