Solving the problem of resource allocation using the dynamic programming method. Solving various practical dynamic programming problems: Optimal resource allocation
Dynamic programming (DP) is a method for finding optimal solutions in problems with a multi-step (multi-stage) structure.
Let us present the general formulation of the DP problem. A controlled process is considered (distribution of funds between enterprises, use of resources over a number of years, etc.). As a result of control, the system (control object) is transferred from the initial state to the state 
. Let's assume that control can be broken down into 
steps. At each step, one of the many admissible controls is selected 
, transferring the system to one of the states of the set 
. Elements of the set 
And 
are determined from the conditions of a specific task. The sequence of system states can be depicted as a state graph shown in Fig. 3.1.
Every step of the way n the effect is achieved 
. Let's assume that the total effect is the sum of the effects achieved at each step. Then the DP problem is formulated as follows: determine such an admissible control 
, which transfers the system from the state 
in a state 
, at which the goal function 
takes the largest (smallest) value, i.e.
The solution of problems by the DP method is carried out on the basis of the principle of optimality, which was formulated by the American scientist R. Bellman: whatever the state of the system as a result of any number of steps, at the next step it is necessary to choose control so that, in combination with optimal control at all subsequent steps led to optimal winnings at all remaining steps, including this one.
Let us denote by 
conditionally optimal value of the objective function on the interval from the step n until the last 
-th step inclusive, provided that before n At the th step, the system was in one of the states of the set 
, and on n On the th step, such a control was selected from the set 
, which provided the objective function with a conditionally optimal value, then 
conditionally optimal value of the objective function in the range from ( n+1
)th to 
-th step inclusive.
In the accepted notation, the Bellman optimality principle can be written in mathematical form as follows
Equality (3.1) is called the main functional equation dynamic programming. For each specific task the equation has a special form.
The computational procedure of the DP method is divided into two stages: conditional and unconditional optimization.
At the stage conditional optimization in accordance with the functional equation, optimal controls are determined for all possible states at each step, starting from the last.
At the stage unconditional optimization steps are considered starting from the first. Since the initial state 
known, the optimal control is selected from the set 
. Selected optimal control
brings the system to a very specific state 
. Due to the fact that the initial state 
is known at the beginning of the second step, it becomes possible to choose the optimal control at the second step 
etc. Thus, a chain of interconnected unconditional optimization solutions is built.
3.1. Optimal resource allocation problem
Let the association be allocated a certain amount of material resources for the reconstruction and modernization of the main production X. Available N enterprises between which it is necessary to distribute this resource. Let us denote by 
the profit that the allocation brings to the national economy j-th enterprise 
resource units. It is assumed that the profit margin depends on both the allocated amount of resource and the enterprise. Moreover, the profit received by enterprises is measured in the same units and the total profit of the association consists of the profits of individual enterprises. It is necessary to find the optimal plan for allocating resources between enterprises, in which the total profit of the association will be maximum.
The task at hand must be considered as a multi-step one.
At the stage conditional optimization we will consider the efficiency of investing in one (for example, the first enterprise), two enterprises together (the first and second), three enterprises together (the first, second and third), etc., and finally, all N enterprises together. The task is to determine the largest value of the function 
provided that 
.
Let us use the Bellman recurrence relation (3.1), which for this problem leads to the following functional equations for 
:
Here's the function 
determines the maximum profit of the first enterprise when allocating it x resource units, function 
determines the maximum profit of the first and second enterprises together when allocating them x resource units, function 
determines the maximum profit of the first, second and third enterprises together when allocating them x resource units, etc., and finally, the function 
determines the maximum profit of all enterprises together when allocating them x resource units.
At the stage of unconditional optimization, the optimal plan for distributing resources between enterprises is determined.
Example 3.1.
To increase the volume of production of products that are in high demand, funds in the amount of 50 million rubles were allocated to four enterprises of the production association. Each enterprise can be allocated: 0, 10, 20, 30, 40 or 50 million rubles. At the same time, the annual increase in production output by each of the enterprises 
depending on investment is known and given in table. 3.1.
Table 3.1
|
Volume of allocated funds x(million rubles) |
Annual increase in product output (million rubles), depending on the volume of allocated funds |
|||
|
|
|
|
|
|
Find the optimal plan for the distribution of funds between enterprises, ensuring the maximum annual increase in production output by the production association.
Lesson Plan
Academic discipline MATHEMATICAL METHODS AND MODELS IN ECONOMICS
Lesson topic Solving various practical DP problems using mathematical methods.
Lesson Objectives
Develop skills in solving dynamic programming problems.
Development of the quality of mind, attention, and academic work skills of students.
Instilling discipline and determination in students.
Lesson equipment Lecture notes, V.P. Agaltsov " Mathematical methods in programming."
During the classes:
Organizing time:
checking absentees, filling out the log.
Updating of reference knowledge: answers to security questions
What tasks are called multi-step?
What mathematical apparatus is used to solve multi-step problems?
What is optimal control u*?
What is the algorithm for the two-circle successive approximation method?
Give examples of optimal resource allocation problems.
Learning new material:
Classic dynamic programming problems
Longest common subsequence problem: Given two sequences, you need to find the longest common subsequence.
Problem of finding the longest increasing subsequence: given a sequence, you need to find the longest increasing subsequence.
Editorial distance problem (Levenshtein distance): given two strings, you need to find the minimum number of erases, replacements and additions of characters that transform one string into another.
The problem of calculating Fibonacci numbers
The problem of the order of matrix multiplication: given matrices, ..., it is required to minimize the number of scalar operations for their multiplication.
Trajectory selection problem
Sequential Decision Making Problem
Labor Utilization Problem
Inventory management problem
The knapsack problem: from an unlimited set of objects with the properties “cost” and “weight”, it is required to select a certain number of objects in such a way as to obtain the maximum total cost with a limited total weight.
Floyd-Warshall algorithm: find the shortest distances between all vertices of a weighted directed graph.
Bellman-Ford algorithm: find the shortest path in a weighted graph between two given vertices.
Maximum independent set of vertices in a tree: given a tree, find the maximum set of vertices such that no two of them are connected by an edge.
Example: Optimal resource allocation
Capital 40 million rubles. the investor must invest in four investment projects in order to obtain maximum income. The profitability of projects is given in the table (investments are multiples of 8 million rubles)
u
Profit from implementation
f4(u)
f3(u)
f2(u)
f1(u)
55
39
120
115
10 0
120
135
134
14 0
145
158
147
Solution:
This is a dynamic programming problem. The solution consists of two stages. At the first stage (from end to beginning) we look for a conditional optimal solution, at the second (from beginning to end) we look for the optimal solution to the problem.
Stage 1.
We distribute capital between four projects and calculate the profit received L (i ), i = 8,16,24,32,40.
1 step: Funds are invested in the fourth project.
L(8)= 55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
Step 2: Funds are invested in the fourth and third projects.
u
Profit from implementation
1 step
f3(u)
55
39
10 0
120
14 0
145
Step 3: Funds are invested in the fourth, third (step 2) and second projects.
u
Profit from implementation
Step 2
f 2(u)
94
108
120
135
135
175
158
175
134
214
147
Stage 2:
At the fourth step, we select the maximum of the obtained profit values L (40) = 214.
And returning to reverse order From table to table (from 4 steps to 1) we select such income values at which the value 214 is obtained.
Maximum income 214 million rubles. from the invested funds can be received with the following distribution of funds:
1 project – 0 million rubles.
2 project – 24 million rubles.
3rd project – 8 million rubles.
4 project – 8 million rubles.
Consolidating new material:
5. Summing up the lesson: conclusions, assessments, homework:
(2) clause 5.1
Ср12: formation and assimilation of content theoretical material
Teacher's signature
The dynamic programming method allows you to successfully solve many economic objectives(see, for example,). Let's consider one of the simplest such problems. We have at our disposal some reserve of funds (resources) K, which must be distributed among enterprises. Each of the enterprises, when some funds are invested in it, generates income that depends on , i.e., representing some kind of function. All functions are given (of course, these functions are non-decreasing).
The question is, how should funds K be distributed among enterprises so that in total they generate maximum income?
This problem is easily solved using the dynamic programming method. Although in its formulation it does not contain any mention of time, it is still possible to mentally unfold the operation of distributing funds in some sequence, considering the first step to be the investment of funds in the enterprise, the second - to, etc.
Controlled system S in in this case- funds or resources that are distributed. The state of the system S before each step is characterized by one number S - the available stock of funds not yet invested. In this task, “step management” is the funds allocated to enterprises. It is required to find optimal control, i.e. such a set of numbers for which the total income is maximum:
Let us solve this problem first in general, formulaic form, and then for specific numerical data. Let us find for each step the conditional optimal gain (from this step to the end), if we come to this step with a reserve of funds S. Let us denote the conditional optimal gain , and the corresponding conditional optimal control - the funds invested in the enterprise -
Let's start optimization from the last step. Let us approach this step with a balance of funds S. What should we do? Obviously, invest the entire amount S in the enterprise. Therefore, the conditional optimal control at the th step: give the last enterprise all available funds S, i.e.
and the conditional optimal gain
Given a whole range of values of S (locating them quite closely), we will know for each value of S . The last step is optimized.
Let's move on to the penultimate step. Let us approach it with a reserve of funds S. Let us denote the conditional optimal payoff on two last steps x: (which is already optimized). If we allocate funds to the enterprise at the step, then there will be left for the last step. Our winnings at the last two steps will be equal to
and you need to find one at which this gain is maximum:
The sign means that the maximum value is taken over all possible values (we cannot put in more than S), from the expression in curly brackets. This maximum is the conditional optimal gain for the last two steps, and the value at which this maximum is achieved is the conditional optimal control at the step.
and the corresponding conditional optimal control is the value at which this maximum is achieved.
Continuing in this way, we will finally reach the enterprise. Here we will not need to vary the values of S; we know for sure that the stock of funds before the first step is equal to K:
So, the maximum gain (income) from all enterprises has been found. Now all that remains is to “read the recommendations.” The value at which the maximum (13.4) is reached is the optimal control at the 1st step.
After we invest these funds in the first enterprise, we will have them left. “Reading” the recommendation for this value S, we allocate to the second enterprise optimal quantity means: etc. until the end.
Now let's solve a numerical example. The initial stock of funds (standard units), and it is required to optimally distribute it among five enterprises. For simplicity, we assume that only whole amounts of funds are invested. The income functions are given in Table 13.1.
Table 13.1
In each column, starting from a certain amount of investment, income stops increasing (in reality, this corresponds to the fact that each enterprise is able to “master” only a limited amount of funds).
Let's carry out conditional optimization as described above, starting from the last, 5th step. Every time we approach the next step, having a reserve of funds?, we try to allocate one or another amount of funds for this step, take the winnings at this step according to table 13.1, add them with the already optimized winnings at all subsequent steps until the end (taking into account that we already have less funds left, just for the amount of funds that we have allocated) and find the investment at which this amount reaches its maximum. This investment is the conditional optimal control at this step, and the maximum itself is the conditional optimal gain.
Table 13.2 shows the results of conditional optimization for all steps. The table is constructed as follows: the first column gives the values of the stock of funds S with which we approach this step. The table is further divided into five pairs of columns, corresponding to the step number.
Table 13.2
The first column of each pair gives the value of the conditional optimal control, the second - the conditional optimal gain. The table is filled from left to right, top to bottom. The decision at the fifth - last - step is forced: all funds are allocated; At all other steps, the solution must be optimized. As a result of sequential optimization of the 5th, 4th, 3rd, 2nd and 1st steps we get full list all recommendations for optimal control and the unconditional optimal gain W for the entire operation - in this case it is equal to 5.6. In the last two columns of Table 13.2, only one row is filled in, since we know exactly the state of the system before the start of the first step: . Optimal controls at all steps are highlighted with a frame. Thus, we received the final conclusion: we must allocate two units out of ten to the first enterprise, five units to the second, two to the third, none to the fourth, and one unit to the fifth. With this distribution, the income will be maximum and equal to 5.6.
Send your good work in the knowledge base is simple. Use the form below
Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.
Posted on http://www.allbest.ru/
Resource allocation problem using dynamic programming method
To expand the production capacity of three enterprises A, B and C, a certain number of units of additional electricity are allocated in the amount of x 0 = 8 units. Electricity can be released in the form of 1, 2, 3, 4, 5, 6, 7 and 8 units. By investing x i units of electricity in the development of the i-th enterprise, you can receive income from i units at the enterprise. Exist different variants x i (k) allocation of additional electricity. They bring income to i (k), k=1,n. Possible options development of enterprises are given in Table 1. The total income for all enterprises should be maximum, i.e. y=? y i (k)>max
Table 1. Enterprise development options
|
Option k |
Enterprise A |
Enterprise B |
Enterprise C |
||||
Mathematical staging tasks:
y=? at i (k)> max
?X i (k)?x 0
Solution:
Let's start considering the procedure for solving the problem at hand from the last (3 steps) stage (Table 2), at which investments are allocated to enterprise C. Conditional optimal control at the third stage is sought as a solution to the equation
g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4
Table 2. Conditionally optimal solutions (step 3)
|
State |
Control |
|||||||
There are four possibilities for investing funds - four step controls x C (1) = 0 units, x C (2) = 1 unit, x C (3) = 2 units, x C (4) = 3 units. and nine theoretically possible states of the system S 2 preceding the allocation of funds to enterprise C - the volumes of investments not distributed to the 3rd stage: 0,1,2,3,4,5,6,7,8.
Let us assume that the system was in state S 2 =2. Then, for step control x C (2) = 1, the income of C (2) will be equal to 3 units. (Table 3), and step control x C (3) = 2 will be optimal for this state, giving a conditionally maximum gain g c (S 2) = 5. If the system was in state S 2 =3, then all step controls are allowed: x C (1) = 0 units, x C (2) = 1 unit, x C (3) = 2 units, x C (4) = 3 units. , and the optimal control will be x C (4) = 3, which provides a conditionally maximum gain g c (S 2) = 6.
Table 3 dynamic programming investment distribution
All possible states preceding the 3rd stage are filled in similarly. Optimal values indicators are highlighted in bold in the tables.
Next, the second stage is considered in the same way (Table 4), which consists of allocating investments to enterprise A. At the second stage, the total gain is the sum of the winnings received in the third and second stages, and is given by the ratio:
g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4
Thus, for the state S 1 =3 with step control x A (2) = 1 we obtain:
g A (S 1)=max k f A +g c ]
Max k 4+g c =4+5=9, where we find from Table 1, and g c from Table 3. All states are filled in similarly.
Table 4. Conditionally optimal solutions (step 2)
|
State |
f A +g c |
Control |
||||||
Here situations arise in which the optimal solution will not be the only one. Thus, in the state S 1 = 3, step controls x A (2) = 1 and x A (3) = 2 will be conditionally optimal, giving the same gain g A (S 1)=9
Table 5. Unconditionally optimal solutions (step 1)
At the first stage (Table 5) - the allocation of investments to enterprise B - there is only one previous state of the system, corresponding to the initial state S 0 =8. The unconditionally optimal gain is determined by the expression:
y * = g B (S 0)= max k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5
Unconditionally optimal controls that ensure maximum income can be different.
Scheme for finding everyone optimal options distribution of investments between enterprises (Table 6) is presented in Figure 1.
Table 6. Optimal distribution of investments.
Figure 1. Scheme of optimal distribution of investments between enterprises
Conclusion: having considered the problem of resource allocation using the dynamic programming method, two options for optimal resource allocation have been identified.
Posted on Allbest.ru
...Similar documents
general characteristics and economic performance indicators of the three enterprises under study. Solving the problem of production planning, as well as investment distribution using linear and dynamic programming. Comparative analysis results.
course work, added 04/25/2015
Multi-step processes in dynamic tasks. The principle of optimality and recurrence relations. Dynamic programming method. Problems of optimal allocation of funds for production expansion and production program planning.
course work, added 12/30/2010
Dynamic programming method and its main stages. Optimal equipment replacement strategy. Minimizing costs for construction and operation of enterprises. Optimal distribution resources in STROYKROVLYA LLC and investments in PKT Khimvolokno.
course work, added 01/08/2015
Mathematical model of production planning. Drawing up an optimal plan production activities enterprise method linear programming. Finding the best way distribution of monetary resources during the planning period.
thesis, added 08/07/2013
Calculation of transportation costs using the method minimum costs. Finding conditional optimal equality in the process of dynamic programming. Linear algebraic equation Kolmogorov for the average non-failure time of a redundant system.
course work, added 01/14/2011
Graphical method solving the problem of optimization of production processes. Application of a simplex algorithm to solve an economically optimized production management problem. Dynamic programming method for selecting the optimal path profile.
test, added 10/15/2010
Optimal distribution plan Money between enterprises. Developing a plan for each enterprise in which the return on investment will be highest value. Using linear and dynamic programming methods.
course work, added 12/16/2013
Character traits linear programming problems. General formulation of the production planning problem. Construction of a mathematical model of the distribution of company resources. Sensitivity Analysis optimal solution. Compiling a sustainability report.
presentation, added 12/02/2014
Finding the optimal securities portfolio. Review of methods for solving the problem. Construction of a mathematical model. Cone programming problem. Dependence of the initial capital distribution vector on one of the initial parameters.
thesis, added 02/11/2017
Dynamic programming model. The optimality principle and the Bellman equation. Description of the process of modeling and constructing a computational dynamic programming scheme. The problem of minimizing the costs of construction and operation of enterprises.
Instructions. Select the number of businesses.
Example No. 1. The operation of two enterprises is planned for n years. Initial resources equal to s0. Funds x invested in the 1st enterprise at the beginning of the year give profit f1(x) at the end of the year and are returned in the amount of g1(x). Funds y invested in the 2nd enterprise at the beginning of the year give profit f2(y) at the end of the year and are returned in the amount of g2(y). At the end of the year, the returned funds are redistributed between industries. Determine the optimal fund distribution plan and find the maximum profit.
Let's solve the problem using the dynamic programming method. Control operation production process Let's break it down into stages. On each of them we will choose control so that it leads to winnings both on at this stage, and on all subsequent ones until the end of the operation. This is optimality principle, formulated by the American mathematician A. Bellman.
Let's divide the entire period into three stages by year and number them starting from the first.
Let us denote by x k And y k the amount of funds allocated to each enterprise at the k-th stage, and after x k + y k = a k- the total amount of funds at this stage. Then the first enterprise brings in 3 at this stage x k, and the second is 4 y k units of income. Total income at k-th stage 3 x k + 4y k.
Let us denote by f k ( a k) is the maximum income that the industry receives from both enterprises at the kth and all subsequent ones. Then the functional equation reflecting the Bellman optimality principle takes the form:
f k (a k)=max(3x k + 4y k +f k +1 (a k +1)).(1)
Because x k + y k = a k , theny k = a k - x k and3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . That's whyf k (a k) = max(-x k + 4a k + f k+1 (ak+1)). (2)
0 ≤ x k ≤ a k
In addition, ak is the funds allocated to enterprises at the k-th stage, and they are determined by the balance of funds received at the previous (k-1) stage. Therefore, according to the conditions of the problem, optimal control at each stage
ak = 0.5x k -1 + 0.2y k -1 = 0.5x k -1 +0.2(a k -1 -x k -1) = 0.3x k -1 +0.2a k -1 . (3)
I. Optimization conditions
We start planning from the last third stage
At k=
3
we obtain from (2)
f 3 (a 3) = max (- x 3 + 4a 3 + f 4 (a 4))
0 ≤ x 3 ≤ a 3
Since there is no fourth stage, then f 4 (a 4)=0 And
f 3 (a 3) = max (- x 3 + 4a 3 )=4a 3
0 ≤ x 3 ≤ a 3
(maximum expression ( -
x 3 + 4a 3) will be at x 3 =0)).
So for the third last stage we have: f 3 (a 3) = 4a 3 ,x 3 = 0,y 3 =a 3 -x 3 =a 3 ,
Where a 3 = 0,3x 2 + 0,2a 2 , which follows from formula (3).
At k = 2 from (2) and (3) we obtain:
f(a 2) = max (-x 2 + 4a 2 + f 3 (a 3))=
0 ≤ x ≤ a 2
=max (-x 2 + 4a 2 + 4a 3 )= max (-x 2 + 4a 2 + 4( 0,3x 2 + 0,2a 2)) max(0.2x 2 + 4.8a 2 ) 5a
0 ≤ x ≤ a 2
because the maximum of the expression ( 0,2
x 2 + 4.8a 2) will be at x 2 =a 2.
Then for the second stage we have: f 2 (a 2) = 5a 2, x 2 = a 2, y 2 = a 2 x 2 = 0, while
a 2 = 0.3x 1 + 0.2a 1 taking into account (3).
At k = 1 taking into account (2) and (3) we obtain:
f 1 (a 1) = max (-x 1 + 4a 1 + f 2 (a 2))=
0 ≤ x ≤ a 1
= max (-x 1 + 4a 1 + 5a 2 )= max (-x 1 + 4a 2 + 5(0.3x 1 + 0.2a 2))= max (0.5x 1 + 5a 1 )=5, 5a 1
0 ≤ x ≤ a 1
at x 1 = a 1.
So for the first stage f 1 (a 1) = 5.5a 1 ,x 1 =a 1 ,y 1 = 0.
The process is over. At the first stage, the total amount of distributed funds is known - a 1= 900 units Then the maximum income received by both enterprises in three years will be f 1 (a 1) = 5.5*900 = 4950 den. units
II. Unconditional optimization
Let's find out what the optimal management of the process of allocating funds between the first and second enterprises should be to obtain maximum income in the amount of 4950 den. units
1st year. Because x 1 =a 1 And ,
y 1 = 0, then all funds in the amount of 900 den. units are given to the first enterprise.
2nd year. Funds are allocated a 2 = 0.3x 1 + 0.2a 1 = 0.5 a 1=450 units, x 2 = a 2, y 2 = 0.
All of them are transferred to the first enterprise.
3rd year. Funds are allocated a 3 = 0,3x 2 + 0,2a 2 = 0,5 a 2= 225 units, x 3 = 0,y 3 =a 3. All of them are transferred to the second enterprise.
We present the results of the solution in the form of a table.
| Period | Facilities | Enterprise No. 1 | Enterprise No. 2 | Remainder | Income |
| 1 | 900 | 900 | 0 | 450 | 2700 |
| 2 | 450 | 450 | 0 | 225 | 1350 |
| 3 | 225 | 0 | 225 | 45 | 900 |
| 4950 |
Example No. 2. Optimal phased distribution of funds between enterprises during the planning period.
The management of the company, which has a cooperation agreement with three small enterprises, has allocated working capital for them in the amount of 100,000 USD for the planned annual period. For each enterprise, the functions of quarterly income and quarterly working capital balance are known, depending on the amount x allocated for the quarter. At the beginning of the quarter, the funds are distributed in full between three enterprises (income is calculated from these invested funds), and at the end of the quarter, the remaining funds are accumulated by the company’s management and again distributed in full between the enterprises.
Draw up a plan for the quarterly distribution of funds for the year (4 quarters), allowing you to achieve the maximum total income for the year.
f 1 (x)=1.2x, f 2 (x)=1.5x, f 3 (x)=2x; g 1 (x)=0.7x, g 2 (x)=0.6x, g 3 (x)=0.1x
