Engineering Optimization: Theory and Practice, Fourth Edition

208 Linear Programming II: Additional Topics and Extensions

4.5.1 Changes in the Right-Hand-Side Constantsbi

Suppose that we have found the optimal solution to a LP problem. Let us now change

thebi tobi+ bi so that the new problem differs from the original only on the

right-hand side. Our interest is to investigate the effect of changingbitobi+ bion

the original optimum. We know that a basis is optimal if the relative cost coefficients

corresponding to the nonbasic variablescjare nonnegative. By considering the pro-

cedure according to whichcjare obtained, we can see that the values ofcjare not

related to thebi. The values ofcjdepend only on the basis, on the coefficients of the

constraintmatrix, and the original coefficients of the objective function. The relation

is given in Eq. (4.10):

cj=cj−πTAj=cj−cTBB−^1 Aj (4.33)

Thus changes inbiwill affect the values of basic variables in the optimal solution and

the optimality of the basis will not be affected provided that the changes made inbido

not make the basic solution infeasible. Thus if the new basic solution remains feasible

for the new right-hand side, that is, if

X′B=B−^1 (b+b)≥ 0 (4.34)

then the original optimal basis,B, also remains optimal for the new problem. Since the

original solution, say†

XB=











x 1

x 2

..

.

xm











is given by

XB=B−^1 b (4.35)

Equation (4.34) can also be expressed as

xi′=xi+

∑m

j= 1

βijbj≥ 0 , i= 1 , 2 ,... , m (4.36)

where

B−^1 =[βij] (4.37)

Hence the original optimal basisBremains optimal provided that the changes made in

bi, bi, satisfy the inequalities (4.36). The change in the value of theith optimal basic

variable,xi, due to the change inbiis given by

X′B−XB=XB=B−^1 b

†It is assumed that the variables are renumbered such that the firstmvariables represent the basic variables

and the remainingn−mthe nonbasic variables.