Local Perturbation Analysis of Linear Programming with Functional Relation Among Parameters

Top

Introduction

The main purpose of classical sensitivity analysis is to examine the variations of the objective function's optimal values and the solution components as a result of the infinitesimal changes in one of the parameters while the other ones are kept fixed (Bradley et al., 1977). One of the problems confronted in classical sensitivity analysis is when several parameters are changed simultaneously. In those cases, classical methods cannot obtain the effect of the perturbations on the objective function as well as on the optimal solution because when the simultaneous changes happen in the amplitudes range of basic variables or binding constraints, the order of basic solution changes. However, there is a conservative bound for the objective function coefficients or the right-hand side (RHS) parameters on their simultaneous changes. This bound is introduced under the 100 percent rule of changes when the perturbed coefficients of objective function are related to basic variables, or when the RHS parameters are related to binding constraints. The 100 percent rule states that if the sum of the proper fraction of the desired changes to the maximum possible change in that direction is less than or equal to one then the current basic optimal solution will remain unchanged (Bradley et al., 1977).

The general form of linear programming (LP) problem can be considered as follows:

(1) where is an matrix with full rank and is a column vector called the RHS parameters resembling the amount of resources, and is the coefficient vector of the objective function; they are collectively called the parameters of the LP problem. A simplex algorithm may be used to solve the LP problems. A simplex algorithm, in each step, chooses a set of the independent columns from matrix, provides the correspondent basic feasible solutions and checks for the optimality conditions. It is assumed that a basic optimal solution is available for this problem.

Let us introduce the following mathematical notations and definitions used throughout this paper and for the simplex table:

• :The set of basic variable indices

• :The set of non-basic variable indices

• B:A sub-matrix of whose columns are associated with the basic variable of S_B

• N:A sub-matrix of whose columns are associated with the non-basic variable of S_N

• c_B:The coefficient vector of the objective function whose elements are related to the basic variable

• :The optimal basic solution of the LP problem

• :The optimal value of the objective function

• :The matrix with entries of the final table of the simplex for the non-basic variables

• :The entries of matrix Y