Головна

Історичні відомості про дисципліну.

  1. V2: {{2}} 1.2 Загальні відомості про вагонному комплексі залізничного транспорту
  2. А) Загальні відомості
  3. База даних, що містить відомості про студентів, які беруть участь в науково-дослідних роботах (НДРС), має ___ структуру.
  4. Квиток 4 історичні етапи розвитку філософської думки і її характеристика.
  5. Квиток №15 питання 1 Історичні форми спільності
  6. БЩІЕ ВІДОМОСТІ ПРО газового зварювання та різання
  7. Введемо відомості про наше підприємство

Глава 1. Загальні відомості про завдання дискретної і комбінаторної оптимізації та методи їх вирішення.

Історичні відомості про дисципліну.

У 1947 р Джордж Данциг (Dantzig) розробив симплексний алгоритм для вирішення завдань лінійного програмування (ЛП), опублікований в 1951 р Уже в той час було визнано, що завдання лінійного програмування з'являються при моделюванні багатьох реальних ситуацій, причому симплекс-метод виявився дуже ефективним на практиці.

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

У той час не було відомо загального методу розв'язання задач цього виду, які називаються завданнями змішаного цілочисельного лінійного програмування (ЦЛП).

У 1958 р Ральф Гоморі (Gomory) опублікував невелику статтю про використання симплексного алгоритму з відносно невеликими модифікаціями для побудови кінцевого алгоритму для знаходження оптимального цілочисельного рішення задачі ЦЛП. Гомори показав, як симплексна таблиця може бути використана для отримання нових нерівностей, які виконуються для всіх рішень, які відповідають обмеженням целочисленности, але яким не задовольняє оптимальне (нецелочисленное) рішення задачі ЛП. Вивчення цих нерівностей, іменованих відсіканнями, швидко стало головною областю подальших досліджень як з теоретичних причин, так і з-за перспективності їх використання у вигляді обчислювального інструменту [1].

У 1955 р в статті Гарольда Куна (Kuhn) описаний комбінаторний алгоритм для задачі цілочислового програмування зі спеціальною структурою - задачі про призначення. У цій роботі вперше застосований спеціалізований метод для вирішення завдання зі спеціальною структурою і вперше використаний прямо-двоїстий алгоритм лінійного програмування.

Хофманн і Круськала (Hoffman, Kruskal) в статті 1956 р показали важливість поняття повної унімодулярності для знаходження цілочисельних рішень задач лінійного програмування.

У статті Ленд і Дойг (Land, Doig) в 1960 р був запропонований перспективний і найбільш популярний в даний час метод вирішення завдань цілочисельного програмування - метод гілок і меж. Сучасні вирішувачі використовують гібридні методи відсікань і гілок і меж.

Стаття Едмондс (Edmonds) (1968 г.) описує випадки, для яких комбинаторно описане безліч відсікань, доданих до задачі ЛП, дозволяє отримати целочисленную оболонку.

Важливість поліноміальних алгоритмів для комбінаторних алгоритмів стала ясна на початку 1970-х років у зв'язку з введенням в області теоретичних основ інформатики класів P (поліноміальних) і NP (недетерміністскіх поліноміальних). Фундаментальний результат Кука (Steven Cook) показав, що є безліч так званих NP-повних задач, що володіють такою властивістю, що якщо будь-яка з них була б розв'язана за поліноміальний час, тоді все завдання також були б в класі NP. Стаття Карпа (Richard Karp), опублікована в 1972 році, підкреслила важливість цих результатів для математичного програмування і показала, що велика кількість завдань цілочисельного програмування (ЦП), для яких не було відомо поліноміальних алгоритмів, належать до класу NP-повних задач.

Джеффріон (Geoffrion) в роботі 1974 р показав, як функція Лагранжа може бути використана для отримання релаксації завдання ЦЛП, що дозволило ввести «важкі» обмеження в цільову функцію завдання.

Слід особливо наголосити надто загальні і ефективні при вирішенні ряду конкретних прикладних задач дискретної оптимізації схеми, запропоновані вітчизняними вченими, такі як метод послідовного конструювання, аналізу та відсіву варіантів В. С. Михалевича-Н. З. Шора (Інститут кібернетики НАНУ), Загальна схема глобального рівноважного пошуку (І. В. Сергієнко, В. П. Шило (Інститут кібернетики НАНУ) [15]), послідовних схема В. А. Емелічева (Білоруський державний університет), Локальні алгоритми Ю. І. Журавльова (Обчислювальний центр РАН) [7].

Основні поняття: завдання комбінаторної і дискретної оптимізації, Моделі дискретного програмування. Постановка завдання, приклади.

під завданням дискретної оптимізації (або дискретного програмування - См. [16]) розуміється завдання математичного програмування

 , (1.1)

де  - Кінцеве безліч допустимих рішень.

завдання комбінаторної оптимізації  має вигляд:  , де  для кінцевого безлічі (  - булеан  , Тобто безліч всіх підмножин множини  ).

Введемо подальші визначення.

Задачею лінійного програмування (ЛП) називається наступна задача  або завдання .

Завдання цілочисельного програмування (ЦП) визначається так: .

Завдання частково цілочисельного лінійного програмування (ЧЦЛП) (або змішаного цілочисельного лінійного програмування (СЦЛП)) виглядає наступним чином:

.

Серед завдань дискретної оптимiзацiї виділяються завдання з бінарними або булеві змінними

Можливо виділити наступні основні класи задач дискретної оптимізації [10]:

1. Завдання з неподільних.

2. Екстремальні комбінаторні задачі.

3. Завдання з неоднорідною розривної цільовою функцією.

4. Завдання на некласичних областях.

5. Деякі багатоекстремального завдання.

6. Дискретні завдання у вузькому сенсі слова (знаходження екстремумів на кінцевих множинах).

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

Приклад 1.1. Розглянемо загальну задачу математичного програмування ми не будемо виписувати її формулювання), в якій деяка змінна  підпорядкована додаткової вимоги дискретності, тобто  може прийняти значення тільки з деякого заданого кінцевого безлічі:

 (1.2)

Завдання з умовою дискретності (1.2) можна звести до задачі частково цілочисельного математичного програмування. Саме, введемо додаткові бінарні змінні  і замінимо (1.2) двома умовами:

 (1.3)

,  (1.4)

Зрозуміло, що (1.3) і (1.4) еквівалентні (1.2). Дійсно, відповідно до (1.4) лише одне з  дорівнює одиниці, а тоді з (1.3) ми отримуємо необхідна умова.

Приклад 1.2. Завдання оптимізації з додатковими умовами типу «або - або» (альтернативними умовами) називаються дихотомічними.

Покажемо, як подібні завдання можуть бути зведені до частково цілочисельним за допомогою підстановок, що використовують бінарні змінні.

Формалізуємо виконання умов

 , (1.5)

якщо для функцій  відомі кінцеві нижні межі .

Введемо додаткову бінарну змінну  і замінимо (1.5) двома умовами (1.6), (1.7):

 (1.6)

 (1.7)

Справді, якщо  прийме в рішенні значення 1, то (1.6) зведеться до  а (1.7) - до  ; при  з (1.6) отримаємо  а з (1.7) -

Приклад 1.3. Розглянемо задачу оптимізації з обмеженнями

 (1.8)

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

 (1.9)

де

и  (1.10)

Умови (1.9) і (1.10) забезпечують необхідну.

Приклад 1.4. Розглянемо формалізацію умовних, або логічних обмежень. Саме, нехай необхідно формалізувати умову виду

якщо  то  (1.11)

де и  - Задані функції. Тут передбачається також, що для функції  відома її верхня межа  , А для функцій и  - Їх нижні межі и  . Умовне обмеження (1.11) можна переписати у вигляді альтернативного умови

або  (1.12)

або  (1.13)

Ввівши бінарну змінну  , Замінимо умови (1.12), (1.13) наступним і умовами

Приклад 1.5. Розглянемо задачу оптимізації з неоднорідною розривної цільовою функцією

 (1.14)

при обмеженнях

 (1.15)

 (1.16)

де

 - Розривна функція.

Припустимо, що задані ще верхня межа для змінних:

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

при обмеженнях

вологості ґрунту та інтенсивності опадів | Завдання про покриття і упаковці


Прикладні задачі покриття | Приклад. Проектування системи відеоспостереження | Завдання упаковки вершин | Завдання пошуку стійкого безлічі в графі | Питання про упаковці контейнера | комбінаторні аукціони | Завдання про ранці | завдання розміщення | Задача про призначення | Завдання визначення оптимального розміру партії продукції |

© 2016-2022  um.co.ua - учбові матеріали та реферати