Вступ

Для NP-повної задачі ще нікому не вдавалося створити швидкий алгоритм розв'язання. Мабуть, це неможливо, хоча це твердження поки що не доведене. Однак на практиці такі задачі дуже часто виникають і стає необхідним розв'язувати їх. До таких задач відноситься й задача про рюкзак, яка входити до класу задач комбінаторної оптимізації. Вона має широке практичне застосування в таких галузях як економіка, прикладна математика, криптографія та ін. Як і для будь-якої іншої задачі оптимізації для задачі про рюкзак може бути застосований метод повного перебору. Однак проблема полягає в тому, що цей метод прийнятний лише для розв'язання задач малої розмірності, що до речі для деяких реальних невеликих даних може цілком вистачити. До того ж подібний алгоритм може бути удосконалений шляхом відкидання недопустимих, з крапки зору обмежень задачі, розв'язків або шляхом розбиття задачі на підзадачі або не розглядаючи одні й ті ж самі допустимі розв'язки декілька разів. Та незважаючи на такі покращення для великих даних, згадані алгоритми займають дуже багато години. Тому враховуючи велике практичне значення, розв'язання оптимізаційних задач та задачі про рюкзак зокрема, актуальним є розробка швидких алгоритмів, які б надавали хоча б наближені розв'язки таких задач. Цю задачу добрі вирішують сучасні математичні методи, у яких закладені принципи природних механізмів прийняття рішень. Сьогодні такі методи отримали назву «Природні обчислення» та активно вивчаються та розробляються вченими, з'являється багато публікацій на дану тему, однак не дивлячись на це, для українських спеціалістів такі методи оптимізації поки що залишаються невідомими. Наукова проблема дослідження полягає в застосуванні наближених методів розв'язання, зокрема методів напрямку природних обчислень, для задачі про рюкзак. Загальною метою дослідження є визначення особливостей застосування методів природного обчислення для отримання наближених розв’язків оптимізаційної задачі про рюкзак. Об’єкт дослідження – методи розв'язання оптимізаційних задач. Предмет дослідження – застосування наближених методів розв'язання для задачі про рюкзак. Позначка, проблема та предмет дослідження визначили його задачі: 1. Аналіз літератури з проблеми дослідження. 2. Аналіз точних методів розв'язання задачі про рюкзак, дослідження пов'язаних із цим проблем. 3. Аналіз наближених методів розв'язання задачі про рюкзак, визначення особливостей застосування даних методів та їх можливостей. 4. Розробка генетичного алгоритму для задачі по рюкзак. 5. Апробація розробленого алгоритму. При вирішенні поставлених задач використовувались методи дослідження: – теоретичний аналіз; – розробка алгоритму; – проведення обчислювального експерименту.