Homework 1 Key
1. We start with the system x1 x2 + 2x3 = 4
2x1 2x2 + 3x3 + x4 = 9 x2 + 2x3 + 2x4 = 2
3x1 2x2 + 7x3 + 3x4 = 15 or in matrix form
2
664
1 1 2 0 4
2 2 3 1 9
0 1 2 2 2
3 2 7 3 15
3
775
:
Then perform the following steps of the Gauss-Jordan elimination.
1
2 r2; 1
2 r3; 1
3 r4
!
2
664
1 1 2 0 4
1 1 3=2 1=2 9=2
0 1=2 1 1 1
1 2=3 7=3 1 5
3
775 r1+r2 !
2
664 1
1 2
0
4
0 0 1=2 1=2 1=2
0 1=2 1 1 1
1 2=3 7=3 1 5
3
775 r1+r4 !
2
664
1 1 2 0 4
0 0 1=2 1=2 1=2
0 1=2 1 1 1
0 1=3 1=3 1 1
3
775
1
3 r3+r4
!
2
664
1 1 2 0 4
0 0 1=2 1=2 1=2
0 1=2 1 1 1
0 1=6 0 2=3 2=3
3
775
1
2 r3+r2
!
2
664
1 1 2 0 4
0 1=4 0 1 1
0 1=2 1 1 1
0 1=6 0 2=3 2=3
3
775
2r3+r1 !
2
664
1 2 0 2 2
0 1=4 0 1 1
0 1=2 1 1 1
0 1=6 0 2=3 2=3
3
775
3
2 r4
!
2
664
1 2 0 2 2
0 1=4 0 1 1
0 1=2 1 1 1
0 1=4 0 1 1
3
775 r4+r3 !
2
664
1 2 0 2 2
0 1=4 0 1 1
0 1=4 1 0 0
0 1=4 0 1 1
3
775 r4+r2 !
2
664
1 2 0 2 2
0 0 0 0 0
0 1=4 1 0 0
0 1=4 0 1 1
3
775
2r4+r1 !
2
664
1 3=2 0 0 4
0 0 0 0 0
0 1=4 1 0 0
0 1=4 0 1 1
3
775
1
From here we deduce that, x1 = 4 + 3=2x2, x3 = x2=4 and x4 = 1 x2=4 describes the in nitely many solutions of this system. We can obtain feasible x1, x3 and x4 for any given value of x2.
2.
max 3x1 + 4x2 + x3 + x4 s:t x1 = 4 + 3x3 x4 x2 = 6 2x3 2x4
a. When x3 and x4 are equal to 0, we obtain x1 = 4 and x2 = 6. These values of the variables yield the objective value 36.
b. When x3 =
and x4 = 0, we obtain x1 = 4+3
and x2 = 62
. This solution gives the objective value 36 + 2
.
c. x1 = 4 + 3
as
increases x1 increases, it never goes to zero therefore we can choose

= 1. x2 = 6 2
as
increases x2 decreases at a rate of 2, therefore we can choose

= 3 at which point x2 will become 0. The new solution is x1 = 13, x2 = 0, x3 = 3 and x4 = 0.
d. Currently, the