Results 1 to 7 of 7

Math Help - Simplex Method Doubt

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    3

    Unhappy 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
    Last edited by miguelito; August 12th 2011 at 03:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Simplex Method Doubt

    Quote Originally Posted by miguelito View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Simplex Method Doubt

    Quote Originally Posted by miguelito View Post
    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}<br />
2 & 2 & 1 & 0 & 5   \\<br />
8 & 2 & 7 & 1 & 0 <br />
\end{array}\right]

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

    \left[\begin{array}{cccc|c}<br />
1 & \boxed{1} & 1/2 & 0 & 5/2   \\<br />
6 & 0 & 6 & 1 & -5 <br />
\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 .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2011
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Simplex Method Doubt

    Quote Originally Posted by miguelito View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Simplex Method Doubt

    Quote Originally Posted by miguelito View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simplex Method
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 24th 2011, 10:47 PM
  2. the simplex method
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: May 2nd 2010, 08:16 PM
  3. Simplex method help
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 22nd 2010, 04:40 PM
  4. Simplex Method
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 30th 2009, 10:45 AM
  5. Simplex method
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: November 23rd 2009, 11:03 PM

Search Tags


/mathhelpforum @mathhelpforum