See PDF version.
See PDF version.
See PDF version.
See PDF version.
\left [\array{
7 & 2 & 6
\cr
-14&-4&-12
} \right ],
|
adding twice the first row to the second produces
\left [\array{
7&2&6
\cr
0&0&0
} \right ].
|
Hence both lines are the same, and the solution set consists of all points on the line 7x + 2y = 6.
\left [\array{
1& -4 &2
\cr
4&-16&8
} \right ].
|
Subtracting four times the first row from the second yields
\left [\array{
1&-4&2
\cr
0& 0 &0
} \right ].
|
Again, these lines are the same, and the solution set consists of all points on the line x - 4y = 2.
\left [\array{
3& 2 & 1 & 8
\cr
2&-3& 2 &-16
\cr
1& 4 &-1& 20
} \right ]
|
Now rearrange to make cancellation easier by hand:
\left [\array{
1& 4 &-1& 20
\cr
2&-3& 2 &-16
\cr
3& 2 & 1 & 8
} \right ]
|
(Note: If using a computer or calculator, you really should rearrange so you
always divide by the largest magnitude entry remaining in the column. Here, I
would not have altered the order. But this happens to be all-integer if you chose
the correct operations.)
Now subtract the first row from the two remaining rows:
\left [\array{
1& 4 &-1& 20
\cr
0&-11& 4 &-56
\cr
0&-10& 4 &-52
} \right ]
|
Next, recognize that - 10 --11 = 1 and subtract the second row from the last row:
\left [\array{
1& 4 &-1& 20
\cr
0&-11& 4 &-56
\cr
0& 1 & 0 & 4
} \right ]
|
Swap rows to place the second column’s 1 in the second row:
\left [\array{
1& 4 &-1& 20
\cr
0& 1 & 0 & 4
\cr
0&-11& 4 &-56
} \right ]
|
Add - 11 times the second row to the last:
\left [\array{
1&4&-1& 20
\cr
0&1& 0 & 4
\cr
0&0& 4 &-12
} \right ]
|
Now divide the last by four:
\left [\array{
1&4&-1&20
\cr
0&1& 0 & 4
\cr
0&0& 1 &-3
} \right ]
|
Eliminate along the last column by adding the last row to the first:
\left [\array{
1&4&0&17
\cr
0&1&0& 4
\cr
0&0&1&-3
} \right ]
|
And eliminate the rest of the second column by subtracting four times the second row from the first:
\left [\array{
1&0&0& 1
\cr
0&1&0& 4
\cr
0&0&1&-3
} \right ]
|
This gives the solution \mathbf{(1,4,-3)}.
\left [\array{
-3&1&-1&-10
\cr
-4&2& 3 & -1
\cr
2 &3&-2& -5
} \right ]
|
Again, if you chose the order correctly, all arithmetic will be with integers. But this time I’ll perform the operations in the sensible numerical order. First, swap the first two rows to place the largest magnitude entry, - 4, at the top:
\left [\array{
-4&2& 3 & -1
\cr
-3&1&-1&-10
\cr
2 &3&-2& -5
} \right ]
|
Now divide the first row by four:
\left [\array{
1 &-0.5&-0.75&0.25
\cr
-3& 1 & -1 &-10
\cr
2 & 3 & -2 & -5
} \right ]
|
Subtract multiples of the first row from the others ( - 3 for the second row, 2 for the third):
\left [\array{
1&-0.5&-0.75& 0.25
\cr
0&-0.5&-3.25&-9.25
\cr
0& 4 & -0.5 & -5.5
} \right ]
|
Swap the second and third rows:
\left [\array{
1&-0.5&-0.75& 0.25
\cr
0& 4 & -0.5 & -5.5
\cr
0&-0.5&-3.25&-9.25
} \right ]
|
Divide the second row by four:
\left [\array{
1&-0.5& -0.75 & 0.25
\cr
0& 1 &-0.125&-1.375
\cr
0&-0.5& -3.25 & -9.25
} \right ]
|
Subtract - 0.5 times the second row from the third:
\left [\array{
1&-0.5& -0.75 & 0.25
\cr
0& 1 & -0.125 & -1.375
\cr
0& 0 &-3.3125&-9.9375
} \right ]
|
Divide the third row by - 3.3125:
\left [\array{
1&-0.5& -0.75 & 0.25
\cr
0& 1 &-0.125&-1.375
\cr
0& 0 & 1 & 3
} \right ]
|
Subtract - 0.125 times the third row from the second:
\left [\array{
1&-0.5&-0.75&0.25
\cr
0& 1 & 0 & -1
\cr
0& 0 & 1 & 3
} \right ]
|
Now subtract - 0.5 times the second row and - 0.75 times the third row from the first:
\left [\array{
1&0&0& 2
\cr
0&1&0&-1
\cr
0&0&1& 3
} \right ]
|
This gives the solution (2,-1,3).
Note: Solving that last problem in an environment like Octave is slightly easier:
There is a lot of work in making that magic \ operator function correctly.
See PDF version.
See PDF version.
Point | Value |
(0,0) | 0 |
(0,2) | 4 |
(3,0) | 15 |
(0,6) | 12 |
(1.5,0) | 7.5 |
(1.2,1.2) | 8.4 |
We could draw the graph to determine which vertices are in the feasible region. Alternately, we can test points against all the inequalities, beginning with the largest value and working downwards. The point (3,0) does not satisfy 4x + y ≤ 6 and is not feasible. The point (0,6) does not satisfy 2x + 3y ≤ 6 and is not feasible. The point (1.2,1.2) satisfies all the inequalities, so the largest value is 8.4 occuring at \mathbf{(1.2,1.2)}.
Point | Value |
(0,0) | 0 |
(10,0) | 10 |
(4,0) | 4 |
(0,10) | 30 |
(20∕3,10∕3) | 50∕3 |
(10∕3,5∕3) | 25∕3 |
Now check points from the least value upwards. (0,0) does not satisfy 5x + 2y ≥ 20. (4,0) does not satisfy 2y ≥ x. (10∕3,5∕3) satisfies every constraint. Thus the minimal value is \mathbf{25∕3} at point \mathbf{(10∕3,5∕3)}.