Тема 6. Задачи оптимизации на графах

Основные понятия теории графов. Типы графов. Способы задания графа, орграфа. Задача о кратчайшем пути между вершинами графа. Эйлеровы и гамильтоновы графы. Построение минимального остовного дерева. Формулировка задачи о коммивояжере. Примеры построения минимального гамильтонового цикла. Сетевой график. Задача сетевого планирования. Основные требования к сетевому графику. Ранние и поздние сроки наступления событий. Критическое время. Критический путь. Ранние и поздние сроки начала и окончания работ. Алгоритм вычисления временных характеристик.

Вопросы для самопроверки

1. Что такое в теории оптимальных решений граф и орграф?

2. Какие способы задания графа вы знаете?

3. Что такое нагруженные и ненагруженные графы?

4. Что такое кратчайший путь между вершинами графа?

5. Как определить расстояния между двумя вершинами ненагруженного графа?

6. Как определить расстояния между двумя вершинами нагруженного графа?

7. Что такое циклы и цепи Эйлера?

8. Сделайте постановку задачи о коммивояжере.

9. Что такое циклы и цепи Гамильтона?

10. Приведите алгоритм построения минимального остовного дерева.

11. Какие основные числовые характеристик графа опредляются?

Тема 7. Теория игр.

Игра как модель конфликтной ситуации. Платежная матрица. Игра с седловой точкой. Решение игры графическим способом. Приведение матричной игры m × n к паре двойственных задач. Упрощение и графическое решение игр. Игры в условиях риска. Понятие игры «с природой».

Вопросы для самопроверки

1.Что является целью по теории игр?

2.Что такое стратегия игрока?

3.Что такое платежная матрица?

4.Как определить верхнюю и нижнюю цену игры? Каково соотношение между ними?

5.Какая игра имеет седловую точку?

6.Что означает решение игры в чистых стратегиях?

7.Что такое оптимальная смешанная стратегия?

8.Сформулируйте основную теорему теории игр – теорему Фон-Неймана.

9.Как можно графически решить игру?

10. На чем основана связь матричной игры и ЗЛП?

11. В чем отличие игр с природой?

12. Перечислите основные критерии решения игр с природой.

Тема 8. Принятие оптимальных решений в условиях риска и неопределенности

Понятие стохастического программирования. Общая постановка задачи оптимального принятия решения в условиях риска. Общая постановка задачи принятия оптимального решения в условиях неопределенности. Матрица вероятных исходов. Алгоритм принятия решения в условиях риска. Основные критерии принятия решения в условиях неопределенности. Критерий Лапласа. Критерий Гурвица. Критерий Сэвиджа. Минимаксный критерий.

Вопросы для самопроверки

1. Сформулируйте задачу принятия решений в условиях неопределенности

2. Сформулируйте задачу принятия решений в условиях риска

3. Алгоритм принятия решения по критерию Вальда.

4. Алгоритм принятия решения по критерию Сэвиджа.

5. Алгоритм принятия решения по критерию Гурвица.

6. Алгоритм принятия решения по критерию Лапласа.

Поиск по сайту: