На трех складах A1, A2, A3 хранится a1=200, a2=55, a3=100 единиц одного и того же груза. Этот груз требуется доставить трем потребителям B1, B2 и B3, заказы которых составляют b1=130, b2=45, b3=180 единиц груза соответственно. Стоимости перевозок cij указаны в соответствующих клетках транспортной таблицы.
Bj
Ai B1 B2 B3 Запасы
A1 5 2 4 200
A2 3 5 6 55
A3 1 8 3 100
Потребители 130 45 180
Составить оптимальный план, обеспечивающий минимальную стоимость перевозок и найти эту стоимость.
Решение
Проверим условие разрешимости задачи.
A=i=1mai=200+55+100=355;
B=j=1nbj=130+45+180=355.
Как видно, суммарная потребность груза в пунктах назначения равна запасам груза. Следовательно, модель исходной транспортной задачи является закрытой.
Составим первый план транспортной задачи методом наименьшей стоимости. Заполнение клеток таблицы начнем с левой верхней клетки.
Bj
Ai B1 B2 B3 Запасы
A1 5 2
45 4
155 200
A2 3
30 5 6
25 55
A3 1
100 8 3 100
Потребители 130 45 180
Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 =5. Следовательно, опорный план является невырожденным.
Запишем исходное опорное решение в виде матрицы перевозок
X0=0451553002510000
Значение целевой функции для этого опорного плана равно:
FX0=2∙45+4∙155+3∙30+6∙25+1∙100=1050
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β2=2; α1+β3=7;
α2+β1=3; α2+β3=6;
α3+β1=1.
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=2; α3=0
β1=1; β2=2; β3=4
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=5-0-1=4
∆22=5-2-2=1
∆32=8-0-2=6
∆33=3-0-4=-1
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 3;3: ∆33=-1.
Для этого в клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 Запасы
A1 5 2
45 4
155 200
A2 + 3
30 5 - 6
25 55
A3 - 1
100 8 + 3 100
Потребители 130 45 180
Цикл приведен в таблице 3,3→3,1→2,1→2,3.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 25 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках
. В результате перемещения числа k=25 по циклу получим новую распределительную таблицу, в которой клетка 3;3 стала занятой.
Bj
Ai B1 B2 B3 Запасы
A1 5 2
45 4
155 200
A2 3
55 5 6 55
A3 1
75 8 3
25 100
Потребители 130 45 180
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β2=2
α1+β3=4
α2+β1=3
α3+β1=1
α3+β3=3
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=1; α3=-1
β1=2; β2=2; β3=4.
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=5-0-2=3;
∆22=5-1-2=2;
∆23=6-1-4=1;
∆32=8--1-2=7.
Опорный план является оптимальным, так как все оценки свободных клеток положительны.
X=045155550075025
Минимальные затраты составят: FX=1025.
Анализ оптимального плана.
Из 1-го склада необходимо груз направить во 2-й магазин в количестве 45 единиц, в 3-й магазин в количестве 155 единиц.
Из 2-го склада необходимо весь груз направить в 1-й.
Из 3-го склада необходимо груз направить в 1-й магазин в количестве 75 единиц, в 3-й магазин в количестве 25 единиц.
Реализуем решение транспортной задачи при помощи Excel.
В Excel существует надстройка Поиск решения, которая, в частности, помогает решать транспортные задачи
Задать вопрос
на новый заказ в Автор24.
