Consider a problem of scheduling production of a certain item to meet a given demand over N time periods. Let us denote:
xi: The amount of product stored at the beginning of period i, where i = 0,...,N - 1. There is a nonnegativity constraint on xi. ui: The amount of product produced during period i. There is a constraint 0 ≤ ui ≤ ci, where the scalar ci is given for each i. di: The amount of product demanded during period i. This is a given scalar for each i
The amount of product stored evolves according to the equation
where ai and bi are given scalars for each i. Formulate this problem as a minimum cost flow problem. Hint: For each i, introduce a node that connects to a special artificial node.