На три базы A1, A2, A3 поступил однородный груз в количествах, соответственно равных 150, 180 и 170 единиц.
Этот груз требуется перевезти в пять пунктов назначения B1, B2, B3, B4, B5 соответственно в количествах 70, 70, 130, 130 и 100 единиц.
Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице
Пункт отправления Пункт назначения Запасы
B1 B2 B3 B4 B5
A1 2 3 4 2 4 150
A2 8 4 1 4 1 180
A3 9 7 3 7 2 170
Потребители 70 70 130 130 100
Найти план перевозок данной транспортной задачи тремя способами.
Решение
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2 3 4 2 4 150
A2 8 4 1 4 1 180
A3 9 7 3 7 2 170
потребители 70 70 130 130 100
Проверим условие разрешимости задачи.
A=i=1mai=150+180+170=500;
B=j=1nbj=70+70+130+130+100=500.
Как видно, суммарная потребность груза в пунктах назначения равна запасам груза на базах. Следовательно, модель исходной транспортной задачи является замкнутой.
Составим первый план транспортной задачи методом северо-западного угла.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2
70 3
70 4
10 2 4 150
A2 8 4 1
120 4
60 1 180
A3 9 7 3 7
70 2
100 170
потребители 70 70 130 130 100
Составим первый план транспортной задачи методом аппроксимации Фогеля.
Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.
Данный метод состоит в следующем:
1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2
70 3 4 2
80 4 150
A2 8 4
70 1
60 4
50 1 180
A3 9 7 3
70 7 2
100 170
потребители 70 70 130 130 100
Составим первый план транспортной задачи методом наименьшей стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2
70 3 4 2
80 4 150
A2 8 4 1
130 4 1
50 180
A3 9 7
70 3 7
50 2
50 170
потребители 70 70 130 130 100
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 =7
. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
FX0=2∙70+2∙80+1∙130+1∙50+7∙70+7∙50+2∙50=1420
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=2
α1+β4=2
α2+β3=1
α2+β5=1
α3+β2=7
α3+β4=7
α3+β5=2
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=4; α3=5; β1=2; β2=2; β3=-3; β4=2; β5=-3
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆12=3-0-2=1;
∆13=4-0+3=7;
∆15=4-0+3=7;
∆21=8-4-2=2;
∆22=4-4-2=-2;
∆24=4-4-2=-2;
∆31=9-5-2=2;
∆33=3-5+3=1.
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 2;2: ∆22=-2.
Для этого в клетку (2;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2
70 3 4 2
80 4 150
A2 8 + 12890517821000138393181199004 1
130 4 - 1
9271050800050 180
A3 9 13779516446500- 7
70 3 7
50 + 2
50 170
потребители 70 70 130 130 100
Цикл приведен в таблице 2,2→2,5→3,5→3,2.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках. В результате перемещения числа k=50 по циклу получим новую распределительную таблицу, в которой клетка 2;2 стала занятой.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 2
70 3 4 2
80 4 150
A2 8 4
50 1
130 4 1 180
A3 9 7
20 3 7
50 2
100 170
потребители 70 70 130 130 100
Оптимизируем план производства и организации перевозок методом потенциалов
Задать вопрос
на новый заказ в Автор24.
