Методи оптимізації та дослідженні операцій

1. Задача лінійного програмування. Її властивості.
2. Геометрична інтерпретація задачі лінійного програмування та графічний метод її розв’язку.
3. Симплекс-метод.
4. Метод штучного базису.
5. Двоїстість в лінійному програмуванні.
6. Двоїстий симплекс-метод.
7. Транспортна задача та її властивості.
8. Методи знаходження початкового базисного розв’язку в транспортній задачі.
9. Метод потенціалів для транспортної задачі.
10. Задача про оптимальний потік та її розв’язування.
11. Задача про максимальний потік та метод Форда-Фалкерсона.
12. Перший алгоритм Гоморі для повністю цілочислових задач та його обґрунтування.
13. Другий алгоритм Гоморі для частково цілочислових задач.
14. Алгоритм Дальтона-Ллевеліна для задач дискретного програмування.
15. Алгоритм Лонд-Дойга для задач цілочислового програмування.
16. Метод гілок та меж і його обґрунтування.
17. Матричні ігри. Розв’язування в чистих стратегіях. Сідлова точка.
18. Мішані стратегії в матричних іграх. Теорема про мінімакс.
19. Зв’язок матричної гри з парою двоїстих задач лінійного програмування.
20. Розв’язування матричних ігор графічно та методом Брауна-Робінсона.
21. Поняття про методи нелінійного програмування. Метод найшвидшого спуску. Метод штрафних функцій. Метод проектування узагальнених градієнтів.
22. Опукле програмування.
23. Розв’язування задачі квадратичного програмування на основі знаходження сідлової точки функції Лагранжа.
24. Задача про призначення та її розв’язування угорським методом.

Типові задачі

1. Записати необхідні і достатні умови існування сідлової точки для функції Лагранжа для задачі:

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

.

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

.

4. Використовуючи метод штрафних функцій знайти максимальне значення функції при умовах:

.

Зробити 2 перші ітерації.

5. Використовуючи метод штрафних функцій знайти мінімальне значення функції при умовах:

.

Зробити 2 перші ітерації.

6. Одна з пари двоїстих задач лінійного програмування для матричної гри з ненульовими елементами розв'язана симплекс-методом. Наведена остання симплекс-таблиця. Знайти стратегії гравців та ціну гри.

і	Базис
			1/3	1/2			2/3
			1/3					-2
				1/3			-1	-1
		x	2/3	1/2			2/3

7. Знайти градієнтним методом мінімальне значення функції . За вихідну точку взяти точку (0, 0) . Використати метод найшвидшого спуску. Виконати дві перші ітерації.

8. Методом гілок та меж знайти найкоротший шлях з вершини 1 до вершини 4.

9. Розв'язати угорським методом задачу про призначення з матрицею ефективності С.

.

10. По останній симплекс-таблиці розвיязку допоміжної ЗЛП записати відсікання Дальтона-Левеліна і зробити один перерахунок симплекс-таблиці двоїстим симплекс-методом.

і	Базис				-1
		-1	3,4			-0,6		1,2
			1,8			2,2		-2
			3,1			-0,5