Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.5.3. Монотонність і скінченність методу потенціалів

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

Нехай план знайдено з плану однією ітерацією методом потенціалів; при цьому було використано цикл (позначимо такий набір клітин через К), утворений клітинами з такими індексами:

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

З першої теореми двоїстості для транспортної задачі маємо:

.

Враховуючи останнє рівняння, встановимо зв’язок між послідовними значеннями цільової функції і , що відповідають опорним планам та :

.

Перша сума правої частини — перевезення, які не були включені в цикл К, друга сума поширюється на ті значення перевезень, де віднімалась вибрана величина q, третя сума і останній доданок охоплюють клітини, де початкове значення було збільшене на величину q. Тобто:

(5.26)

Враховуючи додатність величини q у разі невиродженості плану і від’ємне значення виразу в дужках (), висновуємо, що . Цим і доведена строга монотонність алгоритму, яка у разі виродженості плану не є строгою, оскільки величина q може дорівнювати нулю.

Співвідношення (5.18) є також обґрунтуванням способу вибору клітини, яка вводиться в базис, за максимумом абсолютної величини , оскільки це дасть найбільше зменшення цільової функції.

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