Навигация
7. Деякі висновки
Спробуємо охарактеризувати поводження алгоритмів методу відсікання при рішенні задач цілочисленного лінійного програмування. Як міра тривалості обчислень можуть розглядатися кількість симплексних ітерацій I і кількість правильних відсікань (додаткових лінійних обмежень) D.
Для першого алгоритму Гомори й різних його узагальнень I і D також тісно зв'язані між собою (як показує експеримент, у більшості випадків рішення окремої задачі (?, З) вимагає порівняно невеликої кількості симплексних ітерацій).
Переходимо до викладу окремих властивостей алгоритмів методу відсікання.
Числа I і D мають (у середньому) тенденцію до зростання зі збільшенням числа змінних і обмежень, ростом порядку коефіцієнтів задачі й збільшенням заповнювання матриці 
.
Це явище здається природним, але досвід показує, що в дискретному програмуванні «природне» і «правдоподібне» не завжди виявляється правильним. Точніше кажучи, досвід, накопичений на задачах ЛІНІЙНОГО ПРОГРАМУВАННЯ, не можна механічно переносити на задачі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ.
Насамперед, обертає на себе увага «нерегулярність», «непередбачуваність» поводження алгоритмів методу відсікання. Для ряду задач оптимальне рішення не вдавалося одержати після багатьох тисяч ітерацій, у той час як інші задачі вирішувалися за кілька десятків ітерацій.
Не вдається встановити безпосередній зв'язок між розмірами задач (тобто числом обмежень m і змінних n) і числом ітерацій: невдачі були зафіксовані навіть для невеликих задач (m?10, n?10), а успіхи - для задач досить великого розміру (m = 215, n = 2600). Можливо, втім, що спроба встановлення подібного зв'язку - це неправомірне перенесення результатів ЛІНІЙНОГО ПРОГРАМУВАННЯ в область ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ.
Бути може, більше природною характеристикою задачі (£, З) є не число m лінійних обмежень, що задають багатогранну множину £, а число mц - лінійних обмежень, що задають багатогранну множину V(£)*). Тим часом легко привести приклади, коли при невеликих m і n число mц буде досить велике.
«Нерегулярність» позначається й у наступному факті, поміченому поруч дослідників: іноді вдається істотно скоротити число ітерацій за рахунок перенумерації змінних.
Нарешті, має місце немонотонність наближення псевдоплана Хr до оптимального плану X* – з ростом r відстань ρ(Хr, X*) не обов'язково зменшується й лише на останній ітерації обов'язково стає рівним нулю.
Великий вплив на число ітерацій робить правило вибору рядка, що породжує. Тут також має місце «нерегулярність» - у той час як одне правило приводить до успіху за десятки ітерацій, інше не дає рішення після тисяч ітерацій.
При рішенні задач цілочисленного лінійного програмування по методу відсікання є як успіхи, так і невдачі.
До найбільш успішних робіт варто віднести:
1) Задачі покриття, у тому числі задачі, пов'язані з мінімізацією булевих функцій.
2) Застосування до задач оптимального кодування.
3) Застосування до задачі оптимального добування інформації з паралельних систем пам'яті.
Найбільш характерними задачами, для яких мала місце невдача, є:
1) Задачі комівояжера.
2) Задача теорії розкладів.
3) Деякі з узагальнених задач покриття.
У даний момент відсутнє вичерпне пояснення удач або невдач різних обчислювальних експериментів. Все-таки для задачі комівояжера й задачі теорії розкладів є правдоподібним наступне міркування.
Формулювання цих задач мовою ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ є «неприродної». Для задачі порівняно невеликої в «природній» формулюванні, у моделі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ фігурує велика кількість обмежень і змінних. Можливо, що для цих задач більше перспективними є комбінаторні методи (наприклад, метод галузей і границь для задачі комівояжера). Втім, останнє твердження є спірним, тому що комбінаторні методи дуже чутливі до специфіки задач, введенню додаткових умов і т.п.
Очевидно, успіх у рішенні задач покриття пов'язаний з тим, що вдалося напасти на клас задач, практично важливих і в той же час успішно розв'язуваних. Було б досить цікаво точно охарактеризувати клас задач покриття, добре розв'язуваних по методу відсікання. Це тим більше цікаво, що побудовано приклади узагальнених задач покриття, для яких виникають значні обчислювальні труднощі.
І взагалі, виділення окремих класів ефективно розв'язуваних задач - важлива й цікава проблема.
Висновок
Підведемо деякі підсумки. Метод відсікання перебуває в стадії розвитку й удосконалювання. При реалізації цього методу виникають труднощі, що носять, очевидно, не тільки технічний, але й принциповий характер. У даний момент можна говорити про рішення за допомогою методу відсікання задач не більш ніж середнього розміру (сотні змінних і десятки обмежень).
Найбільш перспективними для подальших досліджень по методу відсікання представляються наступні напрямки:
1) Дослідження будови множин £ц і V(£ц).
2) Дослідження властивостей правильних відсікань.
3) Вказівка нових способів побудови правильних відсікань.
4) Розвиток нових класів алгоритмів методу відсікання (наприклад, прямих алгоритмів).
5) Виділення окремих класів ефективно розв'язуваних задач.
Література
1. Корбут А.А., Финкельштейн Ю.Ю. Дискретне програмування. – К., 2004
2. Лященко І.Н. Лінійне й нелінійне програмування. – К., 2003
3. Санович К.М. Дослідження операцій. - К.,1999.
Похожие работы
4 9 0 1 0 3 Р5 0 8 4 -2 0 0 1 4 F 0 -5 -6 0 0 0 Таблиця № 1 – Вихідна симплекс-таблиця Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи: 1. За вихідною с-т знаходять опорне рішення Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змі ...
... . Механізм переривань забезпечує ефективна взаємодія пристроїв уведення-висновку з мікропроцесором. Переривання цікавлять нас тому, що обробка переривань - це прерогатива програмування на мові асемблера. У високорівневих мовах відсутні засоби роботи з перериваннями на машинному рівні. Переривання звичайно викликаються зовнішніми пристроями. Переривання сигналізує мікропроцесору, щоб він призупинив ...
... рішень, зв’язаних із регулюванням витрат і з питань інвестиційної діяльності підприємства. Отже, управлінський облік це формування інформації для управління витратами з метою підвищення ефективності функціонування підприємства. Причому, відповідно до Закону «Про бухгалтерський облік і фінансову звітність в Україні», підприємства вправі самостійно обирати систему і форми ведення управлінського ...
... ‚ є гіпотезою про закон розподілу. Гіпотеза про те‚ що середні розміри деталей‚ які виготовляються на однотипних‚ паралельно працюючих станках‚ приблизно однакові‚ є гіпотезою про параметри розподілу. Зроблений на основі статистичних даних висновок про те‚ що між кількома генеральними сукупностями або між емпіричним і теоретичним розподілом істотних відмінностей немає‚ називають нульовою ( ...
0 комментариев