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

Особливості математичної моделі ТЗ

1. Задача представлена в 1-ій канонічній формі.

2. Коефіцієнти при невідомих в обмеженнях рівні 1.

3. Кожна змінна входить лише двічі у відповідні обмеження (це означає, що така таблиця буде слабозаповненою).

4. Ранг системи обмежень ТЗ ч = m + n –1.

5. Усього в ТЗ буде m∙ n змінних, з них базисних m∙ n-1, а вільних m∙ n-(m∙ n-1).

Висновок. Представлений аналіз математичної моделі ТЗ показує, що така задача може розв’язуватись симплексною процедурою. Однак особливості її математичної моделі дозволили розробити більше прості й зручні методи розв’язування такої задачі, а саме:

- угорський метод;

- метод диференціальних рент;

- метод потенціалів.

Одним з найбільш простих є метод потенціалів.

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

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

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

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

.

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

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

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

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