L.V. Kantorovich, an economist, made an outstanding contribution to economic science. His name is associated with a natural science approach to the study of a wide range of planning problems. L.V. Kantorovich laid the foundation for the modern theory of optimal planning. His major monograph is devoted to a detailed presentation of the main ideas of this theory. “Economic calculation of the best use of resources” . The core of this book is the formulation of the basic production planning problem and the dynamic optimal planning problem. These tasks are quite simple, but at the same time they take into account the most important features of economic planning. One of the attractive qualities is that they are based on a linear programming scheme and, therefore, on a developed analytical apparatus and an extensive set of effective computing tools, some of which were proposed by Leonid Vitalievich himself.

His contribution to the problem of pricing is significant - one of the fundamental ones, affecting essentially all spheres of the functioning of society. L.V. Kantorovich established a connection between prices and socially necessary labor costs. He defined the concept of optimum, optimal development, specifying, in particular, what should be understood by maximum satisfaction of the needs of members of society. From his position on the inseparability of the plan and prices, it follows that socially necessary labor costs depend on the set goals of society.

Thus, the goals of society, the optimal plan and prices form one inseparable whole. He indicated specific conditions under which objectively determined estimates of the optimal plan coincide with the total (direct and associated) labor costs. Determining the prospects of the economy, the presence of giant “natural monopolies” forces them to maintain the calculation of at least reference prices that are mutually agreed upon and with the interests of other sectors of the economy.

Mathematical models are reflected in some courses in political economy. In the works of L.V. Kantorovich studied a number of basic problems of economic theory and business practice. Pointing out the shortcomings of the current economic system, L.V. Kantorovich emphasized that the system of economic indicators should be unified, built on a single principle. In this regard, Leonid Vitalievich devoted a significant part of his work in this area to the development and analysis of specific economic indicators.

In the works of L.V. himself Kantorovich, special attention was paid to the assessment of land resources and water, taking these indicators into account in (procurement) prices for agricultural products. Original approaches to their calculation are proposed (a combination of the least squares method and linear programming). On this basis, recommendations were made to improve the system of economic indicators and calculations in agriculture. The importance of the principles of calculation he proposed in the emerging economic system is only increasing.

In the works of L.V. Kantorovich reveals the essence of the concept of an investment efficiency indicator, shows its role in economic calculations of decision-making, and proposes a method for determining the value of this standard indicator. Thus, L.V. Kantorovich gave a convincing scientific justification for the need to apply the efficiency standard and, based on the optimization approach, gave an objective way to calculate it.

In the work “Depreciation payments for optimal use of equipment” (1965) L.V. Kantorovich revealed the essence of the concept of depreciation. He showed how to improve the efficiency of equipment use by dividing depreciation payments into two types, and using an ingenious mathematical model, he indicated how to determine the numerical value of the depreciation coefficient. This change made it possible to draw a number of fundamental conclusions about the need to adjust the adopted methodology for calculating depreciation.

Leonid Vitalievich showed special interest in transport problems. Even in his first economic works, a general analysis of the transport problem and the method of potentials for solving it were given. This method was widely used in transport (railway, road, sea, air) and in centralized supply authorities for rational attachment and rational organization of transportation. It certainly retains its importance today, along with the widely used methods of dispatch control and route calculations.

In the works “On the use of mathematical models in pricing new equipment”(1968) and “ Mathematical and economic analysis of planning decisions and economic conditions for their implementation” (1971) L.V. Kantorovich studied the problem of efficient operation of transport from an economic point of view, showed what transport tariffs should be depending on the type of transport, cargo, distances, etc. In a number of works, he also considered issues of an integrated transport system - the relationship of transport with other sectors of the national economy and distribution of transportation between modes of transport, taking into account efficiency and especially energy costs. These works remain important today.

In addition to the problems of national economic planning, L.V. Kantorovich examined issues related to sectoral planning. The simplest and most frequently used is the model he proposed, based on the transport problem. He indicated a number of more complex models, in particular production and transport, dynamic, decomposition, in works devoted to current and long-term industrial planning (“Possibilities of using mathematical methods in matters of production planning”, 1958), etc. These issues are reflected in research according to industry automated control systems.

Leonid Vitalievich paid much attention to issues of rational use of labor. They were proposed to introduce payments by enterprises for the use of labor, differentiated by profession, gender, age and territory. He also pointed out the possibilities of a scientific, quantitative approach to social problems, issues of improving the service sector, etc. Issues of economic stimulation of the rational use of labor resources remain relevant today.

For a number of years, and especially in recent years, L.V. Kantorovich was interested in problems of the effectiveness of technical progress, in particular the issues of introducing new technology into production.

Of particular interest is the rationale for the proposal to establish two price levels for fundamentally new products in the first years of their release. Also important was the conclusion about the need to evaluate the contribution to national income of technical progress and science more highly than was obtained using the then accepted calculation methods (“Pricing and Technical Progress”, 1979).

L.V. Kantorovich paid great attention to the introduction of the methods he developed into economic practice. First of all, in this regard, it should be noted a series of works devoted to methods of rational cutting of materials, begun by Leonid Vitalievich back in 1939 - 1942. In 1948 - 1950 these methods were introduced at the Leningrad Carriage Building Plant named after Egorov, at the Kirov Plant and were subsequently distributed at some other enterprises. The wider dissemination of rational cutting methods was facilitated by a series of initiatives carried out on the initiative of L.V. Kantorovich meetings.

Since 1964, at the suggestion of Leonid Vitalievich, a lot of work has been carried out to introduce systematic methods for calculating the optimal loading of rolling mills throughout the country.

As a member of the State Committee on Science and Technology, L.V. Kantorovich carried out a lot of organizational work aimed at improving methods of planning and managing the national economy. He headed the Scientific Council of the State Committee for Science and Technology on the use of optimization calculations, and was a member of many departmental councils and commissions (on pricing, transport, etc.). Leonid Vitalievich's contribution to the study of the problem of production efficiency and, in particular, the problem of the efficiency of capital investments is exceptionally great.

ISSN 1992-6502 (P ri nt)_

2014. T. 18, No. 1 (62). pp. 186-197

QjrAQnQj

ISSN 2225-2789 (Online) http://journal.ugatu.ac.ru

UDC 621.35, 004.02

The theory of optimal use of resources by L. V. Kantorovich in cutting-packing problems: review and history of the development of solution methods

Yu. I. Valiakhmetova, a. S. Filippova

1 FSBEI HPE “Bashkir State Agrarian University” (BSAU) 2 FSBEI HPE “Bashkir State Pedagogical University named after. M. Akmulla" (BSPU)

Received by the editor 02/04/2014

Annotation. Examples of formulations of cutting-packing problems are given, the relevance of which is confirmed by their diversity and versatility of applied significance. The works of L. V. Kantorovich were fundamental for the development of methods for solving such problems. A review of methods for solving classical cutting-packing problems developed by Soviet and Russian scientists over the past 80 years, including scientific schools of the USSR and Russia, is provided. Brief descriptions of the methods and the history of their development are given.

Key words: cutting; package; rational use of resources; optimization; precise methods; heuristic methods, algorithms

Dedicated to the 100th anniversary of the birth of Nobel laureate L. V. Kantorovich

INTRODUCTION

The contribution made by the wonderful and talented scientist Leonid Vitalievich Kantorovich to various fields of mathematics and economics was of great importance in the development of solving applied production problems. In addition, his concept of an optimal economic model at the macroeconomic level still has enormous potential today. And in the speech of the Swedish professor Ragnar Bentzel, which he delivered in 1975, introducing the Nobel Prize laureates in economics L. V. Kantorovich and T. Koopmans, the universal importance of the concept for any economy, regardless of its socio-political form, was noted: “Since The supply of productive resources is limited everywhere; every society is faced with a range of issues relating to the optimal use of available resources and the fair distribution of income among citizens. The point of view from which such normative questions can be considered does not depend on the political organization of the society in question." Therefore, research and development of methods

The work was supported by the Russian Foundation for Basic Research grant 12-07-00631-a.

solutions to problems of rational use of resources are still relevant today.

1. BASIC METHODS

OPTIMAL USE OF RESOURCES

A fundamental role in the formation and development of the theory of optimal use of resources and linear programming was played by the brochure published by Professor L.V. Kantorovich in 1939, which examined various practical problems of organizing production, in which it was necessary to find the best solution. The book was written after consultation with employees of the Plywood Trust on how to solve problems that could not be solved using traditional methods at that time. L. V. Kantorovich proposed the method of resolving multipliers (indices), which establishes the fundamental possibility of finding the best solution for many problems of the national economy, including the problem of mass cutting. Despite the huge range of scientific interests, in subsequent years L. V. Kantorovich repeatedly returned to the problem of rational cutting, for example.

In the 30s last century, the foundations were laid for the theory of cutting sawn raw materials, the founder of which was H. L. Feldman. He proposed a mathematical approach for

solving the problem of maximum spacing when sawing logs. Together with his followers, he created a system focused on maximizing the volume and quality of edged lumber. The exact mathematical solution scheme did not fully take into account real conditions, such as the quality characteristics of raw materials and lumber, so the results in practice could be incorrect. Later, V.A. Zalgaller developed a graphical method for compiling maximum positions, based on the geometric sign of an extremum. The method proposed by V. A. Zalgaller made it possible to bring the theory of maximum deliveries closer to production conditions.

The developed and improved theory, however, even now cannot provide an answer to many problems of sawmill technology, and therefore its further improvement is important. Among the main reasons for this phenomenon: technical progress, changes in the size and quality characteristics of sawn raw materials supplied for cutting and its species composition, stricter requirements of environmentalists, changes in current standards for raw materials and sawn products.

2. VARIETY OF CUTTING AND PACKING TASKS

Cutting problems represent an important technological problem, the optimal solution of which allows minimizing the consumption of available resources. These are tasks such as:

Cutting linear material;

Slitting of tapes and rolls;

Cutting sheets into rectangular blanks;

Use of mixed length materials;

Cutting for serial and non-serial products;

Packaging of three-dimensional containers;

Cutting figured blanks;

Placement of circles;

Geometric coverage of areas with obstacles with elements of various shapes;

The problem of choosing the best dimensions of material for subsequent cutting;

Packing/covering elements of random sizes,

and many others.

Similar problems are encountered in practice in mechanical engineering, metallurgy, woodworking.

manufacturing and clothing industry, pulp and paper industry, etc.

Many tasks that at first glance do not belong to the class of cutting and packaging problems ultimately come down to them. For example, scheduling problems, routing problems, decomposition problems of multiply connected orthogonal polygons, as well as many other applied problems.

If the value of the resource being cut is high, in practice residual problems are also considered: an attempt is made to use waste material resulting from solving previous problems of cutting, packaging or geometric coating.

Cutting, packing, or coating tasks can occur as intermediates in other tasks or interspersed within the same task. For example, you can consider a logistics problem where each vehicle is matched with a route to consumers and a set of cargo corresponding to these consumers. Then finding the route for each vehicle, as well as finding a plan for placing cargo in the cargo compartment, are tasks of the cutting-packing class. Additionally, when placing cargo, you can take into account the order of the vehicle - so that the cargo intended for the last client is loaded first.

Each subject area introduces its own additional requirements into the way problems are solved, and, consequently, into the way known algorithms are adapted.

This article provides a brief overview of methods for solving classical cutting-packing problems developed by Soviet and Russian scientists over the past 80 years. Cutting and Packing (C&P) problems refer to a wide class of problems that can be interpreted in different applications. These include the following tasks:

Cutting the stock of material (when cutting into certain blanks, minimizing the starting material);

Dense placement of geometric objects in a given area (placement of cargo, goods in a warehouse, etc.);

Packing containers (placing items in a limited area);

Choice of assortment (choice when ordering one size from standard);

Space planning (maximizing useful areas when planning taking into account technological requirements);

Ensuring the rhythm of the production process (scheduling tasks, scheduling multiprocessor systems);

Distribution of production capacity (distribution of computer memory);

Arrangement problem in sawmilling (position of saws when sawing logs into boards of different thicknesses, selection of the number of saws to maximize output);

Cutting a tree trunk to length (maximizing production when cutting the trunk into round assortments);

Cutting boards (cutting into blanks closer to the final product; avoiding defects and maximizing the total cubic capacity or the total commercial price);

Cutting sheet material into random blanks (cutting material taking into account the lead-lag of the production of blanks);

Maximum (minimum) geometric coverage (arrangement of the minimum number of pieces of equipment in a given area), etc.

In turn, each of them can be specified in different ways.

Common to problems of this class is the presence of two groups of objects. The correspondence between the elements of these groups is established and assessed. There are different tasks of linear (one-dimensional), rectangular (two-dimensional) and parallelepiped (three-dimensional) cutting-packing. Among these tasks, guillotine cutting and packaging stand out. The problems of nesting - placing parts of complex geometric shapes in given areas - are especially highlighted. For them, the information problems of defining figures, accounting and ensuring their non-intersection, coding, etc. come to the fore. The list of geometric properties of workpieces and materials can be supplemented and taken into account in the mathematical model by some physical and/or economic indicators. A detailed classification of the main models of S&P tasks in Russia is given in.

In the 40s methods for solving cutting problems were aimed primarily at problems of mass production, where the integrity of the results can be neglected. The method proposed by L. V. Kantorovich for solving such problems made it possible to find the optimal cutting, but the laboriousness of the manual solution process required adaptation to production conditions and improvement of the mathematical computing apparatus. It was this issue that the scientific developments of L. V. Kantorovich’s followers and associates were mainly devoted to until the 50-60s. Next, it became possible to implement algorithms on a computer. The programs made it possible to find optimal plans for cutting dimensional linear materials and optimal plans for cutting rectangular sheets into rectangular blanks. Since the 70s. Special attention of researchers in this area was aimed at solving the problems of single and small-scale production.

For the first time, cutting issues were worked out in detail by L. V. Kantorovich together with V. A. Zalgaller at the Leningrad branch of the Mathematical Institute of the USSR Academy of Sciences in the 40s. . A practical test of the success of the mathematical solution methods they developed was carried out at the Leningrad Carriage Works in 1948-1949. Due to the technological requirements and the complexity of calculating the method of resolving multipliers, a lot of work was done to develop and adapt the mathematical apparatus to the production reality of that time through the introduction of new calculation and technological techniques. Thus, V.A. Zalgaller developed a method for selecting integer indices, proposed a solution to a plane problem using an auxiliary linear problem, techniques for cutting material of mixed lengths, and various technical devices. All developed and practically tested methods of that period, the methodology for their use were described in the book “Rational Cutting of Industrial Materials,” published in early 1951. The cutting problems were considered by the authors as examples of the use of linear programming (Linear Programming, LP). When solving cutting problems, the LP model is used with implicitly specified information about the cuttings (matrix columns). In fact, this book was a report on the successful practical implementation in 1948-1949. linear programming for solving industrial problems. The first foreign publications dedicated to LPs are related to

by 1949. The main calculations given in the book were performed manually. To overcome the difficulties associated with constructing acceptable cutting maps, the authors proposed techniques that, in essence, anticipated the ideas of dynamic programming.

To solve the problem of generating cutting, methods based on dynamic programming were developed for the problem of linear cutting, for guillotine cutting - a grid method for generating cuttings with a maximum estimate, counting the full table of indices. I. V. Romanovsky proposed a gluing method limited to states corresponding to jumps. Later, E. A. Mukhacheva developed conditional methods for generating cuttings at each step of the linear programming process, taking into account the specifics of real production. At that time, the main goal of these and many other works was the application of linear programming in the field of production problems. This goal was achieved to one degree or another in conditions of mass and serial production.

3. ACTIVITIES OF SOVIET SCIENTIFIC SCHOOLS ON RESEARCH OF CUTTING-PACKING PROBLEMS

Undoubtedly, this direction received development and widespread use with the advent of computers: for example, the first software implementation on a computer of the index scale method. A method and program for rationally solving a mass linear problem is presented, taking an acceptable amount of time for calculation. Calculation of rational cutting charts for rectangular sheets in the 60s. for a large number of workpieces (more than 60) was practically impossible. And examples of smaller dimensions required many hours of computer program work.

Thus, the use of computers to solve and study the problem of mass cutting in the early 60s. last century was the first step for the emergence of the Ufa scientific school under the leadership of E. A. Mukhacheva. In 1962, Elita Aleksandrovna Mukhacheva entered graduate school at the Novosibirsk Academic Campus of the Institute of Mathematics of the Siberian Branch of the USSR Academy of Sciences in the department of the creator of the theory of linear programming, Leonid Vitalievich Kantorovich, and received the task of developing a program for mass cutting of material, the result is described in.

The priority of L. V. Kantorovich in this area was already recognized in the world; he was in charge of the mathematics and economics department. An employee of the department, student and colleague of L. V. Kantorovich, Doctor of Physical and Mathematical Sciences G. Sh. Rubinshtein became Elita Alexandrovna’s scientific supervisor. At the beginning of 1967, she defended her thesis “Numerical methods for solving certain classes of linear programming problems” for the degree of candidate of physical and mathematical sciences1. Since then, active research in this area has been conducted at the Ufa State Aviation Technical University.

For piece production problems, which are inherently discrete optimization problems, a solution using LP is a simplification that allows you to obtain a result close to the optimal one, with additional restrictions arising in the conditions of serial and mass production. Subsequently, S&P problems were considered without this simplification, as applied problems of combinatorial problems in operations research. C&P problems are typical representatives of NP-hard problems. Due to the non-polynomial complexity of exact algorithms for S&P problems, the authors of many works to this day pay considerable attention to approximate methods, and when developing exact algorithms, to procedures for reducing exhaustive search and calculating lower bounds.

When solving S&P problems, it is necessary to minimize the material used (quantity

1 In 1983, E. A. Mukhacheva (1930-2011) defended her doctoral dissertation “Applied problems of combinatorial optimization, in particular, the cutting and packaging problem” and became the first female Doctor of Science at UAI (Ufa Aviation Institute). While working on her dissertation, she consulted with L. V. Kantorovich, V. A. Zalgaller and in the Novosibirsk academic town. Out of 59 years of work at the Ufa Aviation University (UAI, UGATU), 34 years were heads of departments. The scientific significance of the works of E. A. Mukhacheva and her students is colossal. Students, graduate students, scientists of our country studied mathematical programming, mathematical methods of operations research, theory and calculation methods in cutting-packing problems using textbooks, monographs and articles authored by E. A. Mukhacheva. Many of her followers continue development to this day in Russia and abroad. The results of numerous works have been implemented, for example, at the Kirov Plant (Leningrad), in the production of tractors at the Izhevsk Mechanical Plant, at the Ulyanovsk Aviation Complex, etc.

vo, area or volume). In this case, the optimal value will be greater than or equal to the lower limit and less than or equal to the upper limit.

Using boundaries, the solution obtained by one or another method is evaluated. The upper bound, for example, obtained approximately by any heuristic method and refined during calculations, is used in the branch and bound method to reduce the set of nodes in the decision tree being viewed: nodes whose score is not less than the upper bound are eliminated.

When solving problems using exact methods, the use of boundaries allows you to reduce the running time of the algorithm. Thus, more operating time of the exact algorithm is spent on proving the optimality of the solution found, possibly obtained already at the beginning of the calculations. For this stage, the lower limit is very important, the value of which should be as close as possible to the optimum. The problem of calculating lower bounds remains fundamental in the development of effective exact methods for solving S&P problems. Of particular interest for calculations are refined lower bounds; they allow you to either quickly cut off “weak” partial solutions or simply stop calculations when a sufficiently good result is achieved. A method for constructing lower bounds based on linear relaxation is proposed. It is shown that the optimal value of the original problem can be estimated by solving the corresponding linear cutting problem. A refinement of this lower bound is proposed using a method of fixing certain variables.

Traditional for single S&P problems are mathematical models of integer linear programming (ILP). But others should be noted, for example, those proposed at the beginning of the 21st century: matrix model - representation of a rectangular package by two binary matrices characterizing all possible intersections of rectangles with sections of the container area parallel to the coordinate axes; a model proposed by V.N. Markov, in which a sheet of material is described by a raster sequence of points.

Methods based on CLP turned out to be acceptable for solving problems of linear (one-dimensional) and guillotine cutting. As for classes of non-guillotine packing problems, LP algorithms can hardly now be considered suitable for solving them. So far, for these tasks, most of the existing precision

Solution methods are reduced to enumerating the entire set of feasible solutions. Improved enumeration methods are also combined for these problems under the name “branch and bound method”. Back in 1973, I.V. Romanovsky and N.P. Hristova proposed the dichotomy method for solving discrete minimax problems. To obtain a lower estimate in, the authors proposed using problem relaxation, passing from the set of feasible solutions to some of its subsets.

In the 60s in Kharkov, under the leadership of V.L. Rvachev and Yu.G. Stoyan, approaches to solving problems with shaped workpieces are being developed. To describe figures bounded by a contour of a finite number of segments and arcs of circles, a special type of R-function is introduced, which makes it possible to determine whether a point belongs to a figure by one inequality, which makes it possible to simplify the check of the non-intersection of figures with each other. The search for optimal placements is carried out by composing a large number of random non-overlapping positions, each of which is then transferred by the gradient method to a locally minimal position. This approach was further developed. Used as a means of mathematical and computer modeling, R-functions made a significant contribution to the formalization of 2D and 3D C&P problems and the development of methods for solving them.

It should be noted the significant contribution made to the theory and practice of modeling the placement of geometric objects by the scientific school of Yu. G. Stoyan (Ukraine, Institute of Mechanical Engineering Problems of the National Academy of Sciences). At the end of the 60s. On the basis of the Ufa Aviation Institute, under the leadership of E. A. Mukhacheva, another scientific school is emerging, which is actively working on S&R problems to this day, including problems with arbitrary-shaped workpieces. Since the 60s. Research is underway on the problems of figure cutting at Gorky University, in the team of L. B. Belyakova, at the Institute of Technical Cybernetics of the AP BSSR, Minsk. At the same time, simplified algorithms for solving figure cutting problems using computers are being used at many manufacturing enterprises in the USSR.

More detailed review of publications before the 70s. presented in the expanded second (1951) and third (2012) editions of the book. The third reissue was prepared with the participation of V. A. Zalgaller.

nal conditions relating to various industries: metallurgy, shipbuilding, woodworking, paper and clothing industries. For example, at the Karelian Institute of Forestry Industry under the leadership of I.V. Sobolev, at Petrozavodsk State University under the leadership of V.A. Kuznetsov, work is being carried out related to the application of optimization methods at industrial enterprises in Karelia and the North-West of Russia. Methods for solving optimization problems in the pulp and paper industry are being developed here. They are implemented in application software packages aimed at solving problems associated with cutting and planning work in the woodworking industry. In addition to tasks related directly to cutting, technological problems in organizing production are considered: for ease of assembly, it is necessary to produce simultaneously or almost simultaneously all the parts of the product being produced at the moment, and the features of preliminary cutting limit the possibilities of laying these parts in rectangles, which leads to large waste . This is, for example, sawing logs, cutting corrugated cardboard.

In the 70s At Omsk State University, under the leadership of A. A. Kolokolov, research and development of algorithms for solving discrete optimization problems, which are reduced to cutting-packing problems, also begins. The main focus of this research group is on linear integer programming problems, applied placement problems, and cutting problems encountered in light industry and clothing production. New algorithms and approaches based on the use of regular partitions of relaxation sets, L-partitions, have been developed and studied. It should be noted that problems with automation of the cutting process are still being solved to this day in Omsk and Novosibirsk. An overview of existing CAD systems for design and technological preparation of clothing production is presented in. Although the main task of these systems is the modeling of individual and small-scale clothing, the process of cutting material does not use complex optimization calculation methods. One can note the work of A. A. Petunin, carried out in Yekaterinburg since the late 70s, which is aimed at automating the design of cutting sheet material. They made it possible to later develop the universal Sirius system with its own

with a new graphical interface, aimed at a wide range of equipment for cutting sheet materials.

4. MODERN DEVELOPMENT OF METHODS FOR SOLVING CUTTING-PACKING PROBLEMS

New effective precision methods have been developed in several directions. On the one hand, CLP tools were improved: modeling, branching methods, cutting planes. On the other hand, purely combinatorial methods developed, which later received their most complete development within the framework of artificial intelligence methods.

For example, a hybrid method of continuous optimization and an exhaustive search algorithm for solving the problem of packing polygons is presented, where the problem of packing rectangles into strips is considered as a special case, and a strategy has been developed for constructing multiple systems of equations and a set of rules for cutting off unpromising vertices of the decision tree. This method was further developed in the late 90s.

The problem of one-dimensional cutting with single complete sets is most suitable for solution by combinatorial methods. One of the first was the branch and bound method based on LP relaxation with column generation. In most variants of the method, branching is carried out along individual columns. In this work, the author uses a dichotomous version of the generalized method for solving discrete minimax problems for this problem. In it, at each stage, branching along the decision tree occurs in two subsets, which reduces the search for feasible solutions. For one-dimensional cutting problems with integer sets - 1D cutting-stock problem (1DCSP) - CLP methods are more effective due to the combinatorial explosion. Most of them use the 1DCSP model with column generation, first proposed in the work of L. V. Kantorovich and A. A. Zalgaller. This model has a very small empirical duality gap. The number of model variables is not limited polynomially by the dimension of the problem (number of items), so it is quite difficult to estimate the number of columns generated when searching for the optimum. In practice, the problem of quickly finding the LP optimum, i.e., the issue of accelerating the convergence of the column generation process, is very relevant.

The question of the effective use of exact combinatorial methods for solving large-dimensional cutting-packing problems remains open to this day. Research is underway to determine cutoffs that make it possible not to consider symmetric versions of the search reduction rules. For example, we consider a method with procedures for dominance, grouping, and determining an acceptable reserve, which allows us to reduce search.

A mathematical apparatus that makes it possible to calculate the optimum in the non-guillotine C&P problem for a finite number of operations was first proposed in , where the problem of packing rectangles is formulated as a combinatorial optimization problem and the “zone method” is proposed for finding the optimal solution. Based on the concept of “zones,” it is proved that for any packing of rectangles one can specify an order such that each subsequent rectangle does not intersect with any of the previous zones (topological sorting). It is shown that among the packings built on step boundaries there are optimal ones. To reduce the number of options, a number of cutoffs have been proposed that make it possible to discard options that are symmetrical to those already considered, or that are obviously no better than others.

Heuristic methods are successfully used to solve combinatorial problems from the class of NP-hard ones. Among high-level heuristics, greedy algorithms stand out, allowing one to achieve upper bounds. Multi-pass heuristics include the method of sequential refinement of estimates (Sequential Value Correction, SVC), which originates from the idea of ​​objectively determined estimates by L. V. Kantorovich. The SVC method is implemented using a modified first-come-first-served scheme with priority and repetition procedures. The ordering of elements is based on the economic meaning of dual variables in linear programming. The method can be called general for solving C&P problems: it is applicable for problems of linear and guillotine cutting, 2D and SD packaging, as well as for figured cutting.

When implementing schemes for constructing solutions in combinatorial problems, various methods are used to represent an admissible solution in the form of a code, which, using the appropriate rule (decoder), is uniquely converted into a packing plan. Encoding and decoding methods significantly affect the efficiency of the resulting solutions. In this case, the decoder itself is a single-pass

tod. A simple and popular decoder is the “lower left” one, which clearly allows you to obtain a packaging plan by code in the form of a sequence (list) of rectangular parts. The Ufa team has developed new block decoders that allow rectangular packaging to be represented in the form of a linear cutting of a special structure, for which linear solution methods are used, resulting in quick and effective solutions. 3D packaging is presented in a similar way.

If, with the chosen decoding method, the solution is repeated, slightly changing the already used code, then the value of the objective function will change for the better or for the worse. With repeated repetition, you can get a fairly good solution. Technologies for constructing local search algorithms for C&P have been developed on this principle, in combination with a combination of various decoders.

Thus, introducing elements of randomness into a deterministic algorithm increases its effectiveness. For example, the efficiency of the SVC algorithm mentioned above increased after introducing stochastic elements into it. The rapid development of probabilistic methods for local optimal search began 20 years ago with the advent of metaheuristics for solving NP-hard problems. In Russia, a review of probabilistic methods for local optimal search for NP-hard problems was made in. The review discusses general designs of tabu search, simulated annealing, evolutionary, and genetic algorithms. It is shown that these algorithms, different in their structure, use the general mathematical construction of finite Markov chains, and it is also proved that with the correct implementation of the search procedures for the specified metaheuristics, when there is no effect of “getting stuck” in the local optimum, convergence in the probability of the best found solution to the optimal one will be observed solving the problem.

Genetic algorithms were the first among complex metaheuristics to be used for C&P problems. Various coding methods and techniques for identifying the simplest structures (gene, alleles, chromosome) are possible. This gives rise to various classes of genetic algorithms. Genetic algorithms are also being successfully developed to solve figure cutting problems. Other metaheuristics are also being explored and used. Moreover, in recent

The use of artificial intelligence has been actively developing over the years.

Changes in the country that began in the 80s allowed Russian scientists to actively publish their work abroad in publications dedicated to operations research and participate in international conferences. A community called SICUP (Special Interest Group in Cut-and-Pack) brings together many researchers interested in this problem around the world. SICUP organizes sessions on S&P issues within the framework of international conferences. It was decided to organize a new community ESICUP (http://pagmas.fe.up.pt/~esicup/tiki-

index.php). And the opposite situation is the participation of foreign researchers in Russian special publications, joint research, for example.

In the USSR, scientific and practical seminars and conferences were held in Leningrad, Ufa, Zvenigorod and other cities. In the modern period, sections are organized as part of the conferences: Mathematical programming and applications (Ekaterinburg, IMM URO AN RF); Discrete analysis and operations research (DAOR, Novosibirsk, IM SB RAS); Computer Science and Information Technologies (CSIT, Ufa, UGATU); Resource-saving technologies (OPTIM, St. Petersburg); Optimization methods and their applications (Baikal International Conference on Mathematical Programming, Irkutsk); Discrete mathematics and economic applications (Omsk, branch of the Institute of Mathematics SB RAS), etc.

In the last decade, the theoretical aspects of the cutting-packing problem and geometric covering, due to their NP complexity, remain relevant. The main focus of Russian scientific research on C&P methods and problems is related not only to improving the efficiency of methods for solving them, but also to problems in which cutting and packaging tasks are included as subtasks. This imposes additional conditions and restrictions in setting tasks. For example: in the timber industry, in light industry, in the design of electronic circuits, in transport and warehouse logistics, in the construction and shipbuilding industries, etc.

For example, the works examine the problems of planning the production of corrugated containers, selecting vehicles and placing products, planning the production of lumber, planning the loading of water transport, cutting and packaging in the model.

in the development of technological processes under stochastic conditions of the production process, criteria for the effectiveness of such tasks are considered.

The theoretical prerequisites for creating an automated cutting control system in the clothing industry are described in the work; the problem of parametric modeling of complex three-dimensional objects and its application is explored. The paper provides a brief overview of existing CAD systems for design and technological preparation of clothing production. One of the first developments in the field of CAD for the designer of garments was the Belarusian system “AUTOCROY” (Minsk), operating in the 80s. at NPO Belbyttekhnika. The first system designed specifically for designing clothing using a personal computer was the LEKO system, developed by the Central Research and Production Institute of the Garment Industry (TsNIISHP). Currently, the system is used by small sewing and knitting enterprises, as well as universities that train specialists in the field of designing garments. Following LEKO, a series of CAD systems appears: ASSOL System (Center for Computer Technologies at the Moscow Institute of Physics and Technology); The T-FLEX/CLOTHING system uses standard design techniques; GRACE, etc. One of the latest developments was the ELEANDR-CAD system (Scientific and Technical Center for Design and Technology at MGUDT and the Eleander LLC company, 2003). In this paper, the authors study the problem of minimal coverage using the example of designing fur products.

Research has shown that tasks in which it is necessary to form, in a certain sense, an optimal set of objects (machines, sets of clothing models, techniques, properties), covering the “needs” of another set (works, clients, orders, characteristics) when certain conditions determined by the specifics are met problems can be reduced to covering problems and their various modifications. Based on this, a hybrid algorithm has been developed to solve problems of optimizing the selection of objects in the process of technical preparation of production, including when determining the dominant properties of materials, using the example of light industry. An original approach to studying the connection between the problems of orthogonal cutting and covering using the example of problems of constructing routes that satisfy certain restrictions is given by T. Pa-

nyukova, . The author noted that in problems of cutting sheet material, a flat graph is a model of the cutting plan, and a route covering all edges determines the trajectory of the cutting tool. The paper presents a modification of the algorithm for constructing a covering with ordered coverage for the case of a multiconnected graph. Constructing a graph covering with ordered coverage solves the cutting problem. Of greatest interest are coatings with a minimum number of chains, since the transition from one chain to another corresponds to an idle pass of the cutting tool.

An example of the use of genetic algorithms to automate the placement of different-sized fuel elements in electronic modules of a three-dimensional layout based on a thermal criterion is given in the work.

Many works have been devoted to solving the problem of placing cargo in the cargo compartments of vehicles, which arises as a subtask in logistics systems. For example, the problem of managing the loading of containers is solved, taking into account their physical characteristics; for this problem, the conditions for technological loading and unloading of consumer goods are taken into account, i.e. sequence of customer visits when delivering goods.

The paper proposes an algorithm for solving a problem that arises, for example, in the construction industry - the problem of geometric coverage of a multiconnected polygon with an orthogonal resource. The initial information is the dimensions of the area to be covered and the available orthogonal resource, and the dimensions of the covering elements that must subsequently be cut from the resource are not determined in advance. This determines the multi-criteria optimization of the process of constructing interconnected rational plans for geometric covering with rectangular elements of unspecified sizes and cutting the orthogonal resource into covering elements.

Technological features of cutting equipment determine the emergence of problems of designing control programs for sheet metal cutting machines. In the work, the author notes the importance of the problem of cost and significance of various stages of the process of cutting blanks from a material resource, such as, for example, moving the cutting tool to another place of the sheet being cut and new cutting. Thus, in addition to dense placement of workpieces on the cutting plan, the objective function is aimed at optimizing the route

cutting tools, taking into account the cost of cutting, new insertion.

Considerable attention is also paid to theoretical developments of the problem of cutting and packaging. For example, in the works the problems of packing corrugations (orthogonal connected polygons) are considered from the standpoint of the general theory of the problem of optimal placement of geometric objects, algorithms for packing "-dimensional corrugations based on linear programming methods are proposed, as well as models and methods for optimizing the packing of "-dimensional parallelepipeds.

CONCLUSION

The variety of cutting problems, together with the importance of their rational solution, determines the undying interest of experienced and young researchers around the world in this problem, which is associated with a steady growth trend in the number of new techniques for solving them.

C&P problems have a remarkable combination of their broad practical applicability and their belonging to NP-hard problems, which makes this problem an important testing ground for new research. Thanks to this, the ideas of L. V. Kantorovich will be used and developed in various areas of scientific and practical human activity related to the problem of cutting.

BIBLIOGRAPHY

1. Kantorovich L. V. Mathematics, management, computer science: monograph / ed.: G. A. Leonov, V. S. Katkalo, A. V. Bukhvalov, St. Petersburg: Higher. school management: Publishing house of St. Petersburg University, 2010. 575 p. [L. V. Kantorovich, Mathematics, management, informatics: monograph, (in Russian). Edited by G. A. Leonov, V. S. Katkalo, and A. V. Buhvalov, St.Ptsb.: Management higher school: St. Petersburg University Publishing House, 2010. ]

2. Kantorovich L. V. Mathematical methods of organization and production planning. Leningrad State University, 1939. 67 p. . [L. V. Kantorovich, Mathematical Methods of Production Management and Planning, (in Russian). Leningrad: Leningrad Univ., 1939.]

3. Kantorovich L.V. Rational methods of metal cutting // Proiz.-tekhn. Bulletin NK Ammunition USSR. 1942. No. 7-8. pp. 21-29. [L. V. Kantorovich, “Efficient Methods of Metal Cutting,” (in Russian), Product.-techn. bulletin. of NK Ammunition of the USSR, no. 7-8, pp. 21-29, 1942. ]

4. Feldman H. L. System of maximum sawing positions. M.: Gostekhizdat, 1932. [H. L. Feldman, Maximum delivery system for sawing, (in Russian). Moscow: Gostehizdat, 1932. ]

5. Zalgaller V. A. New in the preparation of supplies for sawing logs. L.: TsNIIL "Sevzaples", 1956. Issue. 67. [V. A. Zalgaller, A step forward in delivery formation for timber sawing, (in Russian). Leningrad: CNIIL "Sevzaples", vol. 67, 1956. ]

6. Valiakhmetova Yu. I., Mukhacheva E. A., Filippova A. S., Gilmanova N. A., Karipov U. A. Multimethod

orthogonal packaging technology and its application in transport logistics tasks // Supplement to the journal “Information Technologies”. 2009. No. 12. 31 p. [U. I. Valiahmetova, et al., “Multimethod technology of orthogonal bin-packing and its application in transport logistics problems,” (in Russian), in Appendix to Magazine Information technologies, no. 12, 2009. ]

7. Mukhacheva E. A., Mukhacheva A. S., Valeeva A. F., Kartak V. M. Local search methods in problems of orthogonal cutting and packaging: analytical review and development prospects // Information technologies. 2004. No. 5. Appendix. pp. 2-17. [E. A. Mukhacheva, et al., “Local search methods in orthogonal cutting-packing problems: analytical survey and development outlook,” (in Russian), in Appendix to magazine Information Technologies, no 5, pp. 2-17, 2004. ]

8. Kantorovich L. V., Zalgaller V. A. Calculation of rational cutting of materials. Lenizdat, 1951. 198 p. [L. V. Kantorovich and V. A. Zalgaller, Computation of effective material cutting, (in Russian). Lenizdat, 1951. ]

9. Bulavsky V. A., Yakovleva M. A. On solving the problem of optimal cutting of linear materials on a computer // Linear programming: Proceedings of Scientific. meeting about the application of mathematics. methods in economics research and planning. M.: USSR Academy of Sciences, 1961. T. IV. pp. 83-87. [V. A. Bulavski and M. A. Jakovleva, “To solve problems of linear material cutting on COMPUTER,” (in Russian), in Linear programming. Papers of scientific conference on mathematical method application in economics. research and planning, vol. IV. Moscow: AS USSR, 1961, pp. 83-87. ]

10. Mukhacheva E. A. Rational cutting of rectangular sheets into rectangular blanks // optimal planning: p6. scientific tr. Siberian Branch of the USSR Academy of Sciences. 1966. Vol. 6. P. 43-115. [E. A. Mukhacheva, “Effective cutting of rectangular sheets to rectangular items,” (in Russian), in Optimal planning: Collection of scientific papers SO AS USSR, Issue 6, pp. 43-115, 1966. ]

11. Romanovsky I.V. Solution of the guillotine cutting problem by processing the list of states // Cybernetics. 1969. No. 1. P. 102-104. [I. V. Romanovski, “Solution of guillotine cutting problem by the method of sorting out of the state list,” (in Russian), Cybernetics, no. 1, pp. 102-104, 1969. ]

12. Mukhacheva E. A. Methods of conditional optimization in the problem of rational cutting of sheet metal // Optimization: p6. scientific tr. Siberian Branch of the USSR Academy of Sciences. 1978. Vol. 22. pp. 83-93. [E. A. Mukhacheva, “Methods of conditional optimization in the problem of effective cutting of sheet rolling,” (in Russian), in Optimization: Collection of scientific papers SO AS USSR, 1978, Issue 22, pp.83-93. ]

13. Romanovsky I.V. Program for solving the linear cutting problem. - Optimal planning. Novosibirsk 1969. Issue 12. [I. V. Romanovski, “Program of solving the linear cutting problem,” (in Russian), in Optimal planning, Novosibirsk, 1969, Issue 12. ]

14. Kartak V. M. Updated lower bound for the problem of packing rectangles into a semi-infinite strip // Bulletin of UGATU. 2008. T. 10, No. 2 (27). pp. 154-158. [V. M. Kartak, “A new low bound for orthogonal packing problem,” (in Russian), Vestnik UGATU, vol. 10, no. 2 (27), pp. 154158, 2008. ]

15. Belov G., Kartak V., Rohling H., Scheithauer G. One-dimensional relaxations and LP bounds for orthogonal packing // ITOR, 2009. Vol. 16. P. 745-766. [G. Belov, et al. "One-dimensional relaxations and LP bounds for orthogonal packing," ITOR, vol. 16, p. 745-766, 2009. ]

16. Kartak V. M. Matrix algorithm for finding an optimal solution for the problem of packing rectangles into a semi-infinite strip // Information technologies. 2008. No. 2. P. 24-30. [V. M. Kartak, “Matrix algorithm for searching the optimum solution of rectangular packing in a semi-endless strip,” (in Russian), Information technologies, no. 2, pp.24-30, 2008. ]

17. Markov V. N. Knowledge base for non-guillotine cutting and packaging // Information technologies. 2007. No. 4. pp. 17-23. [V. N. Markov, “Basic knowledge for nonguillotine cutting-packing,” (in Russian), Information technologies, no 4, pp. 17-23, 2007. ]

18. Romanovsky I. V., Khristova N. P. Solution of discrete minimax problems by the dichotomy method // Zh. Vychislit. mathematicians and math. physics. 1973. T. 13, No. 5. P. 1200-1209. [I. V. Romanovski and N. P. Hristova, “Solution of discrete minimax problems by dichotomy method,” (in Russian), J. of calculat. math. and math. Physics, vol. 13, no. 5, pp. 1200-1209, 1973. ]

19. Stoyan Yu. G., Yakovlev S. V. Mathematical models and optimization methods of geometric design. Kyiv: Naukova Dumka, 1986. 268 p. [U. G. Stojan and S. V. Jakovlev, Mathematical models and optimization methods of geometrical design, (in Russian). Kiev: Naukova dumka. 1986. ]

20. Rvachev V.L., Stoyan Yu.G. To the problem of optimal placement of circular patterns // Cybernetics. 1965. No. 4. [V. L. Rvachev and U. G. Stojan, “To the problem of optimal placement of round patterns,” (in Russian), Cybernetics, no. 4, 1965. ]

21. Stoyan Y., Terno J., Romanova T., Scheithauer G.

Construction of a Ф-function for two convex polytopes // Applications Mathematicae. 2002. V. 2, No. 29. P. 199-218. [Y. Stoyan, J. Terno, T. Romanova, and G. Scheithauer, “Construction of a Ф-function for two convex polytopes,” Applications Mathematicae, vol. 2, no. 29, pp. 199-218, 2002. ]

22. Verhoturov M. A., Sergeyeva O. Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // PO. 2000. Vol. 20, No. 2. P. 233-247. [M. A. Verhoturov and O. Y. Sergeyeva, “The sequential value correction method for the two-dimensional irregular cutting stock problem,” vol. 20, no. 2, pp. 233-247, 2000. ]

23. Babaev F.V. Rational cutting of sheets into parts of complex geometric configurations // Welding production. 1968. No. 8. [F. V. Babaev, “Effective sheet cutting into items of complex geometric configurations,” (in Russian), Welding production, no. 8, 1968. ]

24. Kantorovich L. V., Zalgaller V. A. Rational cutting of industrial materials. 3rd ed. St. Petersburg: Nevsky Dialect, 2012. 304 p. [L. V. Kantorovich and V. A. Zalgaller, Effective cutting of industrial material, Issue 3, (in Russian). St. Petersburg: Nevskij dialect, 2012. ]

25. Sobolev I.V. Management of lumber production. M.: Lesn. industry, 1981. 181 p. [I. V. Sobolev, Timber production control, (in Russian). Moscow: Timber prod., 1981. ]

26. Kuznetsov V. A., Shegelman I. R. Application of mathematical methods and PCs in forestry. St. Petersburg: SPbLTA, 1988. 68 p. [V. A. Kuznetsov and I. R. Shegelman, Application of mathematical methods and PC in logging areas, (in Russian). St.Petersbourg: Publishing house St. Ptsb, LTA, 1988. ]

27. Kuznetsov V. A. Cutting problems in the pulp and paper industry. SPb.: SPbLTA, 2000. 132 p. [V. A. Kuznetsov, Cutting problems in pulp and paper industry, (in Russian). St. Ptsb: Publishing house St. Ptsb. LTA, 2000. ]

28. Kolokolov A. A. On the number of cutting planes in the first Gomori algorithm // Problems of analysis of discrete information. Novosibirsk: Institute of Economics and Economics of the USSR Academy of Sciences, 1975. pp. 84-96. [A. A. Kolokolov, “About the number of cut-ting-off planes in the first algorithm of Gomory,” (in Russian), in Problems of discrete information analysis, Novosibirsk: IEOIP SO AS USSR, 1975, pp.84-96. ]

29. Kolokolov A. A. Regular partitions and cuts in integer programming // Siberian Journal of Operations Research. 1994. No. 2. P. 18-39. [A. A. Kolokolov, “Regular splitting and cutting off in integr programming,” (in Russian), Siberian journal of operational research, no. 2, pp. 18-39, 1994. ]

30. Kolokolov A. A., Korobova A. B., Zakharova E. O., Privalova Yu.I. Development of discrete optimization models for the formation of a collection of teenage clothing // Omsk Scientific Bulletin. 2006. No. 7 (43). pp. 138-140. [A. A. Kolokolov, et al., “Development of discrete optimization models for designing teenagers’ clothes,” (in Russian), The Omsk scientific bulletin, no. 7 (43), pp. 138-140, 2006. ]

31. Frolovsky V.D., Frolovsky D.V. Modeling and development of complex surfaces in AutoCAD R14 // CAD and graphics. 1998. No. 3. P. 74-75. [V. D. Frolovski and D. V. Frolovski, “Modeling and evolving of complex surfaces in AutoCAD R14,” (in Russian), SAD and graphics, no. 3, pp.74-75, 1998. ]

32. Landovsky V.V., Pishchinskaya O.V., Frolovsky V.D. Modeling the process of designing clothes for female figures with postural disorders. // News of higher educational institutions. North Caucasus region. Series tech. Sci. 2009. No. 6. P. 114-118. [ V. V. Landovski, O. V. Pischinskaja, and V. D. Frolovski, “Modeling of the process of designing clothes for women’s figures of defect posture,” (in Russian), Bulletin of highest schools, North-Caucasus region. Series tech. science, no 6, pp. 114118, 2009. ]

33. Korobtseva N. A. CAD for clothing: historical excursus and review of existing systems // Textile industry. 2003. No. 5. P. 61-62; No. 6. pp. 63-65. [N. A. Korobtsev, “SAD of clothing: historical excursus and present systems review,” (in Russian), Textile industry, no. 5, pp. 61-62, no. 6, pp. 63-65, 2003. ]

34. Petunin A. A. Integrated CAD “Sirius” for automation of cutting and blank production. Concept. Experience in development and implementation // Resource-saving technologies: mathematical support for optimization problems in computer-aided design systems: collection of articles. report 1st All-Russian scientific-practical conf. on solving optimization problems in industry. St. Petersburg: TsNIITS, 2001. pp. 126-129. [A. A. Petunin, "Integrated SAD "Sinus" for automation of cutting--logging production. Concept. Experience of development and implementation," (in Russian), in Resource-saving technologies: Mathematical ensuring of optimization problems in systems of automat designing: Collection of reports 1st All-Union scientific--practical conference on solution of optimization problems in industry, St. Ptsb: CRITS, 2001, pp. 126-129. ]

35. Petunin A. A. Optimization of the tool route for machines cutting sheet material // Computer Science and Information Technologies: Intern. scientific ed.: mat. 13th Int. conf. CSIT"2011 (Garmisch-Pantherkirchen, Germany, September 27 - October 2, 2011). Ufa, 2011. T. 1. P. 179-182. [ A. A. Petunin, "Tool route optimization for structural sheet cutting machines, " in Proc. 13th workshop on Computer Sciences and Informational Technologies, (CSIT"2011) Garmish-Panterkirhen, Germany, 2011, (in Russian), Ufa, 2011, vol. 1, pp. 179-182. ]

36. Novozhilova M. V. Solution of the problem of searching for a global extremum of a linear objective function on the structure of linear inequalities: preprint. Academy of Sciences of the Ukrainian SSR, Institute of Problems of Mechanical Engineering. Kharkov, 1988. 48 p. [ M. V. Novozhilova, Solving the problem of global extremum search for linear goal function on the basis of linear inequality structure, (in Russian). Preprint. AS Ukr.SSR. Institute of engineering industry problems. Kharkov, 1988. ]

37. Katsev S. B. On one class of discrete minimax problems // Cybernetics. 1979. No. 5. P. 139-141. [S. B. Katsev, “About one class of discrete minimax problems,” (in Russian), Cybernetics, no. 5, pp. 139-141, 1979. ]

38. Lipovetsky A.I. Toward optimization of free placement of rectangles // Automation of design in mechanical engineering. 1985. pp. 80-87. [A. I. Lipovetski, “To optimize of rectangular free placement,” (in Russian), Automation design in engineering industry, Minsk, pp. 80-87, 1985. ]

39. Akkuratov G.V., Bereznev V.A., Brezhneva O.A.

On a method for solving an equation with Boolean variables // Decision Making under Uncertainty: Interuniversity. scientific Sat. Ufa: UAI, 1990. pp. 145-154. [ G. V. Accuratov, V. A. Bereznev, and O. A. Brezhneva, “About the method of solving equation with Boolean variables,” (in Russian), Making decision under uncertainty conditions. Interinstitute scientific collection, Ufa: USATU, pp. 145-154, 1990. ]

40. Mukhacheva E. A., Zalgaller V. A. Linear programming cutting problems // Int. J. of Software Engineering and Knowledge Engineering. 1993. V. 3, No. 4. P. 463-476. [E. A. Mukhacheva and V. A. Zalgaller, “Linear programming cutting problems,” Int. J. of Software Engineering and Knowledge Engineering, vol. 3, no. 4, pp. 463-476, 1993. ]

41. Mukhacheva A. S., Valeeva A. F., Kartak V. M. Problems of two-dimensional packaging in containers: new approaches to the development of methods for local search for the optimum. M.: MAI, 2004. 193 p. [ A. S. Mukhacheva, A. F. Valeeva, and V. M. Kartack, Problems of 2D packings into containers: new approaches to development of local optimum search methods, (in Russian). Moscow: MAI, 2004. ]

42. Mukhacheva A. S. Technology of block structures for local optimal search in rectangular packaging problems // Information technologies. Application. 2004. No. 5. P. 18-31. [A. S. Mukhacheva, "Technology of block structures for optimal local search in rectangular bin-packing problems", (in Russian), in in Appendix to Magazine Information technologies. Appendix, no. 5, pp. 18-31, 2004. ]

43. Kochetov Yu. A. Probabilistic methods of local search for discrete optimization problems // Discrete mathematics and its applications: p6. lectures for youth. and scientific school in discrete mathematics and its applications. M.: Publishing house of the center for applied research at mech.-mathematics. Faculty of Moscow State University, 2000. P. 87-117. [U. A. Kochetov, “Probabilistic methods of local search for discrete optimization problems,” (in Russian), in Discrete mathematics and its application. Collection of lectures of students and scientific schools on discrete mathematics and its applications, Moscow: Publishing house of the applied research center of the mech.-maths depart. MSU, 2000, pp. 87-117. ]

44. Norenkov I. P. Heuristics and their combinations in genetic methods of discrete optimization. // Information Technology. 1999. No. 1. P. 2-7. [I. P. Norenkov, “Heuristics and their combinations in discrete optimization genetic methods,” (in Russian), in Appendix to Magazine Information technologies, no. 1, pp. 2-7, 1999. ]

45. Mukhacheva A. S., Chiglintsev A. V., Smagin M. A., Mukhacheva E. A. Two-dimensional packaging problems: development of genetic algorithms based on mixed procedures for local search for an optimal solution // Information technologies. Application. 2001. No. 9. 28 p. [ A. S. Mukhacheva, et al., “2D bin-packing problems: development of genetic algorithms based on compound procedures of local search for optimal solution,” (in Russian), in Appendix to Magazine Information technologies, no. 9, 2001. ]

46. ​​Frolovsky V. D., Pushkaryova G. V. Metal cutting motion optimization for NC-programs design, using genetic algorithms. Proc. of the 6th Int. Conf. on Computer Graphics and Artificial Intelligence, Limoges (France), May 14-15, 2003. P. 143-152. [V. D. Frolovsky and G. V. Pushkaryova, “Metal cutting motion optimization for NC-programs design, using genetic algorithms,” Proc. of the 6th Internat. Conf. on Computer Graphics and Artificial Intelligence, Limoges (France), May 14-15, 2003, pp. 143-152. ]

47. Korchevskaya O. V., Zhukov L. A. Obtaining lower bounds for two- and three-dimensional orthogonal packing problems [Electronic resource] // Researched in Russia: electronic journal. 2008. 62. pp. 685-694. URL: http:// zhurnal.ape.relarn/articles/2008/062.pdf [ O. V. Korchevskaja, L. A. Zhukov, "Low boundaries procure for 2G and 3D orthogonal bin-packing problems," (in Russian), Electronic magazine "Investigated in Russia", 62, 2008. pp. 685-694, http:// zhurnal.ape.relarn/articles/2008/062.pdf ]

48. Mukhacheva E., ed. Special issue: Decision making under conditions of uncertainty (cutting-packing problems) // The International Scientific Collection. 1997. Ufa, Russia. [E. Mukhacheva, ed. Special issue: Decision making under conditions of uncertainty (cutting-packing problems). The International Scientific Collection, Ufa, Russia, 1997. ]

49. Sergeyeva O., Scheithauer G., Terno J. The value correction method for packing of irregular shapes // Decision making under conditions of uncertainty (cutting-packing problems): The Int. Sci. Collection. Ufa, 1997. P. 261-270. [ O. Sergeyeva, G. Scheithauer, and J. Terno, “The value correction method for packing of irregular shapes,” Decision making under conditions of uncertainty (cutting--packing problems). The International Scientific Collection, Ufa, 1997, pp. 261-270. ]

50. Belov G., Kartak V., Rohling H., Scheithauer G. One-dimensional relaxations and LP bounds for orthogonal packing. ITOR, 2009. V. 16. P. 745-766. [G. Belov, et al., “One-dimensional relaxations and LP bounds for orthogonal packing,” ITOR, vol. 16, pp. 745-766, 2009. ]

51. Frolovsky V. D. Parametric modeling and identification of three-dimensional objects with a complex structure // Information systems and technologies: material. Intl. scientific-technical Conf.. Novosibirsk: NSTU, 2003. T. 1. P. 153-155. [V. D. Frolovski, “Parametric simulation and identification of 3D objects with complicated structure,” (in Russian), in Proc. Int. Sci.-Tech. Conference "Information Systems and Technologies", Novosibirsk, NGTU, 2003, vol. 1, pp. 153-155. ]

52. Kolokolov A. A., Nagornaya Z. E., Archimenko M. Yu., Ivanova S. D. Design of fur products using mathematical modeling // Dynamics of systems, mechanisms and machines: material. IV Int. scientific-technical conf., dedicated 60th anniversary of Omsk State Technical University. Book 1. Omsk: Omsk State Technical University, 2002. pp. 297-299. [A. A. Kolokolov, et al., “Fur goods design using mathematical modeling, Dynamics of systems, mechanisms and machines,” (in Russian), in Proc. 4 Int. Sci.-Tech. Conference to the 60 anniversary of OmGTU, vol.1, Omsk, 2002, pp. 297-299. ]

53. Panyukova T. A. Optimal Euler coverings with ordered coverage for planar graphs // Discrete Analysis and Operations Research. March-April, 2011. T. 18, No. 2. P. 64-74. [ T. A. Panukova, “Optimal Euler coverings with ordered union for flat graphs,” (in Russian), in Discrete analysis and operational research, MarchApril, vol. 18, no. 2, pp. 64-74, 2011. ]

54. Novikov I. S. Automatic placement of different-sized electronic elements through genetic search with migration // Design and technology of electronic means. 2007. No. 1. P. 33-38. [I. S. Novikova, “Automatic allocation of electronic elements of different sizes by genetic search with migration,” (in Russian), in Design and technology of electronic facility, no. 1, pp. 33-38, 2007. ]

55. Mukhacheva E. A., Valeev R. S. Local search for the placement of product items based on the analysis of their nomenclature // Information technologies. 2010. No. 6. P. 18-23. [E. A. Mukhacheva and R. S. Valeev, “Local search of Commodity allocation based on their product range,” (in Russian), in Informational Technologies, no. 6, pp. 18-23, 2010. ]

56. Mukhacheva E. A., Bukharbaeva L. Ya., Filippov D. V., Karipov U. A. Optimization problems of transport logistics: operational placement of containers during cargo transportation // Information technologies. 2008. No. 7. P. 17-22. [E. A. Mukhacheva, et al., “Optimization problems of transportation logistics; containers operational allocation while cargo conveying,” (in Russian), Information Technologies, no. 7, pp. 17-23, 2008. ]

57. Telitsky S.V., Filippova A.S. An integrated approach to solving the problem of covering an area with workpieces of uncertain sizes // Scientific and Technical Journal of St. Petersburg State Polytechnic University. Computer science. Telecommunications. Management

tion. 2 (145) / 2012, St. Petersburg, 2012. pp. 61-67. [ S. V. Telitskiy and A. S. Filippova, “Complex approach to solving the problem of area covering with items of non-defined sizes,” (in Russian), in Scientific-technicheskye Vedomosty SPbGPU, Informatics. Telecommunication. Management, 2(145)/2012, StPsb, pp. 61-67, 2012. ]

58. Vasilyeva L. I. Packing algorithms for N-dimensional corrugations based on linear programming methods: dis. ...cand. tech. Sciences / UGATU, 2000. [L. I. Vasilyeva, “Packing algorithms od N-dimensionv corrugations based on linear programming methods,” (in Russian): Dissertation for scientific degree of a Cand. of Tech. Sci, UGATU, 2000.].

59. Kartak V. M. Models and methods for optimizing the packaging of n-dimensional parallelepipeds: dis. ...cand. physics and mathematics Sciences / UGATU, 1999. [V. M. Kartak, “Models and methods of optimization of n-dimensional parallelepiped packing,” (in Russian): Dissertation for scientific degree of a Cand. of physics-maths Sci, UGATU, 1999. ]

VALIAKHMETOVA Yulia Ilyasovna, associate professor. department mathematics. Dipl. Eng. (USATU, 2004). Cand. tech. sciences in mathematics mode-lyr., number. methods and program complexes (USATU, 2008). Research in the region optimization cutting-packing tasks. FILIPPOVA Anna Sergeevna, prof. department applied computer science. Dipl. Eng. (USATU, 1996). Dr. Tech. Sciences Mat. simulation, num. methods and program complexes (SSAU, 2007). Research in the region combinatorial algorithms.

Title: Theory of optimal resource utilization by L. V. Kanto-rovich in cutting-packing problems: overview and history of development of solving methods Authors: Yu. I. Valiakhmetova, A. S. Filippova. Affiliation:

1 Bashkir State Agrarian University (BSAU), Russia.

2 Bashkir State Pedagogical University of M. Akmulla (BSPU), Russia.

Email: [email protected], [email protected]. Language: Russian.

Source: Vestnik UGATU (scientific journal of Ufa State Aviation Technical University), vol. 18, no. 1 (62), pp. 186-197, 2014. ISSN 2225-2789 (Online), ISSN 1992-6502 (Print). Abstract: The article presents examples of solution techniques for cutting-packing problems, which are still relevant to this day taking into account their diversity and many-sided applicability. The scientific papers by L. V. Kantorovich are considered to be fundamental for the development of these procedures. The article gives an overview of procedures for solving cutting-packing problems that have been developed by Soviet and Russian scientists in the last 80 years, including various scientific schools of the USSR and Russia. Summary of solving procedures and the history of their development are also described. Key words: cutting, optimal use of resources, optimization, exact methods, heuristic methods.

VALIAKHMETOVA, Yuliya Ilyasovna, Associate Prof., Dept. of Mathematics, Dipl. Engineer-programmer (UGATU, 2004). Cand. of Tech. Sci. (UGATU, 2008). FILIPPOVA, Anna Sergeevna, Prof., Dept. of Applied Informatics. Dipl. Systems Engineer (UGATU, 1996). Cand. of Tech. Sci. (Ufa State Univ., 1999).,Dr. of Tech. Sci. (Samara State Aerospace Univ., 2007).

As is known, in the practice of economic activity, the choice between various options (plans, decisions) involves searching for the best. When a housewife goes to the market to buy meat, and a designer seeks to find the optimal way to place machines, they are looking for options that require a minimum of costs or a maximum of results, taking into account certain restrictions (money, resources, time).
Solving a problem like this can be difficult, especially when there are a large number of options. The time and costs when choosing the optimum are not always justified: the costs of searching and searching through options may exceed the achieved gain.
As practice shows, experience and intuition are insufficient to justify the optimal solution.
138
A more reliable and effective way is to use mathematical (quantitative) approaches and calculations. However, mathematical approaches and justifications were ignored for a long time by theorists who made the “weather” in economic science. Many important works were frozen, publications by mathematical economists were slowed down and limited. And yet, during that period, mathematical research continued, even in the conditions of persecution of mathematicians, brilliant results were achieved.
One of the most significant and striking achievements in the field of economic and mathematical research was the discovery by Leonid Vitalievich Kantorovich (1912-1986) of the Linear Programming Method. Linear programming is the solution of linear equations (equations of the first degree) by drawing up programs and using various methods for their sequential solution, which significantly facilitates calculations and achievement of the desired results.
For the development of the linear programming method, or, as stated in the diploma of the Swedish Academy of Sciences, for “contribution to the theory of optimal resource allocation,” L. V. Kantorovich, the only Soviet economist, was awarded the Nobel Prize in Economics (1975). The prize was awarded to him jointly with the American economist Tjalling Charles Koopmans; who, somewhat later, independently of Kantorovich, proposed a similar methodology.
The development of linear programming began with the search for a solution to a practical problem. Engineers from the plywood trust approached Kantorovich with a request to find an effective way to allocate resources that would ensure the highest equipment productivity. The company’s employees were racking their brains over how, with five machines and eight types of raw materials, to provide the optimal option for plywood production. In other words, it was necessary to find a solution to a specific technical and economic problem with a target function (“functional”) - to maximize the output of finished products.
Kantorovich's merit is that he proposed a mathematical method for selecting the optimal option. Solving a particular problem of the most rational loading of equipment, the scientist developed a method called the linear programming method. In fact, he opened a new branch in mathematics, which has become widespread in economics.
139
chesical practice; contributed to the development and use of electronic computing technology.
Kantorovich was not a “pure” economist, but he perfectly understood the importance of the method of maximization with limited resources, and therefore the creation of a mathematical basis for solving typical economic problems.
The conditions of the optimum problem and the goal to be achieved can be expressed using a system of linear equations. Since there are fewer equations than unknowns, the problem usually has not one but many solutions. You need to find one, according to the terminology of mathematicians, an extreme solution.
In the problem of optimizing the production of plywood, Kantorovich introduced a variable that should be maximized as the sum of the costs of production produced by all machines. The limiters were presented in the form of equations establishing the relationship between all the factors spent in production (wood, glue, electricity, working time) and the amount of output (plywood) on each of the machines. For indicators of production factors, coefficients were introduced, called resolving factors, or multipliers. With their help, the task is resolved. If the values ​​of the resolution multipliers are known, then the required values, in particular, the optimal volume of output, can be found relatively easily.
Kantorovich substantiated the economic meaning of the coefficients (resolution multipliers) he proposed. They represent nothing more than the marginal costs of the limiting factors. In other words, these are objectively significant prices for each factor of production in relation to the conditions of a fully competitive market.
To solve the optimal problem, Kantorovich used the method of successive approximations, sequential comparison of options with the choice of the best in accordance with the conditions of the problem.
Let's say you need to solve a transport problem and justify the most rational distribution of cargo flows. For example, a total of 180 tons of cargo needs to be transported from three sources to three consumers, whose total demand is also 180 tons. The difficulty is that the cargo is distributed unevenly: one supplier has 50 tons, another has 60, and a third has 70 tons. .
140
Consumer demand is also unequal; it amounts to 40, 85 and 55 tons respectively. The distances (shoulders) for transporting goods are also unequal - from 1 to 6 km. The task is to draw up a transportation plan that would meet the requirement of minimizing cargo turnover (minimum number of ton-kilometers).
How to solve this problem? In everyday practice, managers can engage in monotonous work of lengthy selection of possible options. Gradually they will be able to move from a transportation plan of, say, 750 t/km to a plan of 655 t/km. The search will require a lot of effort and a significant amount of calculations. The main thing is that it is difficult to establish which of the proposed options is optimal. Let’s say a variant of the plan has been found with a cargo turnover of 575 t/km. But it remains unknown whether there are one or more more cost-effective plan options available.
The problem becomes completely insoluble if we move from a relatively simple scheme to setting the task of drawing up an option for transporting one or more products (coal, cement, building materials) on a regional or national scale. Even in the case of consolidation and aggregation of the initial indicators (the number of senders and recipients of mass works), it turns out that only the network diagram will cover tens of thousands of aggregated points, and calculations and comparison of options will require such a number of operations, for the implementation of which it will be necessary to involve a little or not the entire population of Russia.
The first work that outlined the essence of the method proposed by Kantorovich was published in 1939 under the title “Mathematical methods for organizing production planning.” Continuing his research, the scientist develops a general theory of rational use of resources.
During the Great Patriotic War, Kantorovich, being a professor at the Naval Engineering Academy in besieged Leningrad, substantiated, based on the linear programming method, the optimal placement of production and consumer factors. The book he prepared in 1942, “Economic Calculation of the Most Expedient Use of Resources,” unfortunately, was not published at that time.
Later, one of his largest works, “Economic Calculation of the Best Use of Resources” (1959), was published.
141
This book, as noted by members of the Scientific Council on the Application of Mathematics in Scientific Research and Planning, presents an in-depth analysis of the ideas of linear programming developed by the author earlier, and at the same time, for the first time, the problem of developing an optimal plan for the entire national economy as a mathematical model is posed39.
Kantorovich's undoubted merit is the identification of dual estimates in linear programming problems. It is impossible to simultaneously minimize costs and maximize results. One contradicts the other. At the same time, both of these approaches are interrelated; if, say, an optimal transportation scheme is found, then a certain price system corresponds to it. If optimal price values ​​are found, then it is relatively easy to obtain a transportation scheme that meets the optimality requirement.
For any linear programming problem, there is a conjugate, or dual, problem. If the direct problem is to minimize the objective function, then the dual problem is to maximize.
Dual assessments make it possible in principle to compare not only price and cost indicators, but also utility. At the same time, dual, interrelated assessments correspond to specific conditions. If conditions change, then assessments change. To a certain extent, the search for the optimum is the determination of socially necessary costs, taking into account, on the one hand, labor and cost costs, and on the other hand, social needs, the usefulness of the product for consumers.
When getting acquainted with works on linear programming, you may encounter some terminological subtleties. The term “resolving multipliers”, originally used by Kantorovich, in subsequent works receives a slightly different interpretation and a different formulation, namely objectively determined estimates. These estimates are not arbitrary; their values ​​are objectively determined; they are specified by the specific conditions of the problem. The values ​​of objectively determined assessments are only suitable for this task,
Kantorovich suggested calculating them when developing plans; Enterprises are called upon to rely on these indicators when calculating costs and output volumes of certain types of products. Objectively determined assessments are adjusted according to
142
depending on the relationship between demand and production volumes. This kind of calculation, introduced into planning and management practice, is designed to optimize the use of resources.
The ideas and proposals put forward by Kantorovich included the use of market categories in business practice. In fact, at that time a search was underway and the prerequisites for a conceptual basis for reforming the existing economic system were being formed.
With the active participation of Kantorovich and his closest colleagues and friends - Viktor Valentinovich Novozhilov (1892-1970), Vasily Sergeevich Nemchinov (1894-1964) in the second half of the 50s - early 60s. A domestic economics and mathematics school is being formed. All three continued to develop linear programming methods, built economic models, and then moved on to develop a system of models called SOFE (system of optimal functioning of the economy).

ABSTRACT

Topic: “Application of linear programming methods in

military affairs. Simplex method"

2nd year cadet, 1st flight. 8th company

Far Eastern Military Institute

them. K.K. Rokossovsky

Vereshchak Dmitry Vladimirovich

PLAN

I. What is linear programming

II. Main directions of using linear programming in military affairs

1.Transportation problems (transport) problem

2. Problems of optimal allocation of funds

defeats

III. Simplex method

IV. Conclusion

I. WHAT IS LINEAR PROGRAMMING

Every day, without always realizing it, every person solves the problem: how to get the greatest effect with limited funds.

Our funds and resources are always limited. Life would be less interesting if this were not so. It is not difficult to win a battle with an army 10 times larger than the enemy's; Hannibal, in order to defeat the Romans at Cannae, commanding half the army, had to act very deliberately.

To achieve the greatest effect with limited funds, you need to draw up a plan, or program of action. Previously, the plan in such cases was drawn up “by eye” (now, however, it is often the same). In the middle of the 20th century, a special mathematical apparatus was created that helps to do this “according to science.” The corresponding branch of mathematics is called mathematical programming. The word “programming” here and in similar terms (“linear programming, dynamic programming”, etc.) owes partly to a historical misunderstanding, partly to an inaccurate translation from English. In Russian it would be better to use the word “planning”. Mathematical programming has only this in common with computer programming: most mathematical programming problems that arise in practice are too cumbersome for manual calculation; they can only be solved with the help of a computer, having first compiled a program.

The birth of linear programming is considered to be 1939, when the brochure by Leonid Vitalievich Kantorovich “Mathematical methods of organizing and planning production” was published. Since the methods outlined by L.V. Kantorovich were little suitable for manual calculation, and high-speed computers did not exist at that time, L.V. Kantorovich’s work remained almost unnoticed.

Linear programming received its rebirth in the early fifties with the advent of computers. Then a general passion for linear programming began, which in turn caused the development of other branches of mathematical programming. In 1975, academician L.V. Kantorovich and American professor T. Koopmans received the Nobel Prize in Economic Sciences for their “contribution to the development of the theory and optimal use of resources in economics.”

These prizes got their name in honor of their founder - the famous chemist and inventor Alfred Nobel, they were to be awarded for scientific discoveries in the field of physics, chemistry, physiology or medicine, for literary works “reflecting human ideals”, as well as for those who "will make a significant contribution to the unity of peoples, the abolition of slavery, the reduction of the size of existing armies and the promotion of peace agreements." The prize was not intended for mathematicians. However, in 1969, the Swedish Bank, on the occasion of the 300th anniversary of its founding, established a prize in memory of A. Nobel - in economic sciences. It was awarded in 1975 to L.V. Kantorovich and T. Koopmans for the creation of a new mathematical science (called linear programming) and the application of this theory in economics.

In his autobiography submitted to the Nobel Committee, Leonid Vitalievich Kantorovich talks about the events that happened in 1939. He, a 26-year-old mathematics professor, was approached for advice by employees of the gliding trust laboratory, who needed to solve the problem of the most profitable distribution of material between machines. This problem boiled down to finding the maximum of a linear function defined on a polyhedron. The maximum of such a function was achieved at a vertex, but the number of vertices in this problem reached a billion... Therefore, a simple enumeration of vertices was not suitable. Leonid Vitalievich wrote: “it turned out that this task is not accidental. I discovered a large number of problems of a similar mathematical nature, varied in content: the best use of crop areas, choice of equipment loading, rational cutting of material, distribution of transport cargo flows... This persistently prompted me to search for an effective method for solving them.” And already in the summer of 1939, L.V. Kantorovich’s book “Mathematical methods of organizing and planning production” was put into typing, which laid the foundations of what is now called mathematical economics.

But let's go back to 1939. They say that truth is born of heresy and, alas, this is what happened with the ideas of L.V. Kantorovich in the field of economics. They were not understood at the time of their inception, were declared heresy, and his work was interrupted.

Leonid Vitalievich's concepts were rediscovered in the West soon after the war. For many years, the American economist T. Koopmans attracted the attention of mathematicians to a number of problems related to military topics. He actively contributed to organizing a mathematical team to develop these problems. As a result, it was realized that it was necessary to learn how to solve problems of finding extrema of linear functions on polyhedra defined by linear inequalities. At the suggestion of Koopmans, this branch of mathematics was called linear programming.

The American mathematician A. Danzig in 1947 developed a very effective concrete method for numerically solving linear programming problems (it was called the simplex method). The ideas of linear programming gained enormous popularity throughout the world within five or six years, and the names of Koopmans and Danzig became widely known everywhere.

Around this time, Koopmans learned that even before the war, something similar to the development of the beginnings of linear programming had already been done in distant Russia. How easy it would have been for Danzig and Koopmans to ignore this information! A small book, published in an insignificant circulation, addressed not even to economists, but to production organizers, with a minimum of mathematics, without clearly described algorithms, without proof of theorems - in short, is such a book worth taking into account... But Koopmans insists on translation and publication in the West Kantorovich's books. His name and ideas become known to everyone. Let us pay tribute to the nobility of the American scientist!

And for Leonid Vitalievich himself - how natural it would have been for him, having experienced the first formidable blows of retrogrades, to beware of the “sins” of youth, to forget about all this economics and return to mathematics. But L.V. Kantorovich continues to write mathematical works inspired by economic ideas, and also participates in specific developments in production. At the same time (simultaneously with Danzig, but without knowing his work) he developed a method, later called the simplex method. As soon as a small gap formed in the 50s and some of the forbidden became possible, he organized a group of students at the Faculty of Economics of Leningrad State University to teach methods of optimal planning. And since 1960, Leonid Vitalievich has been dealing only with economic and related mathematical problems. His contribution in this area was recognized by the Lenin Prize in 1965 (awarded to him jointly with V.S. Nemchinov and V.V. Novozhilov) and, as already mentioned, the Nobel Prize in 1975.

II .MAIN DIRECTIONS OF USING LINEAR PROGRAMMING IN MILITARY AFFAIRS.

The most common uses of linear programming in military affairs are:

Transportation problem (transport problem)

The task of distributing forces and means (distribution of forces and means of destruction among targets, distribution of forces and means of reconnaissance, etc.)

1. TRANSPORTATION PROBLEMS (TRANSPORTATION PROBLEM).

These problems are historically among the first to be solved using linear programming. Depending on the chosen efficiency criterion, transport tasks are distinguished by mileage, by cost, by time, jointly by mileage and cost criteria, with restrictions on road and transport capacity, tasks in a network setting, etc.

Let us formulate in general form the transport problem of linear programming based on the cost criterion. This task is important when time is not a determining factor in organizing transportation.

Let there be m warehouses in which some homogeneous product (fuel and lubricants, ammunition, etc.) is concentrated in quantities of i (i=1,2,…,m) units, respectively. There are n consumers of this product in quantities of b j (j=1,2,…,n) units, respectively. Based on experiments and calculations, it is known that it costs ij monetary units to deliver one unit of product from the i-th warehouse to the j-th consumer.

All c ij values ​​are constants. The listed source data is presented in Table 1.

Let us denote by x ij ³0 (i=1,2,…,m; j=1,2,…n) the quantity of product planned for delivery from the i-th warehouse to the j-th consumer. Naturally, if x ij =0, then delivery of the product from the i-th warehouse to the j-th consumer is not planned. The plan for providing all consumers is determined by the table (matrix):

Table 1.

Warehouses	Consumers				Inventory in warehouses
1
…
Need

Obviously, it is possible to offer a large number of plans (1) for providing consumers, but when choosing any of them, the following conditions must be taken into account:

(2)

(3)

Expressions (2) determine that from any warehouse you can take no more product than the stock available there. Expressions (3) mean that each consumer is fully provided with his application. According to the meaning of the task, the following condition must be met:

The last expression means that there are enough stocks in warehouses to supply all consumers.

The total cost of transportation for any selected plan (1) is determined by the expression:

(4)

The transport linear programming problem based on the cost criterion is formulated as follows.

Find such values ​​of x ij (i.e. find such a transportation plan (1)) that satisfies conditions (2), (3), under which the total cost of transportation (4) will be minimal.

For large m and n, this problem can be solved on a computer. To do this, you need to enter the initial data in Table 1 into the machine and use the developed program. For small m and n, the problem can be solved manually using general solution methods. For values ​​of m and n up to 5-6, the problem can often be solved by rough calculations, enumeration of options and logical thinking.

Task. To provide fuel and lubricants for four tank formations, there are three warehouses. The reserves of fuels and lubricants and the requirements for them are known. Determining the cost of delivering one ton of fuel and lubricants from each warehouse to any connection. All initial data are recorded in Table 2.

Formulate a linear programming problem for these conditions and determine a plan for supplying fuel and lubricants to connections in which the total cost of transporting it will be minimal.

Solution: Let us denote by x ij (i=1,2,3; j=1,2,3,4) the amount of fuel and lubricants planned for delivery from the i-th warehouse (i=1,2,3) to the j-th connection ( j=1,2,3,4).

Table 2.

Warehouses	Connections				Stocks of fuel and lubricants in warehouses
1
2
Demand for fuel and lubricants

The choice of plans depends on the stocks of fuel and lubricants in warehouses and the needs of connections for them, which is mathematically determined by the expressions:

(2 1)

(3 1)

The total costs of transporting fuels and lubricants are determined by linear expressions:

It is required to determine such values ​​of x ij (choose such a plan) satisfying expressions (2 1) and (3 1), which reduce the efficiency criterion to a minimum. This is how the linear programming problem is formulated for these conditions.

This problem can be solved by elementary calculations and reasoning.

Let us mark in the columns with asterisks the minimum values ​​for the cost of transporting one ton of fuel and lubricants. It is necessary to plan delivery to each connection from the warehouse for which this cost will be the least or close to it, but taking into account the costs of delivering fuel and lubricants to other connections. Obviously, it is advisable to deliver fuel and lubricants completely from the 1st warehouse to the 1st and 4th connections, so it is advisable to choose x 11 = 350, x 14 = 500. It is advantageous to deliver fuel entirely from the 3rd warehouse to the second compound. But then there will be large costs when delivering fuel and lubricants to the 3rd compound from the 2nd warehouse. Therefore, it is advisable to choose x 13 =50, x 33 =350, i.e. bring fuel to the 3rd connection from the 1st and 3rd warehouses, and bring 200 tons for the 2nd connection from the warehouse, x 22 = 200, x 32 = 250. The calculation results are listed in Table 2, according to which it is convenient to check the fulfillment of conditions (2 1), (3 1) by finding the sums x ij in rows and columns.

With this plan, costs will be minimal:

To compare the cost savings you can have by choosing the optimal plan, let’s consider one of the possible plans:

x 11 =350, x 12 =450, x 13 =x 14 =0, x 21 =x 22 =x 23 =0,

x 24 =300, x 31 =x 32 =0, x 33 =400, x 34 =200

With this plan, the cost of transportation will be equal to:

It is more than 1950 K min units, which is more than 30%.

The resulting optimal solution is the basis for applying an objective solution to the supply of fuel and lubricants connections, taking into account the specific situation.

2.OBJECTIVES OF OPTIMAL DISTRIBUTION OF WEAPONS.

The problems of optimal distribution of weapons are generally formulated as follows: there is a certain number of weapons and targets. It is required to distribute weapons among targets in such a way that the overall effect of use is, in a certain sense, optimal.

The defeat of the enemy is one of the important elements of combat operations. Therefore, solving problems to defeat is an important stage in planning and controlling combat operations.

There are two main types of goal allocation problems:

For weapons on defense;

For attack weapons;

The distribution of means of destruction of defense is carried out during combat operations; the identified targets and emerging conditions are unknown in advance and are largely determined by the enemy. Calculations need to be done very quickly, which is possible with modern computing tools.

The distribution of attack weapons among identified targets can be planned in advance based on calculations. However, there is no sharp boundary between these options because in both cases new goals are identified, conditions change and recalculations will need to be made.

The task of distributing weapons of destruction during full combat operations is very complex and requires taking into account a large number of factors. Some particular problems are successfully solved using linear programming.

Let's consider the first of these problems. There are m different weapons and n targets. The following assumptions are made:

The number of weapons does not exceed the number of targets m£n;

Goals have different importance, determined by the importance coefficient k j (j=1,2,…,n);

Each target cannot have more than one weapon assigned to it, that is, the maximum number of targets must be fired at;

The probabilities p ij of hitting the j-th target by the i-th weapon are known, which form a table of hit probabilities:

(5)

The hit probability table is calculated using the corresponding shooting theory formulas.

The attachment or non-assignment of the i-th weapon to the j-th target is expressed by the value x ij , which takes the value 1 when there is an attachment, and 0 when it is not.

The plan for distributing funds by purpose will be determined by the table (Table 1). In the general case, we will choose a weighted mathematical description of the number of destroyed targets, which is determined by the expression

(6)

where k j (j=1,2,…,m) are coefficients that determine the importance of goals. If the goals are of equal importance, then k 1 =k 2 =...=k m =1. With these values, expression (6) is the mathematical expectation of the number of destroyed targets. The requirement that each means be assigned to some end is determined by the expressions

(i=1,2,…,m) (7)

The conditions that no more than one weapon is assigned to each target are determined by the expression

(j=1,2,…,n) (8)

In the case of an equal sign in all expressions (8), m=n holds, otherwise m

Find integer values ​​x ij ³0 (find such a plan) satisfying conditions (7) and (8) that turn the efficiency criterion (6) to a maximum.

As you can see, this is a linear programming problem, and of a transport type. Unlike the transportation problem, values ​​of x ij are sought here that take only two possible values: 0 and 1.

For small m and n, target distribution problems can be solved by elementary calculations and reasoning.

Task. Reconnaissance detected three equivalent enemy targets. To destroy them, the command allocates three weapons. The probabilities of hitting each target by any means are known (Table 3).

Table 3.

Means of destruction				Quantity defeats
1
2
Number of targets

It is required to formulate a linear programming problem using the mathematical expectation criterion for given conditions and determine the optimal target distribution plan.

Solution. The efficiency criterion in this task according to formula (6) is determined by the expression:

Here we put k 1 =k 2 =k 3 =1, because all goals are equal. Expressions (7) and (8) for the problem conditions will look like:

(10)

(11)

Find such positive integer roots x ij of equations (10) and (11) for which the efficiency criterion (9) takes on the maximum value.

To determine the optimal plan, we find the maximum probability values ​​in the columns of Table 3 and mark them with asterisks. Obviously, the 3rd means must be assigned to the second goal (x 32 = 1). It is equally advisable to assign the first means to the 1st or 3rd goal. But since the closest value to the maximum probability for the 3rd goal is greater than for the 1st goal, it is advisable to assign the 1st means to the 1st goal (x 11 = 1), and the 2nd means to the 3rd goal (x 23 =1).

The maximum value of the mathematical expectation of the number of targets hit will be equal to:

With an optimal plan, an average of two targets will be hit. For comparison, consider the following plan: x 13 =1, x 22 =1 and x 31 =1. With this plan, the average losses will be equal to

Thus, only through optimal target distribution can the effectiveness of weapons be significantly increased (in this example, almost twofold). This fact is not only of economic importance, but also increases the efficiency of completing the task of hitting a target.

III. SIMPLEX METHOD.

Simplex method for solving linear programming problems. Let a system of n linear equations with m variables (n

(3.22)

Let us assume that among the nth-order determinants that can be composed of the coefficients, the first n columns are nonzero.

Then system (3.22) can be resolved with respect to the variables x 1 , x 2 , …, x n which, as before, will be called basic variables. As a result of solving system (3.22), the basic variables will be expressed in terms of the remaining variables x n+1, x n+2, ..., x m, called free. Number of free variables k=m-n. We have a solution to system (3.22) in the form:

(3.23)

Free variables remain arbitrary. Giving them different values, we obtain all solutions of system (3.22). We will find one of the solutions if we equate all free variables to zero. Then we get:

x 1 =b 1, x 2 =b 2, ..., x n =b n; x n+1 =x n+2 =…=x m =0

If all numbers b 1, b 1, …, b n are non-negative, then we will have a non-negative solution to system (3.22), corresponding to the corner point (vertex) of the polyhedron of non-negative solutions, this is the so-called support solution.

It is very convenient to solve a system with respect to the basic variables x 1, x 2, ..., x n, using the properties of nth order determinants. We will solve this system by sequentially eliminating the unknowns.

Let us write the coefficients of equations (3.24) in table form and enclose element a 11 in a frame

(3.27)

We will separate the coefficients from the unknown free terms by a line, and the element a 11 enclosed in a frame will be called the resolving element.

Let us write out the corresponding table for the coefficients of equations (3.26)

(3.28)

Coefficient a’ 21 is zero

From equation (3.25) it follows that

On the table (3.27) we connect the element a 2j with the resolving element with a straight line. Consider a rectangle whose diagonal is a drawn line. We will call this diagonal the first diagonal. The second diagonal is a straight line connecting the elements a 21 and a 1j, circled. As follows from formula (3.29), in order to obtain the element a 2j, it is necessary to subtract the product of the second diagonal from the product of the elements of the first diagonal. The remaining elements of the second line are calculated according to the same rule. This rule resembles the rule for calculating second-order determinants, so we will briefly call it the D-rule.

The transition from the table of coefficients (3.27) to the table (3.28), performed using the D-rule, will be called a simplex transformation or S-transformation of one table to another.

Obviously, to perform the S-transform using the first equation, it is necessary that the coefficient a 11 ¹0, otherwise the variable x 1 will be missing in the first equation.

If we now take the first equation of system (3.22) and the third and perform the same calculations, we will exclude x 1 from the third equation. Continuing the same calculations, we eliminate x 1 from all equations except the first. We will perform calculations in the following order. First we write down the table of coefficients of the system (3.22)

(3.30)

If a 11 ¹0, and we want to exclude x 1 using the first equation, then we take the element a 11 as resolving and in the table (3.30) we circle it with a frame. The row and column in which the enabling element is located are called the enabling row and enabling column, respectively. In table (3.30) this is the first row and the first column.

Applying the simplex transformation, we move on to a new table. In the new table, the elements of the permit string are rewritten without changes. All elements of the resolution column except the resolution element itself are replaced with zeros.

The remaining elements of the new table are calculated using the D-rule. For example, to calculate the element a’ ij, we connect the element a ij on the table (3.30) with the element a 11 of the line. As a result, we have the first diagonal. The second diagonal is obtained from connecting the elements a i1 and a 1j, circled on the table. By the D-rule we have

When performing simplex transformations, the diagonals shown in table (3.30) do not actually need to be carried out: they are easily identified in the mind.

Having performed the S-transform on the table (3.30), we obtain a new table

(3.31)

This table corresponds to the system of equations:

(3.32)

System (3.32) is equivalent to the original system (3.22), but in system (3.32) the variable x 1 is excluded from all equations except the first. If in table (3.31) the element a’ 22 ¹0, then, taking it as a resolving element and performing an S-transform on table (3.31), we obtain a new table. And in the system of equations corresponding to this table, the variable x 2 will be excluded from all equations except the second.

If in table (3.31) a’ 22 =0, then in the second column we will find an element that is not equal to zero and take it as resolving. Let it be a’ 12 . Then, performing a simplex transformation on table (3.31), we will eliminate x 2 from all equations except the i-th one. Continuing this way, after n transformations we will arrive at a table that has, for example, the following form.

(3.33)

Table (3.33) corresponds to a system of equations equivalent to the original system. This system of equations looks like:

(3.34)

We can assume that system (3.34) is solved with respect to the basic variables x 1, x 2, ..., x n. We will not transfer the terms corresponding to free variables to the right side for the actual solution of system (3.34) with respect to the basic variables, since in the future we will be interested in the solution where all free variables are equal to 0.

Assuming x n+1 =x n+2 =…=x m =0, we get:

If it turns out that x 1 ³0, x 2 ³0, …, x m ³0, then the set of numbers (x 1, x 2, …, x n, 0, 0, …, 0) gives a non-negative solution to the system.

Let's look at an example. Given a system of equations

It is necessary to resolve this system with respect to the variables x 1, x 2, x 3. Therefore, the free variables will be x 4, x 5, x 6. Let's write a table corresponding to this system of equations.

Let's solve the system for x 1 using the first equation. We take the first element of the first row as the resolving element, and subject the table to an S-transformation. We get a new table where the first row is rewritten, zeros are written in the first column, and the remaining elements are calculated using the D-rule.

This table corresponds to a system of equations resolved for x 1 (x 1 is included only in the first equation). It is more convenient to exclude x 2 using the third equation, since the coefficient of x 2 in the third equation is equal to one. We take it as a resolving element. Writing a new table

The system of equations corresponding to this table is resolved for x 1 and x 2 (x 1 is included only in the first equation, and x 2 only in the third).

To resolve the system relative to x 3, we take the coefficient at x 3 in the second equation as the resolving element. The new table looks like

The last table corresponds to the system solved with respect to the basis variables x 1 , x 2 , x 3 . Setting the free variables x 4 , x 5 , x 6 equal to zero, we obtain the equations:

3x 1 =-18, whence x 1 =6

3x 2 =-6, whence x 2 =2

3x 3 =3, whence x 3 =-1

The set of numbers x 1 =6, x 2 =2, x 3 =-1, x 4 =0, x 5 =0, x 6 =0 is one of the solutions to this system. It does not belong to the region of feasible solutions, since one of the coordinates x 3 is negative.

To solve a linear programming problem, it is important to be able to find non-negative (reference) solutions to a given system of equations.

The rule for choosing a resolving element when finding a non-negative solution to a system of equations.

Let a system of equations be given

(3.36)

If, when performing simplex transformations when moving from one system to another, we make sure that the resolving elements are positive, then at the last stage of resolving the system with respect to the basic variables, we will obtain a system of the form (3.34) and using formulas (3.35) we will find non-negative values ​​of the basic variables. We compose the ratios of the free terms b k to the positive elements a kj of the resolution column and among the numbers choose the smallest value. If the smallest value is achieved at k=i, then i is the number of the resolving line, and the resolving element will be a ij .

Let's consider an example of finding non-negative solutions to a system of equations.

Example. Find a non-negative solution to the system of equations

We write a table corresponding to this system

Let's try to resolve this system with respect to x 1, i.e. the variable x 1 will be considered the basic variable. The first column will be the base column. We make up the ratios of free terms to the positive elements of the first column 10/2=5; 4/7. The smallest of these numbers is 4/7. The numbers 4 and 7 are on the second line. Therefore, the resolving line will be the second line and the resolving element is the number 7. Performing a simplex transformation, we obtain a new table

This table corresponds to a system of equations resolved with respect to the basic variable x 1. Since both sides of any equation of the system can be multiplied and divided by any constant number (the system will be equivalent to the previous one), then if the rows of the table have a common factor, it can be reduced by it. The last row of the previous table has a common factor of 7; reducing by it, we get the table

Let us introduce the variable x 3 into the basis, i.e. Let's take the third column as the resolving column.

Of the two ratios 62/13 and 10/3, the second one is smaller. Therefore, the resolving element will be 3. Performing a simplex transformation, we obtain the table

We shorten the first line by 28, the second by 21

Let us introduce the variable x 2 into the basis. The resolving element will be 5. Performing the simplex transformation again, we get the table

We shorten the last line by 3

This table corresponds to a system of equations resolved with respect to the basic variables x 1 , x 2 , x 3 . The free variables here are x 4 and x 5 . Setting free variables equal to zero, we obtain:

5x 1 =12, x 1 =12/5; 5x 2 =2, x 2 =2/5; 5x 3 =18, x 3 =18/5;

Set of numbers x 1 =12/5; x 2 =2/5; x 3 =18/5; x 4 =0; x 5 =0

Gives a non-negative answer to a given system of equations. These numbers can be considered as the coordinates of the corner point (vertex) of the set (polyhedron) of feasible solutions.

LITERATURE

Malyavko K.F. "Application of mathematical methods in military

Zhurko M.D. “Mathematical methods and fundamentals of their application

in command and control of troops."

Quantum magazine No. 6, 1989.

“In 1937, V.I. Smirnov became the director of the Research Institute of Mathematics and Mechanics, created at the university in 1932, and transferred the leadership of the mathematics department L. V. Kantorovich. This new position was associated with great changes in his entire life. It all started with ordinary scientific advice to production workers.

In 1938, Kantorovich was approached by employees of the Plywood Trust, who were studying ways to increase the effective utilization of production facilities. According to the mathematical classification, they had an extremal problem - a problem to find the maximum of some simple function of a large number of variables. While consulting them, Leonid Vitalievich immediately saw (it’s simple) that classical methods of solving this problem cannot provide an effective solution. He developed and proposed a new, more effective method. His method was based on the use of special quantities (factors) that generalize well-known factors in mathematics Lagrange. But the consulting task itself was only an impetus for research. Kantorovich began to think about similar situations and soon saw numerous applications of such models and such methods in various economic and techno-economic situations. Analyzing the properties of the mentioned multipliers in these models, he drew remarkable analogies between the multipliers and economic indicators specific to specific models, a kind of “internal prices” of economic situations, even those situations in which there were no prices. It is interesting that the Leningrad economist Viktor Valentinovich Novozhilov (1892-1970) came to similar conclusions (without using mathematical models) at about the same time.

I will try to explain what a mathematician who did not even know the correct (and terrible, in my opinion) economic language could do in economics. Let's start with a practical question, one of those that Kantorovich asked himself. An enterprise can increase the output of its products while increasing its cost (that is, the cost per unit of production). Is it profitable to do this, and if so, to what extent? Soviet economic science and practice answered this question negatively: under no circumstances.

How did Kantorovich answer this question? If the market needs a given product and pays for it more than the cost of the enterprise, then increasing output is beneficial, contrary to the economic views of that time. The size of demand for a product sets its boundary (“marginal”) price and the corresponding marginal cost. Any production whose cost is less than this limit is profitable. Now this is obvious and elementary (if more complex factors are not included in the consideration).

In Soviet times, “market arguments” were contraindicated, and the word “marginal” (or “marginal”) was prohibited. In addition, the volume of production was dictated by the plan, and it was not recommended to link it with profitability. But even in such a situation, you can take care of efficiency. Let's imagine that several enterprises produce this product and their costs are different and depend on the volume of output. And in this case, there will be a boundary value of the cost that determines the effective volume of output: not a single enterprise’s cost should exceed this boundary value, and with a lower cost, the enterprise produces products only in the case when an increase in its production is impossible. This is, of course, the simplest of these questions. But already a new important indicator appears in it - the marginal cost of production. It's all about these indicators. Kantorovich found that such auxiliary indicators arise in many cases where limited resources have to be divided. They arise from the mathematical analysis of the problem, but they turn out to be very useful for the economic study of a practical situation, since they can always be given a clear (albeit unusual) economic meaning.

One of the situations considered by Kantorovich is the transport problem. In it, you need to determine where, where and how much to transport, if balanced volumes of production and consumption of a homogeneous product are given. The emerging indicators are interpreted as transport prices of the product at all points of the network, and transportation occurs only in those directions where the cost of transportation is equal to the difference between these prices at the destination and departure points, and the cost will not be less than this difference anywhere - that’s how prices are arranged. The resulting transport prices depend on the specific task. They are not related to production conditions, but they tell the economist where, given a given demand and a given set of costs, it is profitable to increase production, and where it is desirable to reduce it.

In May 1939, Kantorovich made a report at the university on his results, and with amazing efficiency, the Leningrad State University publishing house published this report as a separate brochure in the fall of the same year. Almost immediately, Kantorovich began working on a detailed presentation of his theory. This work continued during the war. […]

Leonid Vitalievich ensured that a meeting was organized in Moscow at the USSR State Planning Committee, at which he outlined his ideas, but the negative outcome of this meeting was predetermined. Kantorovich recalled: “Everything said that it was necessary to leave this work for a certain time. Their continuation was becoming dangerous - as I later learned, my assumptions were not unfounded. The option of my isolation was seriously discussed.”

Razumovsky I.V., L.V. Kantorovich: “A reasonable generalization gives more than a detailed study, in Sat.: Famous University Students: Essays on the Pets of St. Petersburg University, Volume 3, St. Petersburg, “Famous University Students,” 2005, p. 461-462.