Authors: Dhananjay P. Mehendale
In this paper we propose a new algorithm for linear programming. This new algorithm is based on treating the objective function as a parameter. We transform the matrix of coefficients representing this system of equations in the reduced row echelon form containing only one variable, namely, the objective function itself, as a parameter whose optimal value is to be determined. We analyze this matrix and develop a clear method to find the optimal value for the objective function treated as a parameter. We see that the entire optimization process evolves through the proper analysis of the said matrix in the reduced row echelon form. It will be seen that the optimal value can be obtained 1) by solving certain subsystem of this system of equations through a proper justification for this act, or 2) By making appropriate and legal row transformations on this matrix in the reduced row echelon form so that all the entries in the submatrix of this matrix, obtained by collecting rows in which the coefficient of so called unknown parameter d whose optimal value is to be determined, become nonnegative and this new matrix must be equivalent to original matrix in the sense that the solution set of the matrix equation with original matrix and matrix equation with transformed matrix are same. We then proceed to show that this idea naturally extends to deal with nonlinear and integer programming problems. For nonlinear and integer programming problems we use the technique of Grobner bases since Grobner basis is an equivalent of reduced row echelon form for a system of nonlinear equations, and the methods of solving linear Diophantine equations respectively.
Comments: 6 Pages. Presented and Published in the Proceedings of International Conference on Perspectives of Computer Confluence with Sciences 2012, ICPCCS 12.
[v1] 2012-12-11 09:05:35
Unique-IP document downloads: 15 times
Add your own feedback and questions here: