Аннотация 2
Abstract 3
Введение 5
1 Анализ транспортных задач линейного программирования 7
1.1 Описание транспортной задачи 7
1.2 Многоиндексные задачи линейного программирования 8
1.3 Методы решения транспортных задач 10
2 Проектирование ПО для решения проблемы целочисленности в
многоиндексной транспортной задаче 15
2.1 Постановка задачи и выбор средств разработки 15
2.2 Разработка алгоритмов решения задачи 15
2.3 Исследование прототипа приложения в MS Excel 18
3 Разработка ПО для решения проблемы целочисленности в
многоиндексной транспортной задаче 28
3.1 Разработка приложения 28
3.2 Тестирование приложения 38
3.3 Экспериментальное исследование решения проблемы
целочисленности в многоиндексной транспортной задаче 44
Заключение 46
Список используемой литературы и используемых источников 47
Приложение A Полный код программы 49
Решение проблемы целочисленности в многоиндексной транспортной задаче является важным современным направлением исследований, результаты которого востребованы во многих областях практической деятельности. Доктор физико-математических наук Л.Г. Афраймович в работе «Потоковые методы решения многоиндексных задач транспортного типа» определяет область прикладного применения таких задач следующим образом: «Существует широкий класс прикладных задач, формализуемых в виде многоиндексных задач (целочисленного) линейного программирования транспортного типа. Примерами таких задач являются задачи распределения ресурсов в иерархических системах: задача объемно-календарного
планирования, задача формирования портфеля заказов, задача переработки газового конденсата, задача распределения мощностей каналов передачи данных, транспортная задача с промежуточными пунктами. [9]. Многоиндексные задачи транспортного типа возникают также в области статистики и в смежной области защиты статистических данных [17], [11] в задаче целочисленного сбалансирования многоиндексных матриц» [1].
В деятельности предприятия АО «ВАЗИНТЕРСЕРВИС» большую роль играет логистика транспортных поставок запасных частей к автомобилям. Применение методов решения многоиндексных транспортных задач с ограничением на получение целочисленного решения в этом случае обеспечивает оптимальные логистические решения, что потенциально может позволить сэкономить на транспортных расходах. Этим определяется актуальность работы...
В ходе анализа предметной области рассмотрены основные виды транспортных задач и определены их отличительные черты в классе задач линейного программирования. Изучены виды и области применения многоиндексных транспортных задач. В результате выполнено описание транспортной задачи, изучены методы решения многоиндексных транспортных задач, определены исследуемые методы - симплекс метод и метод Гомори.
По результатам предварительного исследования проблемы целочисленности многоиндексных транспортных задач на прототипе программного обеспечения в MS Excel установлено, что при отсутствии дополнительных ограничений проблема целочисленности многоиндексной транспортной задачи не возникает. Определены правила формирования дополнительных ограничений, при которых проблема целочисленности в решении многоиндексной транспортной задачи имеет место.
В ходе проектирования ПО для решения проблемы целочисленности в многоиндексной транспортной задаче выполнена постановка задачи на разработку, выбор средств разработки, разработан алгоритм решения задачи, исследован прототипа приложения в MS Excel. В результате моделирования работы приложения и генераторов исходных данных на прототипе в программе MS Excel установлена пригодность прототипа для использования при тестировании разрабатываемого приложения.
Разработано программное обеспечение, позволяющее решить проблему целочисленности. Проведено тестирование разработанного ПО. В частности, при тестировании генератора данных поставщиков установлено, что нестабильность времени расчета имеет место, но практически не оказывает существенного влияния на работоспособность приложения. С использованием разработанного ПО выполнен вычислительный эксперимент по исследованию влияния размера задачи на время расчета.
