What are the approaches to solving optimization problems?

Question

Programming

Let's imagine that I am writing a small strategy game, turn-based for simplicity. All players (corporations) have at their disposal only one type of resource - loans. By paying credits, players can acquire: a) sources that produce credits; b) units (equipment units that consume a small amount of credits per turn). Corporation players can also take limited loans from Cosmobank, which they then repay with interest.
Question: how can I write a function (for an AI player) that could tell me what actions to take in the game steps s(1), s(2), ... s(N-1), so that in step s(N ) have X units while spending a minimum of credits?
I believe this problem belongs to the class of optimization problems. Tell me, what methods and models are used to solve such problems? Would approaches change if there were more than one resource in the game?
UPD1. While I had thoughts that it would be possible to look for approaches/solutions in:
- dynamic programming;
- research operations [in economics];
— theory of automatic control;
- genetic algorithms - there is no guarantee of achieving a globally optimal solution;
- neural networks - not familiar with them, so it may not be applicable at all.

Answer 1

I think this problem is very close to the problems of optimal control theory. Namely, the problem of finding the optimal program control. If we consider this problem in continuous time, and also exclude bank loans for simplicity, then it can be expressed as follows. Let the state of the system be expressed as a vector x[i] = {x1, x2, x3}, where:
x1 is the number of credit factories
x2 is the number of tanks (units)
x3 is the number of credits in the cash register
Then we have the following equations:
dx1/dt = u1 is the speed buying new credit factories. This value is set by the regulator, it must be found according to the condition of the problem
dx2/dt = u2 - the rate of purchase of new tanks. Similarly, the value is set by the regulator, it needs to be found
dx3 /dt = k1*x1 – k2*x2 – k3*u1 – k4*u2, where:
k1 is the rate of production of loans by factories
k2 is the cost of maintaining a tank per unit of time
k3 is the cost of factories
k4 is the cost of tanks
, so the control efficiency can be expressed using the integral. First, let's write down the costs at each point in time:
s = k2*x2 + k3*u1 + k4*u2
The total costs will be the integral of this function:
I = integral from 0 to t1 of s * dt.
Further, restrictions are imposed on the control and state variables:
x3 >= 0 — the balance must be positive;
u1 >= 0 - selling factories is prohibited;
u2 >= 0 - selling tanks is prohibited.
In this formulation, the problem of finding the optimal program control is given on the first pages of textbooks on the theory of optimal control.
Dif. the equations describing the system are, fortunately, linear, so TOU provides relatively easy ways to solve such a problem. Having dealt with the solution of the problem in continuous time, it will be possible to move on to the solution in discrete time, although I think it will be more difficult.
I note that in the original formulation in continuous time, the solution of the problem can be obtained from heuristic considerations. First, tanks require maintenance costs. Therefore, to minimize costs, it makes no sense to keep tanks. It is better to buy them all at the very last moment.
Dealt with the tanks. It turns out that until the very end of the functioning of the system, it is necessary to work only for loans. The number of credits in the cashier by the end of the work should be equal to the cost of all purchased tanks. Let's write all this in the form of equations:
x2(t) = 0 for t<T, x2(T)=N is the number of tanks by the end of work
where T is the end time of work.
u2(t) = 0 for t<T, u2(T) = N*delta(tT) is the Dirac delta function.
lim(t->T) x3(t) = k4*N — after buying tanks, it makes no sense to leave money in the cash register, so the amount of money in the cash register by the end of the work should be equal to the cost of all purchased tanks.
It remains to resolve the issue of buying credit factories. Obviously, it makes sense to build factories only as long as they pay off. Since the cost of the factories is equal to k3, and their productivity is equal to k1, then we equate and get:
k1*to = k3, where to is the payback time of the factories. Hence:
to = k3/k1.
How many factories should be built? If we want to maximize the number of tanks N, then we should maximize the number of credits by the end of the work. Consequently, factories need to be built to the maximum as long as they pay off. To the maximum - this means that all initial capital and all current profit must be invested in factories, and stop doing this at the moment T-to. During T-to, there is net accumulation, and before that time, money is zero. Hence:
lim(x3->0) = 0 — all the initial capital is fully spent on factories
x3(t)=0 for 0<t<T-to
x3(t)=k1*x1o*t for to<=t<T
where x1o is the number of factories by the time the accumulation phase begins.
At each moment, the profit brought by the factories will be equal to k1*x1(t). All this profit before the start of the accumulation phase will be invested in the purchase of new factories. Therefore, we have the equation:
k1*x1 = k3*dx1/dt
This is the simplest dif. first order equation, its solution is the exponent. Consequently, the number of factories during the build phase will grow exponentially, and in the same way the rate of buying new factories will increase.
But I considered the case of maximizing N for a given T. According to the initial condition of the problem, we have both T and N. Although this is a less interesting case, the customer’s desire is the law! Let's consider it too.
Since there is nowhere to minimize the costs of building tanks for a given N, only the costs of building factories remain among the other costs. They can be minimized on the basis of having the minimum possible number of factories to accumulate the required number of credits. When is the best time to buy factories? Obviously, at the beginning of the game, since the longer the factories exist, the more they give profit. Therefore, here, too, the entire functioning of the system will be divided into 3 stages: the construction phase, the accumulation phase, and the final chord for buying tanks. The amount of money in the cashier at the end will also be equal to the cost of the purchased tanks. In turn, in the accumulation phase, the amount on hand will grow linearly starting from zero at the beginning of the accumulation phase. It is easy to write equations similar to those given above and calculate the moments of transition between phases.

Answer 2

You need Dijkstra's algorithm (it's a modification of the A* algorithm).

Answer 3

In my opinion, the usual task of linear programming, if there is no opposition from other players (there is no competition for resources).

Answer 4

Genetic algorithms as the most generalized and suitable for a wide range of tasks