Решить транспортную задачу методом потенциалов

Пусть xij  количество единиц продукции, перевозимой с i- го пункта производства в j-й центр распределения. По условию эти переменные неотрицательны. Целевая функция (минимум суммарных транспортных расходов) имеет вид: F(x) = 6x11 + 3x12 + 4x13 + 5x14 + 5x21 + 2x22 + 3x23 + 3x24 + 3x31 + 4x32 + 2x33 + 4x34 + 5x41 + 6x42 + 2x43 + 7x44 → min
Ограничения по запасам:
x11 + x12 + x13 + x14 ≤ 20 (для 1 пункта производства)
x21 + x22 + x23 + x24 ≤ 70 (для 2 пункта производства)
x31 + x32 + x33 + x34 ≤ 50 (для 3 пункта производства)
x41 + x42 + x43 + x44 ≤ 30 (для 4 пункта производства)
Ограничения по потребностям:
x11 + x21 + x31 + x41 = 15 (для 1-го центра распределения)
x12 + x22 + x32 + x42 = 30 (для 2-го центра распределения)
x13 + x23 + x33 + x43 = 80 (для 3-го центра распределения)
x14 + x24 + x34 + x44 = 20 (для 4-го центра распределения)
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 20 + 70 + 50 + 30 = 170
∑b = 15 + 30 + 80 + 20 = 145
Модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем фиктивную потребность, равной 25. Тарифы перевозки единицы груза к этому пункту потребления полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 Запасы
A1 6 3 4 5 0 20
A2 5 2 3 3 0 70
A3 3 4 2 4 0 50
A4 5 6 2 7 0 30
Потребности 15 30 80 20 25
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
B1 B2 B3 B4 B5 Запасы
A1 6 3 4 5 0[20] 20
A2 5[15] 2[30] 3 3[20] 0[5] 70
A3 3[0] 4 2[50] 4 0 50
A4 5 6 2[30] 7 0 30
Потребности 15 30 80 20 25
Значение целевой функции для этого опорного плана равно:F(x) = 0*20 + 5*15 + 2*30 + 3*20 + 0*5 + 2*50 + 2*30 = 355
Проверим оптимальность опорного плана . Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v5 = 0; 0 + v5 = 0; v5 = 0
u2 + v5 = 0; 0 + u2 = 0; u2 = 0
u2 + v1 = 5; 0 + v1 = 5; v1 = 5
u3 + v1 = 3; 5 + u3 = 3; u3 = -2
u3 + v3 = 2; -2 + v3 = 2; v3 = 4
u4 + v3 = 2; 4 + u4 = 2; u4 = -2
u2 + v2 = 2; 0 + v2 = 2; v2 = 2
u2 + v4 = 3; 0 + v4 = 3; v4 = 3
v1=5 v2=2 v3=4 v4=3 v5=0
u1=0 6 3 4 5 0[20]
u2=0 5[15] 2[30] 3 3[20] 0[5]
u3=-2 3[0] 4 2[50] 4 0
u4=-2 5 6 2[30] 7 0
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;3): 0 + 4 > 3; ∆23 = 0 + 4 - 3 = 1 > 0
Выбираем максимальную оценку свободной клетки (2;3): 3Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 5 Запасы
1 6 3 4 5 0[20] 20
2 5[15][-] 2[30] 3[+] 3[20] 0[5] 70
3 3[0][+] 4 2[50][-] 4 0 50
4 5 6 2[30] 7 0 30
Потребности 15 30 80 20 25
Цикл приведен в таблице (2,3 → 2,1 → 3,1 → 3,3).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е