Compatibility theory

From Glossary

Jump to: navigation, search

The idea that a solution's character does not change for a particular perturbation. In linear programming the character could be an optimal basis, and the theory is concerned with whether a particular basis remains optimal when the data is changed in a prescribed direction. A Fundamental Theorem of Basis Compatibility is the following:

LaTeX: h is an admissible direction for perturbing LaTeX: (b, c) if, and only if, it is compatible with some equilibrium basis.

The range of compatiblity of a basis, LaTeX: B, for a direction, LaTeX: h, is the greatest step for which LaTeX: B remains optimal:

\sup \{t : B \;\mbox{ is optimal for the LP defined by }\; r + th\}.

The basis spectrum is the greatest range:

\sup\{ \mbox{range}(B; h) : B \;\mbox{ is optimal for the LP defined by }\; r\}.

Personal tools