Имеются три пункта поставки однородного груза A1

Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 запасы
A1 24 27 18 27 21 200
A2 18 26 21 32 31 250
A3 27 33 23 31 34 200
потребители 120 100 120 110 130
Проверим условие разрешимости задачи.
A=i=1mai=650; B=j=1nbj=580.
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную потребность, равной 70. Тарифы перевозки единицы груза к этому магазину полагаем равны нулю.
Занесем исходные данные задачи в распределительную таблицу.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18 27 21 0 200
A2 18 26 21 32 31 0 250
A3 27 33 23 31 34 0 200
потребители 120 100 120 110 130 70
Составим первый план транспортной задачи методом наименьшей стоимости.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18
120 27 21
80 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 23 31
110 34
20 0
70 200
потребители 120 100 120 110 130 70
Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 =87. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
FX0=18∙120+21∙80+18∙120+26∙100+31∙30+31∙110+34∙20+0∙70=13620
Оптимизируем план производства и организации перевозок методом потенциалов . Составим систему уравнений для определения потенциалов
α1+β3=18
α1+β5=21
α2+β1=18
α2+β2=26
α2+β5=31
α3+β4=31
α3+β3=23
α3+β6=0
Проверим оптимальность опорного плана. Найдем потенциалы αi, βj. по занятым клеткам таблицы, в которых αi+βj=cij, полагая, что α1=0.
α1=0; α2=10; α3=13
β1=8; β2=16; β3=18; β4=18; β5=21; β6=-13
Вычислим оценки ∆st свободных переменных (свободных клеток):
∆11=24-0-8=16; ∆12=27-0-16=11; ∆14=27-0-18=90; ∆16=0-0+13=13
∆23=21-10-18=-7; ∆24=32-10-18=4; ∆25=0-10+13=3
∆31=27-13-8=6; ∆32=33-13-16=4; ∆33=23-13-18=-8
Опорный план не является оптимальным, так как существуют отрицательные оценки свободных клеток.
Выбираем максимальную оценку свободной клетки 3;3: ∆33=-8.
Для этого в клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 - 18
149860444500149860508000120 27 + 21
9969557150080 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 14986018796000+ 23 31
110 - 34
20 0
70 200
потребители 120 100 120 110 130 70
Цикл приведен в таблице 3,3→3,5→1,5→1,3.
Из грузов, стоящих в минусовых клетках, выбираем наименьшее.
Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем из стоящих в минусовых клетках. В результате перемещения числа k=20 по циклу получим новую распределительную таблицу, в которой клетка 3;3 стала занятой.
Bj
Ai B1 B2 B3 B4 B5 B6 запасы
A1 24 27 18
100 27 21
100 0 200
A2 18
120 26
100 21 32 31
30 0 250
A3 27 33 23
20 31
110 34 0
70 200
потребители 120 100 120 110 130 70
Оптимизируем план производства и организации перевозок методом потенциалов