# Linear Programming

• Jul 13th 2008, 06:45 PM
squarerootof2
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?
• Jul 13th 2008, 09:39 PM
NonCommAlg
Quote:

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: $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$
• Jul 14th 2008, 11:47 PM
squarerootof2
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.
• Jul 15th 2008, 12:10 AM
CaptainBlack
Quote:

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
• Jul 15th 2008, 12:42 AM
squarerootof2
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.
• Jul 15th 2008, 12:45 AM
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.
• Jul 15th 2008, 04:57 AM
CaptainBlack
Quote:

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