267 Pages

## Problem

Consider the LP problem:

\begin{align} Max \quad 2x -3y + z \\ x + y + z \le 10 \\ 4x - 3y + z \le 3 \\ 2x + y - z \le 10 \\ x, y, z \ge 0 \end{align}

Construct the initial tableau T1 and solve the tableau using the simplex method.

## Solution

Constructing the tableau

Introduce slack variables s1, s2, s3.

x y z s1 s2 s3 Z
s1 1 1 1 1 0 0 0 10
s2 4 -3 1 0 1 0 0 3
s3 2 1 -1 0 0 1 0 10
Z -2 3 -1 0 0 0 1 0

Pivot 1

To identify the entering variable, look at the row in the bottom (row 4 in this problem). Look for the most negative entry. This is, -2, found under column 1. Hence the entering variable is x. To select the entering variable, look the numbers on the far right and perform division calculations with respect to the entries under column 1.

$10/1 = 10$
$3/4 = 0.75$
$10/2 = 5$

Select the row with the smallest quotient (row 2). Hence the leaving variable is s2.

x y z s1 s2 s3 Z
s1 1 1 1 1 0 0 0 10
s2 4 -3 1 0 1 0 0 3
s3 2 1 -1 0 0 1 0 10
Z -2 3 -1 0 0 0 1 0

Now clear the other coefficients in column 1 using row-reduction methods. For this pivot, perform the following computations:

$4R_1 - R_2$
$2R_3 - R_2$
$2R_4 + R_2$

The tableau becomes

x y z s1 s2 s3 Z
s1 0 7 3 4 -1 0 0 37
x 4 -3 1 0 1 0 0 3
s3 0 5 -3 0 -1 2 0 17
Z 0 3 -1 0 1 0 2 3

Pivot 2

In tableau 2, column 3 of row 4 has the most negative entry, so z is the entering variable.

$37/3 = 12.333333$
$3/1 = 3$

Omit $17/-3$ because non-positive denominators are ignored. Since row 2 has the smallest quotient, x is the leaving variable.

x y z s1 s2 s3 Z
s1 0 7 3 4 -1 0 0 37
x 4 -3 1 0 1 0 0 3
s3 0 5 -3 0 -1 2 0 17
Z 0 3 -1 0 1 0 2 3

Now clear the other coefficients in column 3 using row-reduction methods. For this pivot, perform the following computations:

$R_1 - 3R_2$
$R_3 + 3R_2$
$R_4 + R_2$
x y z s1 s2 s3 Z
s1 -12 16 0 4 -4 0 0 28
z 4 -3 1 0 1 0 0 3
s3 12 -4 0 0 2 2 0 26
Z 4 0 0 0 2 0 2 6

There are no more negative entries in row 4! This means we are done! The maximum value can be calculated in to ways.

Method 1: Look at row 4 and the rightmost entry, then divide by the entry to its immediate left.

$Z = 6/2 = 3$

Method 2: Look at the variables in the rightmost column and look at the values associated with non-slack variables. For this tableau, we only have $z = 3$. This means $(x,y,z) = (0,0,3)$. Substitutes these values into the original objective function.

$Z = 2(0) - 3(0) + 3 = 3$
Community content is available under CC-BY-SA unless otherwise noted.