Extreme Point Solutions in Mathematical Programming: An Opposite Sign Algorithm

摘要

Several important and efficient methods of solution of specific types of linear programming problems have the feature of sometimes providing optimal solutions which are not extreme-point (or basic) solutions, so that important and useful analyses provided by knowledge of the optimal dual evaluators are not available. It is also often desirable to be able to begin with a solution suggested by knowledgeable persons with experience in the field (or other considerations) and to proceed immediately to a basic solution at least as good as the suggested one. In this paper it is shown how part of the technique of proof of the opposite sign theorem can be employed in a simple algorithm to achieve this end. This method is equally valid when maximizing a nonlinear but convex objective function. A tested ALGOL code is provided for executing the algorithm in a manner compatible (as a procedure) with other programs. (Author)