Note on Degeneracy
Abstract
Given a linear program in standard form, Min cx s.t. Ax = b, x > or = 0, where A is an m x n matrix with rational coefficients, one technique used to resolve degeneracy in the simplex algorithm is the lexicographic rule. This rule adjoins to b a non-singular m x m square matrix M. the appended columns of M are updated along with b on each iteration. When the ratio test for determining the pivot row results in a tie, the ratio test is applied to the corresponding elements of the updated columns of M in turn, from left to right, until the tie is resolved. In this note we prove that it is only necessary instead, to adjoin to b a single column d whose ith component is d sub i = pi sub i, (or preferably the fractional part of pi sub i in order that d sub i < 1). Any transcendental number can be used instead of pi = 3.14.... The proof exploits the fundamental property of a transcendental number namely, it can never be a root of a polynomial equation Alpha sub 1 x + alpha sub 2 squared +....+ alpha sub p sub x to the p power = 0 when alpha sub 1, alpha sub 2,...., alpha sub p are rational and not all zero.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1989
- Accession Number
- ADA208724
Entities
People
- Alamuru S. Krishna
Organizations
- Stanford University