Операция 2.1. Расчет потенциалов

Проверка плана транспортной задачи в описываемом методе на оптимальность осуществляется с помощью потенциалов. Потенциалы – это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим u_i, потенциалы столбцов – v_j. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А₂В₃. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u₃ = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле

. (3.6)

Потенциал первого столбца v₁ = u₂ + c₂₁ = 0 + 4 = 4;

второго: v₂ = u₂ + c₂₂ = 0 + 7 = 7;

третьего: v₃ = u₂ + c₂₃ = 0 + 13 = 13;

пятого: v₅ = u₂ + c₂₅ = 0 + 2 = 2.

Рассчитанные потенциалы записываем напротив соответствующих столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 2 потенциалы столбов найдены, переходим к расчету потенциалов строк.

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и базисной клетке А₁В₃ по формуле

, (3.7)

где u₁ = v₃ – c₃₁ = 13 – 8 = 5.

Для строки 3 потенциал будет равен:

u₃ = v₅ – c₃₅ = 2 – 1 = 1.

Также рассчитываем потенциалы для всех строк и столбцов (табл. 3.6).

Таблица 3.6 - Расстановка потенциалов и перераспределение поставок