# Simplex Method Doubt

• Aug 12th 2011, 01:51 PM
miguelito
Simplex Method Doubt
I'm learning the simplex method and solved some exercises but I'm having trouble solving simple exercises that already comes in standard form, example:

min z = 8x1 + 2x2 + 7x3
subject to:
2x1 + 2x2 + x3 = 5
x1 , x2 , x3 ≥ 0

The linear program is already in standart form.No need to add slack variables so how to solve the exercise with simplex algorithm?
On what basis I start the simplex?

The same problem occurs in the exercise below.

min z = x1 − 3x2 + 3x3
subject to:
x1 − 3x2 + 2x3 = 0
x1 + x2 + x3 = 1
x1 , x2 , x3 ≥ 0

Thanks
• Aug 12th 2011, 03:01 PM
FernandoRevilla
Re: Simplex Method Doubt
Quote:

Originally Posted by miguelito
min z = 8x1 + 2x2 + 7x3 subject to:
2x1 + 2x2 + x3 = 5
x1 , x2 , x3 ≥ 0

The problem is equivalent to find the minimum of $z=8x_1+2x_2+7(5-2x_1-2x_2)$ with the restrictions:

$\begin{Bmatrix}x_1\geq 0\\x_2\geq 0\\5-2x_1-2x_2\geq 0\end{matrix}$

i.e. you can use the graphic method in $\mathbb{R}^2$ .
• Aug 12th 2011, 03:21 PM
miguelito
Re: Simplex Method Doubt
Ohh thanks good solution but these exercises should be solved using the simplex algorithm and not a graphical method.

Any ideas using the tableau?
• Aug 12th 2011, 10:21 PM
FernandoRevilla
Re: Simplex Method Doubt
Quote:

Originally Posted by miguelito
Any ideas using the tableau?

The problem is equivalent to find the maximum of $w=-8x_1-2x_2-7x_3$ with the restrictions $2x_1+2x_2+x_3=5,x_1\geq 0,x_2\geq 0, x_3\geq 0$ :

$\left[\begin{array}{cccc|c}
2 & 2 & 1 & 0 & 5 \\
8 & 2 & 7 & 1 & 0
\end{array}\right]$

$\left[\begin{array}{cccc|c}
1 & \boxed{1} & 1/2 & 0 & 5/2 \\
8 & 2 & 7 & 1 & 0
\end{array}\right]$

$\left[\begin{array}{cccc|c}
1 & \boxed{1} & 1/2 & 0 & 5/2 \\
6 & 0 & 6 & 1 & -5
\end{array}\right]$

A basic feasible solution is $P=(x_1,x_2,x_3)=(0, 5/2,0)$ and $w(P)=-5$ . Besides, this a maximum solution. Why?. So, $z_{\min}(0,5/2,0)=-(-5)=5$ .

P.S. Forget those <br/>, I don't know what on earth mean in $\LaTeX$ code .
• Aug 14th 2011, 05:12 AM
miguelito
Re: Simplex Method Doubt
Thanks again, but what kind of rule you use to choose the initial basis(x2) for this type of exercise? Aleatory?
What rules to define the initial bases when the exercise is in the standard form?
In other exercises I always use the slack variables as the initial basis.
• Aug 14th 2011, 06:38 AM
FernandoRevilla
Re: Simplex Method Doubt
Quote:

Originally Posted by miguelito
Thanks again, but what kind of rule you use to choose the initial basis(x2) for this type of exercise? Aleatory?

Not exactly in an aleatory way. Notice that if we get the identity matrix ( $1\times 1$ in this case ) in the column corresponding to $x_2$ and we get a $0$ below the identity matrix then, the coefficients of $x_i\neq x_2$ in the last row are $\geq 0$ . According to a well-known theorem we obtain a maximum feasible basic solution.
• Aug 15th 2011, 01:14 AM
FernandoRevilla
Re: Simplex Method Doubt
Quote:

Originally Posted by miguelito
min z = x1 − 3x2 + 3x3 subject to:
x1 − 3x2 + 2x3 = 0
x1 + x2 + x3 = 1
x1 , x2 , x3 ≥ 0

As in my previous post, you'll find:

$\begin{bmatrix}{\;\boxed{1}}&{0}&{\;\;5/4}&{0}&{3/4}\\{\;0}&{\boxed{1}}&{-1/4}&{0}&{1/4}\\{\;0}&{0}&{\;\;\;1}&{1}&{0}\end{bmatrix}$

So, $w_{\max}(3/4,1/4,0)=0$ or equivalently $z_{\min}(3/4,1/4,0)=-0=0$ .