ПИТАННЯ ДО ЗАЛІКУ З МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ

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. Порівняльна характеристика основних методів розв’язання ЗЦЛП (методів перерізу Гоморі та методу гілок і границь).

Словник

ТЕРМІНИ     ВИЗНАЧЕННЯ

АНАЛІЗ НА ЧУТЛИВІСТЬ АНАЛІЗ (МОДЕЛЕЙ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ) НА ЧУТЛИВІСТЬ являє собою дослідження впливу зміни вихідних параметрів моделі на її оптимальний розв’язок.

БУЛЕВІ ЗМІННІ      БУЛЕВІ ЗМІННІ – змінні, що можуть набувати одне з двох значень: нуль або одиниця.

ДВОЇСТА ЗАДАЧА

          ДВОЇСТА ЗАДАЧА – допоміжна задача математичного програмування, що формулюється з умов вихідної (прямої) задачі.

ДВОЇСТІ ОЦІНКИ (ДИВ. ТАКОЖ ТІНЬОВІ ЦІНИ)

          ДВОЇСТІ ОЦІНКИ (ДИВ. ТАКОЖ ТІНЬОВІ ЦІНИ) – величини, що характеризують приріст (додатній або від’ємний) значення цільової функції внаслідок збільшення використання відповідного ресурсу на одиницю.

ЕКСТРЕМУМ          ЕКСТРЕМУМ – мінімальне або максимальне значення функції. В області її визначення.

ЗАДАЧА З ПОСЛАБЛЕНИМИ ОБМЕЖЕННЯМИ         ЗАДАЧА З ПОСЛАБЛЕНИМИ ОБМЕЖЕННЯМИ – задача, що використовується як допоміжна при розв’язанні задачі цілочисельного програмування. Відрізняється від останньої тим, що не містить умов цілочисельності змінних.

ЗАДАЧА «ПРО ПРИЗНАЧЕННЯ» ЗАДАЧА «ПРО ПРИЗНАЧЕННЯ» - різновид транспортної задачі, що має на меті визначення найбільш вигідних призначень працівників на робочі місця.

ЗАДАЧА МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ        ЗАДАЧА МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ – це оптимізаційна задача, що зводиться до задачі знаходження мінімуму або максимуму функції декількох змінних в обмеженій області її визначення.

ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ          ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ – різновид задачі математичного програмування, що містить у своєму складі тільки лінійні функції.

МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ      МАТЕМАТИЧНЕ ПРОГРАМУВАННЯ – математичний аппарат, що застосовується для розв’язання задач відповідного типу.

МЕТОД ГАУСА

          МЕТОД ГАУСА – метод розв’язання систем лінійних рівнянь, який, у свою чергу, покладено в основу універсального (симплексного) методу розв’язання задач лінійного програмування.

МЕТОД ГІЛОК І ГРАНИЦЬ           МЕТОД ГІЛОК І ГРАНИЦЬ – метод розв’язання задач цілочисельного лінійного програмування.

МЕТОД МІНІМАЛЬНОЇ ВАРТОСТІ, МЕТОД ПІВНІЧНО-ЗАХІДНОГО КУТА

          МЕТОД МІНІМАЛЬНОЇ ВАРТОСТІ, МЕТОД ПІВНІЧНО-ЗАХІДНОГО КУТА  – методи побудови початкового розв’язку транспортної задачі.

МЕТОД ПОТЕНЦІАЛІВ

          МЕТОД ПОТЕНЦІАЛІВ – метод, що застосовується для перевірки розв’язку транспортної задачі на оптимальність та вибору змінної для включення до базису.

МЕТОД ФЛАДА      МЕТОД ФЛАДА – метод розв’язання так званої задачі «про призначення».

ОПТИМІЗАЦІЯ       ОПТИМІЗАЦІЯ – відшукання екстремуму функції в обмеженій області.

ПЕРЕРІЗ ГОМОРІ   ПЕРЕРІЗ ГОМОРІ – обмеження, що відсікає від області допустимих розв’язків задачі з послабленими обмеженнями підобласть, що не містить цілочисельних розв’язків.

ПОТЕНЦІАЛИ        ПОТЕНЦІАЛИ – допоміжні змінні

РОЗПОДІЛЬЧИЙ МЕТОД

          РОЗПОДІЛЬЧИЙ МЕТОД – метод, що застосовується при розв’язанні транспортної задачі для визначення змінної, що підлягає виключенню з базису, та переходу до нового, покращеного розв’язку.

СИМПЛЕКСНИЙ МЕТОД СИМПЛЕКСНИЙ МЕТОД – універсальний метод розв’язання задач лініійного програмування

ТІНЬОВІ ЦІНИ        див. ДВОЇСТІ ОЦІНКИ

ТРАНСПОРТНА ЗАДАЧА  ТРАНСПОРТНА ЗАДАЧА – різновид задачі лінійного програмування із специфічною структурою. Спрямована на відшукання таких закріплень постачальників продукції за її споживачами, що забезпечать мінімум сумарних транспортних витрат.