Numerical Methods and Optimization

306 Numerical Methods and Optimization: An Introduction

To compute v = B

−1

b

b

b, we solve the system Bv = b

b

b for v:

⎡

⎣

120

300

211

⎤

⎦

⎡

⎣

v

1

v

2

v

3

⎤

⎦

=

⎡

⎣

4+Δ

6

8

⎤

⎦

⇔

⎡

⎣

v

1

v

2

v

3

⎤

⎦

=

⎡

⎣

2

1+Δ/2

3 − Δ/2

⎤

⎦

, (12.30)

and v ≥ 0 if and only if −2 ≤ Δ ≤ 6. Thus, the basis consisting of x

1

,x

2

,

and x

6

will remain optimal if and only if −2 ≤ Δ ≤ 6. Next we consider two

concrete examples of the right-hand side change, one with Δ chosen within

the allowable interval, and the other one outside the interval.

First, consider Δ = −1 (which is within the interval [−2, 6]). Then from

(12.30) we have

x

∗

B

=

⎡

⎣

x

1

x

2

x

6

⎤

⎦

= B

−1

b

b

b =

⎡

⎣

2

1/2

7/2

⎤

⎦

,

so the optimal solution to (12.28) with Δ = −1is[x

1

,x

2

,x

3

]