# 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.