T. Unger : On some Aspects of (Matrix) Data Perturbation in Linear Programming Problems

Author(s) :

T. Unger

Title :

On some Aspects of (Matrix) Data Perturbation in Linear Programming Problems

Preprint series

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 98-28, 1998

Mathematics Subject Classification :

90C31 [ Sensitivity, etc. ]

49K40 [ Sensitivity of optimal solutions in the presence of perturbations ]

90C05 [ Linear programming ]

Abstract :

This paper is concerned with the sensitivity of optimal basic solutions of a linear program under simultaneous changes in all coefficients. We consider the case of linear dependency of the objective function , the RHS, and the matrix coefficients on a scalar parameter. Firstly, we use the representation of the optimal solution set by its extreme points getting results in case the perturbations appear in one column only. In the second part we consider an approach proposed by Freund using the Neumann series of the optimal basis' inverse. Freunds results are corrected, extended, and compared to those of Dinkelbach.

Keywords :

Parametric linear programming, Optimal basis, Optimality intervals, Sensitivity analysis

Language :

english

Publication time :

11/1998