Section 5-3

(10)
 
Consider the following system of inequalities:
5x1 + x2
≤ 35
4x1 + x2
≤ 32
x1
≥ 0
x2
≥ 0

Graph the system. Then introduce slack variables and convert this to a system of equations. Find the basic solutions and classify them as feasible or not feasible.

You already know how to graph such a system (if not, you need to learn!). There are four corner points (0,0), (0,32), (3,20), and (7,0). Here's a picture:

[Graphics:Images/5-3_gr_1.gif]

Now we change the problem constraints into a system of linear equations by introducing slack variables.
5x1 + x2 + s1   = 35
4x2 + x2   + s2 = 32

Just as was done in class (and in the text -- you're reading that, right?) we can set pairs of the variables equal to zero, and solve for the remaining two variables to get the basic solutions. There are six ways to set two of the variables equal to zero, as the following table suggests:

x1
x2
s1
s2
0
0
0
0
0
0
0
0
0
0
0
0

Remember, in each row, the variables set equal to 0 are called nonbasic variables. The remaining variables are called basic variables.By plugging each row back into the above system, we can solve for the basic variables and fill in the rest of the table. If any of the slack variables are negative, that means the point (x1, x2) is not feasible. Let's put it all in a table.

x1
x2
s1
s2
point (x1, x2)
feasible?
0
0
35
32
(0, 0)
yes
0
35
0
-3
(0, 35)
NO
0
32
3
0
(0, 32)
yes
7
0
0
4
(7, 0)
yes
8
0
-5
0
(8, 0)
NO
3
20
0
0
(3, 20)
yes

Now compare this table with the graph above. Marvel at how it all matches up.

The point of this exercise is to illustrate that it is not necessary to graph the feasible region in order to find corner points. In particular, this method would work even if there were more than 2 variables. In the next section the Simplex method will incorporate these ideas to achive a procedure for solving maximization problems with any number of variables.