Results 1 to 2 of 2

Math Help - Linear programming

  1. #1
    ULB
    ULB is offline
    Newbie
    Joined
    Aug 2010
    Posts
    1

    Linear programming

    hi,
    can you help me solve this probleme or how to begin

    thk


    min 2x1 − x2 − x3
    scq x1 +x2 + x4 6
    2x1 +x3 8
    4x1 2x2 − x3 4
    xj0 j= 1,...,4
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by ULB View Post
    hi,
    can you help me solve this probleme or how to begin

    thk


    min 2x1 − x2 − x3
    scq x1 +x2 + x4 6
    2x1 +x3 8
    4x1 2x2 − x3 4
    xj0 j= 1,...,4
    As a special favour to you, here is a link to my foolproof instructions for solving linear programming problems by the simplex method. You can find them at http://www.maths.leeds.ac.uk/~pmt6ecl/simplex.pdf. Download that pdf file and follow the instructions there.

    To get you started, notice that your problem here is in what I call nonstandard form. So you need to start by following the procedure on page 2 of the pdf file. For a start, the objective function -2x_1 - x_2 - x_3 is to be minimised. So you should replace it by its negative, M = 2x_1 + x_2 + x_3, which you maximise (and the answer to the problem will then be the negative of that).

    Next, some of the inequalities have a \geqslant instead of a \leqslant. Change the sign of everything in them so as to flip the inequality sign. That gives you the set of inequalities

    \begin{aligned}x_1+\phantom{2}x_2\phantom{{}+x_3}+  x_4 &\leqslant 6,\\ 2x_1\phantom{{}+2x_2}-x_3\phantom{{}+x_4} &\leqslant -8,\\ -4x_1 +2x_2 + x_3\phantom{{}+x_4}&\leqslant -4,\end{aligned}

    together with the objective equation

    -2x_1 - x_2 - x_3 + M = 0.

    The matrix for the initial simplex tableau is then

    \begin{bmatrix}1&1&0&1&1&0&0&0&6\\ 2&0&-1&0&0&1&0&0&-8\\ -4&2&1&0&0&0&1&0&-4\\ -2&-1&-1&0&0&0&0&1&0\end{bmatrix}.

    (Some people leave out the last-but-one column in the tableau, which does not play an essential part in the reduction process.)

    You now have to follow the reduction process described in Steps B2, B3 and B4 on the second page of the pdf file, and then you can read off the solution to the problem.

    If you are unsure about how to operate the pivoting procedure, there are some good worked examples here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 3rd 2009, 09:09 PM
  2. Linear programming
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 4th 2009, 03:48 PM
  3. Replies: 1
    Last Post: November 17th 2008, 04:18 AM
  4. linear programming
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 10th 2008, 08:01 AM
  5. Linear Programming
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 20th 2007, 12:42 PM

Search Tags


/mathhelpforum @mathhelpforum