Principles of Mathematics in Operations Research

Solutions 255

where Af = {xi,si,X3,X4}. Then, Bland's rule (lexicographical order)

marks the first variable. Since the reduced cost of xi is negative and xi is

at its upper bound; as X\ is decreased, z is increased. Hence, X\ enters.

0

0

0

<

Si

x 2

«3

=

1

7

11

-1

1

0

a <

00

10

CO

a < 6 — 1 = 5(bounds of x\)

=>a = min{l,10-7,5} = 1.

Thus, s\ leaves.

4.

B = {__,__, s 3 } => B =

1 20

1 10

001

=*B~l =

-1 20

1 -10

0 01

xB =

Xi

x 2

S3

-1 2 0"

1 -10

0 0 1

'30'

13

20

-1 2 0"

1 -1 0

0 01

"1035]

0100

0034

O O CO O

-4

17

20

1 2-3-5"

1-13 5

0 0 3 4

"0"

0

3

0

—

-4

17

20

-9

9

9

=

5

8

11

z = (2,3,0)

5

8

11

(0,0,1,4) (10 + 24) + 3 = 37.

c;-4r^1 iV=(0,0,l,4)-(2,3,0)

-1 2-3-5

1-13 5

0 0 3 4

= (0,0,1,4) - (1,1,3,5) = (-1,-1,-2,-1),

where Af = {s\, s 2 ,xz,Xi). All of the reduced costs are negative for all

the nonbasic variables that all are at their lower bounds. Hence, x* =

(xi,X2,X3,X4)T = (5,8,3,0)T is the optimum solution, where z* = 37.

b)(P):
max 2xi + 3x2 + x$ + 4x4
s.t.

xi + 2x2 + 3x 3 + 5x 4 < 30 (j/i)

xi+x 2 < 13 (y 2 )