Markov decision-making models are generalized in different directions, in particular, to the case Markov reconstruction problems. The most useful generalization is obtained when unequal or variable transition times are considered. In simple models, it is assumed that the transition from state to state and observation of the state are instantaneous, and the length of time between transitions from state to state can be of variable or random length.

Whenever a state is observed, a solution is selected and cannot be changed until the process moves to a new state, where a new solution is selected, etc. This model is a combination of Markov chain theory and restoration theory; usually called Markov reconstruction problem.

Test questions for Chapter 6.

1. What components does a directed network consist of?

1. How is the network capacity matrix constructed?

1. How is the network flow matrix formed?

1. Why are the capacity and flow matrices subtracted?

1. What is a network diagram and what is it used for?

1. How are the early start and early finish times of work determined?

1. What is the total float for some event on the network diagram?

1. How is the critical path determined?

1. What is called the state vector of a certain system?

1. What is the trajectory of a system in state space?

1. What is the problem of optimal control?

1. How is the optimality criterion formulated?

1. What is dynamic programming?

1. Formulate the Bellman optimality principle.

1. What is the essence of the forward and backward sweep algorithms when searching for the shortest path?

Options for assignments for Chapter 6.

For networks in each of the options:

1) Find the maximum flow from the source (1) to the final node of the network - the sink, assuming that one of the numbers in brackets for each arc (i, j) determines the capacity of the arc;

1) Assuming that arcs (1)®(2), (1)®(3), etc. define some jobs, the minimum and maximum duration of which are given by the numbers indicated under the corresponding arcs, find the critical path from the initial event (1) to the end;

1) Search for the shortest path from the start node to the end node of the network. Consider the distances between nodes i, j given by one of the numbers in brackets.

Let's say there is a problem that we have already solved by dynamic programming, for example, the eternal Fibonacci numbers.
Let's reformulate it a little. Let us have a vector from which we want to obtain a vector. Let's expand on the formulas a little: . You can see that from a vector you can get a vector by multiplying by some matrix, because only the added variables from the first vector appear in the final vector. This matrix is ​​easy to derive, here it is: . Let's call it the transition matrix.

This means that if we take the vector and multiply it by the transition matrix n - 1 times, we get a vector containing fib[n] - the answer to the problem.

Now, why is all this necessary? Matrix multiplication has the property of associativity, that is, (but at the same time it does not have commutativity, which in my opinion is surprising). This property gives us the right to do this: .

This is good because now you can use the fast exponentiation method, which works in . In total, we were able to calculate the Nth Fibonacci number as the logarithm of arithmetic operations.

And now a more serious example:

Example #3: Ramp Sequence

Solution

First, a solution without a transition matrix:

1) Dynamics state: dp[n] - the number of sawtooth sequences of length n ending with the number last. Moreover, if less == 0, then the last digit is less than the penultimate one, and if less == 1, then it is more.
2) Initial values:
for last in range(10): dp = 9 - last dp = last 3) Recalculation of dynamics:
for prev in range(10): if prev > last: dp[n] += dp if prev< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) The answer is the sum dp[N] .

Now we need to come up with an initial vector and a transition matrix to it. The vector seems to come up quickly: all states denoting the length of the sequence N . Well, the transition matrix is ​​derived by looking at the conversion formulas.

Transition vector and matrix

Dynamics by subsegments

Example #4: Packing a string

Let's define a compressed string:
1) A string consisting only of letters is a compressed string. She unclenches into herself.
2) A string that is the concatenation of two compressed strings A and B. It is decompressed into a concatenation of decompressed strings A and B.
3) String D(X) , where D is an integer greater than 1 and X is a compressed string. It is decompressed into a concatenation of D strings decompressed from X .
Example: “3(2(A)2(B))C” expands to “AABBAABBAABBC” .

It is necessary to find out from the string s the length of the shortest compressed string that decompresses into it.

Solution

This problem is solved, as you probably already guessed, by dynamics in subsegments.

1) Dynamics state: d[l][r] - compressed string of minimum length, decompressed into string s
2) Initial states: all substrings of length one can be compressed only into themselves.
3) Recalculation of dynamics:
The best answer has some last operation compression: either it's just a string from capital letters, or it is the concatenation of two strings, or the compression itself. So let's go through all the options and choose the best one.

Dp_len = r - l dp[l][r] = dp_len # The first compression option is just a string. for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Try dividing by two compressed substrings for cnt in range(2, dp_len): if (dp_len % cnt == 0): # If it is not divisible, then there is no point in trying to divide good = True for j in range(1, (dp_len / cnt) + 1 ): # Check that all cnt substrings are the same good &= s == s if good: # Try to divide into cnt identical substrings and compress dp[l][r] = min(dp[l][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Recalculation order: direct ascending substring length or lazy dynamics.
5) The answer lies in d.

Example #5:

Dynamics by subtrees

Example #6: Logical tree

It is required to find the minimum number of changes in logical operations in internal vertices such that the value at the root changes or to report that this is impossible.

Solution

1) Dynamics state: d[v][x] - the number of operations required to obtain the value x at vertex v. If this is not possible, then the state value is +inf .
2) Initial values: for leaves, it is obvious that your value can be obtained in zero changes, but it is impossible to change the value, that is, it is possible, but only in +inf operations.
3) Conversion formula:
If this vertex already has a value x , then zero. If not, then there are two options: change the operation at the current vertex or not. For both you need to find best option and choose the best one.

If the operation is “AND” and you need to get “0”, then the answer is the minimum of the values ​​d[i] , where i is the son of v .
If the operation is “AND” and you want to get “1”, then the answer is the sum of all values ​​d[i] , where i is the son of v .
If the operation is “OR” and you want to get “0”, then the answer is the sum of all values ​​d[i] , where i is the son of v .
If the operation is “OR” and you need to get “1”, then the answer is the minimum of the values ​​d[i] , where i is the son of v .

4) Recalculation order: the easiest way to implement it is lazily - in the form of a depth-first search from the root.
5) The answer is d xor 1].

Dynamics by subsets

Example #7: Hamiltonian cycle of minimum weight, or the traveling salesman problem

Solution

Since we are looking for a cycle passing through all vertices, we can choose any vertex as the “initial” vertex. Let this be vertex number 0.

1) State of dynamics: dp[v] - the path of minimum weight from vertex 0 to vertex v, passing through all vertices lying in mask and only through them.
2) Initial values: dp = 0, all other states are initially +inf.
3) Conversion formula: If the i-th bit in mask is 1 and there is an edge from i to v, then:
dp[v] = min(dp[v], dp[i] + w[i][v]) Where w[i][v] is the weight of the edge from i to v .
4) Recalculation procedure: the simplest and convenient way- this is to write lazy dynamics, but you can get creative and write an enumeration of masks in order of increasing the number of unit bits in it.
5) The answer lies in d[(1<< N) - 1] .

Dynamics by profile

These problems can be solved by exhaustive search in , where a is the number of tiling options for one cell. Dynamics by profile optimizes time along one of the dimensions to linear, leaving only a coefficient in the exponential. You will get something like this: .

A profile is k (often one) columns, which are the boundary between the part that has already been paved and the part that has not yet been paved. This border is only partially filled. Very often it is part of the dynamic state.

Almost always the state is a profile and where that profile is. And the transition increases this location by one. You can find out whether it is possible to switch from one profile to another in a time linear to the profile size. This can be checked every time during the recalculation, but it can also be pre-calculated. We will pre-calculate a two-dimensional array can - is it possible to move from one mask to another by placing several figures, increasing the position of the profile by one. If you pre-calculate, it will take less time to complete and more memory.

Example #8: Domino tiling

Solution

Here the profile is one column. It is convenient to store it in the form of a binary mask: 0 - an untiled cell of the column, 1 - a tiled cell. That is, total profiles.

0) Pre-calculation (optional): go through all pairs of profiles and check that it is possible to go from one to another. In this problem this is checked like this:

If in the first profile there is a 1 in the next place, then in the second there must be a 0, since we will not be able to cover this cell with any figure.

If in the first profile there is a 0 in the next place, then there are two options - either in the second it is 0 or 1.
If 0, this means that we must place a vertical domino, which means the next cell can be considered as 1. If 1, then we place a vertical domino and move to the next cell.

Examples of transitions (from the top profile you can go to the bottom ones and only in them):

After that, save everything in the can array - 1 if you can go, 0 if you can’t.
1) Dynamics state: dp - the number of complete tilings of the first pos - 1 columns with the mask profile.
2) Initial state: dp = 1 - left border of the field - straight wall.
3) Conversion formula:
dp += dp * can
4) The order of traversal is in increasing order of pos.
5) The answer lies in dp.

The resulting asymptotics is .

Dynamics along a broken profile

Now, after adding a break to the profile, you can move on to the next state, adding just one figure covering the left cell of the break. That is, by increasing the number of states by N times (we must remember where the break point is), we reduced the number of transitions from one state to another from to . Asymptotics improved from to .

Transitions in dynamics along a broken profile using the example of a problem about tiling with dominoes (example No. 8):

Reply recovery

Each problem has its own way of recovering the answer, but the most common are:

• Store the complete answer to the subtask next to the dynamics state value. If the answer is something large, it may require too much memory, so if another method can be used, it is usually done.
• Reconstruct the answer, knowing the ancestor(s) of the given state. It is often possible to reconstruct a response by knowing only how it was received. In the same “String Packing”, to restore the response, you can store only the type of the last action and the states from which it was received.
• There is a way that does not use additional memory at all - after recalculating the dynamics, go from the end along the best path and compose the answer along the way.

Small optimizations

Memory

Time

State replacement

Example #9: Number expansion

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Among the problems solved using mathematical programming, one can distinguish a separate class of problems that require optimization of multi-step (multi-stage) processes. Such problems are distinguished by the possibility of dividing the solution into several interconnected stages. To solve such problems, dynamic programming or, as it is also called, multi-stage programming is used. Its methods are optimized to find the optimal solution to multi-step problems that can be divided into several stages, steps, etc.

Origin of the term

The use of the word “dynamic” in the name originally implied that the division into subtasks would occur primarily in time. When using dynamic methods to solve production, economic and other problems in which the time factor appears, breaking it down into separate stages is not difficult. But it is also possible to use dynamic programming techniques in tasks where individual stages are not related in time. In a multi-step problem, you can always select a parameter or property that can be used to divide it into separate steps.

Algorithm (method) for solving multi-stage problems

The dynamic programming algorithm or method is based on the principle of sequential optimization of a problem, when the solution to a general problem is divided into a number of solutions to individual subproblems and then combined into a single solution. Very often, individual subproblems turn out to be the same, and one general solution significantly reduces calculation time.

A feature of the method is the autonomy of solving the problem at each individual stage, i.e., regardless of how the process was optimized and solved at the previous stage, only the process parameters that characterize it at the moment are used in the current calculation. For example, a driver moving along the road makes a decision about the current turn regardless of how and how long he drove before.

Method from above and method from below

Despite the fact that when calculating at a separate stage of solving a problem, the process parameters at the current moment are used, the result of optimization at the previous stage affects the calculations of subsequent stages to achieve the best result as a whole. Dynamic programming calls this solution principle the optimality method, which determines that the optimal strategy for solving a problem, regardless of the initial decisions and conditions, must be followed by subsequent decisions at all stages to create an optimal strategy relative to the initial state. As we can see, the process of solving a problem is a continuous optimization of the result at each individual stage from the first to the last. This method is called the top-down programming method. The figure schematically shows the top-down solution algorithm. But there is a class of multi-step problems in which the maximum effect at the last stage is already known, for example, we have already arrived from point A to point B and now we want to find out whether we drove correctly at each previous stage or whether something could have been done more optimally. A recursive sequence of stages arises, i.e. we go, as it were, “from the opposite direction.” This solution method is called the “bottom-up programming method.”

Practical use

Dynamic programming can be used in any field of activity where there are processes that can be divided into a number of identical small stages according to some parameter (time, amount, temperature, etc.). Dynamic solution methods are most widely used in control theory and in the development of computer systems.

Finding the optimal path

Using dynamic optimization, it is possible to solve a wide class of problems of finding or optimizing the shortest path and other problems in which the “classical” method of enumerating possible solution options leads to an increase in calculation time and is sometimes completely unacceptable. The classic dynamic programming problem is the knapsack problem: given a certain number of objects with a certain mass and cost, and it is necessary to select a set of objects with the maximum cost and mass that does not exceed the volume of the knapsack. A classic search of all options in search of the optimal solution will take considerable time, but with the help of dynamic methods the problem is solved in an acceptable time frame. The problems of finding the shortest path for transport logistics are basic, and dynamic solution methods are optimally suited for solving them. The simplest example of such a task is building the shortest route using a car GPS navigator.

Production

Dynamic programming is widely used in solving a variety of production problems, such as inventory management to maintain the required number of components at any given time, scheduling of the production process, routine and overhaul of equipment, uniform workload of personnel, the most efficient distribution of investment funds, etc. To solve production problems using dynamic programming methods, special software packages have been developed that are integrated into popular enterprise management systems, such as SAP.

Scientific field

Dynamic programming methods are widely used in various scientific research. For example, they are successfully used in speech and image recognition algorithms, when processing large amounts of data in sociology and

Hello, Habrakhabr. I'm currently working on a textbook on Olympiad programming, one of the paragraphs of which is devoted to dynamic programming. Below is an excerpt from this paragraph. Trying to explain this topic as simply as possible, I tried to accompany complex moments with illustrations. I'm interested in your opinion on how clear this material is. I would also be glad to receive advice on what other tasks should be included in this section.

In many Olympiad programming problems, solving using recursion or exhaustive search requires performing a very large number of operations. An attempt to solve such problems, for example, by exhaustive search, leads to exceeding the execution time.

However, among exhaustive search and some other problems, we can distinguish a class of problems that have one good property: having solutions to some subproblems (for example, for a smaller number n), you can find a solution to the original problem almost without searching.

Such problems are solved using the dynamic programming method, and by dynamic programming itself we mean reducing the problem to subtasks.

Sequences

Fibonacci sequence F n is given by the formulas: F 1 = 1, F 2 = 1,
Fn = F n - 1 + F n- 2 at n> 1. Need to find F n by number n.

One solution that may seem logical and efficient is to solve using recursion:

Int F(int n) ( if (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Using such a function, we will solve the problem “from the end” - we will reduce step by step n until we reach known values.

But as you can see, such a seemingly simple program already at n= 40 works noticeably for a long time. This is due to the fact that the same intermediate data is calculated several times - the number of operations grows at the same speed as the Fibonacci numbers grow - exponentially.

One way out of this situation is to save already found intermediate results for the purpose of their reuse:

Int F(int n) ( if (A[n] != -1) return A[n]; if (n< 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
The given solution is correct and effective. But for this problem a simpler solution is also applicable:

F = 1; F = 1; for (i = 2; i< n; i++) F[i] = F + F;
This solution can be called a “from the beginning” solution - we first fill in the known values, then we find the first unknown value ( F 3), then the next one, etc., until we reach the desired one.

This is exactly the solution that is classic for dynamic programming: we first solved all the subproblems (we found all F i For i < n), then, knowing the solutions to the subproblems, we found the answer ( F n = F n - 1 + F n - 2 , F n- 1 and F n- 2 have already been found).

One-Dimensional Dynamic Programming

Let the initial problem be to find a certain number T with initial data n 1 , n 2 , ..., n k. That is, we can talk about the function T(n 1 , n 2 , ..., n k), the value of which is the answer we need. Then we will consider the tasks as subtasks
T(i 1 , i 2 , ..., i k) at i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

The following one-dimensional dynamic programming problem occurs in various variations.

At n < 32 полный перебор потребует нескольких секунд, а при n= 64 exhaustive search is not feasible in principle. To solve the problem using the dynamic programming method, we reduce original problem to subtasks.

At n = 1, n= 2 the answer is obvious. Let's assume that we have already found K n - 1 , K n- 2 — the number of such sequences of length n- 1 and n - 2.

Let's see what the length of the sequence can be n. If its last character is 0, then the first n- 1 — any correct sequence of length
n- 1 (it doesn’t matter whether it ends with zero or one - 0 comes next). There are only such sequences K n- 1 . If the last character is equal to 1, then the penultimate character must be equal to 0 (otherwise there will be two ones in a row), and the first
n- 2 characters - any valid sequence of length n- 2, the number of such sequences is equal K n - 2 .

Thus, K 1 = 2, K 2 = 3, K n = K n - 1 + K n- 2 at n> 2. That is this task actually comes down to finding the Fibonacci numbers.

2D Dynamic Programming

Here are a couple of formulations of such tasks:

Task 2. n*m cells. You can take one-cell steps to the right or down. Count how many ways you can get from the top left cell to the bottom right cell.

Task 3. Given a rectangular field of size n*m cells. You can take one-cell steps to the right, down, or diagonally right and down. Each cell contains some natural number. You need to get from the top left cell to the bottom right cell. The weight of the route is calculated as the sum of numbers from all visited cells. It is necessary to find a route with minimal weight.

A characteristic feature of all such problems is that each individual route cannot go through the same cell two or more times.

Let's consider task 2 in more detail. To some cell with coordinates ( i,j) can only come from above or from the left, that is, from cells with coordinates ( i - 1, j) And ( i, j - 1):

Thus, for a cell ( i, j) the number of routes A[i][j] will be equal to
A[j] + A[i], that is, the problem is reduced to two subtasks. This implementation uses two parameters − i And j- therefore, in relation to this problem we are talking about two-dimensional dynamic programming.

Now we can go sequentially through the rows (or columns) of array A, finding the number of routes for the current cell using the above formula. First you need to put the number 1 in A.

In problem 3, in a cell with coordinates ( i, j) we can get from cells with coordinates
(i- 1, j), ( i, j- 1) and ( i - 1, j- 1). Let's assume that for each of these three cells we have already found the route of the minimum weight, and placed the weights themselves in W[j], W[i],
W. To find the minimum weight for ( i, j), you need to select the minimum of the weights W[j], W[i], W and add to it the number written in the current cell:

W[i][j] = min(W[j], W[i], W) + A[i][j];

This task is complicated by the fact that it is necessary to find not only the minimum weight, but also the route itself. Therefore, in another array we will additionally record for each cell from which side we need to enter it.

The following figure shows an example of the initial data and one of the steps of the algorithm.

Exactly one arrow leads to each of the already passed cells. This arrow shows from which side you need to come to this cell in order to get the minimum weight recorded in the cell.

After passing through the entire array, you will need to trace the route itself from the last cell, following the arrows in the opposite direction.

Subsequence problems

Task 4. Given a sequence of integers. It is necessary to find its longest strictly increasing subsequence.

Let's start solving the problem from the beginning - we will look for the answer, starting from the first terms of this sequence. For each number i we will look for the largest increasing subsequence ending with an element in position i. Let the original sequence be stored in array A. In array L we will record the lengths of the maximum subsequences ending with the current element. Let us find all L[i] for 1<= i <= k- 1. Now you can find L[k] as follows. We look through all elements of A[i] for 1<= i < k- 1. If
A[i]< A[k], то k The th element can become a continuation of the subsequence ending with the element A[i]. The length of the resulting subsequence will be 1 greater than L[i]. To find L[k], you need to go through all i from 1 to k - 1:
L[k] = max(L[i]) + 1, where the maximum is taken over all i such that A[i]< A[k] и
1 <= i < k.

Here, the maximum of the empty set will be considered equal to 0. In this case, the current element will become the only one in the selected sequence, and will not be a continuation of one of the previous ones. After filling the array L, the length of the largest increasing subsequence will be equal to the maximum element of L.

To restore the subsequence itself, you can also store the number of the previous selected element for each element, for example, in an array N.

Let's consider the solution to this problem using the example of the sequence 2, 8, 5, 9, 12, 6. Since there is no element before 2, the maximal subsequence contains only one element - L = 1, and there is none before it - N = 0. Further,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

The only element smaller than A = 5 is A = 2, so 5 can become a continuation of only one subsequence - the one that contains 2. Then
L = L + 1 = 2, N = 1, since 2 is in position number 1. Similarly, we perform three more steps of the algorithm and get the final result.

Now we select the maximum element in the array L and from the array N we reconstruct the subsequence itself 2, 5, 9, 12.

Another classic dynamic programming problem is the palindrome problem.

Task 5. Given a string of capital letters of the Latin alphabet. You need to find the length of the largest palindrome that can be obtained by crossing out some letters from a given string.

Let us denote this string by S and its symbols by S[i], 1<= i <= n. We will consider possible substrings of this string with i th j th symbol, we denote them by S(i, j). We will write the lengths of the maximum palindromes for substrings in a square array L: L[i][j] is the length of the maximum palindrome that can be obtained from the substring S(i, j).

Let's start solving the problem with the simplest substrings. For a single character string (that is, a substring of the form S(i, i)) the answer is obvious - there is no need to cross out anything, such a string will be a palindrome. For a two character string S(i, i+ 1) two options are possible: if the characters are equal, then we have a palindrome, there is no need to cross out anything. If the characters are not equal, then cross out any.

Let us now be given a substring S(i, j). If the first (S[i]) and last (S[j]) characters of the substring do not match, then one of them must be deleted. Then we are left with the substring S(i, j- 1) or S(i + 1, j) - that is, we reduce the problem to a subtask: L[i][j] = max(L[i], L[j]). If the first and last characters are equal, then we can leave both, but we need to know the solution to the problem S(i + 1, j - 1):
L[i][j] = L + 2.

Let's look at the solution using the string ABACCBA as an example. First of all, we fill the diagonal of the array with units, they will correspond to the substrings S(i, i) from one character. Then we start looking at substrings of length two. In all substrings except S(4, 5), the symbols are different, so we write 1 in the corresponding cells, and 2 in L.

It turns out that we will fill the array diagonally, starting with the main diagonal leading from the upper left corner to the lower right. For substrings of length 3, the following values ​​are obtained: in an ABA substring, the first and last letters are equal, so
L = L + 2. In the remaining substrings, the first and last letters are different.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

If in the task it is necessary to output not the length, but the palindrome itself, then in addition to the array of lengths, we must construct an array of transitions - for each cell, remember which of the cases was implemented (for clarity, in the figure, instead of the numeric values ​​encoding transitions, the corresponding arrows are drawn) .

An example of solving a problem using the dynamic programming method………………………………………………………...7

List of sources used……………………………………...11

1. Dynamic programming. Basic concepts.

Dynamic programming (DP) in computer systems theory, a way to solve complex problems by breaking them down into simpler subtasks. It is applicable to problems with an optimal substructure, which look like a set of overlapping subproblems whose complexity is slightly less than the original one. In this case, the computation time, compared to “naive” methods, can be significantly reduced.

The key idea in dynamic programming is quite simple. As a rule, in order to solve a given problem, it is necessary to solve individual parts of the problem (subtasks), and then combine the solutions to the subtasks into one general solution. Often many of these subtasks are the same. The dynamic programming approach is to solve each subproblem only once, thereby reducing the number of calculations. This is especially useful in cases where the number of repeating subtasks is exponentially large.

Dynamic programming is a mathematical technique that approaches the solution of a certain class of problems by breaking them down into parts, smaller and less complex problems. At the same time, a distinctive feature is the solution of problems in stages, at fixed intervals, periods of time, which determined the appearance of the term dynamic programming. It should be noted that dynamic programming methods are also successfully used when solving problems in which the time factor is not taken into account. In general, the mathematical apparatus can be represented as step-by-step or step-by-step programming. The solution of problems by dynamic programming methods is carried out on the basis of the principle of optimality formulated by R. E. Bellman: optimal behavior has the property that whatever the initial state of the system and the initial solution, the subsequent solution must determine the optimal behavior relative to the state obtained as a result of the initial solution. It follows from this that the planning of each step should be carried out taking into account the overall benefit obtained upon completion of the entire process, which allows optimizing the final result according to the selected criterion.

Thus, dynamic programming in a broad sense is the optimal control of a process by changing the controlled parameters at each step, and, therefore, influencing the progress of the process, changing the state of the system at each step. In general, dynamic programming is a harmonious theory to understand and simple enough to be used in commercial activities when solving both linear and nonlinear problems.

Dynamic programming is one of the branches of optimal programming. It is characterized by specific methods and techniques applied to operations in which the decision-making process is divided into stages (steps). Dynamic programming methods are used to solve variant optimization problems with given optimality criteria, with certain connections between variables and the objective function, expressed by a system of equations or inequalities. In this case, as in problems solved by linear programming methods, restrictions can be given in the form of equalities or inequalities. However, if in linear programming problems the dependencies between the criterion function and variables are necessarily linear, then in dynamic programming problems these dependencies can also be nonlinear. Dynamic programming can be used both to solve problems associated with the dynamics of a process or system, and for static problems associated, for example, with resource allocation. This significantly expands the scope of dynamic programming for solving control problems. And the possibility of simplifying the solution process, which is achieved by limiting the area and number examined when moving to the next stage of options, increases the advantages of this set of methods.

However, dynamic programming also has disadvantages. First of all, there is no single universal solution method. Almost every problem solved by this method is characterized by its own characteristics and requires a search for the most appropriate set of methods to solve it. In addition, the large volumes and complexity of solving multi-step problems with many states lead to the need to select low-dimensional problems or use compressed information. The latter is achieved using methods for analyzing options and processing the list of states.

For continuous-time processes, dynamic programming is considered as a limiting version of a discrete solution scheme. The results obtained in this case practically coincide with those obtained by the maximum methods of L. S. Pontryagin or Hamilton-Jacobi-Bellman.

Dynamic programming is used to solve problems in which the search for an optimum is possible with a step-by-step approach, for example, the distribution of scarce capital investments between new areas of their use; development of demand or inventory management rules that establish the moment of replenishment and the size of the replenishing order; development of principles for production scheduling and equalization of employment in conditions of fluctuating demand for products; drawing up calendar plans for current and major repairs of equipment and its replacement; search for the shortest distances on the transport network; formation of the sequence of development of a commercial operation, etc.