Abstract
The sensitivity analysis in linear programming is a well-known standard, technique to deal with variations of selected entries. Its limitation is that is focuses only on sensitivity of one coefficient or other simple cases.
The real life is, however, more complicated. To handle a bit more complex data variations, various approaches were introduced and studied.
Herein, we address variations of possibly all input data, controlled by a certain matrix norm. More concretely, the aim is to compute the maximum variation of the data in the norm such that the computed optimal basis remains optimal.
First, we present results valid for a general matrix norm. Then we inspect particular norms, such as the spectral and the maximum norm.
We also analyse computational complexity to know for which norms the problem is efficiently computable and for which it is NP-hard.