Engineering Optimization: Theory and Practice, Fourth Edition

140 Linear Programming I: Simplex Method

minimizes the functionf (X)and satisfies the equations:

1 x 1 + 0 x 2 + · · · + 0 xm+a 1 ′′,m+ 1 xm+ 1 + · · · +a′′ 1 nxn =b′′ 1

0 x 1 + 1 x 2 + · · · + 0 xm+a 2 ′′,m+ 1 xm+ 1 + · · · +a′′ 2 nxn =b′′ 2

0 x 1 + 0 x 2 + · · · + 1 xm+am′′,m+ 1 xm+ 1 + · · · +a′′mnxn =b′′m

0 x 1 + 0 x 2 + · · · + 0 xm−f

+c′′m+ 1 xm+ 1 + · · · +c′′mnxn = −f 0 ′′

(3.21)

wherea′′ij,c′′j,b′′i, andf 0 ′′are constants. Notice that (−f)is treated as a basic variable

in the canonical form of Eqs. (3.21). The basic solution that can readily be deduced

from Eqs. (3.21) is

xi =bi′′, i = 1 , 2 ,... , m

f =f 0 n

xi = 0 , i =m+ 1 , m+ 2 ,... , n

(3.22)

If the basic solution is also feasible, the values ofxi, i= 1 , 2 ,... , n, are nonnegative

and hence

b′′i≥ 0 , i= 1 , 2 ,... , m (3.23)

In phase I of the simplex method, the basic solution corresponding to the canonical form

obtained after the introduction of the artificial variables will be feasible for the auxiliary

problem. As stated earlier, phase II of the simplex method starts with a basic feasible

solution of the original linear programming problem. Hence the initial canonical form

at the start of the simplex algorithm will always be a basic feasible solution.

We know from Theorem 3.6 that the optimal solution of a linear programming

problem lies at one of the basic feasible solutions. Since the simplex algorithm is

intended to move from one basic feasible solution to the other through pivotal oper-

ations, before moving to the next basic feasible solution, we have to make sure that

the present basic feasible solution is not the optimal solution. By merely glancing at

the numbersc′′j, j= 1 , 2 ,... , n, we can tell whether or not the present basic feasible

solution is optimal. Theorem 3.7 provides a means of identifying the optimal point.

3.9.1 Identifying an Optimal Point

Theorem 3.7A basic feasible solution is an optimal solution with a minimum objec-

tive function value off 0 ′′if all the cost coefficientsc′′j,j=m+ 1 ,m+ 2 ,... , n, in

Eqs. (3.21) are nonnegative.

Proof: From the last row of Eqs. (3.21), we can write that

f 0 ′′+

∑n

i=m+ 1

c′′ixi=f (3.24)