What mathematical operations are used to determine maximum resource utililzation?

Question

I'm playing a game and would like to leverage mathematics to use optimal resource utilization.

There are three troops I can build (ground, air, and horse). There are also three resources (wood, stone, and ore). The costs are

troop   wood   stone  ore
G       400    200    100
A       100    400    200
H       200    100    400

I'm trying to determine how to make the best use of X wood, Y stone, and Z ore. As a current example, I've got 1320k wood, 436k stone, and 711k ore.

So far I've thrown together a spreadsheet.

The simplest method just says 'what's the most of each troop type I can currently build?' Right now, that's 2180 ground, 1090 air, or 1777 horse. So it seems that the 2180 ground would be the best option. But, I know if I can 2170 ground instead of 2180, I can squeeze in 20 horse, for a total of 2190.

I've been trying to tweek the numbers here, but there has to be some kind of mathematical model I can use. I can't be the first person to encounter this kind of resource problem. I just don't have the mathematical background (actually I bet I do, I just don't have the relevant practice...) to create a formula or model to solve the problem.

Is there a formula, model, principle, or at least further reading I can use to solve this resource problem? Is it perhaps not purely mathematical, in which case where should I be looking?

Answer 1

If you can assign a value to each of the three kinds of troops, you can use linear programming to find the assignment that produces troops of the greatest value. In fact, your problem would become a textbook example of a linear programming problem.

We may as well say that $Value(G) = 1$. It seems that you prefer 20 horse to 10 ground, so $Value(H) > \frac12$, but perhaps you'd like to rate them higher? Linear programming can't tell you how to value the three kinds of troops (because it doesn't know what the game is) but if you can assign the values, it will tell you how to spend your resources to find the distribution that buys the troops of maximum value.

The basic method is that you imagine the set of possible troop choices as a three-dimensional space with axes $G, H,$ and $A$. Each resource constraint defines a region in this space that is bounded by a plane. For example, the Wood region is $400G + 100A + 200H \le 1320000$. There are also some implicit constraints; for example $G\ge 0$.

The troop distribution you choose is a single point that must lie in the intersection of all these regions. Each point has an associated value. The central theorem of linear programming is that the permitted region will be a polyhedron and that the value will be maximized at one of the vertices of this polyhedron. For your simple problem, it's not hard to find the vertices and then evaluate the value function at each vertex to find the optimal solution. For more complicated spaces (with 1000 troop types, say, instead of only 3) there are algorithms that walk along the edges of the polyhedron toward the optimal solution, and stop when they find it, without trying all the vertices.