The Maximum Flow and Minimum Cost–Maximum Flow Problems: Computing and Applications
W. H. Moolman *
Department of Mathematical Sciences and Computing, Walter Sisulu University, Mthatha, South Africa.
*Author to whom correspondence should be addressed.
Abstract
The maximum flow and minimum cost-maximum flow problems are both concerned with determining flows through a network between a source and a destination. Both these problems can be formulated as linear programming problems. When given information about a network (network flow diagram, capacities, costs), computing enables one to arrive at a solution to the problem. Once the solution becomes available, it has to be applied to a real world problem. The use of the following computer software in solving these problems will be discussed: R (several packages and functions), specially written Pascal programs and Excel SOLVER. The minimum cost-maximum flow solutions to the following problems will also be discussed: maximum flow, minimum cost-maximum flow, transportation problem, assignment problem, shortest path problem, caterer problem.
Keywords: Maximum flow, minimum cost-maximum flow, nodes, arcs, source, sink, capacities, costs, objective function, flow conservation and capacity constraints, algorithm, optimal solution, network optimization, transportation problem, assignment problem, shortest path problem, caterer problem.