# Constraineed Maximization Problem

I am creating a game, and have run into quite a tricky problem which I have been wrestling for days. I have been able to turn into somewhat mathematical terms (bare with me, I'm a programmer not mathematician) -- but I am no closer to a solution.

var constants = [1000, 100, 10]; // arbitrary length, arbitrary positive numbers var contributions = [?, ?, ?]; // an array of each constants respective contribution 

Given an array of constants, I am trying to generate an array of contributions which represents each constants contribution to a pool.

SUM(constants[i] * contributions[i]) === pool  That is to say, each constant multiplied by their contribution ... summed up is known as the pool.

Here are the constraints I have to obey:

FOREACH i in constants.length: constants.length * (constants[i] * contribution[i]) isLessThanOrEqualTo pool 

That is to say, if I get the amount of constants I have .. multiply it by constants contribution ... it will always be less than or equal to the size of the pool.

And the last constraint:

All contributions must be less than or equal to 0.01

In other words, no constant can contribute more than 1% of its value to the pool.

Given these constraints, what I want to do is construct my array of contributions in such a way to maximize pool.

What I am looking for, is a function which turns an array of constants into an array of contributions. If anyone could give me any pointers, place to start, library suggestions .. or even work through how this problem would be solved for the example: constants = [1000, 100, 10] -- i would be highly appreciative.

• You may want to review your constrain. If you add all constrains you would have $constants.length*pool\leq constants.length*pool$. So all the constrains have to be equality. It follows easily that you can have only one choice of constribution (given the maximal is .01). In your example, contribution array is $[.0001,.001,.01]$. – Quang Hoang Jul 28 '14 at 16:56
• Hm! Wow, great answer -- you are right. Why when I enter this: Maximize p = 1000x + 100y + 10z subject to x <= 0.01 y <= 0.01 z <= 0.01 3*(1000x) - 1000x - 100y - 10z <= 0 3*(100y) - 1000x - 100y - 10z <= 0 3*(10z) - 1000x - 100y - 10z <= 0 into: zweigmedia.com/RealWorld/simplex.html It solves as p=0 (which as you demonstrated, is not the case) – Heptic Jul 28 '14 at 17:29
• Your input is not "standard". I put "Maximize p = 1000x + 100y + 10z subject to x <= 0.01, y <= 0.01, z <= 0.01, 2000x - 100y - 10z <= 0, - 1000x +200y - 10z <= 0, - 1000x - 100y +20z <= 0" and everything's good. – Quang Hoang Jul 28 '14 at 17:44
• btw, can you let me know about your game when finished? It may be a good example for my students :-) – Quang Hoang Jul 28 '14 at 17:46
• Questions are closed when they are bad or duplicate questions. If you found a solution of a question, however simple it turned out to be, that's a different matter. Just mark the answer as accepted by clicking checkmark next to it, and everybody can move on. – user147263 Jul 28 '14 at 19:32

If you add all constrains you would have $constants.length∗pool≤constants.length∗pool$. So all the constrains have to be equality. It follows easily that you can have only one choice of contributions (given the maximal is .01). In your example, contribution array is [.0001,.001,.01].