Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 13. Degeneracy in Linear Program... > 13.2. Charnes' Perturbation Method - Pg. 159

Degeneracy in Linear Programming 159 practice, an optimal solution is reached in a finite number of steps. For this reason, most instruction codes for electronic computers do not include roles which guarantee convergence. Theoretically, however, it is at least possible for a problem to cycle and therefore it is desirable to develop a procedure that will ensure that cycling will never occur. Two best known procedures for the resolution of degeneracy are the perturbation method, developed by Chames [67] and the lexicographic method developed by Dantzig, Orden and Wolfe [ 117] We present here the method suggested by Charnes. 13.2. Charnes' Perturbation Method We note that degeneracy in a linear programming problem occurs when 'b', the requirement vector of the problem cannot be expressed as a positive linear combination of the basis vectors of some bases formed from the columns of A. It is then expected that if 'b' were perturbed, it might be possible to express the perturbed 'b' as a positive linear combination of each basis vector of every feasible basis and from the solution of this nondegenerate perturbed problem, we may then be able to get a solution of our original problem. Consider the linear programming problem (11.1), where the constraints are xla ~ + x2a2 + ... + x a = b, (13.2)