Данный метод состоит в следующем:
1. На каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
2. Находят max Δcij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.
Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям. Данный метод в ряде задач приводит к оптимальному плану.
ГЛАВА 2. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Постановка задачи
Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный распределения товаров с минимальными затратами.
Дано:
Склад №1=200 шт.
Склад №2=250шт.
Склад №3=200шт.
Требуется доставить штук:
Магазин "Терабайт"= 190шт.
Магазин "Лидер"= 100 шт.
Магазин "Эксперт" = 120 шт.
Магазин "Ока-сервис" =110 шт.
"Владимирский рынок" =130 шт.
Сетка тарифов:
Построим для данной задачи матрицу тарифов, по которой будет происходить поиск оптимального плана распределения товаров между магазинами. Для более удобного решения задачи обозначим магазины и товары переменными:
Магазины:
Магазин "Терабайт"= B1
Магазин "Лидер"= B2
Магазин "Эксперт" = B3
Магазин "Ока-сервис" = B4
"Владимирский рынок" = B5
Товары:
Склад №1= A1
Склад №2 = A2
Склад №3= A3
Тогда матрица будет выглядеть так:
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Потребности |
Следуя данной модели можно найти опорный план и решение поставленной задачи.
2.2 Нахождение первоначального плана методом северо-западного угла
Используя построенную матрицу тарифов найдём оптимальный опорный план методом северо-западного угла.
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Потреб. |
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | 28 [190] | 27 [10] | ||||
| A2 | 26 [90] | 27 [120] | 32 [40] | |||
| A3 | 31 [70] | 34 [130] | ||||
| Потреб. |
Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([A1;B1]). Полностью удовлетворяем потребность данного тарифа. Исключаем первый столбец. Дальше смотрим если запасы ещё остались, рассматриваем рядом стоящий тариф ([A2;B1]), если нет, то исключаем и первую верхнею строк. И рассматриваем следующий тариф по аналогичной схеме. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F=28*190+27*10+26*90+27*120+32*40+31*70+34*130=19040
Результат: Затраты на распределение товаров между магазинами найденные методом северо-западного угла составят 19040 рублей.
2.3 Нахождение первоначального плана методом наименьшей стоимости
Используя построенную матрицу тарифов, найдём оптимальный опорный план методом наименьшей стоимости.
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | ||||||
| A2 | ||||||
| A3 | ||||||
| Потреб. |
Проверим необходимое и достаточное условие разрешимости задачи.
Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | 27[10] | 18[120] | 24[70] | |||
| A2 | 18 [190] | 21[60] | ||||
| A3 | 33 [90] | 31 [110] | ||||
| Потреб. |
Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([A2;B1]). Полностью удовлетворяем его потребность. Исключаем из решения столбец в котором он находился. Ищем следующий минимальный тариф ([A2;B3]). Удовлетворяем его потребности. Исключаем из решения столбец в котором он находился. Дальше продолжаем до тех пор, пока все запасы не будут розданы.
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F=27*10+18*120+24*70+18*190+21*60+33*90+31*110=15170
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15170 рублей.
Метод потенциалов
Для решения транспортной задачи сначала надо найти опорный план методом северо-западного угла и методом наименьшей стоимости, и из них выбрать метод при котором затраты на распределения товаров минимальны.
Для данной задачи минимальным является метод наименьшей стоимости.
Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | 27[10] | 18[120] | 24[70] | |||
| A2 | 18[190] | 21[60] | ||||
| A3 | 33[90] | 31[110] | ||||
| Потреб. |
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij
Для этого построим систему уравнений:
Из этой системы уравнений находим потенциалы, полагая, что u1 = 0:
v1=0, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6
| v1=0 | v2=27 | v3=18 | v4=25 | v5=24 | |
| u1=0 | 27[10] | 18[120] | 24[70] | ||
| u2=-3 | 18[190] | 21[60] | |||
| u3=6 | 33[90] | 31[110] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23
Выбираем максимальную оценку свободной клетки (3;3): 23
Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| B1 | B2 | B3 | B4 | B5 | Запасы | |
| A1 | 27[100] | 18[30] | 24[70] | |||
| A2 | 18[190] | 21[60] | ||||
| A3 | 23[90] | 31[110] | ||||
| Потреб. |
Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).
| v1=0 | v2=27 | v3=18 | v4=26 | v5=24 | |
| u1=0 | 27[100] | 18[30] | 24[70] | ||
| u2=-3 | 18[190] | 21[60] | |||
| u3=5 | 23[90] | 31[110] |
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Подсчитаем затраты на распределение товаров:
F = 27*100 + 18*30 + 24*70 + 18*190 + 21*60 + 23*90 + 31*110 = 15080
Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15080рублей.