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

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

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

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

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

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

.

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

.

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

(5.26)

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

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

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



 
Главная
Банковское дело
Бухгалтерский учет, аудит
Инвестиции
Экономика
Налоги
Финансы
Финансовое право
Прочие дисциплины
Карта сайта
Правила користування