Thread: Finding the optimal solution to a Linear Program

Hi there,

It's the beginning of a new quarter and I can tell my basic linear algebra is failing me at this point. I just need help solving a multi-dimensional linear program. So far this is the LP.

Maximize: 6*x1 + 3*x2 + 8*x3 + 3*x4 + 9*x5 + 5*x6
Subject to:
x1 + x2 <= 480
x3 + x4 <= 400
x5 + x6 <= 230
x1 + x3 + x5 <= 420
x2 + x4 + x6 <= 250
x1, x2, ..., x6 >= 0

From there I have no idea where to go. I know how to solve a two-dimensional LP graphically but I just can't figure this one out.

Thanks in advance! :)

Originally Posted by hjhart

Hi there,

It's the beginning of a new quarter and I can tell my basic linear algebra is failing me at this point. I just need help solving a multi-dimensional linear program. So far this is the LP.

Maximize: 6*x1 + 3*x2 + 8*x3 + 3*x4 + 9*x5 + 5*x6
Subject to:
x1 + x2 <= 480
x3 + x4 <= 400
x5 + x6 <= 230
x1 + x3 + x5 <= 420
x2 + x4 + x6 <= 250
x1, x2, ..., x6 >= 0

From there I have no idea where to go. I know how to solve a two-dimensional LP graphically but I just can't figure this one out.

Thanks in advance!

If you have never done a course that covered solving multidimensional LP problems then you will not get far with this, but here is the Wikipedia article on the simplex algorithm. Also the solver in Excel (and most other spreadsheet programs) will solve LP problems.

CB

Thanks CaptainBlack, we've just gotten into the Simplex method this week. :)