Thread: 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?

Originally Posted by squarerootof2

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: so:

now if then and satisfy all three inequalities. so the maximum of is

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.

Originally Posted by squarerootof2

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

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.

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.

Originally Posted by squarerootof2

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