# Finding the optimal solution to a Linear Program

• Oct 7th 2009, 09:31 PM
hjhart
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! :)
• Oct 11th 2009, 02:50 AM
CaptainBlack
Quote:

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
• Oct 11th 2009, 11:52 PM
hjhart
Thanks CaptainBlack, we've just gotten into the Simplex method this week. :)