- •Математические модели и их виды. Классификация моделей
- •Экстемум функций многих переменных. Линии уровня. Градиент. Условный экстремум
- •Постановка и свойства задачи линейного программирования. Геометрическая интерпретация.
- •Симплекс- метод решения задачи линейного программирования
- •Двойственная задача линейного программирования, ее интерпретация и свойства
- •Транспортная задача и ее математическая модель. Определение опорного плана транспортной задачи
- •Определение оптимального плана транспортной задачи методом потенциалов. Приемы решения методом потенциалов транспортных задач
- •Геометрическая и экономическая интерпретация задач нелинейного программирования. Метод множителей Лагранжа. Возможности численного решения нелинейных и целочисленных задач
- •Основные понятия и общая характеристика задач динамического программирования, их геометрическая и экономическая интерпретация. Нахождение решение задач методом динамического программирования
- •Оптимизационные задачи, решаемые при помощи графов. Алгоритмы на графах
- •Нахождение максимального и минимального пути в графе. Решение транспортной задачи с помощью графов
- •Основные понятия теории массового обслуживания. Компоненты и классификация моделей систем массового обслуживания
- •Определение характеристик систем массового обслуживания. Марковский процесс. Уравнения Колмогорова
- •Одноканальные и многоканальные смо с пуассоновским входным потоком и экпотенциальным распределением длительности обслуживания
- •Основные количественные характеристики простейшего потока.
- •Распределение интервала времени t между произвольными двумя соседними событиями простейшего потока.
- •Одноканальная смо с отказами и ее характеристики
- •Многоканальная смо с отказами и ее характеристики
- •Одноканальная смо с ожиданием и его характеристики. Формула Литтла
- •Многоканальное смо с ожиданием и ее характеристики. Формула Литтла
- •Простейшие задачи решаемые методом имитационного моделирования. Теоретические основы метода имитационного моделирования
- •Моделирование смо с использованием метода Монте- Карло
- •Имитация процессов, происходящих во времени. Основная идея и методы прогнозирования. Количественные методы прогноза. Прогнозирование временных рядов. Модель линейной регрессии
- •Предмет теории игр, основные понятия. Матричные игры. Цны, доминирующие и оптимальные стратегии игр. Принцип минмакса. Решение задач теории игр в чистых стратегиях
- •Стратегические игры в смешанных стратегиях. Основная теорема теории игр. Решение задачи в смешанных стратегиях методами линейного программирования
- •Оценка сложных систем в условиях неопределенности. Матрица рисков. Критерии: Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.
Оптимизационные задачи, решаемые при помощи графов. Алгоритмы на графах
Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
Применение теории графов
В химии (для описания структур, путей сложных реакций, правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
В информатике и программировании (граф-схема алгоритма)
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
В экономике
В логистике
В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).
Оптимальный путь можно выявить полным перебором, просчитав длины всех путей и сравнив их между собой. Посчитаем, сколько различных путей существует в нашей простой задаче. Из А в каждую из точек – a, b, c – ведет по одному пути. В каждую из точек d, f, h ведут три пути, а всего в конце второго шага имеется 9 путей. На последнем шаге количество путей не увеличивается. Конечно, можно сравнить по всей длине 9 путей. Но с ростом количества шагов и количества точек на каждом шаге число вариантов резко возрастает. Пусть m – число шагов, n – число точек на каждом шаге. В конце первого шага будет n вариантов (по одному на каждую точку). В конце второго шага будет n2. Т. к. на последнем шаге число вариантов не увеличивается, всего будет вариантов. При значительных величинах m и n перебор всех вариантов становится невозможным даже на компьютере.
Основная идея динамического программирования заключается в сокращении перебора за счет отбрасывания бесперспективных путей. В любой точке, где сходится несколько путей, их можно сравнить между собой по длине, оставить лучший, запомнить его и его длину, а остальные отбросить. На рис. 7.2. в точке d сходятся 3 пути (изa, b и c), для каждого из них вычисляется длина, лучший путь запоминается, а два других отбрасываются.
Алгоритм расчета следующий.
1. Делается первый шаг от начала.
2. Берется первая точка а.
3. Вычисляется . Запоминаются Fa и точка А – откуда пришел лучший путь (он здесь единственный).
4. Берется следующая точка b и для нее проделываются все те же процедуры, что и для а.
5. После расчетов для точки c делается следующий шаг.
6. Берется точка d. В нее входят 3 пути. Для каждого из них вычисляется Запоминается как Fd меньшая из вычисленных длин и точка, откуда ведет путь. Пусть и , тогда , запоминается точка с. Это значит, что путь через точку с в d сохраняется для дальнейшего анализа, а пути в d через a и b отбрасываются.
7. После рассмотрения очередной точки осуществляется переход к следующей точке на данном шаге. Когда на рассматриваемом шаге все точки закончились, делается следующий шаг и т.д.
8. В точке В из трех сходящихся в ней путей выбирается лучший.
9. Проходя в обратном направлении, восстанавливают оптимальный путь. Напр., в точке В лучшим оказался путь из d, а в d – из c, а в c ведет единственный путь из А. Тогда оптимальный путь проходит через точки A–c–d–B.
При таком процессе в данном примере приходится сравнивать 12 путей (по 3 на каждую из точек d, f, h, В). Но сравнения проводятся на одном шаге, а не на всей длине, как это было бы при полном переборе. Перебор существенно сокращается.
В литературе распространенно утверждение, что при решении задач динамического программирования анализ вариантов нужно проводить от конца к началу. Это утверждение ошибочно. Можно проводить анализ как от начала к концу, так и наоборот. Посмотрим на рис. 7.2. Пусть оптимальный путь – A–c–d–B. Проведем анализ от конца.
Первый шаг – от В назад. Для каждой точки d, f и h оставляется по одному условно оптимальному пути, выходящему из нее: dB, fB и hB соответственно. На втором шаге назад рассматриваются пути, проходящие через точки a, b, c и оставляется по одному условно оптимальному пути. Так как дуга cd (по условию) входит в оптимальный путь, то для точки c остается условно оптимальный путь cd. На последнем этапе сравниваются пути, выходящие из точки А, т.к. Ac входит в оптимальный путь, то будет оставлена дуга Ac, а весь оптимальный путь выявится как A–c–d–B.
Оптимальный путь можно рассчитывать от начала к концу, и наоборот. Если в расчете нет ошибок, результат будет одинаковым. Т. к. длины дуг неизменны, длина оптимального пути не зависит от порядка его расчета.