A.E. Aksenov – Engineer, Deputy Head of Department,
JSC «Typhoon» (Kaluga)
E-mail: rtsys@mail.ru
A.M. Donetskov − Ph.D. (Eng.), Associate Professor,
«Information Systems and Networks» Department, Kaluga Branch of the Bauman MSTU
E-mail: dam1358@mail.ru
A.S. Nikolaev – Ph.D. (Eng.), Associate Professor,
«Information Systems and Networks» Department, Kaluga Branch of the Bauman MSTU
E-mail: nikolanta@yandex.ru
Matching tasks occupy a special place in the design and construction of electronic devices. Matching problems are divided into problems of finding the maximum matching in bipartite and arbitrary graphs. Setting a task of finding the maximum matching in a bipartite graph. Let a bipartite graph be given G X YU=< , , > , where X is the left set of vertices, Y is the right set of vertices, U is the set of edges. The problem is to find in G a subset of edges such that no two of them have a common vertex. Two edges are called independent if they do not have a common vertex. Matching − many independent edges. Matching with the largest number of edges - maximum matching. There is an Edmonds algorithm that allows you to find the exact solution in time O(n3), where n is the number of vertices. In the paper, the author considers the approach to finding a solution to this problem using the MS Excel tool «Solver». To find a solution, an auxiliary table (decision table) of the same dimension was used as the original model. Elements of the new table can take only two values 0 or 1. In addition, to find a solution, restrictions are introduced that the sum of the elements of the decision table by rows and columns should not exceed 1. A cell containing the formula of sum of the product of the two matrix was used as a criterion for optimality. The author also considered the problem of finding matching the maximum weight in a weighted bipartite graph; another name for this problem is the optimal assignment problem. Setting a task: set a bipartite complete graph G X YUW U=< , , , ( ) > is given, where X is the left vertex set, Y is the right vertex set, W U( ) is the edge weight, it is necessary to find the perfect matching of the maximum weight. To solve this problem, the same approach was used as for the previous task. The original approach to solving the problem of finding the maximum matching in an arbitrary graph deserves special attention. It was proposed to use the incident matrix to set the source model. To find the maximum matching using MS Excel «Solver», it was proposed to use the solution column. The values of this column can be 0 or 1, and the dimension is equal to the number of edges of the graph. One limitation is that the sum of the product of the current incident matrix column and the decision column should not exceed 1. The optimality criterion for this problem is the sum of the elements of the decision column. The author describes the use of the proposed approach on the example of packaging in containers. The paper describes in detail the approach of finding matching the maximum weight in a weighted arbitrary graph. To solve this problem, the approach described earlier with the following additions was used. Additionally, a column of weights of edges of the same dimension as the column of solutions is introduced. The optimality criterion is the sum of the products of the column of solutions and the column of weights of edges. Using concrete examples, the author has shown that MS Excel is a universal tool for solving a wide range of optimization problems.
- Aksenov A.E., Donetskov A.M., Nikolaev A.S. Microsoft Excel kak instrument resheniya kombinatornykh zadach. Elektromagnitnye volny i elektronnye sistemy. 2019. Т. 24. № 3. S. 40−44. DOI: 10.18127/j15604128-201903-07 (in Russian).
- Ankundinov V,Kh., Maksimov A.V. Kineticheskaya model′ geksapoda. Ch. II. Bikvaterionnye modeli. Elektromagnitnye volny i elektronnye sistemy. 2019. Т. 24. № 3. С. 25-32. DOI: 10.18127/j15604128-201903-05 (in Russian).
- Borsuk N.A., Derugina E.O., Latsin S.M., Ryabtsev Ya.V. Adaptivnaya sistema upravleniya pitaniem semeistva mobil′nykh bortovykh vychislitel′nykh kompleksov. Elektromagnitnye volny i elektronnye sistemy. 2019. Т. 24. № 3. С. 55-61. DOI: 10.18127/j15604128201903-09 (in Russian).
- http://www.math.nsc.ru/LBRT/k4/LOR/lor_Theme6.pdf (25.03.2020).
- https://algorithmica.org/ru/matching (25.03.2020).
- Baryshev A.V., Fedotova E.L. K voprosy ispol′zovaniya nadstroiki Excel «Poisk resheniya» v zadachakh lineinogo programmirovaniya. Internet-zhurnal «Naukovedenie». 2015. Т. 7. № 3. http://naukovedenie.ru/PDF/54TVN315.pdf (25.03.2020) (in Russian).
- https://au.cdkrot.me/get/spbau-2020/term3-dm (26.03.2020).
- http://pages.cs.wisc.edu/~shuchi/courses/787-F09/scribe-notes/lec5.pdf (25.03.2020).
- http://www-math.mit.edu/~goemans/18433S09/matching-notes.pdf (25.03.2020).
- http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf (25.03.2020).