
Тип работы:	Предмет:	Язык работы:

Разработка программного обеспечения для решения проблемы целочисленности в многоиндексной транспортной задаче

Работа №	140056
Тип работы	Бакалаврская работа
Предмет	математика и информатика
Объем работы	63
Год сдачи	2023
Стоимость	4700 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	24

Не подходит работа?

Узнай цену на написание

Содержание

Аннотация 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 установлена пригодность прототипа для использования при тестировании разрабатываемого приложения.
Разработано программное обеспечение, позволяющее решить проблему целочисленности. Проведено тестирование разработанного ПО. В частности, при тестировании генератора данных поставщиков установлено, что нестабильность времени расчета имеет место, но практически не оказывает существенного влияния на работоспособность приложения. С использованием разработанного ПО выполнен вычислительный эксперимент по исследованию влияния размера задачи на время расчета.

Литература

1. Афраймович Л. Г. Потоковые методы решения многоиндексных задач
транспортного типа. Диссертация на соискание ученой степени доктора физико-математических наук [Электронный ресурс]. URL:
http://www.ccas.ru/avtorefe/0002d.pdf. (дата обращения: 30.04.2023).
2. Библиотека времени Chrono [Электронный ресурс]. URL: https://inf- w.ru/?p=8305 (дата обращения: 30.04.2023).
3. Википедия. Свободная энциклопедия. algorithm (C++) [Электронный
ресурс]. URL: https://ru.wikipedia.org/wiki/Algorithm_(C%2B%2B) (дата
обращения: 30.04.2023).
4. Википедия. Свободная энциклопедия. fstream [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Fstream (дата обращения: 30.04.2023).
5. Википедия. Свободная энциклопедия. Iostream [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Iostream (дата обращения: 30.04.2023).
6. Википедия. Свободная энциклопедия. time.h [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Time.h (дата обращения: 30.04.2023).
7. Википедия. Свободная энциклопедия. vector (C++) [Электронный
ресурс]. URL: https://ru.wikipedia.org/wiki/Vector_(C%2B%2B) (дата
обращения: 30.04.2023).
8. Подробный разбор симплекс-метода [Электронный ресурс]. URL: https://habr.com/ru/post/474286/ (дата обращения: 30.04.2023).
9. Прилуцкий М.Х. Распределение однородного ресурса в иерархических системах древовидной структуры // Труды международной конференции «Идентификация систем и задачи управления SICPRO’2000». - М.: ИПУ им. В.А. Трапезникова РАН. 2000. С. 2038-2049.
10. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. Учебное пособие. - М.: Физмалит. 2007
11. Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. Т. 16. № 3. С. 70-76.
12. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании // Доклады АН СССР. 1979. Т. 244. № 5. С. 1093-1096.
13. Briskorn D., Drexl A., Spieksma F.C.R. Round robin tournaments and three index assignment // 4OR: a Quarterly Journal of Operations Research. 2010. V. 8. P. 365-374.
14. Chrono на C ++ [Электронный ресурс]. URL:
https/www.geeksforgeeks.org/chrono-in-c/ (дата обращения: 30.04.2023).
15. Dantzig G.B. Linear programming and extensions. - Princeton, NJ: Princeton University Press. 1963...20