45.Метод потенціалів. Алгоритм

Розглянемо мет. розв`язування, який базується на теорії двоїстості, мет. потенціалів.

Вик-ся лвоїсті змінні: Ui - змінні, які х-ють процес постачання; Vj - х-ють процес споживання.

Ці змінні наз. потенціалами задачі. Алгоритм розв`язування наступний:

1)Для усіх базисних змінних (не нульових) складається р-ня потенціалів: Хі НЕ=0: Ui+Vj=Cij

2)Одержана с-ма р-нь розв`язується відносно змінних Ui, Vj. С-ма розв`язується тільки в тому випадку, коли різниця між кількостями змінних та р-нь=1. Уцьому випадку одна із змінних довільно дорівнюється нулю,а потім послідовним аналізом кожного р-ня знаходяться ін. змінні.

Якщо різниця між кількостями > 1, то така с-ма наз. виродженою, і щоб її розв`язати, її необхідно привести до норм. вигляду. Для цього одна із нульових змінних вважається фіктивною базисною, і с-ма доповнюється фіктивним р-ням потенціалів.

3)Складання р-ня потенціалів для вільних змінних і знаходження фактичних оціночних коефіцієнтів Сіj.

Хіj=0: Ui=Vj=Cij

4)Аналіз одержаного плану на оптимальність С`ij=Cij

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

Цикл - Замкнутий контур, який своїми вершинами, крім початкової, проходить через базисні змінні. Поч. циклу відповідає змінній, яка > всього порушує умови оптимальності. Геометрично цикл будується безпосередньо в табл. потужностей.

Згідно з побудованим циклом складається послідовність змінних. Потім така послідовність розмічається знаками "+", "-", починаючи з "+".

6)Знаходження нового плану розподілу ресурсів. Для цього знах. величина коригування, яка = мінімальному значенню змінної з позначкою "-".

/\ = min {Xij} !дописать!

Усі базисні змінні, які ввійшли до циклу, коригуються на величину /\ з відповідною позначкою, тобто Хіj=Xij+ - /\. Змінні, які не ввійшли до циклу, не коригуються.

7)Одержаний новий план необхідно перевірити на оптимальність, починаючи з пункта №1.

Примітка! Іноді трапляються випадки, коли неможливо побудувати нормальний цикл перерозподілу ресурсів. У цьому випадку дозволяється будувати вироджений цикл, у якому ще одна вершина, крім початкової, проходить через нульову змінну. Причому, знак цієї змінної повинен бути обов`язково "+".