Numerical Methods and Optimization

260 Numerical Methods and Optimization: An Introduction

The corresponding auxiliary problem was presented in (11.29) and is given by

(hereweusee

1

,e

2

, and s

3

instead of x

4

,x

5

,andx

6

for convenience):

maximize − a

1

− a

2

subject to −2x

1

+3x

2

+4x

3

− e

1

+ a

1

=12

3x

1

+2x

2

+ x

3

− e

2

+ a

2

=6

x

1

+ x

2

+ x

3

+ s

3

=9

x

1

,x

2

,x

3

,e

1

,e

2

,s

3

,a

1

,a

2

≥ 0.

We solve the Phase I LP using the simplex method in the tableau format.

Expressing the objective through nonbasic variables,

z = −a

1

− a

2

= −(12 + 2x

1

− 3x

2

− 4x

3

+ e

1

) − (6 − 3x

1

− 2x

2

− x

3

+ e

2

)

= −18 + x

1

+5x

2

+5x

3

− e

1

− e

2

,

we obtain the following step 0 tableau:

zx

1

x

2

x

3

e

1

e

2

s

3

a

1

a

2

rhs Basis

1 −1 −5 −51 1 000−18 z

0 −23 4−10 010 12 a

1

03 2 10−10 0 1 6 a

2