Решение задачи распределения ресурсов дискретного типа методами линейного программирования
Автор: Баркалов Сергей Алексеевич, Глушков Александр Юрьевич, Моисеев Сергей Игоревич
Рубрика: Информатика и вычислительная техника
Статья в выпуске: 2 т.20, 2020 года.
Бесплатный доступ
Введение. При планировании проектов, комплексов работ часто приходится решать задачи распределительного типа, связанные с оптимальным распределением ресурсов. Существующие методы решения подобных задач предполагают наличие аналитической зависимости непрерывного типа между объемами распределяемого ресурса и показателями эффективности. Однако оптимизационные задачи становятся не применимыми, когда ресурс дискретный и зависимости задаются табличными способами. Цель исследования. Разработать математическую модель решения задачи оптимального распределения ресурсов дискретного типа с таблично заданными критериями оптимальности методами линейного программирования. Описать методику численного решения задачи с использованием вычислительной техники. Материалы и методы. Решить поставленную задачу удается путем формирования аналитической зависимости кусочно-непрерывного типа между объемом распределенного ресурса и критерием оптимальности. Это позволяет сформулировать оптимизационную задачу, решаемую методами математического программирования. Построить аналитическую целевую функцию удается с помощью введения дополнительных параметров и ограничений. Численное решение задачи можно получить как с помощью математических пакетов прикладных программ, таких как, например, Mathcad, так и с использованием систем программирования. В работе описана методика решения задачи в среде MS Excel с использованием надстройки «Поиск решений». Результаты. Разработана математическая модель решения дискретной распределительной задачи для критерия оптимальности, заданного таблично, методами целочисленного линейного программирования. Описана методика численного решения в среде MS Excel. Заключение. Ранее подобные задачи решались методами динамического программирования, что более затруднительно в вычислительном плане. Проведенные вычислительные эксперименты показали высокую точность вычислений по модели и устойчивость к изменению исходных данных.
Ресурсы, оптимизация, распределение, линейное программирование, математическое моделирование
Короткий адрес: https://sciup.org/147233755
IDR: 147233755 | УДК: 338.242 | DOI: 10.14529/ctcr200203
Solution of the discrete resources distribution problem by methods of linear programming
Introduction. When planning projects, work packages, one often has to solve distribution-type problems associated with the optimal allocation of resources. Existing methods for solving such problems suggest the presence of an analytical dependence of a continuous type between the volumes of the distributed resource and performance indicators. However, optimization problems become inapplicable when the resource is discrete and dependencies are specified in tabular ways. Aim. To develop a mathematical model for solving the problem of the optimal distribution of resources of a discrete type with table-defined optimality criteria using linear programming methods. Describe the method of numerical solution of the problem using computer technology. Materials and methods. It is possible to solve the problem by forming an analytical dependence of a piecewise-continuous type between the volume of the distributed resource and the optimality criterion. This allows us to formulate an optimization problem solved by mathematical programming methods. It is possible to construct an analytical objective function by introducing additional parameters and restrictions. A numerical solution to the problem can be obtained both using mathematical packages of applied programs, such as, for example, “Mathcad”, and using programming systems. The paper describes the methodology for solving problems in the MS Excel environment using the add-on “Solver”. Results. A mathematical model is developed for solving a discrete distribution problem for the optimality criterion given in a table by integer linear programming methods. The technique of numerical solution in the MS Excel environment is described. Conclusion. Previously, such problems were solved by dynamic programming methods, which is more difficult in the computational plan. Conducted computational experiments showed high accuracy of model calculations and resistance to changes in the source data.
Список литературы Решение задачи распределения ресурсов дискретного типа методами линейного программирования
- Соколов, А.В. Методы оптимальных решений. В 2 т. Т. 1: Общие положения. Математическое программирование / А.В. Соколов, В.В. Токарев. - М.: Физматлит, 2012. - 564 с.
- Юдин, Д.Б. Задачи и методы линейного программирования. Математические основы и практические задачи/Д.Б. Юдин, Е.Г. Гольштейн. - М. : Либроком, 2016. - 322 с.
- Карзаева, Н.Н. Математическое программирование в экономике: учеб.пособие /Н.Н. Кар-заева. - М. : Финансы и статистика, 2010. - 240 с.
- Карманов, В.Г. Математическое программирование / В.Г. Карманов. - М. : Физматлит, 2008. - 264 с.
- Кремер, Н. Ш. Исследование операций в экономике: учеб. для вузов / Н.Ш. Кремер. -3-е изд., перераб. и доп. -М. : Изд-во Юрайт, 2013. - 438 с.
- Баркалов, С.А. Математические методы и модели в управлении и их реализация в MS Excel / С.А. Баркалов, С.И. Моисеев, В.Л. Порядина. - Воронеж: Воронежский ГАСУ, 2015. - 265 с.
- Математические и инструментальные методы экономики: учеб. пособие / П.В. Акинин и др. - М. : КноРус, 2016. - 151 с. - (Для бакалавров).
- Моисеев, С.И. Математические методы и модели в экономике: учеб. пособие / С.И. Моисеев, А.В. Обуховский. - Изд. 2-е, испр. - Воронеж: АОНО ВПО «Ин-т менеджмента, маркетинга и финансов», 2009. - 160 с.
- Барлаков, С.А. Модели и методы в управлении и экономике с применением информационных технологий [Электронный ресурс]: учеб. пособие / С.А. Барлаков, С.И. Моисеев, В.Л. Порядина. - СПб.: Интермедия, 2017. - 264 с.
- Fourer, R. AMPL: A Modelling Language for Mathematical Programming / R. Fourer, D.M. Gay, B.W. Kernighan. - 2nd ed. - Duxbury, 2002. - http://ampl.com/resources/the-ampl-book/chapterdownloads/
- Симаков, Е.Е. Методика решения математических задач с помощью программирования и компьютерного моделирования /Е.Е. Симаков //Информатизация образования и науки. - 2016. -№ 4 (32). - С. 126-140.
- Тарасов, В.Н. Математическое программирование: теория, алгоритмы, программы: учеб. пособие / В.Н. Тарасов, Н.Ф. Бахареева. - Самара: Поволжский гос. ун-т телекоммуникаций и информатики, 2007. - 222 с.
- Киселев, Н.Г. Применение математического пакета MATHCAD для решения задач линейного программирования / Н.Г. Киселев // Системы управления, технические системы: устойчивость, стабилизация, пути и методы исследования: материалы науч.-практ. семинара молодых ученых и студентов. - 2017. - С. 169-172.
- Решение оптимизационных задач на языке программирования VISUAL С# с использованием математических пакетов /И.А. Гурин, Н.А. Спирин, В.В. Лавров, М.В. Бякова //Моделирование и наукоемкие информационные технологии в технических и социально-экономических системах: тр. IVВсерос. науч.-практ. конф. с междунар. участием. - 2016. - С. 70-74.
- Леоненков, А.В. Решение оптимизационных задач в среде MS Excel / А.В. Леоненков. -СПб.: БХВ-Петербург, 2005. - 704 с.
- Аверина, Т.А. Модели распределения ресурсов в программе антикризисного управления / Т.А. Аверина, С.А. Баркалов, О.Л. Смольянова // Управление развитием крупномасштабных систем MLSD'2019: материалы двенадцатой междунар. конф. Науч. электрон. изд. / под общ. ред. С.Н. Васильева, А.Д. Цвиркуна. - 2019. - С. 1162-1164. DOI: 10.1109/MLSD.2019.8911048
