Рішення задач цілочисленного програмування
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?тже, не більше чим [n+s (m+2+s)] = (n-m-2) нулів. Але вище було відзначено, що серед чисел (51) повинне бути (n-m) нулів. Вийшло протиріччя. Теорема 1 доведена.
Наслідок (з теореми 1). Для того щоб алгоритм Данцига був кінцевим, необхідно, щоб шуканий оптимальний план лежав на ребрі багатогранної множини (40) - (41) (передбачається, що задача (39) - (41) невиродженна).
Хоча ця умова і є досить твердим, йому задовольняють, наприклад, всі (невиродженні) задачі наступного виду.
Максимізувати
(56)
при умовах
(57)
(58)
(59)
ціле, (60)
А це важливий клас задач.
Однак наведене в наслідку необхідна умова кінцівки алгоритму Данцига не є достатнім. Дійсно, має місце наступна
Теорема 2. Якщо для деякого оптимального плану x задачі (39) - (42) і деякого плану x задачі (39) - (41) мають місце нерівності
(61)
и
(62)
те алгоритм Данцига не буде кінцевим.
Доказ. Допустимо, що алгоритм Данцига кінцевий. Тоді з (61) треба, що крапка x була відсічена на якійсь (скажемо, р-й) ітерації, так що
(63)
Але з (62) і леми одержимо
(64)
Порівнюючи (63) і (64), одержуємо протиріччя. Теорема 2 доведена.
Отже, спрощений алгоритм Данцига буде кінцевим лише в досить рідких випадках.
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) Деякі з узагальнених задач покриття.
У даний момент відсутнє вичерпне пояснення удач або невдач різних обчислювальних експериментів. Все-таки для задачі комівояжера й задачі теорії розкладів є правдоподібним наступне міркування.
Формулювання цих задач мовою ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ є неприродної. Для задачі порівняно невеликої в природній формулюванні, у моделі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ фігурує велика кількість обмежень і змінних. Можливо, що для цих задач більше перспективними є комбінаторні методи (наприклад, метод галузей і границь для задачі комівояжера). Втім, останнє твердження є спірним, тому що комбінаторні методи дуже чутливі до специфіки задач, введенню додаткових умов і т.п.
Очевидно, успіх у рішенні задач покриття повязаний з тим, що вдалося напасти на клас задач, практично важливих і в той же час успішно розвязуваних. Було б доси?/p>