Simplex algorithm method

From Wikipedia, the free encyclopedia

This article deals with one of many methods for solving a linear programming problem using the simplex algorithm. For a formal definition of the method and an explanation of why it works, refer to the simplex algorithm page. This article will use an example linear programming problem to work through the algorithm.

1 The initial problem
2 Slack variables
3 Simplex tableaux
4 The optimality condition
5 Choosing a pivot
6 Creating a new tableau
7 Repeat the pivoting process

[edit] The initial problem

The initial problem is described as follows:

Maximise $Z = 4x+3y \,$

subject to the constraints

$4x+y \le 3$
$2x+3y \le 4$
$x\ge0, y\ge0. \,$ (standard non-negativity constraints)

[edit] Slack variables

Introduce slack variables which represent unused capacity in the constraints:

$4x+y+s=3 \,$
$2x+3y+t=4 \,$
$x\ge0, y\ge0, s\ge0, t\ge0. \,$

Rewrite the objective to get the (ideal) objective function (i.e. all excess capacity used):

$\begin{matrix} & 4x & + & 3y & + & 0s & + & 0t & = & Z \\ Z \ - & 4x & - & 3y & - & 0s & - & 0t & = & 0 \end{matrix}$

[edit] Simplex tableaux

This application of the simplex algorithm uses tables, called tableaux, to represent calculations and intermediate steps to completing a problem. The first step is to form an initial tableau. We have four variables: x, y, s, t, and two equations. Therefore, we have to set two variables to zero to solve them.

The variables set to zero are called non-basic variables.
The variables not set to zero are called basic variables.

For the initial tableau, the basic variables are always the slack variables. The initial tableau is set up as follows:

Basic variable	x	y	s	t	Value
+Tableau I
s	4	1	1	0	3
t	2	3	0	1	4

Z	-4	-3	0	0	0

The first row represents the first constraint
The second row represents the second constraint
The third row represents the objective function

Notice that the basic variables appear only in one row, and only with a coefficient of one, and in their column, all other entries read zero.

This tableau represents the solution $x=0, y=0, s=3, t=4, Z=0\,$ . To find these values, the first and last columns are read off:

$s = 3$
$t = 4$
$Z = 0$

We know x and y are zero because they are non-basic variables.

[edit] The optimality condition

A tableau represents an optimal solution if:

The objective row contains zero entries in the columns of basic variables
The objective row contains no negative entries in the columns of non-basic variables

Tableau I does not satisfy this condition so the solution is not optimal. We therefore modify this tableau to give a second one corresponding to another vertex of the linear program's feasible region.

[edit] Choosing a pivot

We need to find a non-basic variable to become a basic variable and also the basic variable to replace with this non-basic variable. To find the new basic variable, select the column with the most negative entry in the objective row. In Tableau I, this is the 'x' column with -4. This is called the pivotal column

In order to find the basic variable being replaced, we calculate $θ$ values for each row (except the objective row). $θ$ is given by the entry in the 'value' column divided by the entry in the pivotal column.

For the first row:

$\theta=\frac{3}{4}=\frac{3}{4} \,$

For the second row:

$\theta=\frac{4}{2}=2 \,$

The pivotal row is then taken to be the smallest of these $θ$ values. The pivot is found at the intersection of the pivotal row and the pivotal column. It is usually ringed or shown in bold:

Basic variable	x	y	s	t	Value
+Tableau I with pivot
s	4	1	1	0	3
t	2	3	0	1	4

Z	-4	-3	0	0	0

[edit] Creating a new tableau

The first step to tableau II is to divide the pivotal row by the pivot so the pivot now reads 1:

Basic variable	x	y	s	t	Value
s	1	$\frac{1}{4}$	$\frac{1}{4}$	0	$\frac{3}{4}$
t	2	3	0	1	4

Z	-4	-3	0	0	0

The next step is to add or subtract multiples of this new row from the other rows in the tables, so that they read zero, as they should for a basic variable.

For the second row (the t row), subtract 2 x Row 1 (the s row):

Basic variable	x	y	s	t	Value
s	1	$\frac{1}{4}$	$\frac{1}{4}$	0	$\frac{3}{4}$
t	0	2.5	-0.5	1	2.5

Z	-4	-3	0	0	0

For the third row (the Z row), add 4 x Row 1 (the s row):

Basic variable	x	y	s	t	Value
s	1	$\frac{1}{4}$	$\frac{1}{4}$	0	$\frac{3}{4}$
t	0	2.5	-0.5	1	2.5

Z	0	-2	1	0	3

The final step is to replace the old basic variable with the new:

Basic variable	x	y	s	t	Value
+Tableau II
x	1	$\frac{1}{4}$	$\frac{1}{4}$	0	$\frac{3}{4}$
t	0	2.5	-0.5	1	2.5

Z	0	-2	1	0	3

This tableau represents the solution where $t=2.5, x=\frac{3}{4}, y=0, s=0, Z=3 \,$ However, there is still a negative value in the objective row, so this solution is not optimal either. Therefore a third tableau is needed.

[edit] Repeat the pivoting process

The pivotal column is the one with −2 in the objective row, which is 'y'.

The pivotal row is the one with the smallest $θ$ value:

For the first row:

$\theta=\frac{\frac{3}{4}}{\frac{1}{4}}=3 \,$

For the second row:

$\theta=\frac{2\frac{1}{2}}{2\frac{1}{2}}=1 \,$

Therefore, the pivot is the intersection of the t-row and the y-column.

Now divide the pivotal row by the pivot:

Basic variable	x	y	s	t	Value
x	1	$\frac{1}{4}$	$\frac{1}{4}$	0	$\frac{3}{4}$
t	0	1	-0.2	0.4	1

Z	0	-2	1	0	3

Then, add or subtract multiples of this row to the remaining rows:

Row 1: Subtract 1/4 × Row 2

Row 3: Add 2 × Row 2

Then, replace the basic variable:

Basic variable	x	y	s	t	Value
+Tableau III
x	1	0	0.3	-0.1	0.5
y	0	1	-0.2	0.4	1

Z	0	0	0.6	0.8	5

This tableau represents the solution where $x=0.5, y=1, s=0, t=0, Z=5 \,$ . It is an optimal solution, as there exist no negative basic variables and all non-basic variables are zero.