Транспортная задача. Метод потенциалов

Транспортная задача относится к классу задач ЛП. Транспортная задача решает проблему нахождения оптимального плана перевозок некоторого однородного груза из m пунктов отправления в n пунктов назначения. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, т.к. позволяет фирмам и предприятиям существенно сократить расходы на транспорт.

Метод потенциалов проверять опорный план транспортной задачи на оптимальность.

Метод потенциалов:

Введем строку потенциалов u _i и столбец потенциалов v _j. Полагая, что u₁=0, а остальные u _i и v _j найдем так, чтобы

а) для заполненных ячеек выполнялись равенства ;

б) для незаполненных ячеек выполнялись равенства .

Критерий оптимальности:

Если известны потенциалы решения Х₀ транспортной задачи и для всех незаполненных ячеек выполняются условия , то Х₀ является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.