Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Laboratory work №7

Topic: Multistage decision-making problems.

Dynamic programming method.

Goal of the work:

- to study the methods of making multi-stage decisions;

- implement the method of dynamic programming in the MS Excel environment, check the adequacy of the obtained results.

The order of work

1. Study theoretical information about the task of making multi-stage decisions under conditions of certainty.

2. Study the essence and features of the dynamic programming method and Bellman's principle of optimality.

3. Choose the subject area of decision-making.

4. Perform a verbal formulation of the decision-making task in the chosen subject area, determine the target functions.

5. Perform presentation of initial data and search for an optimal solution using the Bellman method in the MS Excel environment. Make a graphic representation of the problem. Explain the result by showing the optimal solution on the graph.Compare the obtained solutions. Explain the results. Demonstrate the process of finding solutions to the teacher.

6. Make a report on laboratory work.

7. Defend laboratory work.

Content of the report

1. Topic of the work.

2. Goal of the work.

3. Individual task.

4. Description of the work execution.

5. Interpretation of the obtained results.

6. Conclusions.

Individual tasks

In accordance with the selected subject area and individual task (table 1), connect the vertices of the decision-making stages and set the weights of the connections. Find the best solution by performing the necessary calculations in MS Excel.

Table 1

BRIEF THEORETICAL INFORMATION

1 DYNAMIC PROGRAMMING

Dynamic programming is a mathematical method of finding optimal solutions for managing multi-sttage processes in which the state of the certain system changes over time or in stages. Such systems and processes are widespread in the real world. To manage them, it is necessary to use mathematical methods, which include the method of dynamic programming (DP). The theoretical basis of the DP method is the principle of optimality.

All objects in the real world change over time. In a simplified way, such a change of a wide class of objects and systems can be presented as discrete, step-by-step or phased. The process, in which there is a sequential transition of an object or system from one state to another, is called a multi-stage process.

The states of managed systems can be influenced by the decision maker. When managing the system, the task of finding and choosing the best, expedient, optimal management solution arises. Such problems are called problems of managing multi-stage processes, problems of multi-stage optimization, problems of dynamic programming.

Such tasks include:

1) distribution of resources (financial, material information, etc.) between several enterprises in order to obtain the maximum profit for a certain period;

2) drawing up calendar plans for project management;

3) management of stocks of raw materials and finished products to ensure uninterrupted operation of the enterprise;

4) road design under the conditions of complex topography;

5) loading vehicles with objects of various sizes for the transportation of goods;

6) robot and people training with augmented reality.

DP is associated with the name of Richard Bellman, who formulated a principle that allows you to significantly reduce the number of decisions in multi-stage nonlinear problems.

Formulation of the problem

We consider the system S, which can change its state over time. There is a process running in the system. The process is controlled. Control is a way of influencing the system.

The decision-making process can be divided into n steps:

S₀^k – the initial state of the system (can be an element of the set of initial states S₀^k∈S₀);

S_i^j – the state of the system after the i-th step;

S_n^m – the final state of the system (can be an element of a set of final states S_n^m∈S_n);

U_i – control at the i-th step;

U(U₁ - U_n) – control vector.

Under the control U(U₁ - U_n) the system transits from the state S₀^k to the state S_n^m:

With the transition from the state S₀^k to the state S_n^m decision selection is performed using a criterion W.

Among all possible controls U, which transit the system from the state S₀^k to the state S_n^m, it is necessary to choose the one that gives the maximum function W.

Dynamic programming tasks are solved by the method of forward sweep (from the first step to the last) and the reverse sweep method (from the last step to the first).

The process of finding a solution is divided into two stages:

- conditional optimization;

- unconditional optimization.

At the stage of conditional optimization, conditional optimal gains and conditional optimal controls are determined.

Bellman's method

The Bellman optimality method is based on the principle of backward sweep): control at each step must be chosen so that the sum of the income should be maximal or cost should be minimal at all subsequent steps.

Equation of a state: S_i= S_i(U_i , S_i-1) – the system has transited to the state S_i from S_i-1 under control of U_i, and an income was obtained f(U_i,S_i-1).

W_i+1(S_i) – optimal gain in the following steps.

f(U_i , S_i-1)+W_i+1(S_i) – a gain on this step and on all subsequent steps.

According to the Bellman principle, a control U_i you need to choose so that this amount has a maximum (if it is about our incomes) or a minimum (in the case of expenses).

For conditional optimization:

- the basic functional equation:

W_i(S_i–1) = max_Ui{f_i(U_i,S_i-1) + W_i+1(S_i)}.

- functional equation for the last step:

W_n(S_n–1) = max_Un{f_n(U_n,S_n-1)}.

For unconditional optimization:

- if the initial state is given, then W_max = W₁(S₀).

- if the initial state is given, but it is said that it belongs to the set of initial states, then W_max = max_S0єS W₁(S₀) = W₁(S₀^*).

You can visualize the problem and the solution process using an oriented graph. On the graph, the states of the system are represented by vertices in columns. Columns are decision stages and vertices are alternative solutions. The transition of the system from one state to another is displayed by edges. Each edge is assigned a cost, that is, a real number. The task is to mark the graph, that is, to replace certain edges with arcs when moving from the final vertex to the initial one. The found path will be the optimal solution.