Тема 3. Задачи о минимальном остове.

Содержание

• Тема 1. Классификация моделей.
• Тема 1. Классификация моделей.
• Основные признаки классификации моделей.
• Область использования.
• Учет в модели временного фактора.
• Способ представления модели.
• Тема 2. Классификация языков компьютерного моделирования.
• Тема 3. Этапы и цели компьютерного математического моделирования.
• Раздел 1. Задачи линейного программирования.
• Тема 1. Математическое программирование. Общий вид задач линейного программирования.
• Формулировка задачи.
• Геометрическая интерпретация задачи линейного программирования.
• Найти минимальное значение линейной функции
• Тема 2. Графический метод решения задач линейного программирования.
• Примеры задач, решаемых графическим методом.
• Обобщение графического метода решения задач линейного программирования.
• Тема 3. Симплекс - метод.
• Каноническая задача лп на максимум.
• Вспомогательная задача лп.
• Алгоритм метода искусственного базиса
• Вспомогательная задача лп.
• Алгоритм метода искусственного базиса.
• Тема 4. Транспортная задача.
• 4.2 Составление опорного плана.
• 4.3 Метод потенциалов.
• Раздел 2. Теория графов.
• Тема 1. Основные понятия теории графов.
• Элементы множества V называются вершинами графа g (или узлами), элементы множества u-его ребрами. Вершины и ребра графа называют также его элементами и вместо VV и u u пишут Vg и ug.
• 1.2 Операции над графами.
• 1.3.Связность графов.
• 1.4 Эйлеровы графы.
• 1.5 Гамильтоновы графы.
• Тема 2. Поиск пути в графе.
• 2.2 Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Дейкстры).
• 2.3 .Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин (алгоритм Флойда).
• 2.4 Путь с минимальным количеством промежуточных вершин (волновой алгоритм).
• 2.5 Нахождение k путей минимальной суммарной длины во взвешенном графе с неотрицательными весами (алгоритм Йена).
• Тема 3. Задачи о минимальном остове.
• 3.1 Деревья.
• 3.1 Построение минимального остовного дерева (алгоритм Краскала).
• 3.1 Деревья.
• 3.1 .Построение минимального остовного дерева (алгоритм Краскала).
• Раздел 3. Динамическое программирование.
• Тема 1. Метод динамического программирования.
• 1.2 Идеи метода динамического программирования
• 1.3 Выбор состава оборудования для технологической линии.
• Исходные данные для примера
• Тема 2. Задача инвестирования.
• Тема 3. Замена оборудования.
• Тема 4. Задача о загрузке.
• 4.2 Рекуррентные соотношения для процедур прямой и обратной прогонки.
• 4.3 Решение задачи о загрузке.
• Раздел 4. Системы массового обслуживания (смо). (8 часов).
• Тема 1. Основные понятия теории массового обслуживания.
• Тема 2. Простейшие смо и нахождение их параметров.
• Перечень характеристик систем массового обслуживания можно представить следующим образом:
• 2. Одноканальная смо с неограниченной очередью
• 3. Одноканальная смо с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания
• 4. Одноканальная смо с произвольным потоком заявок и произвольным распределением времени обслуживания
• Раздел 5. Имитационное моделирование.
• Тема 1. Простейшие задачи, решаемые методом имитационного моделирования.
• Тема 2. Основные понятия теории Марковских процессов.
• Тема 3. Метод Монте – Карло.
• Раздел 6. Прогнозирование.
• Тема 1. Основная идея прогнозирования. Методы прогнозирования
• Тема 2.Теории экспертных оценок.
• Раздел 7. Теория игр.
• Тема 1. Основные понятия теории игр.
• 1. 1 Понятие об играх и стратегиях
• Тема 2. Простейшие методы решения задач теории игр.
• Раздел 8. Элементы теории принятия решений. (2 часа).
• Основные понятия.
• Принятие решений в условиях полной неопределенности
• Принятие решений при проведении эксперимента.
• 2. Принятие решений в условиях полной неопределенности
• 2.1 Максиминный критерий Вальда.
• Критерий равновозможных состояний.
• 3. Принятие решений при проведении эксперимента.
• 3.1. Принятие решений в условиях неопределенности.
• 3.2. Использование смешанной стратегии
• 3.3. Принятие решений в условиях риска