Метод потенціалів. Попередні відомості й поняття:

Попередні відомості й поняття:

1. Будь-яку сукупність кліток розподільної таблиці називають набором.

2. Набір, у якого дві й тільки дві клітки розташовані в межах рядків або стовпців називають ланцюгом. З погляду геометрії ланцюг являє собою розімкнуту ламану лінію

3. Ланцюг, у якого перша й остання клітки розташовані в одному рядку або в одному стовпці називається циклом. З геометричної точки зору цикл можна інтерпретувати, як замкнуту ламану лінію,

.

Необхідно розрізняти базисні й небазисні клітки таблиці ТЗ. У базисних клітках завжди записуються невід’ємні значення перевезень. Кількість базисних кліток повинна дорівнювати m+ n-1. Небазисні клітки є порожніми, тобто незаповненими.

Відмітимо, якщо кількість базисних кліток < m+ n-1, то ТЗ називають виродженою.

Для усунення виродженості до складу базисних кліток включають небазисні, але значення перевезень в них дорівнює 0.

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

Теорема (про оптимальний план ТЗ

Попередні відомості. Складемо математичну модель ТЗ

(75)   (76)

(74)

(77)

До задачі (74)-(77) складають двоїсту

(78)

З огляду на те, що U_i й V_j можуть мати будь-які знаки, то якщо змінним U_i присвоїти знак (-), тоді двоїста задача має вид

(79)

(80)