Network Flow in Graph Theory – The Producer’s Problem

AUTHOR AND
AFFILIATION

GEORGE MATHEW
Department of Mathematics, BCM College, Kottayam, 686001, Kerala (India)
MERLIN MARY ABRAHAM (merlinmabraham@gmail.com)
Department of Mathematics, BCM College, Kottayam, 686001, Kerala (India)

KEYWORDS:

Network, flow, feasible flow, flow value, s-t cut, augmenting path, leeway, maximum flow, Subject classification: 05C21

Issue Date:

October, 2017

Pages:

440-447

ISSN:

2319-8044 (Online) – 2231-346X (Print)

Source:

Vol.29 – No.10

PDF

Click Here Download PDF

DOI:

http://dx.doi.org/10.22147/jusps-A/291004

ABSTRACT:

The maximum flow problem was first formulated in 1954 by T.E. Harris and F.S. Ross as a simplified model of soviet Railway traffic flow1. In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm for calculating the maximum flow, the Ford-Fulkerson algorithm2. It was in 1951 when the American mathematician, George Dantzig put forward the network simplex algorithm to solve mininimum cost flow problem. We take a typical example and find the maximum flow and minimum cost. Finally we generalise The Producer’s Problem based on some assumptions and find the maximum flow and minimum cost in it. We observe that the minimum unit cost in The Producer’s Problem increases with the number of items produced increases, in contrast to natural expectation.

Copy the following to cite this Article:

G. Mathew; M. M. Abraham, “Network Flow in Graph Theory – The Producer’s Problem”, Journal of Ultra Scientist of Physical Sciences, Volume 29, Issue 10, Page Number 440-447, 2017


Copy the following to cite this URL:

G. Mathew; M. M. Abraham, “Network Flow in Graph Theory – The Producer’s Problem”, Journal of Ultra Scientist of Physical Sciences, Volume 29, Issue 10, Page Number 440-447, 2017

Available from: http://www.ultrascientist.org/paper/852/network-flow-in-graph-theory-the-producers-problem


The maximum flow problem was first formulated in 1954 by T.E. Harris and F.S. Ross as a simplified model of soviet Railway traffic flow1. In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm for calculating the maximum flow, the Ford-Fulkerson algorithm2. It was in 1951 when the American mathematician, George Dantzig put forward the network simplex algorithm to solve mininimum cost flow problem. We take a typical example and find the maximum flow and minimum cost. Finally we generalise The Producer’s Problem based on some assumptions and find the maximum flow and minimum cost in it. We observe that the minimum unit cost in The Producer’s Problem increases with the number of items produced increases, in contrast to natural expectation.