lign="justify"> .4 Тип і версія необхідної операційної системи.
Для виконання програми необхідна операційна система MS-DOS 3.0 і вище.
4. Алгоритм методу
Задача про ранці.
Турист готується до тривалого переходу. Він може нести вантаж вагою b, який може включати n типів предметів. Кожен окремий предмет типу j важить a [j] (j = 1, n), а корисність його використання в переході оцінюється числом c [j]. Необхідно визначити, скільки предметів кожного типу турист повинен покласти в рюкзак, щоб сумарна цінність спорядження була максимальною. Формальна запис завдання має наступний вигляд:
,. (3.3)
До задачі такого роду в першому наближенні може бути зведена завдання комплектації обладнанням багатоцільового літального апарату.
Метод лексикографічного неявного перебору (мЛНП)
Цей метод заснований на процедурі перебору окремих точок області можливих рішень, аналогічної впорядкування слів у словнику і званої тому лексикографічної. Всі змінні вихідної задачі упорядковуються по швидкості зміни. Якщо ніяких додаткових міркувань при цьому не використовувати, то цей порядок буде відповідати природному порядку нумерації змінних вихідної формалізованої запису оптимізаційної завдання: самої медленноменяющейся змінної буде x [1], а самій швидкоплинні - x [n]. B процесі перебору кожна змінна приймає послідовно цілочисельні значення, починаючи з (як правило,) і кінчаючи. Але перш ніж збільшити значення змінної x [j] на одиницю, необхідно перебрати всі можливі комбінації змінних x [j +1],., X [n]. Для цього кожна з них повинна пробігти всі свої значення від найменшого до найбільшого можливого. Розглянемо цю процедуру на прикладі. Нехай n = 3, а змінні x [j] можуть приймати послідовно наступні значення:
x [1] = A, B; x [2] = 1, 2; x [3] = a, b, g.
Тоді при природному впорядкування змінних по швидкості зміни послідовність розглянутих точок буде наступною:
1) A 1 a, 4) A 2 a, 7) B 1 a, 10) B 2 a,
) A 1 b, 5) A 2 b, 8) B 1 b, 11) B 2 b,
) A 1 g, 6) A 2 g, 9) B 1 g, 12) B 2 g.
У самому простому варіанті розглянутого методу зменшення обсягу обчислень здійснюється за рахунок використання так званого "фільтруючого" обмеження. Застосування методу лексикографічного перебору з використанням тільки фільтруючого обмеження не вимагає, як це буде видно з подальших міркувань, виконання умов лінійності цільової функції і обмежень задачі цілочислового програмування. Однак ми будемо розглядати саме цей випадок, оскільки ряд додаткових можливостей скорочення обсягу обчислень реалізуються тільки для нього. p> Передбачається, що вихідна задача наведена до виду, коли напрям оптимізації цільової функції визначено таким чином:
. (3.30)
Фільтраційне обмеження перший раз мож...
