Постановка лінійної цілочисленної задачі. Теоретичні основи методів відсікання. Задача з булевими змінними. Перший та другий алгоритми Гомори. Алгоритм Дальтона й Ллевелина. Поняття припустимого й оптимального рішення. Область пошуку екстремума.
Серед практично важливих задач відшукання умовного екстремуму лінійної функції важливе місце займають задачі з вимогою цілочисленності всіх (частини) змінних. Існують різні методи рішення таких задач, і помітне місце серед них займають методи відсікання.Математична модель цієї задачі може бути представлена в такий спосіб: в області, певної умовами Її математична модель у загальному виді записується в такий спосіб: в області, певної умовами До класу задач цілочисленного програмування примикають задачі, у яких умова цілочисленності всіх або частини змінних замінено вимогою дискретності. Математична модель загальної задачі дискретного програмування може бути представлена в такий спосіб: в області, певної умовами Неважко бачити, що умова (2-3) задачі (1-4) і умова (6) задачі (5-7) є часткою случаємо умови (9) задачі (8-10).Відповідну їй задачу без вимоги цілочисленності змінних, тобто задачу (11, 12, 14) назвемо (?, C) - задачею. Порушимо питання: чи не можна рішення (?ц, C) - задачі одержати шляхом рішення якоїсь спеціальним образом побудованої задачі без вимоги цілочисленності змінних і такий, що оптимальні рішення вихідної (?ц, C) - задачі й задачі без вимог цілочисленності змінних будуть збігатися. Якщо умова цілочисленності виконується по всім змінним, то оптимальне рішення (?, C) - задачі є оптимальне рішення (?ц, C) - задачі. Будується додаткове обмеження, що володіє тим властивістю, що з його допомогою відтинається частина області, у якій утримується оптимальне рішення (?, C) - задачі й не втримується жодного припустимого рішення (?ц, C) - задачі. додаткове обмеження повинне відтинати частина області, у якій не втримується припустимих рішень цілочисленної (?ц, C) - задачі, але є знайдене оптимальне рішення нецілочисленної (?, C) - задачі, тобто обмеження повинне мати властивість правильності, що не дозволяє втратити оптимальне рішення вихідної (?ц, C) - задачі.Дальтон і Ллевелин розглядають широкий клас задач - частково дискретні задачі лінійного програмування й стосовно до них модифікують другий алгоритм Гомори. Нагадаємо, що рішенням задачі дискретного програмування будемо називати вектор, координати якого належать ?ц області виду: (27) Якщо x(?k, C) є неприпустимим рішенням задачі (27-30) і , тоді, використовуючи i-ю рядок симплексної таблиці, можна побудувати відсікання, що володіє властивістю правильності по формулах: (31) Нехай в оптимальному рішенні x(?k, C) координата не задовольняє умові (29). Оскільки Nk - множина індексів небазисних змінних xi, які в оптимальному рішенні дорівнюють нулю, то рівність (31) приймає вид і буде негативним відповідно до умови теореми.Але, як показали Гомори й Гофман, кінцівка алгоритму Данцига гарантується лише для дуже вузького класу задач. На прикладі алгоритму Данцига видно, наскільки тонким є питання про побудову правильних відсікань і як обережно варто підходити до різним спрощеним алгоритмам. Нехай x(?r, C)=xr є оптимальним опорним планом задачі (?r, C) і xr не задовольняє умові цілочисленності, Nr - множина індексів, що нумерують небазисні змінні, відповідні xr. Правильне відсікання, що відтинає нецілочисленний оптимум x(?r, C) задачі (?r, C), можна записати в такий спосіб: - Позначимо через упорядковані в порядку зростання компоненти плану x задачі (39) - (41), так що (44)Спробуємо охарактеризувати поводження алгоритмів методу відсікання при рішенні задач цілочисленного лінійного програмування. Числа I і D мають (у середньому) тенденцію до зростання зі збільшенням числа змінних і обмежень, ростом порядку коефіцієнтів задачі й збільшенням заповнювання матриці . Точніше кажучи, досвід, накопичений на задачах ЛІНІЙНОГО ПРОГРАМУВАННЯ, не можна механічно переносити на задачі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ. Для ряду задач оптимальне рішення не вдавалося одержати після багатьох тисяч ітерацій, у той час як інші задачі вирішувалися за кілька десятків ітерацій. Не вдається встановити безпосередній звязок між розмірами задач (тобто числом обмежень m і змінних n) і числом ітерацій: невдачі були зафіксовані навіть для невеликих задач (m?10, n?10), а успіхи - для задач досить великого розміру (m = 215, n = 2600).Метод відсікання перебуває в стадії розвитку й удосконалювання. При реалізації цього методу виникають труднощі, що носять, очевидно, не тільки технічний, але й принциповий характер. У даний момент можна говорити про рішення за допомогою методу відсікання задач не більш ніж середнього розміру (сотні змінних і десятки обмежень).
План
Зміст
Введення
1. Постановка лінійної цілочисленної задачі
2. Теоретичні основи методів відсікання
3. Перший алгоритм Гомори
4. Другий алгоритм Гомори
5. Алгоритм Дальтона й Ллевелина
6. Алгоритм Данцига
7. Деякі висновки
Висновок
Список літератури
Вывод
Спробуємо охарактеризувати поводження алгоритмів методу відсікання при рішенні задач цілочисленного лінійного програмування. Як міра тривалості обчислень можуть розглядатися кількість симплексних ітерацій I і кількість правильних відсікань (додаткових лінійних обмежень) D.
Для першого алгоритму Гомори й різних його узагальнень I і D також тісно звязані між собою (як показує експеримент, у більшості випадків рішення окремої задачі (?, З) вимагає порівняно невеликої кількості симплексних ітерацій).
Переходимо до викладу окремих властивостей алгоритмів методу відсікання.
Числа I і D мають (у середньому) тенденцію до зростання зі збільшенням числа змінних і обмежень, ростом порядку коефіцієнтів задачі й збільшенням заповнювання матриці .
Це явище здається природним, але досвід показує, що в дискретному програмуванні «природне» і «правдоподібне» не завжди виявляється правильним. Точніше кажучи, досвід, накопичений на задачах ЛІНІЙНОГО ПРОГРАМУВАННЯ, не можна механічно переносити на задачі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ.
Насамперед, обертає на себе увага «нерегулярність», «непередбачуваність» поводження алгоритмів методу відсікання. Для ряду задач оптимальне рішення не вдавалося одержати після багатьох тисяч ітерацій, у той час як інші задачі вирішувалися за кілька десятків ітерацій.
Не вдається встановити безпосередній звязок між розмірами задач (тобто числом обмежень m і змінних n) і числом ітерацій: невдачі були зафіксовані навіть для невеликих задач (m?10, n?10), а успіхи - для задач досить великого розміру (m = 215, n = 2600). Можливо, втім, що спроба встановлення подібного звязку - це неправомірне перенесення результатів ЛІНІЙНОГО ПРОГРАМУВАННЯ в область ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ.
Бути може, більше природною характеристикою задачі (?, З) є не число m лінійних обмежень, що задають багатогранну множину ?, а число мц - лінійних обмежень, що задають багатогранну множину V(?)*). Тим часом легко привести приклади, коли при невеликих m і n число мц буде досить велике.
«Нерегулярність» позначається й у наступному факті, поміченому поруч дослідників: іноді вдається істотно скоротити число ітерацій за рахунок перенумерації змінних.
Нарешті, має місце немонотонність наближення псевдоплана Xr до оптимального плану X* - з ростом r відстань ?(Xr, X*) не обовязково зменшується й лише на останній ітерації обовязково стає рівним нулю.
Великий вплив на число ітерацій робить правило вибору рядка, що породжує. Тут також має місце «нерегулярність» - у той час як одне правило приводить до успіху за десятки ітерацій, інше не дає рішення після тисяч ітерацій.
При рішенні задач цілочисленного лінійного програмування по методу відсікання є як успіхи, так і невдачі.
До найбільш успішних робіт варто віднести: 1) Задачі покриття, у тому числі задачі, повязані з мінімізацією булевих функцій.
2) Застосування до задач оптимального кодування.
3) Застосування до задачі оптимального добування інформації з паралельних систем памяті.
Найбільш характерними задачами, для яких мала місце невдача, є: 1) Задачі комівояжера.
2) Задача теорії розкладів.
3) Деякі з узагальнених задач покриття.
У даний момент відсутнє вичерпне пояснення удач або невдач різних обчислювальних експериментів. Все-таки для задачі комівояжера й задачі теорії розкладів є правдоподібним наступне міркування.
Формулювання цих задач мовою ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ є «неприродної». Для задачі порівняно невеликої в «природній» формулюванні, у моделі ЦІЛОЧИСЛЕННОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ фігурує велика кількість обмежень і змінних. Можливо, що для цих задач більше перспективними є комбінаторні методи (наприклад, метод галузей і границь для задачі комівояжера). Втім, останнє твердження є спірним, тому що комбінаторні методи дуже чутливі до специфіки задач, введенню додаткових умов і т.п.
Очевидно, успіх у рішенні задач покриття повязаний з тим, що вдалося напасти на клас задач, практично важливих і в той же час успішно розвязуваних. Було б досить цікаво точно охарактеризувати клас задач покриття, добре розвязуваних по методу відсікання. Це тим більше цікаво, що побудовано приклади узагальнених задач покриття, для яких виникають значні обчислювальні труднощі.
І взагалі, виділення окремих класів ефективно розвязуваних задач - важлива й цікава проблема.Підведемо деякі підсумки. Метод відсікання перебуває в стадії розвитку й удосконалювання. При реалізації цього методу виникають труднощі, що носять, очевидно, не тільки технічний, але й принциповий характер. У даний момент можна говорити про рішення за допомогою методу відсікання задач не більш ніж середнього розміру (сотні змінних і десятки обмежень).
Найбільш перспективними для подальших досліджень по методу відсікання представляються наступні напрямки: 1) Дослідження будови множин ?ц і V(?ц).
2) Дослідження властивостей правильних відсікань.
3) Вказівка нових способів побудови правильних відсікань.
4) Розвиток нових класів алгоритмів методу відсікання (наприклад, прямих алгоритмів).
5) Виділення окремих класів ефективно розвязуваних задач.
