Транспортные задачи закрытого типа
Содержание
Введение…………………………………………………………
1.Транспортные задачи закрытого типа………………………………….4-13.
1.1.Метод СЗУ………………………………………………………......
1.2.Метод минимальной стоимости……………………………….........
1.3.Метод Фогеля……………………………………………………....
2.Метод потенциалов…………………………………………………
2.1.СЗУ……………………………………………………………
2.2.Метод минимальной стоимости……………………………………21-26.
2.3.Метод Фогеля………………………………………………………..
Заключение……………………………………………………
Список используемой литературы…………………………………………..
Введение
Каждый из нас ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы почти всегда ограничены. Жизнь была бы не такой интересной, если бы это было не так. Не сложно выиграть сражение, имея сил и средств в 10 раз больше, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, определить стратегию или программу действий. В середине XX века был создан специальный математический аппарат, помогающий составлять алгоритм действий и выявлять оптимальную стратегию, с точки зрения научного подхода. Возникает понятие линейного программирования. Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью.
В данной курсовой работе будут рассмотрены: понятие транспортной задачи, её особенности, решение транспортных задач методами северо – западного угла, минимальной стоимости, Фогеля, а так же методом потенциалов.
Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.
Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.
Особенности транспортной задачи:
1.Система ограничений это система линейных уравнений.
2.Коэффициенты при переменных в системе уравнений равны 1 или 0.
3.Каждая переменная xij входит в систему ограничений только дважды: первый раз в систему ограничений по предложению, второй раз – в систему ограничений по спросу.
4.Транспортная задача является частным случаем линейного программирования(линейная целевая функция).
5.Единицы измерений всех переменных одни и те же.
6.Весь перевозимый груз должен быть однородным.
1. Транспортная задача (закрытого типа)
1.1. Метод Северо-Западного угла.
Пусть имеется четыре поставщика =130, =100, =155, =110, которые должны доставить потребителям =130, =135, =140, =90.
Матрица транспортных расходов имеет вид:
Для решения задачи требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.
Решение. Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей.
Проверим это условие.
В нашем случае, потребность всех потребителей - 495 единиц продукции равна запасам всех поставщиков.
Приступаем к решению Методом СЗУ.
Суть метода: в данном методе запасы очередного по номеру поставщика используются для обеспечения запросов очередных по номеру потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла, поэтому и называется метод северо-западного угла.
Метод состоит из ряда однотипных шагов, на каждом из которых, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или один потребитель.
1. На основе условия задачи составляем таблицу 1 и приступаем к решению по алгоритму, описанному выше.
Таблица 1.
2. Запасы поставщика , составляют 130 единиц продукции. Потребность потребителя составляет 130 единиц продукции. От поставщика поставляем потребителю 130 единиц продукции, что полностью удовлетворяет запросы потребителя. Исключаем столбец 1 таблицы из дальнейшего рассмотрения.
Далее рассмотрим запасы поставщика , составляют 100 единиц продукции. Потребность потребителя составляет 135 единиц продукции. От поставщика к потребителю будем доставлять 100 единиц продукции. Разместим в ячейку значение равное 100.
Мы полностью израсходовали запасы поставщика. Вычеркиваем вторую строку таблицы 2, то есть исключаем ее из дальнейшего рассмотрения.
Таблица 2
Далее выполняем действия по алгоритму, аналогично предыдущим шагам, заполняя таблицу 3.
Таблица 3
3.) Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
1.2.Метод минимальной стоимости
Суть метода. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
1. Согласно условию задачи составим таблицу.
Таблица 4
2. Заметим, что в методе Северо-западного угла цены перевозок вообще не учитывались. В данном методе учитываются.
Минимальный элемент матрицы тарифов находится в ячейке и равен единице, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика к потребителю наиболее рентабельный.
Разместим в ячейку значение равное 90 .
Мы полностью удовлетворили потребность потребителя .Исключаем столбец 4 из таблицы 5.
Таблица 5
3. Минимальный элемент матрицы тарифов находится в ячейке , делаем поставку в данную ячейку.
Запасы поставщика A1 составляют 40 единиц продукции. Потребность потребителя составляет 140 единиц продукции.
Мы полностью израсходовали запасы поставщика . Вычеркиваем первую строку таблицы 6, т.е. исключаем ее из дальнейшего рассмотрения.
Таблица 6
4.Далее выполняем все действия аналогично.
И получаем таблицу 7 вида:
Таблица 7
Количество базисных ячеек равно семи, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
Общие затраты на доставку всей продукции, для начального решения, составляют 995 ден.ед.
1.3.Метод Фогеля
Условия задачи у нас сохранились, следовательно, начальное решение у нас окажется, оптимальным и метод потенциалов мы использовать не будем.
Суть метода. Метод Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы, и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек.
1. На основе условий задачи составляем таблицу 8.
Таблица 8
2. В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Таблица 9
Вторым действием произведем аналогичную операцию для столбца.
Таблица 10
3. Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает первый столбец. В данном столбце выберем ячейку , как обладающую наименьшим тарифом.
Мы выбираем данную ячейку, так как стоимость доставки единицы продукции от поставщика к потребителю , как минимум, на 2 ден.ед. меньше чем от остальных поставщиков к потребителю .
Таблица 11
4. Далее производим аналогичные действия над строками и столбцами, т.е. находим в каждой строке разность между двумя ячейками с наименьшими тарифами, а в каждом столбце разность.
Таблица 12
Из полученных разностей выберем наибольшую.
Столбец один обладает наибольшей разностью. В данном столбце выберем ячейку , как обладающую наименьшим тарифом.
Заполняем данную ячейку.
5. Далее выполняем аналогичные операции, над оставшимися строками и столбцами.
В результате получаем таблицу вида:
Таблица 13
Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей, т.е. нашли начальное решение.
Общие затраты на доставку всей продукции составляют 1005 ден. ед.
Составив три разных опорных плана тремя разными методами (СЗУ, min стоимости, Фогеля) для транспортных задач закрытого типа, можем заметить, что метод Фогеля наиболее выгодный, так как транспортные расходы будут минимальными. И действительно, проанализировав все три суммы, в каждой из транспортной задачи, заметим, что суммы существенно отличаются друг от друга, так как в методе Фогеля учитываются разницы между минимальными тарифами, то есть в той или иной степени производится анализ, метод же СЗУ более соответствует определенному алгоритму, так же мы не анализируем минимальные значения строк и столбцов(как в др. методах) и при занесении значений в клетку транспортной таблицы этого не учитываем.
2.Метод потенциалов
Метод потенциалов применяется для задач с невырожденным опорным планом. Поэтому необходимо каждый раз (и даже после перепланировки) проверять ОП на вырожденность.
Согласно данному методу мы приписываем каждому поставщику и потребителю потенциал.
Один (любой) из выбранных потенциалов задаем произвольно, то есть равен произвольному числу, которое обозначаем U.
Для того, чтобы определить потенциал клеток транспортной таблицы, используем заполненные клетки.
Условие:
Далее для пустых клеток определяем разность:
Если все разности неотрицательны, то ОП является оптимальным и тогда, записываем матрицу поставок соответствующую этому ОП, и рассчитываем стоимость перевозок.
2.1.Метод северо-западного угла
1. Рассмотрим маршрут доставки от поставщика к потребителю .
Запасы поставщика составляют 130 единиц продукции. Разместим в ячейку значение равное 95.
Мы полностью удовлетворили потребность потребителя, исключаем его из рассмотрения.
Таблица 14.
2. Далее заполняем транспортную таблицу 15 и 16 по алгоритму СЗУ, учитывая фиктивного потребителя.
Таблица 15
Таблица 16
Таблица 17
Итак, мы полностью израсходовали запасы поставщиков и удовлетворили запросы потребителей.
3. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться , где - количество строк в таблице, - количество столбцов в таблице. Количество базисных ячеек равно 7, а требуется, чтобы было 8.
Таблица 18
Количество задействованных маршрутов равно 8, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
4. Рассчитаем сумму.
Но наша задача стоит в использовании метода потенциалов, итак найдем для данной транспортной таблицы потенциалы.
5. Как уже говорилось, первое значение мы берем произвольно.
Допустим .
Таблица 19
Таблица 20
6. Далее работаем с пустыми ячейками.
По данной формуле, находим оценки свободных ячеек :
7. Вносим их в транспортную таблицу 21.
Таблица 21
Среди оценок свободных ячеек есть отрицательные, следовательно, решение не является оптимальным.
8. Сделаем перепланировку .
Таблица 22
9. Записываем таблицу с новыми маршрутами.
Таблица 23
10. Найдем снова потенциалы и поработаем с пустыми клетками.
Таблица 24
Среди оценок свободных ячеек есть отрицательные, следовательно, решение не является оптимальным.
11. Строим новый маршрут в таблице 25.
Таблица 25
12. Далее производим аналогичные действия и повторяем шаги до получения оптимального плана.
В итоге мы получим транспортную таблицу вида.
Таблица 26
Sсзу = 850 ден. ед.
2.2.Метод минимальной стоимости
Найдем начальное решение методом минимального элемента. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
1. В нашем случае, поставщик может дать потребителю товара больше, чем ему требуется, значит, для решения задачи вводим фиктивного потребителя.
Условия задачи остаются прежними. Составим таблицу, которая будет иметь вид:
Таблица 27
2. Таблицу заполняем согласно алгоритму метода минимальной стоимости для задачи закрытого типа, учитывая фиктивного потребителя.
Таблица28
Мы нашли начальное решение, т.е. израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.
3. Для решения задачи методом потенциалов нужно подсчитать потенциалы для каждого поставщика и потребителя.
Примем и посчитаем все потенциалы. Далее дадим оценки свободных ячеек.
Получим таблицу 29 вида:
Таблица 29
После занесения значений в таблицу видим, что есть отрицательные значения в ячейках. Делаем перепланировку.
Таблица 30
4. Делаем перерасчет в ячейках данного маршрута и получаем таблицу вида:
Таблица 31
5. Пересчитаем снова потенциалы и произведем оценку свободных ячеек, чтобы проверить план на оптимальность.
Таблица 32
6. Так как в ячейках есть отрицательные значения, делаем перепланировку.
Таблица 33
Получаем таблицу 34 вида:
Таблица 34
7. Далее снова пересчитываем потенциалы, чтобы проверить оптимальность данного плана.
Получаем таблицу 35 вида:
Таблица 35
Все оценки свободных ячеек неотрицательные, следовательно, найдено оптимальное решение.
Можем найти транспортные расходы:
Smin = 2 40 + 1 90 + 1 95 + 4 5 + 3 25 + 4 95 + 0 35 + 1 110 = 850
Общие затраты на доставку всей продукции, для оптимального решения, составляют 850 ден. ед.
2.3.Метод Фогеля
Найдем начальное решение методом Фогеля. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется не оптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 495 единиц продукции равна запасам всех поставщиков.
1. Согласно условию задачи составим таблицу 36.
Таблица 36
2. Решаем задачу методом Фогеля и получим транспортную таблицу 37.
Таблица 37
3. Для решения задачи найдем потенциалы и оценки свободных ячеек.
Таблица 38
Так как у нас имеются отрицательные значения в ячейках, то следует сделать перепланировку.
Таблица 39
Далее получим таблицу 40 вида:
Таблица 40
4. Далее вновь проверим новый план на оптимальность.
Таблица 41
Sф = 850
Общие затраты на доставку всей продукции, для начального решения, составляют 850 ден. ед.
Заключение
Необходимость решения задач линейного программирования на современных предприятиях очевидна. Построение и решение транспортных задач позволяет, в свою очередь, решать различные технико-экономические и экономические производственные задачи, будь то проблема оптимальной загрузки станка и раскройки стального листа или анализ межотраслевого баланса и оценки темпов роста экономики страны в целом.
В данной курсовой работе были систематизированы теоретические положения по теме применения методов линейного программирования при решении задач, рассмотрена сущность задач линейного программирования, выявлены основные методы решения задач линейного программирования.
Список используемой литературы
1. Лекционный материал доцента кафедры «Прикладная математика» Иванова Андрея Николаевича.
2. Литвак Б. Г. Разработка управленческого решения: Учебник. - 3-е изд., испр. - М.: Дело 2002.
3. Орлов А. И. Теория принятия решений: Учеб. пособие.- М.: Издательство «Март», 2004.