Основні відомості про дискретне математичне програмування

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

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

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

Запитання для самоконтролю

1. Наведіть основні особливості задач, які розв’язуються методами математичного програмування.

2. Наведіть і поясніть узагальнений аналітичний запис задачі математичного програмування.

3. В чому полягає сутність прямої і зворотної задач математичного програмування?

4. Дайте означення допустимого і оптимального розв’язків задачі математичного програмування.

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

6. Перерахуйте і стисло поясніть основні способи формування цільової функції задачі на підставі частинних показників.

7. Поясніть сутність процесу знаходження паретовських розв’язків задачі математичного програмування (на прикладі задачі з двома частинними показниками).

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

9. Чому значення ресурсів, коефіцієнтів задачі ЛП, як правило, не можуть бути від’ємними?

10. Сформулюйте словами цільову функцію задачі вибору раціональної черговості посадки двох повітряних суден. Чим обумовлені обмеження на значення змінних такої задачі?

11. Поясніть, в чому полягає сутність задачі оптимального розподілу потоку повітряних суден на дві “паралельні” ділянки повітряної траси.

12. Сформулюйте словами цільову функцію і обмеження задачі розподілу повітряних суден за маршрутами (авіалініями).

13. Які задачі лінійного програмування можна розв’язати графічним способом?

14. Наведіть порядок розв’язання задачі лінійного програмування графічним способом.

15. Сформулюйте теорему про розв’язок задачі ЛП як про координати крайньої точки (вершини) області допустимих розв’язків задачі.

16. Скільки змінних задачі ЛП включають до базису у процесі розв’язання задачі ЛП симплекс-методом?

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

18. Поясніть, як у процесі розв’язання задачі ЛП симплекс-методом нерівняння-обмеження перетворюють у рівняння. Наведіть приклади.

19. Чим керуються при виборі змінних першого базису у процесі розв’язання задачі ЛП симплекс-методом?

20. В чому полягає сутність канонічної (ступеневої) форми рівнянь-обмежень задачі ЛП?

21. Поясніть, як у процесі розв’язання задачі ЛП симплекс-методом рівняння-обмеження задачі приводять до канонічної (ступеневої) форми.

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

23. Як у процесі розв’язання задачі ЛП симплекс-методом

перевіряють, чи не є оптимальним даний базисний розв’язок?

24. Як у процесі розв’язання задачі ЛП симплекс-методом встановлюють, яку небазисну змінну доцільно, в першу чергу, включити до базису?

25. Як у процесі розв’язання задачі ЛП симплекс-методом встановлюють, яку змінну доцільно виключити з базису?

26. Наведіть узагальнений алгоритм (послідовність) розв’язання задачі ЛП симплекс-методом.

27. Які задачі нелінійного програмування (НЛП) відносять до задач безумовної і які - до задач умовної оптимізації?

28. Наведіть порядок розв’язання задачі нелінійного програмування способом першої і другої похідних цільової функції.

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

30. Які задачі НЛП можна розв’язати способом множників Лагранжа? Наведіть порядок розв’язання задачі цим способом.

31. В чому полягають особливості розв’язання задач дискретного математичного програмування?