Розв’язання Т-задач методом потенціалів

Метод потенціалів ґрунтується на розв’язанні двоїстої до транспорт­ної задачі, яка має вигляд

для системи обмежень

a_i+b_j£ с_ij, i=1,m, j=1,n,

де a_i –потенціали постачальників, b_j – потенціали споживачів.

Таким чином, для того щоб деякий опорний план транспортної задачі був оптимальним, необхідна і достатня його потенціальність, тобто, щоб він задовольняв такі умови.

1. Для базисних клітинок, де x_ij>0, a_i+b_j=с_ij.

2. Для небазисних клітинок, де x_ij=0, a_i+b_j£ с_ij.

При цьому, якою б не була система чисел-потенціалів (a_i, b_j), що задовольняє умови потенціальності плану, для кожної небазисної клітинки вартість циклу визначається рівнянням