Введение 6
Глава 1. Анализ задач линейного программирования 8
1.1 Математическая постановка задачи ЛП 8
1.2 Постановка транспортной задачи 9
1.3 Однопродуктовая транспортная модель 9
1.4 Методы построения опорного плана 12
1.5 Решение транспортной задачи методом МОДИ 16
Глава 2. Многопродуктовая транспортная задача 20
2.1 Формулировка и модель многопродуктовой транспортной задачи 20
2.2 Свойства трехиндексной задачи 26
2.3 Построение начального опорного плана 31
2.4 Метод последовательного распределения 31
2.5 Метод минимального элемента 33
2.6 Метод потенциалов для трехиндексной задачи 35
2.7 Метод простейших преобразований для трехиндексной задачи 38
2.8 Решение трёхиндексной задачи методом потенциалов 39
2.9 Решение трёхиндексной задачи методом простейших преобразований . .. 44
Глава 3. Программная реализация метода простейших преобразований для решения многопродуктовой транспортной задачи 47
3.1 Структура программы 47
3.2 Решение в Excel 51
Заключение 60
Список используемой литературы 61
Одним из самых обязательных элементов поддержания стабильного функционирования любой системы, является процесс транспортировки. Транспорт уже давно стал обыденностью, без которого тяжело представить существование человека. Если отодвинуть удобство для человека на второй план, то транспортировка чего-либо или кого-либо, затрагивает сцену торговли, ведь по имеющимся данным, сфера перевозок свидетельствуют о том, что доля транспортных затрат в цене может достигать 25 - 30%. Поэтому снижение расходов на перевозку грузов было и остается важной и актуальной задачей управления экономической системой.
Задачи транспортного типа подходят на роль задач оптимального планирования перевозки, как нельзя лучше. Подобные задачи составляют специальный класс задач линейного программирования, специфичность которого связана с особой структурой матрицы ограничений, что позволяет строить для их решения алгоритмы, более эффективные, чем стандартный симплекс-метод.
Первые упоминания оптимизации перевозок, датируют серединой 30-х годов ХХ в. и связаны с именами советских математиков А.С. Толстого и Л.В. Канторовича. Наиболее активное время изучения транспортной задачи, выпало на время жизни Хичкока, Купманса, Данцига и др. Исторически первой, и наиболее изученной транспортной моделью является классическая транспортная задача перевозки одного вида товара (однопродуктовая) и некоторые ее варианты. Для этой модели разработана развитая теория и эффективные модификации прямого и двойственного симплекс-метода, известные как метод потенциалов и венгерский метод. Дальнейшее изучение этого класса задач пошло, в основном, в направлении многоиндексных транспортных моделей, посредством которых могут описываться ситуации перевозки товара различными видами транспорта, перевозки нескольких видов товаров, динамические задачи перевозок и ряд других.
С практической точки зрения, задачи в которых присутствует более чем один вид продуктов более естественны. Поэтому представляет интерес изучение различных постановок, особенностей и методов решения многопродуктовых транспортных задач.
Одновременно с этим сложность транспортных задач постоянно увеличивается, и для их решения привлекаются компьютерные мощности. Поэтому увеличивается актуальность в разработке программных комплексов для решения транспортных задач.
Цель работы - программная реализация алгоритма решения многопродуктовой транспортной задачи.
Для достижения поставленной цели в работе решаются следующие задачи:
- изучены методы оптимизации многопродуктовой транспортной задачи;
- решена аналитически многопродуктовая транспортная задача с
использованием оптимизационных методов;
- реализован и протестирован программный модуль алгоритма.
Структура работы включает в себя введение, 3 главы, заключение, список литературы.
В первой главе рассматриваются методы оптимизации однопродуктовой транспортной задачи.
Во второй главе рассматриваются методы оптимизации многопродуктовой транспортной задачи.
В третьей главе описывается программная реализации методов оптимизации многопродуктовой транспортной задачи.
В заключении представлены выводы по проделанной работе.
В ходе выполнения выпускной квалификационной работы проведено исследование, объектом которого являлись методы определения опорного плана и методы улучшения опорного плана многопродуктовой транспортной задачи.
Целью данной выпускной квалификационной работы было решение проблемы оптимизации в многопродуктовой транспортной задаче и ее программная реализация. В ходе данной работы поставлены и выполнены следующие задачи:
- изучены и проанализированы математические методы решения задач линейного программирования транспортного типа, а также метод минимального элемента и метод последовательного распределения, метод потенциалов и метод простейших преобразований для решения многопродуктовой транспортной задачи;
- решена аналитически многопродуктовая транспортная задача с использованием оптимизационных методов;
- реализован и протестирован программный модуль на языке Python алгоритма, который составит такой план перевозок с различными грузами, при котором суммарные издержки на транспортировку будут минимальны.
В результате сделаны следующие выводы из проделанной работы:
- Для построения начального опорного плана многопродуктовой транспортной задачи можно использовать метод минимального элемента;
- Для улучшения начального опорного плана задачи можно использовать метод простейших преобразований;
- Метод простейших преобразований для решения многопродуктовой транспортной задачи возможно реализовать на языке Python.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
