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

Министерство транспорта Российской Федерации

Федеральное агентство железнодорожного транспорта

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Дальневосточный государственный университет путей сообщения»

 
 
 
 
Кафедра «Прикладная математика»

 
 
 
 
Курсовая работа по дисциплине

«Методы принятия управленческих решений»

 
МЕТОДЫ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ

 
Вариант № 7

 
 
 
 
Выполнила: студентка группы Ц16 (1 курс, 2 семестр),

 

                      направления 080200 «Менеджмент»,

 

                      специальности 080200.62 «Менеджмент»,

 

                       Гриднева Юлия Ивановна

Проверил:     преподаватель кафедры «Прикладная математика» ДВГУПС                       

Кадура Елена Вячеславовна

 
 
РЕЙТИНГОВЫЙ БАЛЛ за курсовую работу:_______

ОТМЕТКА за курсовую работу:                      _______

 
 
 
 
 
 
Хабаровск

2014

 

 
Введение

Одна из наиболее распространённых задач математического программирования — транспортная задача. Транспортная задача — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости(достижение минимума затрат на перевозку) или расстояний и критерий времени(затрачивается минимум времени на перевозку).

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из груза , а в маленькие клетки — соответствующие тарифы .

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

1. Весь груз от –го поставщика должен быть выведен полностью

 

2. Ограничения по спросу

-й потребитель должен быть полностью обеспечен грузом. 
 

3. Суммарное предложение равно суммарному спросу.

 

4. Условие неотрицательных поставок

 

Математическая модель транспортной задачи имеет вид

 

 

 
Каноническая задача линейного программирования

Условие 1.3 называется балансовым, а транспортная задача с этим условием – сбалансированной или задачей закрытого типа. Если 
,то транспортная задача называется несьалансированной или задачей открытого типа.

Матрицей транспортных расходов(издержек) называется матрица вида:

 

Множество значений переменных , удовлетворяющих ограничениям транспортной задачи, называются планом перевозок или планом транспортной задачи.

План удобно записывать в виде матрицы перевозок вида:

 

Представим все исходные данные транспортной задачи в таблице, называемой транспортной таблицей

 
 

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

1. Система ограничений системы линейных уравнений
2. Коэффициенты при переменных в системе линейных уравнений равны 1 или 0
3. Каждая переменная входит в систему ограничений дважды: один раз в систему ограничений по предложению (1.1); второй раз в систему ограничений по спросу (1.2)
4. Транспортная задача является частным случаем задачи линейного программирования
5. Единицы измерений всех переменных одинаковы
6. Весь перевозимый груз должен быть однородным

Каждому разбиению переменных на базисные и свободные соответствует единая матрица перевозок. Нулевые поставки – пустые клетки. Полученная матрица перевозок называется опорным планом перевозок или базисным распределением поставок.

Методы нахождения опорных планов для транспортной задачи:

• Метод северо-западного цикла
• Метод минимальной стоимости
• Метод Фогеля

Метод северо-западного цикла

На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность .

Метод минимальной стоимости

Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.

Алгоритм:

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

2. Проверяются строки поставщиков на наличие строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.

3. Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Метод Фогеля

1. В каждой строке находим клетку с минимальной транспортной издержкой и ближайшей к ней транспортной издержкой.
2. Находим разность и её записываем сбоку транспортной таблицы(для каждой строки своя разность)
3. В столбце находим клетку с минимальной транспортной издержкой и ближайшей минимальной транспортной издержкой. Находим их разность и записываем её внизу таблицы(для каждого столбца своя разность)
4. Из найденных разностей находим наибольшую, если их несколько, то выбираем любую. Эта разность определяет тот столбец или ту строку, в ячейке которого (й) будем делать поставку.
5. В клетку снаименьшей пранспортной издержкой делаем поставку указанного выше столбца или строки. И вычеркиваем оставшиеся клетки в зависимости от ограничений.
6. Для оставшейся таблицы процедуру повторяем до тех пор, пока не будут заполнены все клетки.

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

Если число базисных переменных равно рангу , то опорный план невырожденный. Если число заполненных клеток равно , то опорный план невырожденный.

На каждом этапе после осуществления поставки, мы вычеркиваем либо строку, либо столбец; но может оказаться так, что на каком-либо этапе вычеркивается одновременно и строка и столбец (момент вырождения опорного плана). Чтобы избежать данной ситуации необходимо вычеркнуть либо строку. Либо столбец. Например, мы вычеркиваем строку, тогда в следующем этапе  оставленной таблицы делаем нулевую поставку и вычеркиваем столбец. Данную клетку с нулевой поставкой будем считать заполненной, а не пустой.

Вырожденнсоть опорного плана имеет значение для его оптимизации

Оптимальным планом перевозок называется план, стоимость которого минимальна.

Транспортная задача решается в 2 этапа:

1. Построение опорного плана (невырожденного)
2. Оптимизация опорного плана (медот потенциалов)

Алгоритм метода потенциалов:

1. Рассчитать начальный план перевозоки и выделить базисные клетки. Вычислить значение целевой функции.
2. Проверить опорный план на вырожденность. Если опорный план невырожденный, то применяем метод потенциала.
3. Рассчитать значения потенциалов. Положить . Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения
4. Для свободных клеток рассчитать оценки . Если все , тонайдено оптимальное решение.
5. Если , то опорный план неоптимальный. Улучшение плана происходит в результате перераспределения поставок

Перепланировка опорного плана:

1. Выбираем клетку с минимальной разностью, если минимальный разностей несколько, то выбираем любую из них.
2. Из выбранной пустой клетки строим контур, остальные вершины которого должны лежать в заполненных клетках (линии контура только горизонтальные или вертикальные). При построении контура звенья могут пересекаться.
3. Вершина в пустой клетке имеет знак «+». Знаки остальных вершин чередуются.
4. Среди отрицательных вершин выбираем наименьшую поставку. Затем эту поставку прибавляем к поставам с положительной вершиной и отнимаем от поставок с отрицательной вершиной. Выбранная минимальная поставка к клетке зануляется и считается пустой клеткой, а в пустую клетку записываем минимальную поставку.
5. Проверяем полученный план по ограничениям и на вырожденность. Полученный новый опорный план необходимо проверять на оптимальность. Переходим к первому этапу метода потенциала. Эту процедуру повторяем до тех пор, пока все окажутся неотрицательными.
6. Пересчитать целевую функцию.

Часть 1. Транспортная модель закрытого типа

1.1 Условие задачи

Дано поставщиков , предложение каждого -го поставщика составляет единиц, .

Дано потребителей спрос каждого -го потребителя составляет единиц, .

Дана стоимость перевозки единицы товара от -го поставщика к -му потребителю.

Требуется составить план перевозок от -го поставщика к -му потребителю с минимальной стоимостью и рассчитать стоимость плана перевозок.

Обозначим – количество груза, перевозимое от -го поставщика к -му потребителю. Тогда общая стоимость перевозок равна:

 

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

, ,

 
Матрица перевозок (план перевозок) имеет вид:

 
, ,

 
,      

,        

,      

,        

 

Представлю исходные данные транспортной задачи в виде таблицы 1

 
Таблица 1

Исходные данные транспортной задачи

 

 
1.2. Построение  опорных планов транспортной  модели

Проверим необходимое и достаточное условие разрешимости задачи:

 

 

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

1.2.1. Построение  опорного плана методом северо-западного  угла

Используя метод северо-западного угла, построю первый опорный план транспортной задачи

План начинается заполняться с верхнего левого угла. В ячейку 11 делаю поставку 95, затем закрываю 1 столбец, т.к. потребности полностью удовлетворены. (Таблица 2)

 
 
 
 
 
 
 
 
Таблица 2

 

Выбираю ячейку 12 и делаю поставку 10, закрываю 1 строку, т.к. предложение исчерпано. (Таблица 3)

Таблица 3

 

 
Выбираю ячейку 22 и делаю поставку 70, закрываю 2 строку, т.к. предложение полностью исчерпано (Таблица 4)

 
 
 
 
 
 
 
 
 
Таблица 4

 

 
Выбираю ячейку 32 и делаю поставку 80, закрываю 2 столбец, т.к. потребности полностью удовлетворены. (Таблица 5)

 
Таблица 5

 

 
Выбираю ячейку 33 и делаю поставку 135, закрываю 3 столбец, т.к. потребности полностью удовлетворены. (Таблица 6)

 
 
 
 
 
 
 
 
Таблица 6

 

 
Выбираю ячейку 34 и делаю поставку 25. Затем делаю поставку 85 в ячейку 44.(Таблица 7)

Таблица 7

 
Матрица перевозок:

 

 
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.