Рішення задач цілочисленного програмування (стр. 5 из 5)
де 
– число елементів множини 
. З визначення чисел 
одержуємо
(49) 
(50)З (48), (49), (50) і (46) маємо
Лема доведена при р=1.
Тепер допустимо, що лема вірна при 
, і доведемо неї при 
:
Лема доведена.
Користуючись лемою, доведемо дві теореми.
Теорема 1. Якщо кожний оптимальний план задачі (39) – (42) містить не менш (m+2) позитивних компонентів, то алгоритм Данцига не буде кінцевим.
Доказ. Допустимо, що на s-й ітерації алгоритму Данцига вийде шуканий оптимальний план
. Розглянемо числа 
(51)Всі вони цілі й серед них повинне бути (n-m) нулів – це небазисні змінні
. Крім того, за умовою серед чисел 
, повинне бути принаймні (m+2) позитивні числа, тобто не більше чим (n-m-2) нулів.По визначенню чисел
звідси треба, що 
а тому що
повинне бути цілим, те 
(52)Але по визначенню чисел
(53)З (52) одержуємо
(54)і по лемі
(55)З (52), (53) і (55) треба, що серед чисел (51) принаймні [1+(m+1)+s] = [m+2+s] позитивних, а отже, не більше чим [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) Деякі з узагальнених задач покриття.
У даний момент відсутнє вичерпне пояснення удач або невдач різних обчислювальних експериментів. Все-таки для задачі комівояжера й задачі теорії розкладів є правдоподібним наступне міркування.
Формулювання цих задач мовою ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ є «неприродної». Для задачі порівняно невеликої в «природній» формулюванні, у моделі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ фігурує велика кількість обмежень і змінних. Можливо, що для цих задач більше перспективними є комбінаторні методи (наприклад, метод галузей і границь для задачі комівояжера). Втім, останнє твердження є спірним, тому що комбінаторні методи дуже чутливі до специфіки задач, введенню додаткових умов і т.п.
Очевидно, успіх у рішенні задач покриття пов'язаний з тим, що вдалося напасти на клас задач, практично важливих і в той же час успішно розв'язуваних. Було б досить цікаво точно охарактеризувати клас задач покриття, добре розв'язуваних по методу відсікання. Це тим більше цікаво, що побудовано приклади узагальнених задач покриття, для яких виникають значні обчислювальні труднощі.
І взагалі, виділення окремих класів ефективно розв'язуваних задач - важлива й цікава проблема.
Висновок
Підведемо деякі підсумки. Метод відсікання перебуває в стадії розвитку й удосконалювання. При реалізації цього методу виникають труднощі, що носять, очевидно, не тільки технічний, але й принциповий характер. У даний момент можна говорити про рішення за допомогою методу відсікання задач не більш ніж середнього розміру (сотні змінних і десятки обмежень).
Найбільш перспективними для подальших досліджень по методу відсікання представляються наступні напрямки:
1) Дослідження будови множин £ц і V(£ц).
2) Дослідження властивостей правильних відсікань.
3) Вказівка нових способів побудови правильних відсікань.
4) Розвиток нових класів алгоритмів методу відсікання (наприклад, прямих алгоритмів).
5) Виділення окремих класів ефективно розв'язуваних задач.
Література
1. Корбут А.А., Финкельштейн Ю.Ю. Дискретне програмування. – К., 2004
2. Лященко І.Н. Лінійне й нелінійне програмування. – К., 2003
3. Санович К.М. Дослідження операцій. - К.,1999.