Principles of Mathematics in Operations Research

246 Solutions

Problems of Chapter 8

8.1

a) We have six variables and three constraints, therefore we have ( 3 )

candidate bases.

X\ X 2 X 3 Si S 2 S 3

2 10 10 0

0 0 10 1 0

0 10 0 0-1

= 20

A =

Bi = {x 1 ,x 2 ,x 3 }, B 2 = {xi,x 2 ,si}, B 3 = {xi,x 2 ,s 2 }, B 4 = {xi,x 2 ,s 3 },
B 5 = {xi,x 3 ,si}, B 6 = {xi,x 3 ,s 2 }, B 7 = {21,2:3,53}, J5 8 = {x 1 ,s 1 ,s 2 },
BQ = {xi,si,s 3 }, Bw = {xi,s 2 ,s 3 }, Bn - {x 2 ,x 3 ,si}, BX2 = {x 2 ,x 3 ,s 2 },
B\ 3 = {x 2 ,x 3 ,s 3 }, B 14 = {x 2 ,si,s 2 }, B15 = {x 2 ,si,s 3 }, B 16 = {x 2 ,s 2 ,s 3 },
Bn = {x 3 ,s 1 ,s 2 }, B1S = {x 3 ,si,s 3 }, B 19 = {x 3 ,s 2 ,s 3 }, B 20 = {si,s 2 ,s 3 }.
B 2 , B4, B$, BQ, Bg, BQ, B\ 2 , S15, Bn, Big are not bases since they form sin-
gular matrices. Br,Bio,Bis,B 20 are infeasible since they do not satisfy non-
negativity constraints. Thus, what we have is
(xi, x 2 , x 3 , si, s 2 , s 3 )T = (3,2,10,0,0,0)T from Bx •-> point F,
{xi,x 2 ,x 3 , si,s 2 , s 3 )T = (3,2,0,0,10,0)T from B 3 <->• point C,
(xx,x 2 , x 3 , si,s 2 , s 3 )T = (0, 2,10, 6, 0, 0)T from Blx <-> point E,
(x 1 ,x 2 ,x 3 ,s 1 ,s 2 ,s 3 )T = (0,8,10,0,0, 6)T from B 13 '-> point D,
(xi,x 2 ,x 3 ,S!,s 2 ,s 3 )T = (0,2,0,6,10,0)r from Bu <-» point B,
(xi,x 2 ,x 3 ,si,s 2 ,s 3 )T = (0,8,0,0,10,6)T from Bi6 <->• point A.
See Figure S.12.

xN (x^1 ,s^2 ,s^3 )

T. Then,

101

010

001

=>B~

b)

1. matrix form:
   Let xB = (si,x 3 ,x 2 )T,

B =

xB = B-Xb

We are on point E.

z = cTBxB = [Q,2, 2]

cTN-cTBB-lN= [1,0,0] -[0,2,2]

"10-

01

00

-1"

0

1

"10-1"

0 1 0

00 1

' 8"

10

2

=

" 6"

10

2

6

10

2

= 24.

"10-1"

0 1 0

00 1

"2 0 0"

01 0

0 0-1

= [1,-2,2].