Программные продукты и системы

Введение. Задача о распределении ресурсов известна давно, и ее можно считать полностью решенной в случае выпуклой целевой функции. Решение сводится к простому принципу: максимум средств нужно вкладывать в тот ресурс, который в данный момент является наи- более оптимальным в зависимости от условий задачи. Главный вопрос состоит в том, как на- ходить этот ресурс, то есть вершину многогранника, задаваемого системой ограничений. Если целевая функция задачи линейна, то она по определению выпукла, следовательно, решение задачи известно. В современном мире часто встречаются задачи, которые несколько отличаются по своей формулировке от данной. Так, в работе [1] исследована задача оптимального распределения дискретных ресурсов между несколькими проектами, где критерий эффективности задан в табличной форме. Особенность рассматриваемой проблемы заключается в том, что традиционные методы математического программирования с аналитической целевой функцией оказываются неприменимыми из-за дискретного характера распределяемых ресурсов и табличного задания функции эффективности. Авторами предложен оригинальный подход, основанный на методах целочисленного линейного программирования, который позволяет преобразовать табличные данные  в аналитическую целевую функцию путем введения дополнительных параметров и ограничений. Однако он имеет существенное ограничение для задач динамического прогнозирования, так как модель предполагает фиксированные входные данные (матрицу прибыли и ограничения), что делает ее неприменимой в условиях изменяющихся во времени параметров.

В исследовании [2] авторами рассмотрены ключевые аспекты использования линейного программирования, включая формулировку це- левой функции и ограничений, для решения  задач оптимального распределения ресурсов. Кроме того, приведены практические приме- ры задач распределения, такие как о рюкзаке  и о назначениях. Особое внимание уделено классическим методам решения задач линейного программирования – симплекс-методу и методам искусственного базиса. Продемонстрированы возможности применения линейного программирования в различных областях, например,  в планировании производства, в управлении запасами и в транспортной логистике. Однако авторы рассматривают только задачи с линейными зависимостями и детерминированными параметрами, что существенно сужает область применения предложенных методов. В реальных условиях часто встречаются нелинейные зависимости, стохастические параметры и динамически изменяющиеся ограничения, которые требуют использования более сложных методов оптимизации.

В [3] исследована задача синтеза оптимального управления для динамических систем, описываемых моделью Лотки – Вольтерры,  в окрестности особой точки типа «седло». Авторами разработан метод расчета кусочно-постоянного управления, минимизирующего расход ресурсов при заданных ограничениях на величину управляющего воздействия. Особое внимание уделено преобразованию исходной нелинейной задачи в задачу математического программирования с линейным функционалом и нелинейными ограничениями, для решения которой применен метод последовательного линейного программирования. На конкретных примерах продемонстрированы различные структуры управления (1–2 ступени) и рассчитаны оптимальные моменты переключения для случаев как с фиксированным, так и с адаптивным фазовым параметром целевой траектории. Однако в работе не учитывается динамический баланс ресурсов между конкурирующими подсистемами. Метод оптимизирует управление для одной системы, но не решает задачу конфликтного распределения ограниченных ресур- сов.

В работе [4] рассмотрено применение транс- портной задачи линейного программирования для оптимального распределения пожарных ресурсов между складами и пунктами потребления. Автором разработана математическая модель, минимизирующая стоимость перевозок при заданных ограничениях на запасы и потребности. Особое внимание уделено практической реализации модели в MS Excel с ис- пользованием встроенного инструмента «Поиск решения» и симплекс-метода. Предложенная модель рассматривает статическую постановку задачи с фиксированными параметрами спроса и предложения, что ограничивает ее применение для задач динамического распределения ресурсов, где потребности и доступные запасы могут изменяться во времени.

Из зарубежных исследований следует отметить работу [5]. В статье описана модель оптимального распределения человеческих ресурсов (на примере менеджеров проектов) в инженерных проектах с использованием методов многоуровневого нечеткого комплексного оценивания компетенций менеджеров и приоритезации проектов, жадного алгоритма для началь- ного распределения ресурсов, линейного программирования для оптимизации стартовых времен проектов и минимизации общих трудовых затрат. Предложенный подход не учитывает изменения в ходе проекта (например, задержки, изменение приоритетов или появление новых задач), что критично для динамической среды, модель также не предусматривает корректировку распределения ресурсов в реальном времени при изменении условий.

В [6] исследуется линейная задача о распределении ресурсов. Хотя изначальная статическая задача является ее частным случаем, специфика приводит к сложностям при прямом применении традиционных методов. Особенностью рассмотренной в статье [6] задачи является простота нахождения вершин. Предложен алгоритм, основанный на принципе LIFO, который значительно упрощает и облегчает процесс обхода вершин симплекса. Задача о прогно- зировании ресурсов изучена слабо, поэтому  в дальнейших исследованиях будет рассмотрена динамическая задача прогнозирования с изменяемыми параметрами, для решения которой требуется разработать алгоритм на основе принципа продолжения траекторий. Применение этого метода сводит задачу прогнозирования к последовательности задач линейного программирования, что позволяет оптимизировать процессы в различных сферах деятельности.

Таким образом, основными задачами данного исследования являются формулировка задачи прогнозирования, разработка алгоритма для ее решения и рассмотрение применения принципа продолжения траекторий в контексте управления ресурсами, а также создание концепции оптимального решения задачи. На- учная новизна исследования заключается в разработке динамического алгоритма прогнозирования, сочетающего принцип продолжения траекторий с методом LIFO для оптимизации поиска решений, что обеспечивает адаптивное управление ресурсами в условиях изменяющихся параметров.

Метод исследования

Следует отметить, что принцип продолжения траекторий – это процедура, которая исследует изменение структуры оптимального решения задачи при увеличении отрезка, на котором она определена. Процедура строится следующим образом: каждой точке оптимального решения ставится в соответствие локальная вариационная задача, которая формируется, если  в результате увеличения отрезка времени вдоль траектории возникает новая нерегулярность. На основе ее решения определяются новые  режимы и моменты переключения, которые встраиваются в исследуемый момент в структуру оптимальной траектории. Устанавливается, что построенная таким образом траектория удовлетворяет локальному оптимуму.

Задача прогнозирования может быть сформулирована в следующем виде [7]:

                               (1)

при этом должны быть выполнены ограничения:

                                        (2)

Ai £ xi(t) £ Bi,                                          (3)

где Ci, Ai, Bi, M – некоторые заданные числа; x(t) – функция, численно характеризующая количество ресурсов.

Выражения (1)–(3) представляют собой обыч- ную задачу квазистатической оптимизации. Для ее решения сведем ее к стандартной задаче оптимального управления. Так, следуя [7], введем новые переменные:

и

где 

Тогда уравнения (1)–(3) формально сводятся к следующей задаче:

                                     (4)

Ai £ yi(t)ui £ Bi,                                        (5)

где ai – некоторые действительные числа.

Это стандартная задача оптимального уп- равления, для ее решения в источнике [8] предложен эффективный алгоритм, которым и следует воспользоваться в предлагаемой работе.

Решение задачи с помощью принципа  продолжения траекторий

Суть принципа продолжения траекторий  в данном случае заключается в том, что существующая задача оптимального управления заменяется последовательностью задач линейного программирования. Решение всегда лежит в одной из вершин многогранника и пребывает там некоторое время, хотя сама вершина постоянно перемещается. Эту вершину находим  в начальный момент с использованием правила LIFO. В некоторый новый момент времени ограничения перестанут выполняться, то есть произойдет уход из вершины. Следовательно, нужно найти новые вершины и повторить процедуру.

В монографии [7] показано, что в момент времени t = 0 решение задано (1)–(3) и будет лежать в одной из вершин многогранника (4), (5), причем оптимальное значение управления будет постоянным на некотором промежутке времени.

Поэтому необходимо рассмотреть следующую задачу математического программирования:

Ai £ yi(0)ui £ Bi.

Решением будут являться числа u¢11, u¢12, …, u¢1n, u¢1i, причем они остаются постоянными, пока выполняются ограничения

                                    (6)

Ai £ yi(t)u1i £ Bi.                                      (7)

Таким образом, на некотором отрезке [0, t1) решение задачи задается функциями

u11(t) º const, u12(t) º const, u1n(t) º const [5], где t1 – первый момент времени, когда нарушаются ограничения (6), (7).

В момент времени t1 возникает следующая задача математического программирования:

Ai £ yi(t1)ui £ Bi.

Таким образом, получаем набор чисел u21, u22, …, u2n, которые являются решением этой задачи и будут оставаться постоянными до момента времени t2.

Работа данного алгоритма продолжается до тех пор, пока время окончания прогнозирования, то есть время T, не будет достигнуто.

Ключевым моментом в этом алгоритме является поиск решения задачи линейного программирования на каждом шаге. Специфика  и преимущество состоят в очень простом на- хождении вершин многогранника. На каждом этапе решение задачи математического программирования будет строиться с помощью алгоритма, описанного в [8].

Необходимо отметить аспекты научной новизны предложенного алгоритма:

– динамическая адаптивность: в отличие от классических статических методов, алгоритм позволяет оперативно пересматривать стратегию распределения ресурсов в ответ на изменения внешних условий, что особенно актуально для задач с нестационарными параметрами;

– применение принципа продолжения траекторий: метод сводит задачу прогнозирования к последовательности задач линейного программирования, что упрощает вычислительную сложность и обеспечивает устойчивость решений на каждом временном интервале;

– использование правила LIFO: алгоритм значительно ускоряет поиск вершин многогранника решений, что снижает вычислительные затраты и повышает эффективность в реальном времени;

– модульная реализация: предложенная структура программы с четким разделением функций позволяет легко масштабировать и адаптировать метод для различных прикладных задач.

Представленная на рисунке 1 схема иллюстрирует модульную структуру программы, разработанной для решения задачи оптимизации распределения ресурсов. Программа состоит из нескольких взаимосвязанных модулей, каждый из которых выполняет определенную функцию в процессе вычислений. Опишем подробнее каждый модуль и его роли в общем процессе.

Основной модуль: получение входных данных, которые могут включать параметры ресурсов, ограничения и целевые функции. На их основе формируется начальное распределение ресурсов, которое служит отправной точкой для дальнейших вычислений.

Модуль 2: корректировка распределения ресурсов с учетом временных параметров и на- хождение нового распределения ресурсов. Происходит анализ текущего распределения и внесение корректировок на основе новых данных или изменений в условиях задачи.

Модуль 3: создание набора вершин, которые могут представлять собой состояния системы или точки в пространстве решений. Начальная вершина выбирается для начала процесса оптимизации, что может быть важно для сходимости алгоритма.

Модуль 4: оценка оптимальности текущего решения, выбор следующей вершины для анализа и новой по правилу LIFO.

Модуль 5: проведение расчетов и вывод результатов. Выполняются основные вычисления, связанные с оптимизацией распределения ресурсов. Результаты расчетов, включая оптимальное распределение и соответствующие зна- чения целевой функции, выводятся для анализа.

Реализован алгоритм динамического прогнозирования оптимального распределения ресурсов на основе принципа продолжения траекторий и правила LIFO (http://www.swsys.ru/ uploaded/image/2025-4/Kokovkin.html).

Программа написана на Python и демонстрирует основной подход, описанный в статье.

В программе отражены ключевые аспекты алгоритма из статьи, хотя в реальной реализации потребуются более сложные модели динамики ресурсов и дополнительные оптимизации для работы с большими системами.

Обсуждение и анализ результатов

На определенных этапах времени некоторые ресурсы могут приносить минимальные потери [9], а другие будут наиболее оптимальными. Анализ алгоритма показал, что максимум средств нужно вкладывать именно в тот, который в данный момент является наиболее оптимальным на некотором промежутке времени в зависимости от условий задачи (рис. 2). Заметим, что в момент времени t = 0 таким является ресурс 1, поэтому максимум средств необходимо вкладывать именно в него, при t = 1 –  в ресурс 2 и т.д.

В вопросах прогнозирования для построения задачи о распределении ресурсов ключевой является проблема, аналогичная линейной задаче о распределении ресурсов. Классические методы, применяемые к задаче о распределении ресурсов, достаточно изучены, а в ли- нейных функциях весь ресурс следует сосредоточить на одном объекте [10]. Анализ литературы показал, что статический процесс был изучен довольно глубоко, но прогнозирование закупок в динамической системе исследовано недостаточно [11].

Таким образом, можно сделать вывод, что  в каждой вершине многогранника находится решение задачи. Оптимум находится в вершине и будет устойчив до тех пор, пока не нарушаются ограничения, иначе – переход на другую вершину.

Заключение

Предложенный алгоритм был апробирован на ряде стандартных задач базового уровня.  Результаты демонстрируют, что оптимальная стратегия прогнозирования требует концентрации ресурсов в направлениях, обеспечивающих максимальную эффективность в каждый текущий момент при минимальном распределении остаточных средств. Подобные задачи находят широкое практическое применение  в различных технических сферах.

Таким образом, при возникновении задачи об оптимальном прогнозировании и управлениями ресурсами использование данного алгоритма позволяет переориентироваться при изменяющихся условиях (перейти в другую вершину многогранника) и получить наилучший оптимум.

Список литературы

1. Баркалов С.А., Глушков А.Ю., Моисеев С.И. Решение задачи распределения ресурсов дискретного типа методами линейного программирования // Вестн. ЮУрГУ. Сер.: Компьютерные технологии, управление, радиоэлектроника. 2020. Т. 20. № 2. С. 26–35. doi: 10.14529/ctcr200203.

2. Шаназаров Б.М., Эргешов С., Хувджеров Б. Улучшение эффективности распределения ресурсов с помощью линейного программирования // Вестн. науки. 2024. Т. 1. № 5. С. 533–537.

3. Алесова И.М. Оптимальное управление динамическими системами, описываемыми моделью лотки-вольтерры // Современная наука: актуальные проблемы теории и практики. Сер.: Естественные и технич. науки. 2020. № 1. С. 57–61.

4. Толпекина М.Е. Применение задач линейного программирования при разработке модели распределения ресурсов // Пожарная и техносферная безопасность: проблемы и пути совершенствования. 2020. № 3. С. 478–481.

5. Huiling Z., Liu Y. Linear programming analysis of the optimal allocation problem of human resources in engineering projects. AMNS, 2024, vol. 9, no. 1, pp. 1–18. doi: 10.2478/amns-2024-3061.

6. Коковкин Д.А. Об оптимальном управлении запасами торгового предприятия // Инженерные технологии. 2023. № 1. С. 45–49.

7. Афанасьев А.П. Продолжение траекторий в оптимальном управлении // Тр. ИСА РАН. 2005. Т. 17. 208 с.

8. Боровик В.В., Коковкин Д.А., Смирнова П.М. Алгоритм прогнозирования оптимального управления запасами на предприятии // Вестн. ТвГТУ. Сер. Технич. науки. 2024. № 3. С. 96–101. doi: 10.46573/2658-5030-2024-3-96-101.

9. Боровик В.В., Смирнова П.М. Принятие решений в нечетких условиях // Инженерные технологии. 2023. № 1. С. 72–83.

10. Якубова У.Ш., Парпиева Н.Т., Мирходжаева Н.Ш. Некоторые применения графического и симплексного методов решения задач линейного программирования // Бюллетень науки и практики. 2022. Т. 8. № 4. С. 490–498.

11. Соколова А.А. Моделирование процессов симплекс-методом // Анализ проблем внедрения результатов инновационных исследований: сб. статей Междунар. науч.-практич. конф. 2022. С. 88–91.

References

1. Barkalov, S.A., Glushkov, A.Yu., Moiseev, S.I. (2020) ‘Solving the problem of resource allocation of a discrete type by linear programming methods’, Bull. of the South Ural State University. Ser. Comput. Technology, Automatic Control, Radio Electronics, 20(2), pp. 26–35 (in Russ.). doi: 10.14529/ctcr200203.

2. Shanazarov, B.M., Ergeshov, S., Khuvjerov, B. (2024) ‘Improving the efficiency of resource allocation using linear programming’, Bull. of Sci., 1(5), pp. 533–537 (in Russ.).

3. Alesova, I.M. (2020) ‘Optimal control of dynamic systems described by the Lotka-Volterra model’, Modern Sci.: Actual Problems of Theory and Pract. Ser.: Natural and Tech. Sci., (1), pp. 57–61 (in Russ.).

4. Tolpekina, M.E. (2020) ‘The applying of linear programming in the formation of resource distribution model’, Fire and Technosphere Safety: Problems and Ways of Improvement, (3), pp. 478–481 (in Russ.).

5. Huiling, Z., Liu, Y. (2024) ‘Linear programming analysis of the optimal allocation problem of human resources in engineering projects’, AMNS, 9(1), pp. 1–18. doi: 10.2478/amns-2024-3061.

6. Kokovkin, D.A. (2023) ‘Principles of trajectory continuation in the inventory management system of industrial enterprises’, Engineering Technologies, (1), pp. 45–49 (in Russ.).

7. Afanasyev, A.P. (2005) ‘Continuation of trajectories in optimal control’, Proc. ISA RAS, 17, 208 p. (in Russ.).

8. Borovik, V.V., Kokovkin, D.A., Smirnova, P.M. (2024) ‘Forecasting algorithm for optimal inventory management in the enterprise’, Bull. of TvSTU. Ser: Tech. Sci., (3), pp. 96–101 (in Russ.). doi: 10.46573/2658-5030-2024-3-96-101.

9. Borovik, V.V., Smirnova, P.M. (2023) ‘Decision-making in fuzzy conditions’, Engineering Technologies, (1), pp. 72–83 (in Russ.).

10. Yakubova, U.S., Parpieva, N.T., Mirkhodzhaeva, N.S. (2022) ‘Some applications of graphical and simplex methods for solving linear programming problems ‘, Bull. of Sci. and Pract., 8(4), pp. 490–498 (in Russ.).

11. Sokolova, A.A. (2022) ‘Simplex method process modeling’, Proc. Int. Sci.-Pract. Conf. Analysis of Challenges in Implementing Innovative Research Results, pp. 88–91 (in Russ.).