Results 1 to 7 of 7

Math Help - Linear Programming

  1. #1
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128

    Linear Programming

    i'm trying to maximize the equation z=2x1+4x2+3x3 subject to
    x1+x2+x3<=12
    x1+3x2+3x3<=24
    3x1+6x2+4x3<=90
    x1>=0,x2>=0, and x3>=0

    where x1,x2,and x3 are the axis in the graph. i was able to maximize problems in R^2 easily by finding the extreme points, but i'm having difficulty finding extreme points of the polyhedron in R^3. is there any way to find such extreme points in R^3?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by squarerootof2 View Post
    i'm trying to maximize the equation z=2x1+4x2+3x3 subject to
    x1+x2+x3<=12
    x1+3x2+3x3<=24
    3x1+6x2+4x3<=90
    x1>=0,x2>=0, and x3>=0

    where x1,x2,and x3 are the axis in the graph. i was able to maximize problems in R^2 easily by finding the extreme points, but i'm having difficulty finding extreme points of the polyhedron in R^3. is there any way to find such extreme points in R^3?
    add the first and the second inequality together to get:  2x_1+4x_2+4x_3 \leq 36. so: z \leq z+x_3=2x_1+4x_2+4x_3 \leq 36.

    now if x_1=x_2=6, \ x_3=0, then z=36 and x_1,x_2,x_3 satisfy all three inequalities. so the maximum of z is 36. \ \ \ \ \square
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    how would one determine the vertices of this set? i'm not sure what procedures you went through to determine that z=36 is the maximum.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by squarerootof2 View Post
    i'm trying to maximize the equation z=2x1+4x2+3x3 subject to
    x1+x2+x3<=12
    x1+3x2+3x3<=24
    3x1+6x2+4x3<=90
    x1>=0,x2>=0, and x3>=0

    where x1,x2,and x3 are the axis in the graph. i was able to maximize problems in R^2 easily by finding the extreme points, but i'm having difficulty finding extreme points of the polyhedron in R^3. is there any way to find such extreme points in R^3?
    Yes, you use the simplex algorithm, but I can't demonstrate this by hand here but a 3D problen can be done by hand.
    (it is implemented in the Excel solver and many other places).

    RonL
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    ahhh thats what i was figuring he used to solve this problem. unfortunately we have not covered the simplex algorithm yet in too much details. is there another way to do this problem? (for example in R^2 we just figure out the vertices and check the function value at those respective points) if not i guess i'll have to go read up on the simplex algorithm.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    just a thought, but is it possible to see what happens when u set one of the three coordinates to zero (im thinking we will get 3 vertices), and set two of them equal to zero (you get 3 more vertices), etc. and just check those function values? because i'm thinking that if i can somehow find all the vertex points, computing the maximum will be like cake.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by squarerootof2 View Post
    just a thought, but is it possible to see what happens when u set one of the three coordinates to zero (im thinking we will get 3 vertices), and set two of them equal to zero (you get 3 more vertices), etc. and just check those function values? because i'm thinking that if i can somehow find all the vertex points, computing the maximum will be like cake.
    There is a method, its labourious but should work.

    There are six constraints.

    set current best=-10000 lets say

    If you cycle through sets of three assumed active constaints (that is the equality condition applies), these if they are not degenerate they define a point. Check if this satisfies the remaining constraints, if it does it is a vertex of the feasible region. Comupute the objective, if this is bigger than current best set current best equal to it.

    That should do it, it will check more points than the simplex algorithm but it will find an optimum vertex (the objective may be achived along an edge or face but as we ignore degenerate constraint sets we will end up at a vertex).

    You will end up checking 120 sets of constraints this way, there may be a way to reduce that number without having to go to the full simplex algorithm

    RonL

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Linear Programming~Please help!
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: April 13th 2010, 01:12 PM
  2. Replies: 1
    Last Post: November 17th 2008, 03:18 AM
  3. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: May 25th 2008, 03:59 PM
  4. linear programming
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: May 25th 2008, 06:40 AM
  5. Linear Programming
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: February 19th 2008, 07:06 AM

Search Tags


/mathhelpforum @mathhelpforum