Numerical Methods and Optimization

The Simplex Method for Linear Programming 275

and the entering variable is the first nonbasic variable, which is x

1

.

Choosing the leaving variable. To perform the ratio test, we only need

˜x

B

and the first column

˜

N

x

1

of the matrix

˜

N = B

−1

N, which is equal to

˜

N

x

1

= B

−1

× N

x

1

.

We can find v =

˜

N

x

1

by solving the system Bv = N

x

1

for v:

⎡

⎣

220

040

141

⎤

⎦

⎡

⎣

v

1

v

2

v

3

⎤

⎦

=

⎡

⎣

1

3

2

⎤

⎦

⇔ v =

⎡

⎣

−1/4

3/4

−3/4

⎤

⎦

.

We compare the ratios of components of ˜x

B

and

˜

N

x

1

= v:

˜

N

x

1

˜x

B

ratios x

B

⎡

⎣

−1/4

3/4

−3/4

⎤

⎦

⎡

⎣

1/2

3/2

3/2

⎤

⎦

−

2

−

⎡

⎣

x

2

x

3

x

6

⎤

⎦

⇒ x

3

wins.

Updating the basic feasible solution. Next, we update ˜x

B

:

˜x

1

= 2 (min ratio value)

˜x

2

=1/2+(1/4)2 = 1

˜x

6

=3/2+(3/4)2 = 3.

The output of step 3 is given by:

x

B

=

⎡

⎣

x

1

x

2

x

6

⎤

⎦

,c

B

=

⎡

⎣

4

3

0

⎤

⎦

,B=

⎡

⎣

120

300

211

⎤

⎦

, ˜x

B

=

⎡

⎣

2

1

3

⎤

⎦

,

x

N

=

⎡

⎣

x

3

x

4

x

5

⎤

⎦

,c

N

=

⎡

⎣

5

0

0

⎤

⎦

,N=

⎡

⎣

210

401

400

⎤

⎦

.

Step 4. W