Page 76 - 35Linear Algebra

76 The Simplex Method

Example 39 Maximize f(x, y, z, w) = 3x − 3y − z + 4w subject to constraints

c 1 := x + y + z + w = 5
c 2 := x + 2y + 3z + 2w = 6 ,

where x ≥ 0, y ≥ 0, z ≥ 0 and w ≥ 0.

The key observation is this: Suppose we are trying to maximize f(x 1 , . . . , x n )
subject to a constraint c(x 1 , . . . , x n ) = k for some constant k (c and k would
be the entries of Mx and v, respectively, in the above). Then we can also
try to maximize
f(x 1 , . . . , x n ) + αc(x 1 , . . . , x n )

because this is only a constant shift f → f + αk. Choosing α carefully can
lead to a simple form for the function we are extremizing.

Example 40 (Setting up an augmented matrix):
Since we are interested in the optimum value of f, we treat it as an additional
variable and add one further equation

−3x + 3y + z − 4w + f = 0 .

We arrange this equation and the two constraints in an augmented matrix


 
1 1 1 1 0 5  c 1 = 5

 
1 2 3 2 0 6  ⇔ c 2 = 6 .


−3 3 1 −4 1 0  f = 3x − 3y − z + 4w
Keep in mind that the first four columns correspond to the positive variables (x, y, z, w)
and that the last row has the information of the function f. The general case is depicted
in figure 3.1.

Now the system is written as an augmented matrix where the last row
encodes the objective function and the other rows the constraints. Clearly we
can perform row operations on the constraint rows since this will not change
the solutions to the constraints. Moreover, we can add any amount of the
constraint rows to the last row, since this just amounts to adding a constant
to the function we want to extremize.

76