Методы решения транспортных задач
Перейдем к решению задачи.
Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.
Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij ≥ 0, а в маленькие клетки – соответствующие тарифы Cij.
(пояснения)
Наша задача заполнить все клетки числами xij (количеством перевозимого товара) так, чтобы их сумма по строкам была равна аi, по столбцам -bj. Затем эти числа умножаем на стоимости перевозок Cij и складываем. И эта сумма должна принимать минимальное значение.
Решение задачи разбивается на два этапа:
1. Определение опорного плана.
2. Нахождение оптимального решения путем последовательных операций.
Рассмотрим подробно каждый из этапов:
1. Опорный план транспортной задачи можно найти, используя метод "северо-западного угла" или метод "минимального элемента".
Метод северо-западного угла (диагональный)
Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj.
Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj.
|
|
|
Задача: Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.
Пример 1: Составить опорный план задачи методом северо-западного угла.
Решение:
Исходная транспортная таблица имеет вид:
Построим опорный план.
Магазин В1 подал заявку на 20 компьютеров, но со склада А1 мы можем перевести 15 компьютеров, ещё 5 компьютеров мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 компьютеров - доставим их со склада А2.
На складе А2 осталось 8 компьютеров. Выделим из них пять для магазина В3. На складе А2 осталось 3 компьютера. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять компьютеров. Осталось 15 компьютеров, столько, сколько требуется в магазин В5.
Все заявки удовлетворены, все запасы израсходованы.
Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 7.
|
|
|
Опорный план: Х11 = 15, Х21 = 5, Х22 = 12, Х23 = 5, Х24 = 3, Х34 = 5, Х35 = 15.
Все остальные Xij = 0. Такие клетки будем называть пустыми.
Вычислим суммарную стоимость перевозок для построенного плана:
F = 1*15+5*5+1*12+2*5+3*3+4*5+3*15 = 136
Будет ли это минимальная стоимость перевозок, а план – оптимальным, проверим позже.
А сейчас рассмотрим другой метод составления опорного плана.
Метод наименьшего элемента
Сущность метода в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.
Пример 2: Составить опорный план задачи методом наименьшего элемента.
Решение: Исходная транспортная таблица имеет вид:
Построим опорный план.
Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).
Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.
Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.
|
|
|
Вычеркиваем первую строку.
Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.
Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.
Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.
Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.
Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.
Опорный план построен.
Количество заполненных клеток 3+5-1=7.
Х11 = 3, Х12 = 12, Х21 = 2, Х24 = 8, Х25 = 15, Х31 = 15, Х33 = 5.
Все остальные Хij = 0.
Вычислим суммарную стоимость перевозок для построенного плана:
F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147.
147>136, т.е. данный план точно не оптимальный.
Итак, мы изучили 2 способа построения первого опорного плана. При решении задачи вы выбираете тот способ, который вам больше понравился (долее понятен).
2.Теперь необходимо проверить, будет ли построенный план оптимальным, т.е. получим ли мы минимальную стоимость перевозок.
Для этого воспользуемся методом потенциалов.
Дата добавления: 2022-01-22; просмотров: 32; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!