Дискре́тное программи́рование

Дискре́тное программи́рование (дискретная оптимизация) — раздел математического программирования.

Математическое  программирование - это область математики, разрабатывающая теорию, численные методы решения многомерных задач с ограничениями. В отличие от классической математики, математическое программирование занимается математическими методами решения задач нахождения наилучших вариантов из всех возможных.

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

В противоположность задачам  оптимизации с непрерывными переменными, переменные в задачах дискретного  программирования принимают только дискретные значения, например, целочисленные.

 

Комбинаторная оптимизация – область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. В комбинаторной оптимизации используются как математические подходы, так и методы искусственного интеллекта. Алгоритмы комбинаторной оптимизации, одним из наиболее популярных среди них является метод ветвей и границ, применяются при решении NP-трудных задач, позволяя уменьшать пространство допустимых решений с помощью эффективной процедуры поиска.

В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».

Задачи комбинаторной оптимизации можно решить с помощью методов дискретного программирования. Одними из основных методов решения задач дискретного программирования являются метод ветвей и границ (по существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений) и динамическое программирование(Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.)

 

 

 

 

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

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

Розглянемо без детальних доведень один з наближених методів, що дає назву методу вектора спаду [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). Це такі три точки:

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

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

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

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

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

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

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

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