How Can Linear Programming Optimize Seating Capacity Within a Budget?

[uberw00t]

Ok, so ill start this off with this, I don't know a whole lot about math. I do however have a question that I am pretty sure someone on these forums can help me out with.

What I am looking for is an equation that I can later plug different numbers into.

Lets say you have $1,000,000 dollars and you want to buy 2 different kinds of couches.
One couch cost's $350 and seats 4 (couch A), the other costs $900 but seats 7 (couch B). How many of each couch would you need to buy to achieve the most seats possible.

Im not so much looking for an answer to above question, but more looking for an equation I can use to find said answer.

I would greatly appreciate any help with this...

Thanks,
-Chris

 

[aralbrec]

Mathematical programming is the branch of math that solves optimization problems subject to constraints like this. Quite often there isn't a closed form solution.

When the problem has a linear goal and linear constraints (like this one) it is a linear programming problem. When the solutions must also be integers, it is an integer linear programming problem.

For your specific question, I can tell you the four-seat couch supplies seats at a cost of 350/4 = $87.50 each and the 7 seat couch supplies seats at 900/7 = $128.57 each so, given a fixed amount of money, you're going to be best off buying all couch A to maximize the number of seats. If you spend your million dollars, that would be 1e6/350 = 2857.14... of the A type couch. We can't buy 0.14 A couches so it may actually be best to buy 2857 A couches or 2856 A couches and 1 B couch, which would have to be compared for most seats. That is the difference between a linear programming solution and an integer linear programming solution, which is harder to find.


You can solve linear programming problems using an algorithm called the simplex algorithm and many online solvers are available, like this one: http://www.simplexme.com/en/index

You just have to phrase the problem in the standard form and plug it into the solver.

For this problem you are trying to maximize the number of seats subject to the single constraint of spending no more than a million dollars.

maximize 4A+7B
subject to 350A+900B <= 1000000

See if you can figure out how to plug that into the solver.

 

[HallsofIvy]

For only two (or three) variables, you don't need the full power of the simplex. Just graph the constraint to find the "feasible region" (the set of points that satisfy the constraint). The basic idea of "linear programming" is that a maximum or minimum for a linear function, on a convex polygon, occurs at a vertex. Here, the feasible region is the triangle with vertices at (0, 0), (0, 1000000/900)= (0, 10000/9), and (1000000/350, 0)= (100000/35, 0)= (20000/7, 0) where the first component is A and the second component is B. Evaluate 4A+ 7B at each of those three points to see which is the maximum.

 

[uberw00t]

Thanks for the replies guys.
I guess I understated the importance of this line " I don't know a whole lot about math "
Lemme lay it out here.
This is has nothing to do with couches and allot to do with an online game.
The couches in the question above are troops, and the # of seats are offensive points.
I think I made my first post/the original question all more complicated then it needed to be or didnt supply you with enough info, judging by the replies anyway. (below is another form of the same question, with a reply sort of more along the lines of what i was looking for.)

Iif you can help me here, please dumb this **** down about 10 notches.

This is a question I posted to the in game forums and the response I got.

So, let's say your leaving CF and you have 3,000,000 to train troops.
You have 7000 soldiers to train. ospecs are at $250 and leets are at 550.
So with 3 mil, you have enough to train all into specs, OR some specs and some leets.
If there an easy way to find a number of each to train to achieve the most "bang for your buck" (offence points)
I should add, that I would want to train all 7000 soldiers at once, so please don't just say train all the leets you can for now and train more as gc rolls in. Playing orc so 7/1 leets 4/0 specs.
Ive done this before, but its basically allot of calculator time and trial and error punching in variations of troops numbers. There's got to be an easier way.

Reply

3M=250x+550y
7000=x+y
3M-1.75M=-250y+550y
1.25M=300y
y=4166 elites
x=2834 specs

I have worked out the rest of the equation myself (or at least see were I can plug in different values to accommodate different situations) . But I can't for the life of me figure out were he got the 1.75M from.

And am i right in thinking that as long as you are spending ALL the money and training ALL available troops, that as long as there more "leets" you will have the highest amount of offence for the amount of money spent.

Sry about my post/question, I am sure some of you, if not all of you will be bothered by my bieng here, I'm like an anorexic kid at fat camp... I don't belong on these forums lol.