3.9 Simplex Algorithm 141
Since the variablesxm+ 1 , xm+ 2 ,... , xnare presently zero and are constrained to be
nonnegative,the only way any one of them can change is to become positive. But if
c′′i> 0 fori=m+ 1 , m+ 2 ,... , n, then increasing anyxicannot decrease the value
of the objective functionf. Since no change in the nonbasic variables can causefto
decrease, the present solution must be optimal with the optimal value offequal tof 0 ′′.
Aglance overc′′i can also tell us if there are multiple optima. Let allc′′i> 0 ,
i=m+ 1 , m+ 2 ,... , k− 1 , k+ 1 ,... , n, and letc′′k= for some nonbasic variable 0
xk. Then if the constraints allow that variable to be made positive (from its present
value of zero), no change inf results, and there are multiple optima. It is possible,
however, that the variable may not be allowed by the constraints to become positive;
this may occur in the case of degenerate solutions. Thus as a corollary to the discussion
above, we can state that a basic feasible solution is the unique optimal feasible solution
ifc′′j> 0 for all nonbasic variablesxj,j=m+ 1 ,m+ 2 ,... , n. If, after testing for
optimality, the current basic feasible solution is found to be nonoptimal, an improved
basic solution is obtained from the present canonical form as follows.
3.9.2 Improving a Nonoptimal Basic Feasible Solution
From the last row of Eqs. (3.21), we can write the objective function as
f=f 0 ′′+
∑m
i= 1
c′′ixi+
∑n
j=m+ 1
c′′jxj
=f 0 ′′ for the solution given by Eqs. (3.22)
(3.25)
If at least onec′′jis negative, the value offcan be reduced by making the corresponding
xj>0.In other words, the nonbasic variablexj, for which the cost coefficientcnjis
negative, is to be made a basic variable in order to reduce the value of the objective
function. At the same time, due to the pivotal operation, one of the current basic
variables will become nonbasic and hence the values of the new basic variables are to be
adjusted in order to bring the value offless thanf 0 ′′. If there are more than onec′′j< , 0
the indexsof the nonbasic variablexswhich is to be made basic is chosen such that
c′′s= inimumm c′′j< 0 (3.26)
Although this may not lead to the greatest possible decrease inf (since it may not be
possible to increasexsvery far), this is intuitively at least a good rule for choosing the
variable to become basic. It is the one generally used in practice because it is simple
and it usually leads to fewer iterations than just choosing anyc′′j<. If there is a 0
tie-in applying Eq. (3.26), (i.e., if more than onec′′j has the same minimum value),
we select one of them arbitrarily asc′′s.
Having decided on the variablexs to become basic, we increase it from zero,
holding all other nonbasic variables zero, and observe the effect on the current basic
variables. From Eqs. (3.21), we can obtain
x 1 =b 1 ′′−a′′ 1 sxs, b 1 ′′≥ 0
x 2 =b 2 ′′−a′′ 2 sxs, b 2 ′′≥ 0 (3.27)
..
.
