Recitation 2

Example 1: Consider the following simplex tableau:

$x_1$ $x_2$ $x_3$ $s_1$ $s_2$ $s_3$
-2 1 4 1/2 0 0 24
3 0 3 -3/2 1 0 9
2 0 -1 -1 0 1 8
-4 0 -5 3 0 0 64

The basic feasible solution corresponding to this tableau is

$$x_1 = 0, x_2 = 24, x_3=0, s_1 = 0, s_2 = 9, s_3 = 8.$$

If $x_1$ is made a basic variable, the replacement quantities are

$$9/3 = 3, 8/2 = 4.$$

Note that only a row having a positive entry in the column of the entering variable will produce a replacement quantity.

The 3 in row 2 column 1 will be the pivot. The next tableau is

$x_1$ $x_2$ $x_3$ $s_1$ $s_2$ $s_3$
0 1 6 -1/2 2/3 0 30
1 0 1 -1/2 1/3 0 3
0 0 -3 1/2 -2/3 1 2
0 0 -1 1 4/3 0 76

The solution is not optimal because one entry in the objective row is negative.

Example 2 (Degenerate linear program): A solution to linear program is said to be degenerate if one of the basic variables is 0.

Maximize: $50x_1 + 40x_2$; Subject to: $3x_1 + 2x_2 \le 120, x_1 + 6x_2 \le 120, 2x_1 + x_2 \le 80, x_1 \ge 0, x_2 \ge 0$.

The simplex tableau is

$x_1$ $x_2$ $s_1$ $s_2$ $s_3$
3 2 1 0 0 120
1 6 0 1 0 120
2 1 0 0 1 80
-50 -40 0 0 0 0

Choose $x_1$ as the entering variable, the replacement quantities are

$$120/3 = 40, 120/1 = 120, 80/2 = 40.$$

Entry 3 in row 1 column 1 will the pivot. The next tableau is

$x_1$ $x_2$ $s_1$ $s_2$ $s_3$
1 2/3 1/3 0 0 40
0 16/3 -1/3 1 0 80
0 -1/3 -2/3 0 1 0
0 -20/3 50/3 0 0 2000

Since a basic variable $s_3 = 0$, the basic solution is degenerate.

Choose $x_2$ as the entering variable, the replacement quantities are

$$40/(2/3) = 60, 80/(16/3) = 15.$$

Entry 16/3 in row 2 column 2 will be the pivot. The next tableau is

$x_1$ $x_2$ $s_1$ $s_2$ $s_3$
1 0 3/8 -1/8 0 30
0 1 -1/16 3/16 0 15
0 0 -11/16 1/16 1 5
0 0 65/4 5/4 0 2100

The basic solution $x_1 = 30, x_2 = 15, s_1 = 0, s_2 = 0, s_3 = 5$ is optimal and unique.