Й этап
Алгоритм итерационный. На каждой итерации выполняются следующие действия:
1. Рассчитываются потенциалы каждого склада и потребителя как предельные доходы на единицу товара: ui – потенциал i-го склада, vj – потенциал j-го потребителя.
Для элементов опорного плана
ui + vj = Cij. Получается система из m + n -1 уравнений относительно m + n неизвестных. Полагаем u1 = С11 и тогда v1 = 0 и система решается однозначно.
Пример 2
Пусть
Матрица стоимостей транспортировки Сij Табл.7
i j | |||
Потенциалы Табл. 8
ui vj | |||
Потенциалы Табл. 9
ui vj | |||
Потенциалы Табл. 10
ui vj | -3 | ||
2. Рассчитываются двойственные оценки Zij для всех элементов i и j:
Zij = ui + vj.
Рассчитываются характеристические разности
Zij – Сij.
|
|
Если все они не положительны (т.е. Zij – Сij ≤ 0), то план – оптимальный и расчеты заканчиваем. В противном случае переход к п.3.
3. Преобразование плана.
Элементу с наибольшей Zij – Сij присваивается неизвестное значение Q.
Среди элементов опорного плана строится цепочка наименьшей длины, состоящая из элементов xij + Q или xij – Q так, чтобы имел место баланс между потребностями и возможностями: добавление (вычитание) Q в строке в каком-то столбце должно быть компенсировано вычитанием (добавлением) Q в каком-то другом столбце, а вычитание (добавление) Q в строке в каком-то столбце должно быть компенсировано добавлением (вычитанием) Q в данном столбце в другой строке. В результате образуются разности xij – Q. Находим среди них такую, что xij – Q = 0, а остальные были бы неотрицательными. Соответствующее значение Q является максимально возможным. Приняв значение xij = Q для элемента с наибольшей характеристической разностью, получим новый опорный план, у которого по сравнению с предыдущим одни элементы будут уменьшены на Q, некоторые будут увеличены на Q, один или несколько равны 0 (те, для которых xij – Q = 0), остальные останутся неизменными.
Если нулевыми станут более чем одна переменная предыдущего опорного плана, то сохраняем в новом плане ту (или те) компоненту (-ты), у которой (ых) Cij меньше.
Далее переход к очередной итерации, т.е. к п. 1 данного алгоритма.
Пример 2, продолжение.
Для опорного плана табл. 6 выполним п.3 алгоритма.
Табл.11
i j | |||
4 - Q | Q | ||
4 + Q | 2 - Q | ||
Q = arg min [4-Q,2-Q] = 2
Строим новый опорный план, табл. 12
Табл.12
|
|
i j | |||
1-я итерация 2-го этапа.
п.1. Расчет потенциалов
Потенциалы Табл. 13
ui vj | -1 | -6 | |
u1 = C11 = 3 | 3 – 3 = 0 | 2 – 3 = -1 | |
4 – 0 = 4 | |||
10 – (-1) = 11 | 5 – 11 = -6 |
п.2. Расчет характеристических разностей, табл. 14
Характеристические разности ui + vj – Сij Табл. 14
ui vj | -1 | -6 | |
3-6-1=-4 | |||
4-1-6=-3 | 4-6-8=-10 | ||
11+0-10=+1 |
Характеристическая разность Z31 – C31 больше 0 и следовательно данный опорный план не оптимален
п.4. Построение нового опорного плана, табл. 15.
Табл.15
i j | |||
2-я итерация 2-го этапа.
п.1. Расчет потенциалов
Потенциалы Табл. 16
ui vj | -1 | -5 | |
п.2. Расчет характеристических разностей.
Характеристические разности ui + vj – Сij Табл. 17
ui vj | -1 | -5 | |
-3 | |||
-3 | -9 | ||
-1 |
Среди характеристических разностей нет положительных, следовательно последний опорный план – табл. 15 – является оптимальным. На этом вычисления заканчиваем.
Оптимальное значение линейной формы (1) задачи равно 92. Значение линейной формы (1) для начального плана задачи равно 100, для плана 1-й итерации равно 94.