Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

6.6. Наближені методи. Метод вектора спаду

Розроблення та дослідження наближених алгоритмів є досить перспективним напрямком цілочислової оптимізації. Наближені методи заслуговують на увагу більше з практичного погляду, оскільки, як зазначалося вище, застосування точних методів потребує невиправдано значних витрат часу, тоді як пошук наближеного розв’язку дає змогу суттєво скоротити процес знаходження оптимального плану задачі.

Особливо вдалою в літературі, присвяченій проблемам наближених методів, є така ідея формування наближених алгоритмів розв’язування цілочислових задач. Вибирається початковий допустимий план задачі. З таким можливим варіантом розв’язку пов’язується певна (не дуже широка) множина варіантів, які утворюють окіл початкового варіанта. Перебираючи елементи околу, здійснюється перехід до кращого плану або фіксується локальна оптимальність певного варіанта. В першому випадку процес локального покращання плану продовжується, а в другому здійснюється випадковий вибір наступного плану, який беруть за початок пошуку нового оптимального плану. Отже, подібні методи мають вказувати спосіб визначення околу та механізм випадкового пошуку. Крім того, необхідно також ввести правило, за допомогою якого визначається момент закінчення процесу пошуку наближеного розв’язку.

Розглянемо без детальних доведень один з наближених методів, що дає назву методу вектора спаду [27]. Його розробив І. В. Сергієнко в середині 60-х років. У загальному випадку цей метод дає змогу знаходити локальний мінімум цільової функції, проте, якщо вона має відповідні властивості опуклості, то він приводить до визначення глобального мінімуму.

Допустимо, що розглядається задача цілочислового програмування виду:

(6.24)

за умов:

(6.25)

(6.26)

— цілі числа (6.27)

Перш ніж описувати алгоритм методу, введемо деякі необхідні поняття.

Нехай М — деякий дискретний точковий простір. — множина допустимих планів деякої цілочислової задачі виду (6.24)—(6.27). Введемо метрику в простір М, тобто функцію, що визначає відстань між довільними точками цього простору Х та Y. Позначимо її через . Метрика має задовольняти три аксіоми:

1) аксіому тотожності: за умови, що X = Y;

2) аксіому симетрії: ;

3) аксіому нерівності трикутника:

З аналітичної геометрії відомо, що відстань між точками (функцію можна визначати по-різному. Зокрема, у прямокутній декартовій системі координат це може бути довжина вектора тобто , де — відповідно координати точок X та Y у просторі М.

Нехай деякий допустимий план задачі дискретного програмування. Якщо взяти деяке число то множина всіх точок для яких виконується нерівність називається відкритим околом з центром у точці і радіусом r, а множина всіх точок для яких виконується нерівність називається закритим околом.

Визначимо деякий окіл точки з радіусом r1, такий, щоб крім плану він містив би і інші плани задачі, для чого r1 має бути не меншим від деякої величини R. Далі розглядатимемо лише зазначені околи планів задачі. Визначимо функцію у такий спосіб:

Назвемо вектором спаду функції у деякому околі довільної точки (що є одним з допустимих розв’язків задачі цілочислового програмування такий вектор, компонентами якого є величини , де — плани задачі, що належать околу .

Очевидно, що при невід’ємності всіх компонент вектора спаду в околі точки матимемо для будь-якого значення

Остання нерівність означає, що точка є точкою локального мінімуму функції відносно виділеного околу , тобто:

Якщо ж деякі компоненти вектора спаду будуть від’ємними, то це означає, що не є точкою мінімуму в зазначеному околі, оскільки в деяких точках цього околу функція набуває менших значень. Причому та точка виділеного околу, для якої різниця буде найменшою, визначає напрям найшвидшого спаду (зменшення) цільової функції оскільки Цей очевидний факт і лежить в основі обчислювальної схеми застосування методу вектора спаду.

Ідея методу полягає у визначенні компонент вектора спаду для деякої початкової точки. Якщо всі вони невід’ємні, то точку локального мінімуму знайдено, інакше знаходимо центр нового околу і перевіряємо його компоненти на невід’ємність. Процес пошуку розв’язку є послідовним перебором точок, що зменшують значення цільової функції.

Як правило, на кожному кроці алгоритму (тобто для кожного нового околу) не потрібно обчислювати всі компоненти вектора спаду, а лише частину з них, що дає істотний виграш в обсязі і тривалості обчислень.

Наведемо один з можливих алгоритмів реалізації методу вектора спаду.

1. Вибрати початкову точку Х0 і радіус околу R так, щоб точка Х0 була допустимим планом відповідної задачі цілочислового програмування а окіл був таким, що містить також інші допустимі плани задачі. Цей вибір може здійснюватись випадково з податковою перевіркою виконання зазначених умов.

2. Визначаються компоненти вектора спаду в вибраному околі. Якщо всі його компоненти невід’ємні, то точку локального мінімуму знайдено (тобто задача розв’язана і оптимальним цілочисловим планом є ).

3. Якщо не всі компоненти вектора спаду невід’ємні, то вибираємо компоненту яка має найменше значення і визначає точку , що зменшує значення цільової функції і є центром нового околу.

4. Повертаємось до пункту 2. Процес продовжуємо, поки для деякого всі компоненти відповідного вектора спаду не будуть невід’ємними.

Розв’яжемо цілочислову задачу, використовуючи зміст прикладу 6.1.

Розв’язання. Нехай Вибрана точка є допустимим планом задачі, оскільки задовольняє всі обмеження і умову цілочисловості, а окіл вибраного радіуса містить інші плани задачі, наприклад, точку

Визначаємо точки, які належать означеному околу (рис. 6.6). Це такі три точки:

Визначимо компоненти вектора спаду, ввівши такі позначення:

Найменшою є третя компонента вектора спаду, отже, відповідна їй точка стає центром наступного околу Радіус

У новий окіл будуть входити точки з координатами:

Необхідно обчислити значення компонент вектора спаду для зазначених точок. Однак для трьох точок потрібні величини були розраховані на попередньому кроці, і залишається обчислити компоненти вектора для нових точок.

Після проведення обчислень маємо, що найменшого значення набуває компонента вектора, яка відповідає точці тому наступний цент околу переміщається в нову точку Нехай

Обчислюємо компоненти вектора спаду лише в двох точках околу:

Зіставивши ці значення, визначаємо точку нового центру околу з радіусом Компоненти вектора спаду в цьому околі набувають тільки додатних значень. Отже, процедуру наближення завершено, і ця точка є оптимальним планом цілочислової задачі:

Зауважимо, що метод вектора спаду, як видно з опису реалізації алгоритму, придатний для знаходження цілочислового розв’язку також і нелінійних задач.