# Implementation Of Primal-Dual Algorithm As The Linear Programming Engine Of The PCDAIRY Ration Formulation Program

Published by the American Society of Agricultural and Biological Engineers, St. Joseph, Michigan www.asabe.org

Citation:  Computers in Agriculture and Natural Resources, 4th World Congress Conference, Proceedings of the 24-26 July 2006 (Orlando, Florida USA) Publication Date 24 July 2006  701P0606.(doi:10.13031/2013.21942)
Authors:   Abbas Ahmadi and Peter H. Robinson
Keywords:   Ration Formulation, Modeling and Simulation, Decision Support Systems

The heart of our PCDAIRY ration formulation program is a linear programming module. This module is based on the Primal-Dual Algorithm, which is a mixed system for solving a linear program. It combines the Simplex Algorithm and the Dual Simplex Algorithm, thereby avoiding artificial variables completely and reducing the size of the tableau. This usually causes a marked reduction in the number of iterations necessary to optimize the problem. In developing the Simplex Method, we made use of the classical Gauss-Jordan elimination for solving a system of linear equations. The key idea is to take a multiple of one equation and add it to, or subtract it from, another equation to eliminate one of the unknowns from the second equation. The result of completing this elimination systematically is the row echelon form of the coefficients in the augmented matrix. The reduced system, whose solutions are easy to read, is equivalent to the original system of linear equations. The algorithm is implemented using the C++ Windows programming language. The main data structure of the Prim-Dual algorithm is a tableau. The final tableau may be optimal and feasible. In this case, a solution has been found to both the primal and dual programs. If the final tableau is optimal, but contains a negative in the last column due to the fact that no pivot can be found in that row, then the primal program has no feasible solution and its dual is unbounded.