# A Dynamic Programming Approach to Ecosystem Management
## 2 Materials and Methods
### Applications  
The class of minimum cost flow problems includes a variety of applications that can be solved efficiently. Generally, these applications involve determining a plan for delivering goods from their sources to intermediate facilities (warehouses, processing facilities) to customers. Examples of these kinds of problems can be found in goods, waste or cash distribution and management.  
For a directed and connected network containing at least one supply node and one demand node, the variables are denoted as follows:  
\[ij=\text{arc from node }i\text{ to node }j\]  
\[x_{ij}=\text{flow through arc }ij\]  
\[c_{ij}=\text{cost per unit flow through arc }ij\]  
\[u_{ij}=\text{arc }ij\text{ capacity}\]  
\[b_{i}=\text{flow generated at node }i\]  
\[b_{i}>0\text{ if }i\text{ is a supply node}\]  
\[b_{i}<0\text{ if }i\text{ is a demand node}\]  
\[b_{i}=0\text{ if }i\text{ is a transshipment node}\]We can identify a range of special cases:  
A model network for a _transportation problem_ contains a supply node for each source and a demand node representing each destination. The network includes no transshipment nodes. All the arcs are directed from a supply node to a demand node, and a flow \(x_{ij}\) stands for the distribution of \(x_{ij}\) units from source \(i\) to destination \(j\). The cost per distributed unit is identified with the cost per unit of flow. Since there is no upper bound on the individual \(x_{ij}\), we fix each arc capacity to \(u_{ij}=\infty\) for each \(ij\). The goal is to minimize the total distribution cost. It is necessary for the total amount of supply to be equal to or exceed the overall demand.  
A _Transshipment problem_ is a minimum cost flow problem where \(u_{ij}=\infty\) for each \(ij\), meaning that arcs can carry any amount of flow. This kind of problem generalizes special cases of transportation problems with intermediate nodes.  
For the _maximum flow problem_, we consider a directed and connected network in which all flow originates at one node, called the _source_, and terminates at another node, called the _sink_. All the remaining nodes are transshipment nodes. There are no arcs directed to the source, or from the sink. The objective is to maximize the total amount of flow given arc capacities, measuring it either from the source or to the sink. Concretely, the flow can represent goods through the distribution or supply network of a company, or water through a system of aquducts, and so forth.  
A _shortest path problem_ is generally formulated on undirected and connected networks. However, more versions exist, each one fitting for different types of applications.  
The model network must contain an _origin node_ and a _destination node_, and a non-negative distance associated with each link. The objective is to minimize a quantity that can be interpreted as total distance traveled, total time or total cost of a sequence of activities.  
The latter is the kind of model we consider for our application, adapted to find minimum-cost directed paths from the origin to the destination of a directed network. The problem will be approached through a dynamic programming procedure.