Thread: Need help with solving a linear system given certain limits.

Ok its been a while since my college math class days, so I may have lost a step and I may not explain this well, but here is my problem. I am a programmer trying to write an algorithm that will help me balance the difficulty of a game I am working on. Without getting into unnecessary details I have narrowed it down to this.

55a + 25b + 20c + 20d = A
25a + 65b + 20c + 20d = B
25a + 25b + 50c + 20d = C
25a + 25b + 20c + 70d = D
a >= 0
b >= 0
c >= 0
d >= 0

A, B, C, & D are constants I need to be able to enter as parameters, then solve the equations so that I get the minimum a+b+c+d.

Now using a solver I found online, I was able to find that without the >= 0 restrictions I can find the answer by: (sorry i couldn't get latex to work right)
a = (323A - 75B - 80C - 48D) / 12690
b = (-25A + 87B - 20C - 12D) / 4230
c = (-100A - 75B + 343C - 48D) / 12690
d = (-20A - 15B - 16C + 75D) / 4230
but that allows for negative values which I cannot have.

How would I find a set of solutions which includes the >= restrictions?

Use the Excel Solver routine. You can enter all your constraints in there.

As an example, I entered your system with A = 2, B = 3, C = 5, D = 7, and got a = 0, b = 0.25, c = 0, d = 0.06875. Note that the LHS's of the matrix equation do not add up to the RHS's, though Excel did its best.

You should note something: your system is overdetermined. Your coefficient matrix is invertible, which means that your exact system has exactly one solution. That means, among other things, that in order for you to satisfy your constraints, something's going to have to give. On what are you willing to give a little?

1st I was unable to duplicate your results. I should also mention that they will be integer results but figured I could just round up decimal results and that would work for me. Also, I am dealing with much larger values of A,B,C,& D think 100,000 - 10 million range.

Also, I may have left out that the values of a,b,c,d only have to be the minimum to meet or exceed each of the A,B,C,D values. So for example if A,B,C,D all equial 25, then the minimum a+b+c+d = 1 with either a=1 OR b=1 with the rest = 0. The fact that either A or B would exceed the parameters with either 55 if a=1 or 65 if b=1, is perfectly fine as long as all of the parameters A,B,C,D are met or exceeded, and a+b+c+d is minimized.

As for using excel I put all of the data in such that I have an entered value for A,B,C,D and a calculated formula based version if A,B,C,D. Also, I have blank cells for a,b,c,d. I used the solver to target the calculated formula for A and in the "by changing" part selected a,b,c,d. Then I selected "min" and gave it rules where the calculated versions of A,B,C,D had to be greater than the entered values of A,B,C,D, and that a,b,c,d were all integers and greater than 0. This worked sort of but not exactly since the values changed greatly depending on what cell was the initial target. Also, none of the solutions for targeting A,B,C,or D calculated cells gave the true minimum amount.

Ok I'm an idiot, I got to work this morning and it hit me that I should obviously set my target on a cell that is the sum of the values I want to minimize. That works fine. Is there a way to make the solver recalculate automatically though?

Originally Posted by gyan1010

Is there a way to make the solver recalculate automatically though?

Not to my knowledge.