Планируются перевозки топлива из четырех хранилищ A1

Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 запасы
A1 4 3 10 14
A2 4 8 4 10
A3 3 2 5 12
A4 6 6 1 10
потребители 21 15 15
Проверим условие разрешимости задачи.
A=i=1mai=14+10+12+10=46; B=j=1nbj=21+15+15=51
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивную базу, с запасом равным 5. Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
Bj
Ai B1 B2 B3 запасы
A1 4 3 10 14
A2 4 8 4 10
A3 3 2 5 12
A4 6 6 1 10
A5 0 0 0 5
потребители 21 15 15
Составим первый план транспортной задачи методом наименьшей стоимости. Заполнение клеток таблицы начнем с левой верхней клетки.
Bj
Ai B1 B2 B3 запасы
A1 4
11 3
3 10 14
A2 4
10 8 4 10
A3 3
2
12 5 12
A4 6 6 1
10 10
A5 0 0
0 0
5 5
потребители 21 15 15
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 =7 . Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
FX0=4∙11+3∙3+4∙10+2∙12+1∙10+0∙5=127
Оптимизируем план производства и организации перевозок методом потенциалов. Составим систему уравнений для определения потенциалов
α1+β1=4α1+β2=3α2+β1=4α3+β2=2α4+β3=1α5+β2=0α5+β3=0
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=0; α3=-1; α4=-2; α5=-3
β1=4; β2=3; β3=3
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆13=10-0-3=7
∆22=8-0-3=5
∆23=4-0-3=1
∆31=3+1-4=0
∆33=5+1-3=3
∆41=6+2-4=4
∆42=6+2-3=5
∆51=0+3-4=-1
Опорный план не является оптимальным, так как существует отрицательная оценка свободной клетки 5;1.
Выбираем максимальную оценку свободной клетки 5;1: ∆51=-1.
Для этого в клетку (5;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 запасы
A1 - 4
87630-31750086995-19050011 + 3
71120-1270003 10 14
A2 4
10 8 4 10
A3 3
2
12 5 12
A4 6 6 1
10 10
A5 + 84455223520000 - 0
0 0
5 5
потребители 21 15 15
Цикл приведен в таблице 5,1→5,2→1,2→1,1.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках