Recitation 2 – Discrete Thoughts

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.