Simplex Method Doubt

**miguelito** · August 12th 2011, 01:51 PM

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

**FernandoRevilla** · August 12th 2011, 03:01 PM

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$ .

**miguelito** · August 12th 2011, 03:21 PM

Ohh thanks good solution but these exercises should be solved using the simplex algorithm and not a graphical method.

Any ideas using the tableau?

**FernandoRevilla** · August 12th 2011, 10:21 PM

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  , I don't know what on earth mean in $\LaTeX$ code .

**miguelito** · August 14th 2011, 05:12 AM

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.

**FernandoRevilla** · August 14th 2011, 06:38 AM

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.

**FernandoRevilla** · August 15th 2011, 01:14 AM

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$ .

Thread: Simplex Method Doubt

LinkBack

Thread Tools

Display

Simplex Method Doubt

Re: Simplex Method Doubt

Re: Simplex Method Doubt

Re: Simplex Method Doubt

Re: Simplex Method Doubt

Re: Simplex Method Doubt

Re: Simplex Method Doubt

Similar Math Help Forum Discussions

Simplex Method

the simplex method

Simplex method help

Simplex Method

Simplex method

Search Tags