# Thread: Simplex Algorithm

1. ## Simplex Algorithm

I dont understand what to do with this.

1) Represent the linear programing problem below by an initial Simplex Tableau

Maximise P=15x-4y-4z

Subject to 10x-4y+8z <(or equal to) 40
10x+6y+9z <(or equal to) 72
-6x+4y+3z<(or equal to) 48

and x>(or equal to) 0, y> (or equal to) 0, z> (or equal to) 0

2) perform one iteration of the simplex algorithm and write down the values of x,y, z and P that result from the iteration

3) Perform one further iteration of the simplex algorithm and find the values of x, y, z and P at the optimum point

2. Originally Posted by xxchloe741xx
I dont understand what to do with this.

1) Represent the linear programing problem below by an initial Simplex Tableau

Maximise P=15x-4y-4z

Subject to 10x-4y+8z <(or equal to) 40
10x+6y+9z <(or equal to) 72
-6x+4y+3z<(or equal to) 48

and x>(or equal to) 0, y> (or equal to) 0, z> (or equal to) 0

2) perform one iteration of the simplex algorithm and write down the values of x,y, z and P that result from the iteration

3) Perform one further iteration of the simplex algorithm and find the values of x, y, z and P at the optimum point
1) Step 1. Introduce slack variables and restate the problem in terms of a system of linear equations.

This gives the equations

$\displaystyle \begin{array}{ll}10x - 4y + 8z + u &= 40,\\ 10x+6y+9z\phantom{{}+u} +v &= 72,\\ -6x+4y+3z \phantom{+u+v} +w &= 48.\end{array}$

Also, the objective equation is $\displaystyle -15x+4y+4z+P=0$.

Step 2. Construct the simplex tableau corresponding to the system, with the bottom row of the matrix corresponding to the objective equation. The simplex tableau is a matrix whose columns represent the variables x,y,z,u,v,w,P, and the constants on the right-hand side of the equations.

This gives the simplex tableau

$\displaystyle \begin{bmatrix}10&-4&8&1&0&0&0&40\\ 10&6&9&0&1&0&0&72\\ -6&4&3&0&0&1&0&48\\ -15&4&4&0&0&0&1&0\end{bmatrix}$ .

For 2) and 3), the simplex algorithm works like this:

Step 3. (a) Choose the pivot column to be the one containing the most negative element on the bottom row of the matrix. (b) Choose the pivot element by computing ratios associated with the positive entries in the pivot column. The ratio is the element in the right-hand column divided by the corresponding element in the pivot column. The pivot element is the one corresponding to the smallest positive ratio. (c) Construct the new simplex tableau by pivoting about the selected element.

If you are supposed to be able to do this problem then presumably you have seen examples of the simplex algorithm in action, and you ought to be able to carry it out here, and to read off the values of x,y,z and P that it produces.