Транспортные задачи закрытого типа

Содержание

 

Введение……………………………………………………………………3-4.

 

1.Транспортные задачи закрытого типа………………………………….4-13.

 

1.1.Метод СЗУ………………………………………………………........4-6.

1.2.Метод минимальной стоимости……………………………….........7-9.

1.3.Метод Фогеля……………………………………………………......10-13.

 

2.Метод потенциалов……………………………………………………..14-29

2.1.СЗУ……………………………………………………………….......14-21

2.2.Метод минимальной стоимости……………………………………21-26.

2.3.Метод Фогеля………………………………………………………..26-29.

 

Заключение……………………………………………………………………30.

 

Список используемой литературы…………………………………………..31.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Каждый из нас ежедневно, не всегда осознавая это, решает проблему: как   получить наибольший эффект, обладая ограниченными средствами. Наши   средства и ресурсы почти всегда ограничены. Жизнь была бы не такой интересной, если бы это было не так. Не сложно выиграть сражение, имея сил и средств в 10 раз больше, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, определить стратегию или программу действий. В середине XX века был создан специальный математический аппарат, помогающий составлять алгоритм действий и выявлять оптимальную стратегию, с точки зрения научного подхода. Возникает понятие линейного программирования. Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью.

В данной курсовой работе будут рассмотрены: понятие транспортной задачи, её особенности, решение транспортных задач методами северо – западного угла, минимальной стоимости, Фогеля, а так же методом потенциалов.

Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

Особенности транспортной задачи:

1.Система ограничений это система линейных уравнений.

2.Коэффициенты при переменных в системе уравнений равны 1 или 0.

3.Каждая переменная xij входит в систему ограничений только дважды: первый раз в систему ограничений по предложению, второй раз – в систему ограничений по спросу.

4.Транспортная задача является частным случаем линейного программирования(линейная целевая функция).

5.Единицы измерений всех  переменных одни и те же.

6.Весь перевозимый груз должен быть однородным.

 

 

 

1. Транспортная задача (закрытого типа)

 

1.1. Метод Северо-Западного угла.

Пусть имеется четыре поставщика =130, =100, =155, =110, которые должны доставить потребителям =130, =135, =140, =90.

Матрица транспортных расходов имеет вид:

 

Для решения задачи требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.

Решение. Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей.

Проверим это условие.

= 130 + 100 + 155 + 110 = 495,

= 130 + 135 + 140 + 90 = 495.

В нашем случае, потребность всех потребителей - 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.