Linear Programming and Resource Allocation Modeling

9Analyzing Structural Changes

9.1 Introduction

Oftentimes, one is faced with the task of adding or deleting certain variables or structural constraints in a problem for which an optimal basic feasible solution has been found. As in the preceding chapter, rather than resolve completely the adjusted problem, we shall use the information contained within the optimal simplex matrix of the original linear program to determine the effects of the said changes upon the feasibility or optimality of the solution at hand.

9.2 Addition of a New Variable

We first look to the effect on the optimal solution of a given linear programming problem of the introduction of a new variable x_n + 1, with c_n + 1 and a_n + 1 representing its associated objective function coefficient and vector of structural constraint coefficients, respectively. In particular, we are now confronted with solving a problem of the form

If X_B = B⁻¹b represents an optimal basic feasible solution to the problem

then we may also view it as a basic feasible solution to the former problem with x_n + 1 deemed nonbasic or zero. Moreover, this solution will be optimal if Obviously then, if the current solution is no longer optimal ...