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

Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплексным методом, а именно:

1. сначала находят начальный опорный план перевозок ,

2. затем переходят к новому плану , лучшему, такому, что

Z( ) ≤ Z( )

3. проверяют критерий оптимальности полученного решения:

Если для некоторого опорного плана

транспортной задачи существуют такие числа , что

,

,

то есть оптимальный плантранспортной задачи

.

Числа называются потенциаламисоответственно пунктов поставки и пунктов потребления.

Критерий оптимальности решения транспортной задачи следующий:

для того чтобы решение было оптимальным, необходимо и

достаточно, чтобы существовала система чисел ,

которые удовлетворяли бы условиям:

для всех базисных переменных (занятых клеток) и

для всех свободных переменных (пустых клеток).