# Abstract

The problem of optimizing the distribution of an integer resource (funds) by tasks (activities, goals) is investigated. The methods investigating this problem relate to the field of combinatorial optimization, namely, to the tasks of assigning goals. The known methods for solving this problem are numerical, selective, approximate, require a large number of iterations, do not involve checking the conditions for the existence of an integer solution, in some cases they can produce a solution not only far from optimal, but also violating the range of acceptable values of variables. The purpose of this work is to develop a new analytical method for solving the problem of the distribution of integer resources by the method of indefinite Lagrange multipliers. To do this, the allocated resources are represented as the sum of the integer and fractional parts of the number. The conditions are formulated and proved when the fractional parts of the variables of the solution of the problem are zero, that is, it is an integer. A theorem (criterion for the existence of an integer solution) is proved, which determines the necessary and sufficient conditions under which the solution of the problem exists and is found according to the algorithm developed in the article. Such conditions include the homogeneity of resources, as well as additional conditions (restrictions on integers and positivity of additional derived formula conditions of the problem). It is shown that the obtained solution of the problem corresponds to the maximum of the objective function. An algorithm for finding an integer solution to the problem of resource allocation by the method of indeterminate Lagrange multipliers is developed and a specific example is analyzed. The method described in this article can be used for the allocation of resources in industrial production, agriculture, organizational management systems, educational process, solving issues of target allocation in military affairs, building information systems, techno sphere security, emergency response, creating systems for the protection of objects and alarm systems. In this case, it is necessary to adapt it to the problems and tasks under consideration. It can also be used for the distribution of life-supporting resources: food, clothing, heat, electricity, gas, water supply.

# Full Text

Введение Одним из важных классов задач комбинаторной оптимизации является задача о назначении целей. Первоначально задача рассматривалась для военных приложений как задача определения оптимального распределения комплекта различного вооружения (средств поражения) по целям для нанесения максимального ущерба противнику [1-7]. В настоящее время область применения таких задач расширилась за счет моделей распределения ресурсов в экономике [8], системах организационного управления [9, 10], планировании производства продукции [11], банковской сфере [12]. Особое внимание распределению ресурсов уделяется при проектном управлении. В статье [13] для решения данной проблемы используется система рейтингов по рабочим задачам и компетенциям. Во многих задачах о назначении целей имеется требование целочисленности переменных. Например, количество ракет, самолетов-перехватчиков, сотрудников, компьютеров. Требование целочисленности переменных существенно усложняет процесс нахождения оптимального решения [14, 15]. Округление нецелочисленных переменных до целых чисел может привести не только к заметным потерям эффективности целочисленного плана, но и к недопустимому решению. Для решения задачи целочисленного распределения средств применяется метод максимального относительного элемента [14]. Данный метод основан на упорядоченном переборе возможных решений и является численным, приближенным. Проблема при его использовании заключается в том, что точного целочисленного решения задачи может не быть, а на поиск наиболее близкого к нему приближенному решению будут тратиться значительные вычислительные ресурсы. Многие задачи оптимизации распределения нецелочисленных ресурсов для непрерывных функций решаются методом неопределенных множителей Лагранжа [9]. Важным и новым является распространение данного метода на решение задач дискретной оптимизации. Целью данной работы является решение задачи распределения целочисленных ресурсов (задачи дискретной оптимизации) методом неопределенных множителей Лагранжа. 1. Постановка задачи Проблема распределения ресурсов (средств) для решения набора заданных задач заключается в следующем. Имеется n задач и m средств для их решения. Заданы важности и вероятности выполнения j-й задачи каждым средством ( ). Обозначим через - количество средств, назначенных для выполнения j-й задачи. Пусть , где - целая часть числа , - дробная часть. Требуется найти такое распределение ресурсов , при котором вероятность выполнения всех задач будет максимальна. В этом случае максимизируемая целевая функция будет иметь вид (1) Коэффициент - это важность выполнения j-й задачи, - нормировка . Для получения критерия целочисленности решения задачи (1) разложим множитель в ряд, ограничиваясь двумя членами, получим При таком разложении абсолютная погрешность вычисления не превосходит величины В самом деле, абсолютная погрешность не превосходит первого отброшенного члена, т.е. члена При максимальном значении вероятности p = 1 покажем, что Имеем т.е. - это верно. Относительная погрешность не превосходит величины т.е. 4,2 %, что близко к повышенной точности. Погрешность в вычислении функции составляет т.е. Система ограничений задачи распределения ресурсов имеет вид (2) 2. Метод решения Для нахождения экстремума функции (1) при ограничениях (2) запишем функцию Лагранжа: (3) Последние два ограничения системы (2) здесь использовать не будем. Они будут учтены в дальнейшем. Найдем частные производные по , , и приравняем их к нулю. Имеем (4) (5) (6) Из формулы (4) для получаем (7) Из формулы (5) при находим Отсюда (8) Из формулы (7) имеем Отсюда с учетом формулы (8) получаем и Следовательно, (9) Допустим, что . Предположим, что В этом случае тогда и только тогда, когда (10) Отсюда следует, что уравнение (10) выполняется тогда и только тогда, когда все равны. Это означает однородность средств. Тогда из формулы (9) следует, что Определим условие выполнения равенства Подставим из уравнения (8) и из уравнения (9) в первое уравнение системы (2), получим (11) Для краткости введем следующие обозначения: в формуле (11) коэффициент при обозначим через a, второе слагаемое - через b, третье - c. Тогда (12) Из уравнения (12) следует, что тогда и только тогда, когда (13) Таким образом, условие (13) является необходимым условием целочисленности ресурсов. При из уравнения (11) имеем (14) При равенство (14) превращается в равенство (15) При выполнении условия с учетом равенства (15) получаем, что . Для целочисленности необходимо и достаточно, чтобы выражение в скобках в уравнении (15) было кратно n. При выполнении однородности из формулы (8) и (15) для имеем (16) Если - целое положительное число, то для положительной целочисленности необходимо и достаточно, чтобы было целым при Итак, точка , координаты которой вычисляются по формулам (15), (16), при этом в (15) выражение в скобках кратно n и второе слагаемое в формуле (16) является целым числом при , является стационарной точкой с целыми положительными координатами. Достаточное условие экстремума сводится к анализу второго дифференциала функции Лагранжа (3) для найденной точки P при условии, что связаны уравнением Второй дифференциал для функции Лагранжа будет иметь вид (17) при этом Поскольку в точке Р имеется максимум. Таким образом, имеем следующее утверждение. Теорема. Для того чтобы задача целераспределения, сводящаяся к максимизации целевой функции (1) при ограничениях (2), имела положительное целочисленное решение, необходимо и достаточно, чтобы выполнялись следующие условия: 1) однородность средств, т.е. все вероятности должны быть равны; 2) если , то и , вычисленное по формуле (15), должно быть целым положительным; 3) выражение ( ) должно быть целым. В самом деле, пусть выполнены условия 1-3. Тогда из условия 1 следует, что все равны, т.е. выполняется равенство (12) и при выполнении условия 3 из с учетом уравнения (12) следует, что . Тогда отсюда вытекает равенство (15), и с учетом выполнения условия 2 получаем, что - целое положительное число, откуда с учетом выполнения условия 3 имеем - целое положительное число. Из равенства (17) следует, что данное решение максимизирует функцию (1) при ограничениях (2). Докажем теорему в обратную сторону. Пусть - целое положительное решение, максимизирующее функцию (1) при ограничениях (2). Тогда при представлении в виде , где - целая, - дробная части числа, имеем , но тогда выполняется равенство (12) и все равны . Значит, выполняется условие 1. Пусть . Тогда, очевидно, вычисленное по формуле (15), будет целым положительным, т.е. выполняется условие 2. При этом будет вычисляться по формуле (16), а так как и - целые, то выполняется условие 3. 3. Результаты и их обсуждение Рассмотрим практическую реализацию разработанного метода. Приведем алгоритм поиска целочисленного решения задачи распределения средств и разберем конкретный пример. Основные этапы алгоритма решения данной задачи заключаются в следующем. 1. Все вероятности должны быть одинаковы. Если это не так, то производится их корректировка. При невозможности такой корректировки положительного целочисленного решения не будет. 2. Ищется . Пусть это будет . 3. Для должно быть известно, что это целое положительное число, т.е. и - целое положительное число. 4. Значение вычисляется по формуле (15). 5. По формуле (16) находятся значения , которые будут целыми положительными. Рассмотрим следующий пример на выполнение вычислений по разработанному алгоритму. Пусть n = 3; m = 11; p = 0,2; По формулам (15) и (16) находим положительное целочисленное решение: , максимизирующее соответствующую целевую функцию (1), которая при данных значениях: Таким образом, алгоритм позволяет аналитически найти решение задачи распределения ресурсов. Заключение В статье разработан новый метод решения оптимизационной задачи распределения целочисленного ресурса. Доказана теорема (критерий существования целочисленного решения), определяющая необходимые и достаточные условия, при выполнении которых решение задачи существует и находится по разработанному в статье алгоритму. К таким условиям относится однородность ресурсов (средств), а также дополнительные условия (ограничения на целочисленность и положительность дополнительных условий задачи). Разработан алгоритм поиска целочисленного решения задачи распределения ресурсов методом неопределенных множителей Лагранжа и разобран конкретный пример.

# About the authors

### A. V Ganicheva

Tver State Agricultural Academy

### A. V Ganichev

Tver State Technical University

# References

1. Абчук В.А., Матвейчук Ф.А., Томашевский Л.П. Справочник по исследованию операций. - М.: Воениздат, 1979. - 368 с.
2. Берзин Е.А. Оптимальное распределение ресурсов и теория игр. - М.: Радио и связь, 1983. - 216 с.
3. Буравлев А.И. Об оценке влияния системы управления огнем на эффективность поражения целей // Вооружение и экономика. - 2012. - № 1 (17). - С. 25-29.
4. Математическая модель процесса управления средствами ПВО / Д.А. Григорьев, Т.Н. Масленникова, А.Н. Пифтанкин, А.В. Половинкина // Автоматизация процессов управления. - 2019. - № 2 (56). - С. 15-22.
5. Кежаев В.А., Анисимов В.Г., Анисимов Е.Г. Обоснование решений в задачах целераспределения с использованием инновационных технологий дискретного программирования // Известия Российской академии ракетных и артиллерийских наук. - 2012. - № 2 (72). - С. 97-103.
6. Письменная В.А., Якутин А.В. Повышение эффективности решения задачи целераспределения в системах воздушно-космической обороны // Вестник Концерна ВКО «Алмаз - Антей». - 2017. - № 1. - С. 76-81.
7. Юдин А.В. Целераспределение неоднородных средств подавления методом двух функций // Актуальные проблемы науки и техники: материалы IV Междунар. конкурса науч.-исслед. работ, г. Уфа, 10 апреля 2021 г. - Уфа, 2021. - С. 11-15.
8. Славянов А.С. Анализ и практическое применение моделей распределения ресурсов // Бюллетень науки и практики. - 2018. - Т. 4, № 9. - С. 228-244.
9. Ганичева А.В. Оптимальное решение и оценка полезности организационных вопросов // Ярославский педагогический вестник. - 2011. - № 3(2). - С. 53.
10. Menshikh V.V., Samorokovsky A.F., Avsentev O.S. Models of resource allocation optimization when solving the control problems in organizational systems // Journal of Physics: Conference Series. - 2018. - Vol. 973, no 1. - P. 12-40.
11. Mathematical Model for Production Plan Optimization / S. Rezig, W. Ezzeddine, S. Turki, N. Rezg // A Case Study of Discrete Event Systems Mathematics. - 2020. - No. 8 (6). - P. 955.
12. Filippova A.S. Economic-mathematical modeling of a multi-criteria optimization management problem of a retail unit of a commercial bank Perm University Herald // Economy. - 2019. - No 14(1). - P. 93-109.
13. Bakanova A.P., Shikov A.N. The Method of Employee Competencies Management Based on the Ontological Approach // CEUR Workshop Proceedings. - 2020. - No 2590. - P. 1-9.
14. Соболевский В.А. К оценке точности задачи целераспределения средств поражения // Военная мысль. - 2016. - № 8. - С. 32-43.
15. Kataev A.V., Kataeva T.M., Makarova E.L. Project Management: Mathematical Models of Optimal Executors’ Appointment for Project Works // Известия Саратовского университета. Новая сер. Сер. Экономика. Управление. Право. - 2016. - № 3. - С. 294-299.

# Statistics

#### Views

Abstract - 63

PDF (Russian) - 38

### Refbacks

• There are currently no refbacks.

## This website uses cookies

You consent to our cookies if you continue to use our website.