Homework #2 Solutions, Due: Thursday, March 8, 2007

 

x1 x2 x3 -1  
-2 3 -1 -9 = -x4
2 -2 5 0 = -x5
4 3 -7 5 --> max

Choose -1 in Row 1, Column 3 as the Pivot Entry to avoid fractions:

x1 x2 x4 -1  
2 -3 -1 9 = -x3
-8 13 5 -45 = -x5
18 -18 -7 68 --> max

Two choices for Pivot Entry: 2 in Row 1 or -8 in Row 2.

Compare each (Bi/Ai):

(-45/-8) = 5.625

9/2 = 4.5

5.625 > 4.5, So choose 2 as the Pivot Entry:

x3 x2 x4 -1  
1/2 -3/2 -1/2 9/2 = -x1
4 1 1 -9 = -x5
-9 9 2 -13 --> max

Row 2 is a Bad Row, therefore the LP is infeasible.