Операция 2.1. Расчет потенциалов.
Проверка плана транспортной задачи в описываемом методе на оптимальность осуществляется с помощью потенциалов. Потенциалы – это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим ui, потенциалы столбцов – vj. Они могут принимать любые значения. Однако удобнее работать с положительными, целыми и относительно небольшими числами. Такой потенциал первоначально назначается любой строке или столбцу. Рекомендуем поступать следующим образом. Выберем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А2В3. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u3 = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле Потенциал первого столбца v1 = u2 + c21 = 0 + 4 = 4; второго: v2 = u2 + c22 = 0 + 7 = 7; третьего: v3 = u2 + c23 = 0 + 13 = 13; пятого: v5 = u2 + c25 = 0 + 2 = 2. Рассчитанные потенциалы записываем напротив соответствующих столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 2 потенциалы столбов найдены, переходим к расчету потенциалов строк. Потенциал строки 1 рассчитываем по найденному потенциалу столбца 3 и базисной клетке А1В3 по формуле где u1 = v3 – c31 = 13 – 8 = 5. Для строки 3 потенциал будет равен: u3 = v5 – c35 = 2 – 1 = 1. Также рассчитываем потенциалы для всех строк и столбцов (табл. 2.6). Таблица 2.6 Расстановка потенциалов и перераспределение поставок
|
(2.6)
(2.7)
