Principles of Mathematics in Operations Research

250 Solutions

5. revised simplex with B = QR decomposition:

Let XB = (si,x 3 ,x 2 )T, XN = (xi,s 2 ,s 3 )T. Then, B

101

010

001

is upper

triangular, Q = I 3. The rest is the same as above, s 3 enters and si leaves.

B =

001'

010

-10 1

=

"00 1'

0 1 0

-100

"10-1"

01 0

00 1

= QR.

In order to solve BxB = QRxB = b = (8,10,2)r = Q(RxB) = Qb',

b' 3 = 8, b' 2 = 10, &i = -2 =*• x 2 = 8, x 3 = 0, s 3 = x 2 - 2 = 6.

In order to solve wB = c^, first solve wQR — cB = w'R.

w[ - 0, w' 2 = 2, w 3 = 2 + wi = 2.

Then, solve wQ = w'

W3 =0, w 2 = 2, wi = 2.

The rest is the same.

c)

(D):

Min w =8yi + I0y 2 - 2y 3

s.t.

2?/i > 1

2/1 - 2/3 > 2

2/2 > 2

2/1,2/2,2/3 > 0.

See Figure S.12.
8.2 The second constraint is redundant whose twice is exactly the last con-
straint plus the nonnegativity of x. Then,

A =

Xi X 2 X 3 Si S3

2 -1 -1 -1 0

1-2 2 0-1

a) The bases are
Bi = {xi,x 2 }, B 2 = {xi,x 3 }, B 3 = {xi,«i}, B 4 = {xi,s 3 }, B 5 = {x 2 ,x 3 },
B 6 = {x 2 , Si}, B 7 = {x 2 , s 3 }, B 8 = {x 3 , si}, B 9 = {x 3 , s 3 }, Bw = {si, s 3 }.
All bases except B 2 ,B 3 yield infeasible solutions since they do not satisfy
the nonnegativity constraints. Thus, (xi,x 2 ,x 3 , Si,s 3 )T = (2,0,1,0,0)r from
B 2 , and (xi,x 2 ,x 3 ,S!, s 3 )T = (4,0,0, 5, 0)T from B 3.