Difference between revisions of "Network flow problem"

From optimization
Jump to: navigation, search
Line 1: Line 1:
 
Authors: Blake Alexander, Aaron Frank, and Joshua Lee (ChE 345 Spring 2014)
 
Authors: Blake Alexander, Aaron Frank, and Joshua Lee (ChE 345 Spring 2014)
  
Introduction
+
 
 +
== 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.
 
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.
Line 7: Line 9:
 
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 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 <math>\subset</math> { (i, j):i, j <math>\in</math> N, i<math>\neq</math>j}.
+
  A <math>\subset</math> { (i, j):i, j <math>\in</math> N, i<math>\neq</math>j}.
  
 
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 iN, let bibe 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):
 
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 iN, let bibe 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):
  
<math>\Sigma</math>b<math>_{i}</math>= 0 for ''i''<math>\in</math>N
+
  <math>\Sigma</math>b<math>_{i}</math>= 0 for ''i''<math>\in</math>N
  
To guide the solver in solving the paths, we assume that for each arc, there is an associated cost cij, for moving material. Furthermore, xij is the quantity shipped down a certain arc.
+
To guide the solver in solving the paths, we assume that for each arc, there is an associated cost c<math>_{i}</math><math>_{j}</math>, for moving material. Furthermore, x<math>_{i}</math><math>_{j}</math> 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):
 
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  cijxij for (i.j)A
+
  minimize  <math>\Sigma</math>c<math>_{i}</math>x<math>_{i}</math> for (''i''.''j'')<math>\in</math>A
  
 
As stated earlier, Network Flow Optimization problems are limited by constraints. Depending on the circumstances of the problem, these constraints can have some variation.
 
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 problem
 
  
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.
+
== Example ==
  
[[File:Network_Flow_Problem.jpg]]
 
 
Strategies to Solve the Problem
 
 
Blake made equations that describe the diagram but don’t show up on Google Doc. 
 
  
 +
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.
  
 +
[[File:Network_Flow_Problem.jpg]]
  
Solution
+
===Strategies to Solve the Problem===
  
Conclusion
+
  minimize  <math>\Sigma</math>c<math>_{i}</math>x<math>_{i}</math> (A)
 +
  s.t. <math>\Sigma</math>x<math>_{ij}\leq</math>S<math>_{i}</math> For All ''i'' <math>\in</math> S (B)
 +
        <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)
  
 
Sources:
 
Sources:

Revision as of 22:04, 25 May 2014

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


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 iN, let bibe 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)

Sources:

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

Steward: Dajun Yue, Fengqi You

Date Presented: Apr. 10, 2014