Basic concepts of operations research. Operations research Game solution in mixed strategies
I.N. Slinkin
Textbook for students of pedagogical universities
majoring in Informatics
Shadrinsk, 2003
Slinkina I.N.
Operations research. Teaching aid. - Shadrinsk: publishing house of the Shadrinsk State Pedagogical Institute, 2002. - 106 p.
Slinkina I.N. – candidate of pedagogical sciences
The textbook presents the theoretical part of the course "Operations Research". It is intended for students of full-time and part-time departments of faculties implementing the specialty "Informatics".
© Shadrinsky State Pedagogical Institute
© Slinkina I.N., 2002
Questions to the blocks in the course "Operations Research" 5
1.1. The subject and objectives of operations research 7
1.2. Basic concepts and principles of operations research 8
1.3. Mathematical models of operations 10
1.4. Understanding Linear Programming 12
1.5. Examples of economic problems of linear programming. The problem of the best use of resources 13
1.6. Examples of economic problems of linear programming. The problem of choosing optimal technologies 15
1.7. Examples of economic problems of linear programming. Mixture Problem 16
1.8. Examples of economic problems of linear programming. Transport task 17
1.9. Basic types of writing linear programming problems 19
1.10. Conversion methods 21
1.11. Transition to canonical form 22
1.12. Transition to symmetrical notation 25
2.1. Geometric interpretation of a linear programming problem 28
2.2. Solving Linear Programming Problems Graphically 29
2.3. Properties of Solutions to a Linear Programming Problem 34
2.4. General idea of the simplex method 35
2.5. Construction of an initial reference plan for solving linear programming problems using the simplex method 36
2.6. A sign of the optimality of the basic plan. Simplex tables 40
2.7. Transition to a non-worst reference plan. 44
2.8. Simplex transformations 46
2.9. Alternative optimum (a sign of the infinity of the set of reference plans) 51
2.10. The sign of unboundedness of the objective function 52
2.11. The concept of degeneration. Monotonicity and finiteness of the simplex method. Looping 53
2.12. The concept of duality for symmetric linear programming problems 54
3.1. Asymmetric Dual Problems 57
3.2. Open and closed models of the transport problem 61
3.3. Construction of the initial basic plan. Northwest Corner Rule 63
3.4. Construction of the initial basic plan. Minimum element rule 64
3.5. Construction of the initial basic plan. Vogel method 64
3.6. Potential method 65
3.7. Solving Transport Problems with Bandwidth Limitations 69
3.8. Examples of discrete programming problems. The problem of container transportation. Assignment problem 71
3.9. The essence of discrete optimization methods 72
3.10. Convex Programming Problem 74
3.11. Method of Lagrange multipliers 75
3.12. Gradient methods 77
4.1. Methods of penalty and barrier functions 78
4.2. Dynamic programming. Basic concepts. Essence of solution methods 79
4.3. Stochastic programming. Basic concepts 81
4.4. Zero-sum matrix games 83
4.5. Pure and mixed strategies and their properties 85
4.6. Properties of pure and mixed strategies 88
4.7. Reduction of a matrix game to ZLP 92
4.8. Tasks of the queuing theory. Classification of queuing systems 94
4.9. Event streams 96
4.10. Scheme of death and reproduction 97
4.11. Little Formula 99
4.12. The simplest queuing systems 101
Questions to the blocks in the course "Operations Research"
Block 1
1. Subject and tasks of operations research.
2. Basic concepts and principles of operations research.
3. Mathematical models of operations.
4. The concept of linear programming.
5. Examples of economic problems of linear programming. Task
6. Examples of economic problems of linear programming. The problem of choosing optimal technologies.
7. Examples of economic problems of linear programming. Mixture problem.
8. Examples of economic problems of linear programming. transport task.
9. Basic types of writing linear programming problems.
10. Methods of transformation.
11. Transition to the canonical form.
12. Transition to the symmetrical notation.
Block 2
1. Geometric interpretation of the linear programming problem.
2. Solving problems of linear programming by a graphical method.
3. Properties of solutions to a linear programming problem.
4. General idea of the simplex method.
5. Construction of the initial basic plan for solving problems of linear programming by the simplex method.
6. Sign of the optimality of the basic plan. Simplex tables.
7. Transition to a non-worst reference plan.
8. Simplex transformations.
9. Alternative optimum (a sign of the infinity of the set of reference plans).
10. Sign of unboundedness of the objective function.
11. The concept of degeneration. Monotonicity and finiteness of the simplex method. Looping.
12. The concept of duality for symmetric linear programming problems.
Block 3
1. Asymmetric dual problems.
2. Open and closed models of the transport problem.
3. Construction of the initial basic plan. Northwest corner rule.
4. Construction of the initial basic plan. Minimum element rule.
5. Construction of the initial basic plan. Vogel method.
6. Method of potentials.
7. Solving transport problems with limited bandwidth.
8. Examples of discrete programming problems. The problem of container transportation. Assignment task.
9. Essence of discrete optimization methods.
10. The problem of convex programming.
11. Method of Lagrange multipliers.
12. Gradient methods.
Block 4
1. Method of penalty and barrier functions.
2. Dynamic programming. Basic concepts. Essence of solution methods.
3. Stochastic programming. Basic concepts.
4. Matrix games with zero sum.
5. Pure and mixed strategies.
6. Properties of pure and mixed strategies.
7. Reduction of the matrix game to the LLP
8. Problems of the theory of queuing. Classification of queuing systems.
9. Streams of events.
10. Scheme of death and reproduction.
11. Little formula.
12. The simplest queuing systems.
Block 1.
The subject and objectives of operations research
The current state of science and technology, in particular, the development of computer tools for calculating and mathematical substantiation of theories has made it possible to significantly simplify the solution of many problems posed to various branches of science. Many of the problems come down to solving the issue of optimizing production, optimal process control.
The needs of practice have brought to life special scientific methods, which are conveniently grouped under the name "operations research".
Definition: By operations research we will understand the application of mathematical, quantitative methods to justify decisions in all areas of purposeful human activity.
Let some action be taken to achieve a certain goal. The person (or group of persons) organizing the event always has some freedom of choice: it can be organized in one way or another. The decision is some choice from a number of options available to the organizer.
The need to make decisions and test the proposed decision hypothesis is mathematically confirmed by the following examples:
Task 1. About the best use of resources.
The company manufactures several types of products. For their manufacture, some resources are used (including human, energy, etc.). It is necessary to calculate how to plan the work of the enterprise so that the cost of resources is minimal and profit is maximum.
Task 2. About mixtures.
It is necessary to prepare a mixture with certain properties. To do this, you can use some "products" (for calculating diets - food, for feed mixtures - food for animals, for technical mixtures - alloys, liquids for technical purposes). the task is to choose the optimal amount of products (for the price) to obtain the optimal amount of the mixture.
Task 3. transport task.
There is a network of enterprises producing the same type of products of the same quality and a network of consumers of these products. Consumers and suppliers are connected by means of communication (roads, railway lines, air lines). Transportation tariffs are determined. It is necessary to calculate the optimal plan for the transportation of products so that the costs of transportation are minimal, the requests of all consumers are satisfied, and all goods are exported from suppliers.
In each of the above examples, we are talking about some kind of event pursuing a specific goal. Some conditions are given that characterize the situation (in particular, the means that can be disposed of). Within the framework of these conditions, it is required to make such a decision that the planned event would be in some sense more profitable.
In accordance with these general features, general methods for solving such problems are also developed, which together make up the methodological scheme and apparatus of operations research.
Currently, automated control systems (ACS) based on the use of computer technology are widely used. The creation of an automated control system is impossible without a preliminary examination of the controlled process by the methods of mathematical modeling. With the growth in the scale and complexity of events, mathematical methods for justifying decisions are becoming increasingly important.
Basic concepts and principles of operations research
Definition: An operation is any event (system of actions) united by a single plan and directed towards the achievement of some goal.
An operation is always a controlled event, i.e. it depends on the calculations how to choose the parameters that characterize its organization. "Organization" here is understood in the broad sense of the word, including the set of technical means used in the operation.
Definition: Any definite choice depending on the decision parameters is called a decision.
Definition: Optimal solutions are those that are preferred over others for one reason or another.
Purpose of Operations Research– preliminary quantitative substantiation of optimal solutions.
Sometimes, as a result of the study, it is possible to indicate a single, strictly defined solution; much more often, it is possible to identify an area of practically equivalent optimal solutions within which a final choice can be made.
Decision-making itself goes beyond the scope of operations research and belongs to the competence of a responsible person, more often a group of people who are given the right to make a final choice and who are responsible for this choice.
Definition: The parameters, the totality of which forms a solution, are called elements of the solution.
Various numbers, vectors, functions, physical signs, etc. can appear as elements of the solution. For simplicity, the entire set of elements of the solution will be denoted by x.
In addition to the solution elements in any task of operations research, there are also given conditions that are fixed in the condition of the problem and cannot be violated. In particular, such conditions include the means (material, technical, human) that can be disposed of, and other restrictions imposed on the solution. In their totality, they form the so-called "set of possible solutions". Let's denote this set X, and the fact that the solution x belongs to this set, we will write: хОХ.
To compare different solutions in terms of efficiency, you need to have some kind of quantitative criterion, the so-called performance indicator (objective function). This indicator is chosen so that it reflects the target orientation of the operation. The best solution will be considered the one that contributes to the achievement of the goal to the maximum extent. To choose the performance indicator Z, you first need to determine what the solution of the problem should lead to. When choosing a solution, preference is given to one that turns the Z efficiency indicator to a maximum or a minimum. For example, I would like to maximize the income from an operation; if costs are an indicator of efficiency, it is desirable to minimize them.
Very often, the operation is accompanied by the action of random factors: “whims” of nature, fluctuations in supply and demand, failures of technical devices, etc. In such cases, usually, not the value itself, which we would like to maximize (minimize), but the average value (mathematical expectation) is taken as an indicator of efficiency.
The task of choosing a performance indicator is solved for each problem individually.
Task 1. About the best use of resources.
The task of the operation is to produce the maximum amount of goods. The efficiency indicator Z is the profit from the sale of goods at the minimum cost of resources (max Z).
Task 2. About mixtures.
A natural indicator of efficiency, suggested by the formulation of the problem, is the price of the products required for the mixture, provided that the specified properties of the mixture (min Z) must be preserved.
Task 3. transport task.
The task of the operation is to ensure the supply of goods to consumers at minimal transportation costs. Efficiency indicator Z is the total cost of transporting goods per unit of time (min Z).
1. The subject and objectives of the study of operations in the economy. Basic concepts of the theory of operations research.
The subject of operations research is organizational management systems or organizations that consist of a large number of interacting units that are not always consistent with each other and may be opposite.
The purpose of operations research is to quantitatively substantiate decisions made on the management of organizations
The solution that turns out to be the most beneficial for the entire organization is called optimal, and the solution that is most beneficial to one or more departments will be suboptimal.
Operations research is a science that deals with the development and practical application of methods for the most optimal management of organizational systems.
An operation is any event (system of actions) united by a single plan and directed towards the achievement of some goal.
The purpose of operations research is a preliminary quantitative justification of optimal solutions.
Any definite choice of parameters depending on us is called a decision. Solutions are called optimal if they are preferred over others for one reason or another.
The parameters, the totality of which forms a solution, are called elements of the solution.
The set of admissible solutions are given conditions that are fixed and cannot be violated.
Performance indicator - a quantitative measure that allows you to compare different solutions in terms of efficiency.
2. The concept of network planning and management. Network model of the process and its elements.
The method of working with network graphs - network planning - is based on graph theory. Translated from Greek, a graph (grafpho - I write) represents a system of points, some of which are connected by lines - arcs (or edges). This is a topological (mathematical) model of interacting systems. With the help of graphs, it is possible to solve not only network planning problems, but also other problems. The network planning method is used when planning a complex of interconnected works. It allows you to visualize the organizational and technological sequence of work and establish the relationship between them. In addition, it allows you to coordinate operations of varying degrees of complexity and identify operations on which the duration of the entire work (i.e. organizational event) depends, as well as focus on the timely completion of each operation.
The basis of network planning and management is the network model (SM), which models a set of interrelated activities and events that reflect the process of achieving a specific goal. It can be presented in the form of a graph or a table.
Basic concepts of the network model:
Event, work, path.
Events are the results of the execution of one or more activities. They have no extension in time.
A path is a chain of work following one after another, connecting the initial and final vertices.
The duration of a path is determined by the sum of the durations of its constituent works.
3. Construction and ordering of the network diagram.
A network model is used as a model that reflects the technological and organizational interrelations of the process of construction and installation works in network planning and management systems (SPU).
A network model is a graphical representation of processes, the implementation of which leads to the achievement of one or more goals, indicating the established relationships between these processes. The network diagram is a network model with calculated time parameters.
The structure of the network diagram, which determines the mutual dependence of work and events, is called its topology.
Work is a production process that requires time, labor and material resources, which, when performed, leads to the achievement of certain results.
Dependence (fictitious work) that does not require time is depicted by a dotted arrow. Dummy work is used in a network diagram to show the relationships between events and activities.
In the network schedule, time, cost and other characteristics of work are used.
Duration of work - the time of execution of this work in working days or other units of time, the same for all work in the network. The duration of the work can be either a certain (deterministic) or a random variable specified by the law of its distribution.
The cost of work is the direct costs necessary for its implementation, depending on the duration and conditions of this work.
Resources are characterized by the need for physical units necessary to perform this work.
Quality, reliability and other indicators of work serve as additional characteristics of work.
An event is the fact of completion of one or more jobs, necessary and sufficient for the start of one or more subsequent jobs. Each event is assigned a number, called a code. Each job is defined by two events: a start event code, denoted by i, and an end event code, denoted by j.
Events that do not have previous activities are called initial events; events that do not have subsequent - final.
1 The direction of building a network can be of a different nature. A network graph can be built from the initial event to the final one and from the final one to the initial (initial), as well as from any of the events to the initial or final one.
2 When building a network, the following questions are solved:
What work (work) needs to be done to start this work;
What work should be done in parallel with this work;
3 The initial network schedule is built without taking into account the duration of the activities that make up the network.
4 The form of the graph should be simple and visually easy to perceive.
5 Between two events there can be only one work. During the construction of buildings and structures, work can be performed sequentially, in parallel or simultaneously, some in series and some in parallel, as a result of which various dependencies are formed between individual works.
The numbering (coding) of events is performed after the completion of the network construction, starting from the initial event to the final one.
4. Critical path of the network diagram. Time reserves. Early and late dates of events and activities in the network diagram.
In a network diagram, there can be multiple paths between start and end events. The path with the longest duration is called the critical path. The critical path determines the total duration of activities. All other paths have a shorter duration, and therefore the work performed in them has time reserves.
The critical path is indicated on the network diagram by thickened or double lines (arrows).
Two concepts are of particular importance when drawing up a network diagram:
Early start of work - the period before which it is impossible to start this work without violating the accepted technological sequence. It is determined by the longest path from the initiating event to the start of this work.
Late finish is the latest end date for a job that does not increase the total duration of the job. It is determined by the shortest path from a given event to the completion of all work.
Early finish is the deadline before which the work cannot be completed. It is equal to the early start plus the duration of this work.
Late start - the period after which it is impossible to start this work without increasing the total duration of construction. It is equal to the late finish minus the duration of the given work.
If the event is the end of only one job (that is, only one arrow is directed to it), then the early end of this job coincides with the early start of the next one.
The total (full) reserve is the maximum time for which the execution of this work can be delayed without increasing the total duration of the work. It is determined by the difference between late and early start (or late and early finish - which is the same).
Private (free) reserve - this is the maximum time for which you can delay the execution of this work, without changing the early start of the next one. This fallback is only possible when the event includes two or more activities (dependencies), i.e. two or more arrows (solid or dotted) point to it. Then only one of these jobs will have an early finish that coincides with an early start of the subsequent job, while for the others these will be different values. This difference for each work will be its private reserve.
5. Dynamic programming. Bellman's principle of optimality and control.
Dynamic programming is one of the most powerful optimization techniques. The tasks of making rational decisions, choosing the best options, optimal control are dealt with by specialists of various profiles. Dynamic programming occupies a special position among optimization methods. This method is extremely attractive due to the simplicity and clarity of its basic principle - the principle of optimality. The scope of application of the principle of optimality is extremely wide, the range of problems to which it can be applied has not yet been fully outlined. From the very beginning, dynamic programming acts as a means of practical solution of optimization problems.
In addition to the principle of optimality, the main method of research, an important role in the apparatus of dynamic programming is played by the idea of immersing a specific optimization problem in a family of similar problems. Its third feature, which distinguishes it from other optimization methods, is the form of the final result. The application of the principle of optimality and the principle of immersion in multi-step, discrete processes lead to recurrent functional equations with respect to the optimal value of the quality criterion. The resulting equations make it possible to sequentially write out the optimal controls for the original problem. The advantage here is that the task of calculating the control for the entire process is divided into a number of simpler tasks of calculating the control for individual stages of the process.
The main drawback of the method is, in Bellman's words, the "curse of dimensionality" - its complexity increases catastrophically with increasing problem dimensionality.
6. The problem of the distribution of funds between enterprises.
It can be said that the procedure for constructing an optimal control by the dynamic programming method is divided into two stages: preliminary and final. At the preliminary stage, for each step, the SOC is determined depending on the state of the system (achieved as a result of previous steps), and the conditionally optimal gain at all remaining steps, starting from this one, is also dependent on the state. At the final stage, the (unconditional) optimal control for each step is determined. Preliminary (conditional) optimization is performed step by step in reverse order: from the last step to the first; final (unconditional) optimization - also by steps, but in a natural order: from the first step to the last. Of the two stages of optimization, the first is incomparably more important and time-consuming. After the end of the first stage, the implementation of the second stage presents no difficulty: all that remains is to "read" the recommendations already prepared at the first stage.
7. Statement of the problem of linear programming.
Linear programming is a popular tool for solving economic problems that are characterized by the presence of one criterion (for example, to maximize income from production through the optimal choice of a production program, or, for example, to minimize transportation costs, etc.). Economic tasks are characterized by resource constraints (material and/or financial). They are written as a system of inequalities, sometimes as equalities.
From the point of view of forecasting acceptable price intervals (or sales volumes) within the framework of a generalized non-parametric method, the use of linear programming means:
The criterion is the MAX price of the next product from the group of interest f.
The controlled variables are the prices of all products from group f.
The limitations in our forecasting problem using the generalized nonparametric method are:
a) a system of inequalities (constraints on the rationality of consumer behavior) (see 4.2. Forecasting within the framework of a generalized non-parametric method);
b) the requirement of non-negativity of the controlled variables (in our forecasting problem, we will require that the prices for products from group f do not fall below 80% of the prices at the last time point);
c) budget constraint in the form of equality - the requirement that the amount of costs for the purchase of products from group f be constant (taking into account 15% inflation, for example).
8. Graphical method for solving linear programming problems.
The graphical method is based on the geometric interpretation of a linear programming problem and is mainly used in solving problems of two-dimensional space and only some problems of three-dimensional space, since it is quite difficult to construct a solution polytope that is formed as a result of the intersection of half-spaces. The task of a space of dimensions greater than three cannot be represented graphically at all.
Let the linear programming problem be given in a two-dimensional space, i.e., the constraints contain two variables.
Find the minimum value of a function
(2.1) Z = С1х1+С2х2
a11x1 + a22x2 b1
(2.2)a21x1 + a22x2 b2
aM1x1 + aM2x2 bM
(2.3) x1 0, x2 0
Let us assume that system (2.2) under condition (2.3) is consistent and its solution polygon is bounded. Each of the inequalities (2.2) and (2.3), as noted above, defines a half-plane with boundary lines: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0, x2=0 . The linear function (2.1) for fixed values of Z is the equation of a straight line: C1x1 + C2x2 = const. Let us construct a polygon of solutions to the constraint system (2.2) and a graph of the linear function (2.1) for Z = 0 (Fig. 2.1). Then the given problem of linear programming can be given the following interpretation. Find the point of the solution polygon at which the straight line C1x1 + C2x2 = const is the support line and the Z function reaches a minimum.
The values Z = C1x1 + C2x2 increase in the direction of the vector N = (C1, C2), so we move the line Z = 0 parallel to itself in the direction of the vector X. From fig. 2.1 it follows that the line twice becomes a reference in relation to the polygon of solutions (at points A and C), and the minimum value is taken at point A. The coordinates of the point A (x1, x2) are found by solving the system of equations of the lines AB and AE.
If the decision polygon is an unbounded polygonal area, then two cases are possible.
Case 1. The straight line C1x1 + C2x2 = const, moving in the direction of the vector N or opposite to it, constantly intersects the solution polygon and is not a reference to it at any point. In this case, the linear function is unbounded on the solution polygon both above and below (Fig. 2.2).
Case 2. The straight line, moving, nevertheless becomes a support relative to the polygon of solutions (Fig. 2.2, a - 2.2, c). Then, depending on the type of area, a linear function can be bounded from above and unbounded from below (Fig. 2.2, a), bounded from below and unbounded from above (Fig. 2.2, b), or bounded both from below and from above (Fig. 2.2, c).
9. Simplex method.
The simplex method is the main one in linear programming. The solution of the problem begins with consideration of one of the vertices of the conditions polyhedron. If the vertex under study does not correspond to the maximum (minimum), then they move to the neighboring one, increasing the value of the goal function when solving the problem to the maximum and decreasing when solving the problem to the minimum. Thus, moving from one vertex to another improves the value of the goal function. Since the number of vertices of the polyhedron is limited, in a finite number of steps it is guaranteed to find the optimal value or establish the fact that the problem is unsolvable.
This method is universal, applicable to any linear programming problem in canonical form. The system of constraints here is a system of linear equations in which the number of unknowns is greater than the number of equations. If the rank of the system is r, then we can choose r unknowns, which we will express in terms of the remaining unknowns. For definiteness, we assume that the first consecutive unknowns X1, X2, ..., Xr are chosen. Then our system of equations can be written as
The simplex method is based on a theorem called the fundamental theorem of the simplex method. Among the optimal plans for a linear programming problem in canonical form, there is necessarily a reference solution to its system of constraints. If the optimal plan of the problem is unique, then it coincides with some reference solution. There are finitely many different support solutions for the constraint system. Therefore, the solution of the problem in the canonical form could be sought by enumerating the reference solutions and choosing among them the one for which the value of F is the largest. But, firstly, all the reference solutions are unknown and they need to be found, and, secondly, in real problems there are a lot of these solutions and direct enumeration is hardly possible. The simplex method is a certain procedure of directed enumeration of reference solutions. Based on some previously found reference solution using a certain algorithm of the simplex method, we calculate a new reference solution on which the value of the objective function F is not less than on the old one. After a series of steps, we arrive at a reference solution, which is the optimal plan.
10. Statement of the transport problem. Methods for determining base plans.
There are m points of departure ("suppliers") and n points of consumption ("consumers") of some identical product. For each item are defined:
ai - production volumes of the i-th supplier, i = 1, …, m;
вj - demand of the j-th consumer, j= 1,…,n;
cij - the cost of transporting one unit of production from point Ai - the i-th supplier, to point Bj - the j-th consumer.
For clarity, it is convenient to present the data in the form of a table, which is called the table of transportation costs.
It is required to find a transportation plan that would fully satisfy the demand of all consumers, while there would be enough supplies of suppliers and the total transportation costs would be minimal.
Under the transportation plan is understood the volume of traffic, i.e. the quantity of goods to be transported from the i-th supplier to the j-th consumer. To build a mathematical model of the problem, it is necessary to enter m n variables хij, i= 1,…, n, j= 1, …, m, each variable хij denotes the volume of traffic from point Ai to point Bj. The set of variables X = (xij) will be the plan that needs to be found based on the problem statement.
This is a condition for solving closed and open transport tasks (ZTZ).
Obviously, for the solvability of problem 1, it is necessary that the total demand does not exceed the volume of production from suppliers:
If this inequality is met strictly, then the problem is called "open" or "unbalanced", but if , then the problem is called a "closed" transport problem, and will have the form (2):
Balance condition.
This is a condition for solving closed transport tasks (ZTZ).
11. Algorithm for solving the transport problem.
The application of the algorithm requires compliance with a number of prerequisites:
1. The cost of transporting a unit of product from each point of production to each destination must be known.
2. The stock of products at each point of production must be known.
3. The food requirements at each point of consumption must be known.
4. The total supply must be equal to the total demand.
The algorithm for solving the transport problem consists of four stages:
Stage I. Presentation of data in the form of a standard table and search for any acceptable allocation of resources. An acceptable distribution of resources is such that it satisfies all demand at destinations and removes the entire supply of products from production points.
Stage 2. Checking the obtained resource allocation for optimality
Stage 3. If the resulting distribution of resources is not optimal, then the resources are redistributed, reducing the cost of transportation.
Stage 4. Re-checking the optimality of the obtained resource allocation.
This iterative process is repeated until an optimal solution is obtained.
12. Inventory management models.
Despite the fact that any inventory management model is designed to answer two basic questions (when and how much), there are a significant number of models that use a variety of mathematical tools to build.
This situation is explained by the difference in the initial conditions. The main basis for classifying inventory management models is the nature of the demand for stored products (recall that, from the point of view of a more general gradation, we are now considering only cases with independent demand).
So, depending on the nature of demand, inventory management models can be
deterministic;
probabilistic.
In turn, deterministic demand can be static, when the intensity of consumption does not change over time, or dynamic, when reliable demand can change over time.
Probabilistic demand can be stationary, when the probability density of demand does not change over time, and non-stationary, where the probability density function changes with time. The above classification is illustrated in the figure.
The simplest is the case of a deterministic static demand for products. However, this type of consumption is quite rare in practice. The most complex models are models of non-stationary type.
In addition to the nature of demand for products, when building inventory management models, many other factors must be taken into account, for example:
terms of execution of orders. The duration of the procurement period can be constant or be a random variable;
replenishment process. Can be instantaneous or distributed over time;
the presence of restrictions on working capital, storage space, etc.
13. Queuing systems (QS) and indicators of their effectiveness.
Queuing systems (QS) are systems of a special type that implement the repeated execution of tasks of the same type. Such systems play an important role in many areas of the economy, finance, production and everyday life. As examples of CMOs in the financial and economic; In the sphere, banks of various types (commercial, investment, mortgage, innovative, savings), insurance organizations, state joint-stock companies, companies, firms, associations, cooperatives, tax inspectorates, audit services, various communication systems (including telephone exchanges), loading and unloading complexes (ports, freight stations), gas stations, various enterprises and organizations in the service sector (shops, information desks, hairdressers, ticket offices, currency exchange offices, repair shops, hospitals). Systems such as computer networks, systems for collecting, storing and processing information, transport systems, automated production sites, production lines, various military systems, in particular air defense or missile defense systems, can also be considered as a kind of QS.
Each QS includes in its structure a certain number of service devices, which are called service channels (devices, lines). The role of channels can be played by various devices, persons performing certain operations (cashiers, operators, hairdressers, sellers), communication lines, cars, cranes, repair teams, railways, gas stations, etc.
Queuing systems can be single-channel or multi-channel.
Each QS is designed to serve (execute) a certain flow of applications (requirements) that arrive at the input of the system for the most part not regularly, but at random times. Servicing requests, in this case, also lasts not a constant, known time, but a random time, which depends on many random, sometimes unknown to us, reasons. After servicing the request, the channel is released and is ready to receive the next request. The random nature of the flow of requests and the time of their service leads to an uneven workload of the QS: at other times, unserved requests may accumulate at the input of the QS, which leads to an overload of the QS, and sometimes, with free channels, there will be no request at the input of the QS, which leads to an underload of the QS, i.e. e. to idle its channels. Applications that accumulate at the entrance of the QS either “get” into the queue, or, due to the impossibility of further staying in the queue, leave the QS unserved.
Performance indicators for the functioning of the “QS – consumer” pair, where the consumer is understood as the entire set of applications or some of their source (for example, the average income brought by the QS per unit of time, etc.). This group of indicators is useful in cases where some income received from servicing requests and service costs are measured in the same units. These indicators are usually quite specific and are determined by the specifics of the QS, service requests and service discipline.
14. Equations of dynamics for probabilistic states (Kolmogorov's equations). Limit probabilities of states.
Formally differentiating the Kolmogorov–Chapman equation with respect to s at s = 0, we obtain the direct Kolmogorov equation:
Formally differentiating the Kolmogorov-Chapman equation with respect to t at t = 0, we obtain the inverse Kolmogorov equation
It must be emphasized that for infinite-dimensional spaces, the operator is no longer necessarily continuous, and may not be defined everywhere, for example, to be a differential operator in the space of distributions.
In the event that the number of states of the system S is finite and it is possible to go from each state (for one or another number of steps) to each other state, then the limiting probabilities of states exist and also do not depend on the initial state of the system.
On fig. shows a graph of states and transitions that satisfy the condition: from any state, the system can sooner or later go to any other state. The condition will not be fulfilled when the direction of the arrow 4-3 on the graph in Fig. is reversed.
Let us assume that the stated condition is satisfied, and, therefore, the marginal probabilities exist:
The limiting probabilities will be denoted by the same letters as the probabilities of states, while they mean numbers, not variables (functions of time).
It is clear that the limiting probabilities of states should add up to unity: Consequently, a certain limiting stationary mode is established in the system at: let the system and change its own states randomly, but the probability of each of these states does not depend on time and each of them is carried out with some constant probability, which is the average relative time the system spends in this state.
15. The process of death and reproduction.
By a Markov process of death and reproduction with continuous time we mean an s.p. that can take only non-negative integer values; changes in this process can occur at any time t, while at any time it can either increase by one or remain unchanged.
The multiplication flows λi(t) are the Poisson flows leading to an increase in the function X(t). Accordingly, μi(t) are death flows leading to a decrease in the function X(t).
Let us compose the Kolmogorov equations according to the graph:
If a thread with a finite number of states:
The system of Kolmogorov equations for the process of death and reproduction with a limited number of states has the form:
The process of pure reproduction is such a process of death and reproduction, in which the intensities of all death flows are equal to zero.
The process of pure death is such a process of death and reproduction, in which the intensities of all reproduction flows are equal to zero.
16. Queuing systems with failures.
The simplest of the problems considered in the framework of the theory of queuing is the model of a single-channel QS with failures or losses.
It should be noted that in this case the number of channels is 1 (). This channel receives a Poisson flow of requests, the intensity of which is equal to . Time affects intensity:
If an application arrives in a channel that is currently not free, it is rejected and is no longer listed in the system. Applications are serviced during random time , the distribution of which is realized in accordance with the exponential law with the parameter :
17. Queuing systems with waiting.
A request that arrives at a time when the channel is busy is queued and awaits service.
A system with a limited queue length. Let us first assume that the number of seats in the queue is limited by the number m, i.e., if a customer arrives at a time when there are already m customers in the queue, it leaves the system unserved. In the future, if m tends to infinity, we obtain the characteristics of a single-channel QS without restrictions on the queue length.
We will number the QS states according to the number of requests in the system (both serviced and awaiting service):
— the channel is free;
— the channel is busy, there is no queue;
— the channel is busy, one request is in the queue;
— the channel is busy, k - 1 requests are in the queue;
- the channel is busy, tons of applications are in the queue.
18. Decision-making methods in conflict conditions. Matrix games. Pure and mixed strategy games.
A matrix game is a zero-sum final game of two players, in which the payoff of player 1 is given in the form of a matrix (the row of the matrix corresponds to the number of the applied strategy of player 2, the column corresponds to the number of the applied strategy of player 2; at the intersection of the row and column of the matrix is the payoff of player 1, relevant to the applied strategies).
For matrix games, it is proved that any of them has a solution and it can be easily found by reducing the game to a linear programming problem.
The two-player zero-sum matrix game can be viewed as the following abstract two-player game.
The first player has m strategies i = 1,2,...,m, the second has n strategies j = 1,2,...,n. Each pair of strategies (i, j) is assigned a number aij, which expresses the payoff of player 1 at the expense of player 2, if the first player accepts his i-th strategy, and 2 - his j-th strategy.
Each of the players makes one move: player 1 chooses his i-th strategy (i=), 2 - his j-th strategy (j=), after which player 1 receives the payoff aij at the expense of player 2 (if aij
Each strategy of the player i=; j = is often called a pure strategy.
Definition. The mixed strategy of a player is the complete set of probabilities of applying his pure strategies.
Thus, if player 1 has m pure strategies 1,2,...,m, then his mixed strategy x is a set of numbers x = (x1,..., xm) satisfying the relations
xi³ 0 (i= 1,m), =1.
Similarly, for player 2, who has n pure strategies, the mixed strategy y is the set of numbers
y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.
Since each time a player uses one pure strategy excludes the use of another, pure strategies are incompatible events. Also, they are the only possible events.
Pure strategy is a special case of mixed strategy. Indeed, if in a mixed strategy any i-th pure strategy is applied with probability 1, then all other pure strategies are not applied. And this i-th pure strategy is a special case of a mixed strategy. To maintain secrecy, each player applies his own strategies regardless of the choice of the other player.
19. Geometric method for solving a matrix game.
The solution of games of size 2xn or nx2 allows a clear geometric interpretation. Such games can be solved graphically.
On the XY plane, along the abscissa, we set aside a single segment A1A2 (Figure 5.1). Each point of the segment is associated with some mixed strategy U = (u1, u2). Moreover, the distance from some intermediate point U to the right end of this segment is the probability u1 of choosing strategy A1, the distance to the left end is the probability u2 of choosing strategy A2. Point A1 corresponds to pure strategy A1, point A2 corresponds to pure strategy A2.
At points A1 and A2, we restore the perpendiculars and put off the payoffs of the players on them. On the first perpendicular (coinciding with the OY axis), we show the payoff of player A when using strategy A1, on the second - when using strategy A2. If player A uses strategy A1, then his payoff with strategy B1 of player B is 2, and with strategy B2 it is 5. Numbers 2 and 5 on the OY axis correspond to points B1 and B2. Similarly, on the second perpendicular we find points B "1 and B" 2 (payoffs 6 and 4).
Connecting points B1 and B"1, B2 and B"2, we get two straight lines, the distance from which to the OX axis determines the average payoff for any combination of the corresponding strategies.
For example, the distance from any point of the segment B1B"1 to the axis OX determines the average payoff of player A for any combination of strategies A1 and A2 (with probabilities u1 and u2) and strategy B1 of player B.
The ordinates of the points belonging to the broken line B1MB"2 determine the minimum payoff of player A when he uses any mixed strategies. This minimum value is the largest at the point M, therefore, this point corresponds to the optimal strategy U* = (,), and its ordinate is equal to the price of the game v .
We find the coordinates of the point M as the coordinates of the point of intersection of the lines B1B"1 and B2B"2.
To do this, you need to know the equations of lines. You can compose such equations using the formula for the equation of a straight line passing through two points:
Let us compose the equations of lines for our problem.
Line B1B"1: = or y = 4x + 2.
Direct B2B "2: = or y = -x + 5.
We get the system: y = 4x + 2,
Let's solve it: 4x + 2 = -x + 5,
x = 3/5, y = -3/5 + 5 = 22/5.
So U = (2/5, 3/5), v = 22/5.
20. Bimatrix games.
A bimatrix game is a finite game of two players with a non-zero sum, in which the payoffs of each player are given by matrices separately for the corresponding player (in each matrix, the row corresponds to the strategy of player 1, the column corresponds to the strategy of player 2, at the intersection of the row and column in the first matrix is the payoff of the player 1, in the second matrix - the payoff of player 2.)
For bimatrix games, the theory of optimal behavior of players has also been developed, but solving such games is more difficult than conventional matrix games.
21. Statistical games. Principles and criteria for decision-making under conditions of complete and partial uncertainty.
In operations research, it is customary to distinguish between three types of uncertainties:
uncertainty of goals;
the uncertainty of our knowledge about the environment and the factors acting in this phenomenon (uncertainty of nature);
the uncertainty of the actions of an active or passive partner or adversary.
In the above classification, the type of uncertainties is considered from the standpoint of one or another element of the mathematical model. So, for example, the uncertainty of goals is reflected in the formulation of the problem in the choice of either individual criteria, or the entire vector of a useful effect.
On the other hand, the other two types of uncertainties mainly affect the formulation of the objective function of the constraint equations and the decision method. Of course, the above statement is rather conditional, as, indeed, any classification. We present it only to highlight some more features of the uncertainties that must be kept in mind in the decision-making process.
The fact is that in addition to the above classification of uncertainties, one must take into account their type (or "kind") from the point of view of their relationship to randomness.
On this basis, one can distinguish between stochastic (probabilistic) uncertainty, when unknown factors are statistically stable and therefore are ordinary objects of probability theory - random variables (or random functions, events, etc.). In this case, all necessary statistical characteristics (distribution laws and their parameters) must be known or determined when setting the problem.
An example of such tasks can be, in particular, a system for maintenance and repair of any type of equipment, a system for organizing thinning, etc.
Another extreme case can be non-stochastic uncertainty (according to E.S. Wentzel - "bad uncertainty"), in which there are no assumptions about stochastic stability. Finally, we can talk about an intermediate type of uncertainty, when a decision is made on the basis of some hypotheses about the laws of distribution of random variables. At the same time, the decision maker must keep in mind the danger of a discrepancy between his results and real conditions. This risk of mismatch is formalized with the help of risk coefficients.
Risk decision making can be based on one of the following criteria:
expected value criterion;
combinations of expected value and variance;
known limit level;
most likely event in the future.
Operation any event (system of actions), united by a single plan and directed towards achieving a specific goal, is called. The operation is always controlled event, i.e. it is possible to dispose of the method of choosing some parameters that characterize its organization. These options are called control variables.
Any definite choice of such variables is called decision. Decisions can be successful and unsuccessful, reasonable and unreasonable. Optimal name such solutions that, according to some criteria, are preferable to others.
The purpose of operations research is a preliminary quantitative justification of optimal solutions, of which there may be more than one. The final choice of a decision goes beyond the scope of operations research and is made by means of the so-called decision theory.
Any task of operations research has initial "disciplinary" conditions, i.e. such initial data that is fixed from the very beginning and cannot be violated. Together, they form the so-called set of possible solutions.
To compare the effectiveness of different solutions, you need to have a quantitative criterion called performance indicator(or objective function). This indicator is chosen to reflect the target orientation of the operation.
Often the operation is accompanied by the action of random factors. Then, not the value itself that we would like to optimize is taken as an indicator of efficiency, but its average value (or mathematical expectation).
Sometimes an operation accompanied by random factors pursues such a goal. A, which can either be achieved completely or not achieved at all (such as "yes - no"). Then the probability of achieving this goal is chosen as an indicator of efficiency. p(A). (If p(A) = 0 or 1, then we arrive at the well-known “black box” problem in cybernetics.)
The wrong choice of performance indicator is very dangerous. Operations organized according to an unsuccessfully chosen criterion can lead to unjustified costs and losses. (For example, "shaft" as the main criterion for evaluating the economic activity of an enterprise.)
1.3. General statement of the task of operations research
Operations research tasks fall into two categories: a) direct and b) inverse.
Direct tasks answer the question: what will be the efficiency indicator Z if under given conditions y Y some decision will be made x X. To solve such a problem, a mathematical model is built that allows expressing the efficiency indicator through given conditions and a solution, namely:
Where 
given factors (initial data),
control variables (solution),
Z– performance indicator (objective function),
F– functional dependence between variables.
This dependence in different models is expressed in different ways. Relationship between 
And 
usually expressed as limits on 
If the type of dependency F known, then the indicator Z is found by direct substitution 
And 
to this functionality.
Inverse Problems answer the question: how, under the given conditions 
choose a solution 
so that the performance indicator Z turned to the maximum (minimum). Such a problem is called a solution optimization problem.
Let the direct problem be solved, i.e. the operation model is set and the type of dependence F famous. Then the inverse problem (that is, the optimization problem) can be formulated as follows.
Wanted to find such a decision 
at which the efficiency indicator Z
= opt:
This formula reads like this: Z there is an optimal value 
taken over all solutions included in the set of possible solutions X.
The method of searching for the extremum of the efficiency indicator Z and the associated optimal solution 
should always be chosen based on the characteristics of the function F and the type of constraints imposed on the solution. (For example, a classic linear programming problem.)
Operations research- a science dealing with the development and practical application of mathematical, quantitative methods to justify decisions in all areas of purposeful human activity (effective organizational management).
Common Features of Operations Research
In each task, we are talking about some kind of event pursuing a specific goal.
Some conditions are set that characterize the situation (including the means that we can dispose of).
Within the framework of these conditions, it is required to make such a decision that the planned event would be in some sense the most profitable.
Features of Operations Research
A systematic approach to the analysis of the problem posed means that a particular task should be considered from the point of view of its influence on the criterion for the functioning of the entire system.
The greatest effect can be achieved only with continuous research, which ensures continuity in the transition from one task to another, arising in the course of solving the previous one.
Although the goal of operations research is to find the optimal solution, but due to the complexity of computing combinatorial problems, they are limited to finding a “good enough” solution.
Operational research is carried out in a complex, in many areas. To conduct the study, operational groups are created:
Basic Concepts of Operations Research
OPERATION - any controlled (that is, depends on the choice of parameters) event, united by a single plan and aimed at achieving some goal.
SOLUTION - any definite choice of parameters depending on us.
OPTIMAL SOLUTIONS - decisions for one reason or another are preferable to others.
THE PURPOSE OF THE OPERATION STUDY is a preliminary quantitative substantiation of optimal solutions.
SOLUTION ELEMENTS - parameters, the totality of which forms a solution.
PERFORMANCE INDICATOR (TARGET FUNCTION) is a quantitative criterion that allows comparing different solutions in terms of efficiency and reflects the target orientation of the operation (W => max or W => min).
The best solution is the one that contributes to the achievement of the goal to the maximum extent.
The concept of a mathematical model of an operation
A schematic, simplified description of an operation using one or another mathematical apparatus, reflecting the most important features of the operation, all the essential factors on which the success of the operation mainly depends.
Direct and inverse problems of operations research
DIRECT PROBLEMS answer the question of what will happen if, under given conditions, we make some decision x X, i.e. what will be the efficiency indicator W (or a number of indicators).
To solve such a problem, a mat is constructed. a model that allows you to express one or more performance indicators through given conditions and solution elements.
INVERSE PROBLEMS answer the question of how to choose a solution x in order for the efficiency indicator W to turn to a maximum (minimum).
These tasks are more difficult. They can be solved by a simple enumeration of solutions to direct problems.
But when the number of solutions is large, directed enumeration methods are used, in which the optimal solution is found by performing successive “trials” or approximations, each of which brings us closer to the desired optimal one.
Chapter 1. The subject and tasks of operations research.
§ 1. What is operations research and what does it do.
§ 2. Basic concepts and principles of operation research.
§ 3. Mathematical models of operations.
Chapter 2. Varieties of tasks in operations research and approaches to their solution.
§ 4. Direct and inverse problems of operations research. Deterministic tasks.
§ 5. The problem of choosing a solution under conditions of uncertainty.
§ 6. Multicriteria problems of operations research. "Systems approach".
Chapter 3. Linear programming.
§ 7. Problems of linear programming.
§ 8. The main problem of linear programming.
§ 9. Existence of a solution 03LP and ways of finding it.
§ 10. Transport problem of linear programming.
§ 11. Problems of integer programming. The concept of non-linear programming.
Chapter 4. Dynamic Programming.
§ 12. Method of dynamic programming.
§ 13. Examples of solving dynamic programming problems.
§ 14. The problem of dynamic programming in general form. The principle of optimality.
Chapter 5 Markov random processes.
§ 15. The concept of a Markov process.
§ 16. Flows of events.
§ 17. Kolmogorov's equations for state probabilities. Final probabilities of states.
Chapter 6
§ 18. Tasks of the theory of queuing. Classification of queuing systems.
§ 19. Scheme of death and reproduction. Little formula.
§ 20. The simplest queuing systems and their characteristics.
§ 21. More complicated problems in the theory of queuing.
Chapter 7. Statistical modeling of random processes (Monte Carlo method).
§ 22. Idea, purpose and scope of the method.
§ 23. Single lot and forms of its organization.
§ 24. Determining the characteristics of a stationary random process from one implementation.
Chapter 8
§ 25. Subject and problems of game theory.
§ 26. Antagonistic matrix games.
§ 27. Methods for solving finite games.
§ 28. Problems of the theory of statistical solutions.
SUBJECT AND OBJECTIVES OF OPERATIONS RESEARCH
Basic concepts and principles of operations research
In this section, we will get acquainted with the terminology, basic concepts and principles of the science of "operations research".
An operation is any event (a system of actions) united by a single idea and aimed at achieving some goal (all the events discussed in paragraphs 1 - 8 of the previous paragraph are "operations").
An operation is always a controlled event, that is, it depends on us how to choose some of the parameters that characterize its organization. "Organization" here is understood in the broad sense of the word, including the set of technical means used in the operation.
Any definite choice of parameters depending on us is called a decision. Decisions can be successful and unsuccessful, reasonable and unreasonable. Solutions are called optimal if they are preferred over others for one reason or another. The purpose of operations research is a preliminary quantitative justification of optimal solutions.
Sometimes (relatively rarely) as a result of the study, it is possible to indicate a single strictly optimal solution, much more often - to identify an area of practically equivalent optimal (reasonable) solutions within which the final choice can be made.
Note that the very decision-making goes beyond the scope of the study of the operation and falls within the competence of the responsible person, more often - a group of persons who have been given the right to make the final choice and who are responsible for this choice. When making a choice, they can take into account, along with the recommendations arising from the mathematical calculation, a number of considerations (quantitative and qualitative nature) that were not taken into account by this calculation.
The indispensable presence of a person (as the final decision-making authority) is not canceled even in the presence of a fully automated control system, which, it would seem, makes a decision without human participation. We must not forget that the very creation of a control algorithm, the choice of one of its possible options, is also a decision, and a very responsible one. With the development of control automata, human functions are not canceled, but simply moved from one, elementary, level to another, higher. In addition, a number of automated control systems provide for active human intervention during the controlled process.
Those parameters, the totality of which forms a solution, are called elements of the solution. Various numbers, vectors, functions, physical signs, etc. may appear as elements of the solution. For example, if a plan is drawn up for the transportation of homogeneous goods from points of departure A 1, A 2, ..., A m to destinations IN 1,В 2 , ..., В n , then the elements of the solution will be the numbers x ij , showing how much cargo will be sent from the 1st point of departure A i V j-th destination In j . Set of numbers x 11 , x 12, …, x 1 n , …, x m 1 , x m 2 , …, xmn forms a solution.
In the simplest problems of operations research, the number of solution elements can be relatively small. But in most problems of practical importance, the number of solution elements is very large, which the reader can verify by trying to independently select and “name by name” the solution elements in examples 1 - 8 of the previous paragraph. For simplicity, we will denote the entire set of elements of the solution by one letter x and say "decision X".
In addition to the solution elements that we, to some extent, can dispose of, in any task of operations research there are also given, “disciplining” conditions that are fixed from the very beginning and cannot be violated (for example, the load capacity of the machine; the size of the planned task ;
weight characteristics of equipment, etc.). In particular, such conditions include the means (material, technical, human) that we have the right to dispose of, and other restrictions imposed on the solution. In their totality, they form the so-called "set of possible solutions".
Let's denote this set again by one letter x, but the fact that the solution X belongs to this set, we will write it as a formula: X X(read: element X included in the set x).
It is about the fact that in the multitude of possible solutions X highlight those solutions X(sometimes - one, and more often - a whole range of solutions), which from one point of view or another are more effective (more successful, more preferable) than others. In order to compare different solutions in terms of efficiency, you need to have some kind of quantitative criterion, the so-called efficiency indicator (it is often called the “objective function”). This indicator is chosen so that it reflects the target orientation of the operation. The “best” solution will be considered the one that contributes to the achievement of the goal to the maximum extent. To select "say by name" performance measure W, First of all, you need to ask yourself: what we want What are we striving for by undertaking the operation? When choosing a solution, we will naturally prefer one that inverts the efficiency indicator W maximum (or minimum). For example, I would like to maximize the income from an operation; if costs are an indicator of efficiency, it is desirable to minimize them. If it is desirable to maximize the efficiency indicator, we will write it in the form W => max, and if minimized - W => min.
Very often, the operation is accompanied by the action of random factors (“whims” of the weather, fluctuations in supply and demand, failures of technical devices, etc.). In such cases, usually, not the value itself, which we would like to maximize (minimize), but its average value (mathematical expectation) is taken as an indicator of efficiency.
In some cases, it happens that the operation, accompanied by random factors, pursues some very specific goal. A, which can only be achieved completely or not achieved at all (“yes-no” scheme), and we are not interested in any intermediate results. Then, as an indicator of efficiency, the probability of achieving this goal is chosen. R(A). For example, if some object is being fired at with an indispensable condition to destroy it, then the efficiency indicator will be the probability of destroying the object.
The wrong choice of performance indicator is very dangerous. Operations organized from the point of view of an unsuccessfully chosen criterion can lead to unjustified costs and losses (remember, for example, the notorious "val" as the main criterion for assessing the economic activity of enterprises).
To illustrate the principles of choosing an indicator of efficiency, let us return again to examples 1 - 8 of § 1, choose for each of them a natural indicator of efficiency and indicate whether it is required to maximize or minimize it. When examining the examples, one should keep in mind that not all of them have the choice of an efficiency indicator unambiguously dictated by the verbal description of the task, so that there may be differences between the reader and the author on this issue.
1. Plan for the supply of enterprises. The task of the operation is to ensure the supply of raw materials with minimal transportation costs. Performance indicator R- the total cost of transporting raw materials per unit of time, for example, a month ( R => min).
2. Construction of a section of the highway. It is required to plan the construction in such a way as to complete it as soon as possible. A natural indicator of efficiency would be the time to complete the construction, if it were not associated with random factors (failures of equipment, delays in the performance of individual works). Therefore, as an indicator of efficiency, you can choose the average expected time T completion of construction (T => min).
3. Sale of seasonal goods. As an indicator of efficiency, we can take the average expected profit P from the sale of goods for the season (P => max).
4. Snow protection of roads. This is the most economically advantageous snow protection plan, therefore, as an indicator of efficiency, you can choose the average costs per unit of time (for example, per year) R for the maintenance and operation of roads, including costs associated with both the construction of protective devices and road clearance and traffic delays (R => min).
5. Anti-submarine raid. Since the raid has a very specific goal A - the destruction of the boat, then as an indicator of efficiency, you should choose the probability R(A) that the boat will be destroyed.
6. Selective control of products. The natural performance measure suggested by the problem statement is the average expected cost. R for control per unit of time, provided that the control system provides a given level of quality, for example, the average percentage of rejects is not higher than the specified ( R=> min).
7. Medical examination. As an indicator of efficiency, you can choose the average percentage (share) Q patients and carriers of infection who were identified (Q=> check).
8. Library service. Some vagueness was deliberately admitted in the formulation of the problem:
it is not clear what is meant by "best customer service" or "meeting their needs to the greatest extent possible". If the quality of service is judged by the time that the subscriber who requested the book is waiting for it to be received, then the average time can be taken as an indicator of efficiency. T expectations of the book by the reader who applied for it ( T=> min). You can approach the issue from a slightly different perspective, choosing the average number as an indicator of efficiency. M books issued per unit of time (M => max).
The considered examples are specially selected to be so simple that the choice of an efficiency indicator is relatively easy and is directly dictated by the verbal formulation of the task, its (almost always) unambiguous target orientation. However, in practice this is not always the case. The reader can be convinced of this by trying, for example, to choose an indicator of the efficiency of urban transport. What should be taken as such an indicator? The average speed of movement of passengers in the city? Or the average number of passengers carried? Or the average number of kilometers that a person will have to walk, whom transport cannot deliver to the right place? There is something to think about here!
Unfortunately, in most problems of practical importance, the choice of an efficiency indicator is not simple and is solved ambiguously. For any complex task, a situation is typical when the effectiveness of an operation cannot be exhaustively characterized by a single number - it has to involve others to help it. We will get acquainted with such “multicriteria” problems in § 6.
Examples of solving dynamic programming problems
In this section, we will consider (and even solve to the end) several simple (extremely simplified) examples of dynamic programming problems
1. Laying the most advantageous route between two points. Let us recall problem 4 of the previous paragraph and solve it to the end under extremely (and intentionally) simplified conditions. We need to build a path connecting
two points A And IN, of which the second lies to the northeast of the first. For simplicity, let's say. that laying the path consists of a series of steps, and at each step we can move either due east or due north; any way from A V IN is a stepped broken line, the segments of which are parallel to one of the coordinate axes (Fig. 13.1). The construction costs of each of these segments are known. It is required to lay such a path from A V IN, where the total cost is minimal.
How to do it? You can do one of two ways: either go through all possible path options and choose the one on which the costs are minimal (and with a large number of segments this is very, very difficult!); or split the transition process from A V IN into individual steps (one step - one segment) and optimize the control by steps. It turns out that the second method is incomparably more convenient! Here, as elsewhere in operations research, there are advantages to purposeful, organized search for a solution over naive "blind" enumeration.
Let's demonstrate how this is done with a specific example. Divide the distance from A before IN in the east direction, say, into 7 parts, and in the north direction - into 5 parts (in principle, the fragmentation can be arbitrarily small). Then any path from A V IN comprises T\u003d 7 + 5 \u003d= 12 segments directed to the east or north (Fig. 13.2). Let's put down on each of the segments a number expressing (in some arbitrary units) the cost of laying a path along this segment. It is required to choose such a path from A V IN, for which the sum of the numbers on the segments is minimal.
We will consider the constructed path as a controlled system S, moving under the influence of control from the initial state A to the final IN. The state of this system before the start of each step will be characterized by two coordinates: east (X) and northern (y), both are integer (0 X 5 7, 0 at 5). For each of the states of the system (the nodal point of the rectangular grid in Fig. 13.2), we must find the conditional optimal control: we go from this point to the north (control "c") or to the east (control "c"). This control is chosen so that the cost of all remaining steps (including this one) is minimal. We will continue to call this cost the “conditional optimal gain” (although in this case it is not a “gain”, but a “loss”) for a given state of the system. S before starting the next step.
We will unfold the conditional optimization procedure in the opposite direction - from the end to the beginning. First of all, we perform conditional optimization of the last, 12th step. Consider separately the upper right corner of our rectangular grid (Fig. 13.3). Where can we be after the 11th step? Only
 |
where in one (last) step you can get to IN, i.e. at one of the points IN 1 or AT 2 . If we are at the point IN 1 , we have no choice (forced control): we must go east, and it will cost us 10 units. Let's write this number 10 in a circle near the point IN 1 , and the optimal control will be shown by a short arrow emanating from IN 1 and directed to the east. For point AT 2 control is also forced (north), the flow to the end is 14, we will write it in a circle at the point AT 2 . Thus, the conditional optimization of the last step is done, and the conditional optimal gain for each of the points B 1 , B 2 found and recorded in the appropriate mug.
Now let's optimize the penultimate (11th) step. After the penultimate (10th) step, we could end up at one of the points C 1, C 2, C 3(Fig. 13.4). Let us find for each of them a conditional optimal control and a conditional optimal payoff. For point From 1 forced management: go east;
it will cost us 21 units to the end (11 at this step, plus 10, written in a circle at IN 1). The number 21 is written in a circle at a dot From 1 . For point From 2 management is no longer forced: we can go both east and north. In the first case, we will spend 14 units at this step and from AT 2 to the end - 14 more, only 28 units. If we go north, we will spend 13 + 10, for a total of 23 units. Hence, the conditional optimal control at the point From 2 - go north (mark this with an arrow, and write the number 23 in a circle near C 2), For point From 3 the control is again forced (“c”), it will cost 22 units to the end (put the arrow to the north, write the number 22 in a circle when From 3).
Similarly, “backing away” from the penultimate step back, we find for each point with integer coordinates the conditional optimal control (“c” or “b”), which we denote by an arrow, and the conditional optimal gain (expenditure to the end of the path), which we write in a circle. It is calculated as follows: the flow rate at a given step is added to the already optimized flow rate, written in the circle where the arrow leads. Thus, at each step, we optimize only this step, and the ones following it are already optimized. The end result of the optimization procedure is shown in Fig. 13.5.
Thus, conditional optimization has already been performed: no matter where we are, we already know where to go (arrow) and what it will cost us to reach the end (number in a circle). In a circle at a dot A the optimal payoff for the entire construction of the path from A V IN:
W* = 118.
Now it remains to construct an unconditional optimal control - a trajectory leading from A And IN in the cheapest way. To do this, you only need to "obey the shooters", that is, read what they prescribe to do at each step. Such an optimal trajectory is marked in Fig. 13.5 circled twice. The corresponding unconditional optimal control will be:
x* =(s, s, s, s, in, in, s, in, in, in, in, in),
that is, we must take the first four steps to the north, the next two to the east, then again one to the north and the remaining five to the east. Problem solved.
Note that in the course of conditional optimization, we may encounter the case when both controls for some point on the plane are optimal, i.e., lead to the same cost of funds from this point to the end. For example, at the point with coordinates (5; 1) both controls "c" and "b" are optimal and give the flow to the end equal to 62. We arbitrarily choose any of them (in our case, we chose "c"; we could just as well choose "c"). Such cases of ambiguous choice of the optimal control are constantly encountered in dynamic programming; in the future, we will not specially mark them, but simply choose arbitrarily any of the equivalent options. Of course, the optimal control of the entire process may depend on this arbitrariness, but not the optimal gain. In general, in dynamic programming problems (as well as in linear programming problems), the solution is far from always unique.
And now let's go back to the beginning and try to solve the problem in a "naive" way, choosing at each step, starting from the first, the most profitable (for this step) direction (if there are two of them, we choose any). In this way we get control
x = (s, s, in, in, in, in, s, in, in, in, s, s).
Let's calculate the costs for this trajectory. They will be equal W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, which is definitely more than W* = 118. In this case the difference is not very large, but in others it can be significant.
In the problem solved above, the conditions were deliberately simplified to the extreme. Of course, no one will lead the railway track "on the steps", moving only due to the north or due to the east. We made such a simplification in order to choose only from two controls at each point: “from” or “to”. Instead of two possible directions, it would be possible to introduce several of them and, in addition, take smaller steps; this is not of fundamental importance, but, of course, it complicates and lengthens the calculations.
Note that tasks similar to those considered above are very often encountered in practice: for example, when choosing the fastest path between two points or the most economical (in terms of fuel consumption) gain in speed and altitude by an aircraft.
Let us make one passing remark. The attentive reader has probably noticed that in our problem the points A And IN(beginning and end) are in principle no different from each other: it would be possible to build conditional optimal controls not from the end to the beginning, but from the beginning to the end, and unconditional - in the opposite direction. Indeed, this is so: in any dynamic programming problem, “beginning” and “end” can be swapped. This is completely equivalent to the previously described method in terms of calculation, but it is somewhat less convenient when verbally explaining the idea of the method: it is easier to argue, referring to the “already established” conditions at the beginning of this step than to those that are still “coming” after this step. In essence, both approaches are completely equivalent.
2. The problem of resource allocation. The dynamic programming method makes it possible to successfully solve many economic problems (see, for example, ). Consider one of the simplest such problems. We have some stock of funds (resources) at our disposal TO, which should be distributed among T enterprises P 1 , P 2 , ..., P m . Each of the enterprises i when investing in it X generates income based on x, i.e., representing some function ( x). All functions ( x) (i = 1, 2, ..., T) are given (of course, these functions are nondecreasing). The question is how to allocate funds TO. between enterprises, so that in total they give the maximum income?
This problem is easily solved by the dynamic programming method. Although in its formulation it does not contain a mention of time, you can still mentally unfold the operation of distributing funds in some sequence, considering the investment of funds in the enterprise P 1 as the first step, and in P 2 etc.
Managed system S in this case, the funds or resources that are distributed. State of the system S before each step is characterized by one number S- cash reserve not yet invested. In this problem, the "step controls" are the means x 1, x 2, ..., x 3, allocated to businesses. It is required to find the optimal control, i.e. such a set of numbers x 1, x 2, ..., xm, at which the total income is maximum:
(13.1)
We will solve this problem first in a general, formulaic form, and then - for specific numerical data. Find for everyone i-th step is the conditional optimal payoff (from this step to the end), if we approached this step with a margin of funds S. Denote the conditional optimal payoff W i (S), and the corresponding conditional optimal control is the funds invested in i enterprise, - x i (S).
Let's start optimization from the last one, T - step. Let us come to this step with the rest of the funds S. What should we do? Obviously invest the whole amount S entirely to the enterprise P m. Therefore, the conditional optimal control on m-th step: give the last enterprise all available funds S, i.e.
and the conditional optimal payoff
W m (S)= (S).
Given a whole gamut of values S(placing them closely enough), we for each value S we will know x m (S) And W m (S). The last step is optimized.
Let's move on to the penultimate (T- 1)th step. Let us approach him with a reserve of funds S. Denote W m -1 (S) conditional optimal payoff on the last two steps: ( m- 1)-m and m-m (which is already optimized). If we allocate to ( m- 1)th step ( m- 1)th enterprise funds X, then the last step will be S-x. Our payoff on the last two steps will be equal to
,
and need to find it X, at which this gain is maximum:
The sign means that the maximum value is taken over all X, what are possible (to invest more than S, we can't) from the expression in curly braces. This maximum is the conditional optimal payoff for the last two steps, and then the value X, at which this maximum is reached, is the conditional optimal control on (T- 1)th step.
and the corresponding conditional optimal control x i (S) - that value X, at which this maximum is reached.
Continuing in this way, we finally reach the 1st enterprise P 1 . Here we don't need to change the values S; we know for sure that the stock before the first step is equal to TO:
So, the maximum gain (income) from all enterprises is found. Now it remains only to "read the recommendations." That meaning X, at which the maximum (13.4) is reached, and there is an optimal control at the 1st step. After we invest these funds in the 1st enterprise, we will have TO- ."Reading" the recommendation for this value S, we allocate the optimal amount of funds to the second enterprise:
,
and so on until the end.
Now let's solve a numerical example. Initial stock of funds K = 10 (conventional units), and it is required to optimally distribute it among five enterprises (t = 5). For simplicity, we will assume that only integer amounts of funds are invested. income functions ( X) are given in Table 13.1.
Table 13.1
| X | |||||
| 0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0 | 0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5 | 0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8 | 0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5 | 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 |
In each column, starting from a certain amount of investments, incomes cease to grow (in reality, this corresponds to the fact that each enterprise is able to "master" only a limited amount of funds).
Let's perform conditional optimization as described above, starting from the last, 5th step. Every time we come to the next step, having a reserve of funds S, we try to allocate one or another amount of funds for this step, take the gain at this step according to table 13.1, add it to the already optimized gain at all subsequent steps until the end (considering that we already have less funds left, just by such an amount of funds, which we have allocated) and find the investment at which this sum 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 structured as follows: the first column gives the values of the stock of funds S, with with which we approach this step. Further, the table is divided into five pairs of columns, corresponding to the step number. The first column of each pair contains the value
Table 13.2
| S | i=5 | i=4 | i=3 | i=2 | i=1 | |||||
| x5(S) | W 5(S) | x4(S) | W4(S) | x 3(S) | W 3(S) | x2(S) | W2(S) | x 1(S) | W 1(S) | |
| 1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8 | 1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1 | 1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6 | 5,6 |
conditional optimal control, in the second - conditional optimal payoff. 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 has to be optimized. As a result of sequential optimization of the 5th, 4th, 3rd, 2nd and 1st steps, we will get a complete list of all recommendations for optimal control and an 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 line is filled in, since we know exactly the state of the system before the start of the first step:
S0 = K = 10. Optimal controls at all steps are framed. Thus, we got the final conclusion: we need to allocate two units out of ten to the first enterprise, five units to the second, two to the third, none to the fourth, one unit to the fifth. With this distribution, the income will be maximum and equal to 5.6.
To make it clear to the reader how table 13.2 is filled out, we will demonstrate this on one calculation sample. Let, for example, we need to optimize the solution x 3(7)- what to do in the third step, if we approached it with a reserve of funds S= 7, and what is the maximum we can win on all remaining
Table 13.3
| x | 7 - x | W4(7 - x) | +W 4 (7 - x) | |
| 1,8 1,7 1,6 1,4 1,2 1,1 0,6 | 1,0 1,3 1,6 2,3 2,5 2,6 2,7 | 1,8 2,7 2,9 3,0 3,5 3,2 2,7 |
steps, including the third? Let us assume that all steps after the third (4th and 5th) have already been optimized, that is, the first two pairs of columns of Table 13.2 have been filled. Let's find x 3 (7) and W 3(7). To do this, we will compile an auxiliary plate (see table 13.3). The first column lists all possible attachments. X on the third step, not exceeding S = 7. In the second column - what will remain after such an investment from the stock of funds S = 7. In the third column - the gain in the third step from investing X in the third enterprise is filled in by column (table 13.1). In the fourth column - the optimal payoff on all remaining steps (fourth and fifth), provided that we approached the fourth step with the remaining funds (filled in the column i = 4 tables 13.2). In the fifth column - the sum of two payoffs: step and optimized further for a given investment X in the third step.
Of all the payoffs of the last column, the maximum one is selected (in table 13.3 it is equal to W 3(7) = 3.6, and the corresponding control X(7) = 2).
The question arises: what if in the auxiliary table of type 13.3 the maximum is reached for more than one x, and at two or more? We answer: it does not matter which one to choose; the gain does not depend on it. In general, in dynamic programming problems, the solution should not be unique at all (we have already mentioned this).
3. The problem of loading the machine. Using the dynamic programming method, you can successfully solve a number of the optimization problems described in Chapter 3, in particular, some integer programming problems. Note that the integrality of solutions, which makes linear programming problems so difficult, in this case does not complicate, but, on the contrary, simplifies the procedure (as it was simplified for us by the integrality of embeddings in the previous problem).
As an example, consider the problem of loading a machine (we already mentioned it in the previous chapter): there is a certain set of objects P 1 , P 2 ,..., P n (each in a single copy); their weights are known q 1 , q 2 , ..., q n and cost from 1, with 2 , ..., with n . The load capacity of the machine is Q. The question is which of the items should be taken into the car so that their total cost (with the total weight Q) was the maximum?
