5.2. Метод потенціалів

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

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)

Теорема

Для того, щоб деякий план був оптимальним необхідно й достатньо, щоб для нього існувала система m+n чисел U_i й V_j, причому таких чисел, щоб виконувалися умови

(81)

для кліток небазисного набору й

(82)

для кліток базисного набору.

Тут числа U_i й V_j відповідно називаються потенціалами пунктів відправлення й потенціалами пунктів призначення. Тоді умови (81) і (82) називаються умовами потенційності кліток небазисного набору (81) і базисного набору (82).

У зв'язку з відзначеним теорему про оптимальний план ТЗ у компактному виді можна представити в такий спосіб.

Теорема

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

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

.

Цілком очевидно, що для базисного набору кліток , тому що в клітках зазначені невід’ємні значення перевезень. Тоді, щоб виконувалися умови Слейтера необхідно й достатньо, щоб для базисного набору кліток вирази в дужках перетворювалися б в 0, тобто .

В той же час для небазисного набору кліток . Це означає, що вираз в дужках може бути будь-яким (у рамках припустимого плану). Тоді для небазисного набору кліток в оптимальному плані повинне виконуватися співвідношення виду . Теорема доведена.

Алгоритм методу потенціалів складається з 2-х кроків: попереднього й загального, який повторюється.

Попередній крок:

1. Складають первісний опорний план.

2. Складають первісну систему потенціалів.

3. Перевіряють план на потенційність.

Цілком очевидно, що якщо план потенційний, то він оптимальний, тоді на цьому етапі завершують розв’язок задачі.

Якщо план непотенційний, то він не оптимальний, і тоді переходять до загального кроку, який повторюється. У загальному кроці виконують наступні операції.

Загальний крок:

1. Перебудовують опорний план з метою його поліпшення.

2. Перебудовують систему потенціалів.

3. Перевіряють план на потенційність.

Відмітимо, що метод потенціалів сходиться й притім завжди за кінцеве число ітерацій.