Conversion of linear programmes to network flow problems

The research carried out throughout this thesis is concerned with the conversion of Linear Programmes to Network Flow Problems. Although a Network Flow Problem can always be expressed as a Linear Programme, the converse is not always true. Many people have found that some classes of Linear Programmes were in fact `hidden' Network Flow Problems, but few have actually put forward a systematic way of testing if any Linear Programme can be successfully converted to a Network Flow Problem. The algorithm proposed in this thesis directly attempts to construct the graph associated with the constraint matrix of the original LP programme. If a graph can be produced, then row operations and column scaling are carried out to actually yield, if possible, the equivalent Network Flow Model. If a graph cannot be constructed, then the LP is not convertible to an NFP. Chapter I provides an introduction to the problem as well as an exhaustive literature review. Chapter II is concerned with the theoretical foundations of the work carried out in the rest of the thesis. Chapter III describes two known algorithms that test if a necessary condition for an LP to be convertible is satisfied. Chapter IV provides a simple test (backed by a computer program) on the constraint matrix of the Linear programme. Chapter V presents our algorithm as well as its theoretical foundations. Chapter VI points at some further lines of research ahead. Appendix I solves a real-life example. Appendix II contains the references. Appendix III gives the listing of the computer program mentioned in chapter IV. (D81698)