Simplex Method

Usage notes

A linear program can be put into several different forms.
We present a conditional maximization problem as follows:

Find x, y >= 0 subject to the constraints



y <= 2





5x + 2y <= 7





5x +  y <= 6

such that the objective function



f(x,y) = x + y

is maximized.
These inequality can be transformed into equations by introducing additional slack variables u, v, w >= 0 and writing:



y - 2 = -u





5x + 2y - 7 = -v





5x +  y - 6 = -w

Often special notations are used for linear programs. One of the common notations for this type of problem is the annoted table.

x	y	-1
0	1	2	= -u
5	2	7	= -v
5	1	6	= -w
1	1	0	= f

Notice that with this table it is always implicit that x, y, u, v, w >= 0 and that the function f should be maximized.

a)

Each of the equations x = 0, y = 0, ..., w = 0 defines a straight line in the xy-plane and together the inequality x, y, ..., w >= 0 restricts the feasible region R (i. e. the subset of points (x,y) for which all inequalities are satisfied). The following picture should make clear the situation:

i)

Can the optimal feasible vector be somewhere in the interior, away from the boundaries?
Yes

No

ii)

With the aid of the picture find x and y, so that f(x,y) is maximal.
x = ___________________ y = ___________________ f(x,y) = ___________________

b)

The simplex algorithm starts with a table associated with a feasible point x = y = 0 and then walks from one vertex of the feasible region R to another, while the value of f is not decreasing. Each vertex of R is determined by setting two of the five variables x, y, u, v, w to zero.
For the above picture, let us use the possible path of the algorithm:
(x = 0, y = 0) -> (w = 0, y = 0) -> (w = 0, v = 0) -> (u = 0, v = 0)

i)

Starting with the table

x	y	-1
0	1	2	= -u
5	2	7	= -v
5	1	6	= -w
1	1	0	= f

perform the first step of the simplex algorithm

w	y	-1
___________________	___________________	___________________	= -u
___________________	___________________	___________________	= -v
___________________	___________________	___________________	= -x
___________________	___________________	___________________	= f

ii)

Perform the second step of the simplex algorithm

w	v	-1
___________________	___________________	___________________	= -u
___________________	___________________	___________________	= -y
___________________	___________________	___________________	= -x
___________________	___________________	___________________	= f

iii)

Perform the third step of the simplex algorithm

u	v	-1
___________________	___________________	___________________	= -w
___________________	___________________	___________________	= -y
___________________	___________________	___________________	= -x
___________________	___________________	___________________	= f

c)

If we are interested only in the solution, then we can set u = v = 0 and get a linear system: Ax = b:

Determine the matrix A and the vector b from the start table. Use them to compute the coordinates x and y of the solution and the maximum of f.

A =
___________________ ___________________
___________________ ___________________

b =
___________________
___________________

x = ___________________ y = ___________________ f(x,y) = ___________________

Home

Feedback to quiz developers, problem reports...please use it!!!

Name:
	Restore previous session, if applicable Start blank quiz
Note:	If you wish to ask for a hint or a solution, or if you want your answers checked, you have to log in. Your answers, or the fact that you asked for a hint or solution, may be recorded.