- •1. Теория графов
- •1.1 Остовные деревья минимального веса.
- •Алгоритм Прим
- •Алгоритм Краскал
- •1.2 Нахождение кратчайших путей между двумя заданными вершинами. Алгоритм Дийкстры
- •Алгоритм Дийкстры
- •Модифицированный алгоритм Дийкстры
- •1.3 Нахождение кратчайших цепей между всеми парами узлов в сети
- •Алгоритм Флойда (Floyd r. W.)
- •Модификация алгоритма Флойда
- •1.4 Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона
- •Алгоритм Форда-Фалкерсона
- •1.5 Обобщенные задачи о потоке
- •1.5.1 Построение потока в сети с двойным ограничением потока по дугам
- •1.5.2 Построение потока в сети с пропускными способностями узлов
- •1.5.3 Построение потока в сети с несколькими источниками-стоками
- •1.5.4 Построение потока в сети с неориентированными ребрами
- •1.6 Определение потока заданной величины минимальной стоимости. Алгоритмы Басакера-Гоуэна, Клейна
- •Алгоритм Басакера-Гоуэна (Basaker r.G., Gowen p.J)
- •Алгоритм Клейна (Klein m.)
- •2 Сетевое планирование
- •2.1 Построение сетевых моделей
- •2.2 Расчет и анализ сетевых моделей
- •Задача №1
- •Задача №2
- •I. Поиск критических путей
- •II. Поиск резервов работ
- •Правило №2.1
- •3 Линейное программирование
- •3.1 Примеры задач лп
- •3.2 Свойства решений задач линейного программирования
- •3.3 Двумерные задачи линейного программирования. Графический метод решения. Исследование на разрешимость
- •3.3.1 Построение области допустимых решений целевой функции f.
- •3.3.2 Построение прямой уровня
- •3.3.3 Максимизация целевой функции f
- •3.4 Симплекс-метод.
- •3.4.1 Построение начального опорного плана.
- •3.4.2 Симплексные таблицы
- •3.4.3 Примеры решения задач симплекс-методом
- •4. Теория двойственности в линейном программировании
- •4.1 Понятие двойственности. Построение пары взаимно двойственных задач
- •4.2 Теоремы двойственности и их экономическое содержание
- •4.3 Анализ решения задач линейного программирования
- •5. Транспортная задача
- •5.1 Постановка транспортной задачи в матричной форме. Построение исходного опорного плана
- •5.2 Метод потенциалов
- •5.3 Дополнительные условия в транспортных задачах.
- •6. Дискретное программирование.
- •6.1 Метод Гомори для решения задачи целочисленного линейного программирования
- •7. Динамическое программирование
- •7.1 Многошаговые процессы в динамических задачах
- •7.2 Принцип оптимальности и рекуррентные соотношения
- •7.3 Вычислительная схема динамического программирования
- •7.4 Оптимальное распределение средств на расширение производства
- •8. Матричные игры
- •8.1 Парные матричные игры с нулевой суммой
- •8.2 Платежная матрица
- •Нижняя и верхняя цена игры
- •8.3 Смешанные стратегии
- •8.3 Решение матричной игры сведением к задаче линейного программирования
- •8.4 Решение матричной игры графическим методом
- •8.5 Приближенный метод решения матричных игр
- •Практические работы Практическая работа №1 Построение остовного дерева графа. Нахождение найкратчайшего расстояния между заданными вершинами графа
- •Практическая работа №2 Нахождение наикратчайших расстояний между всеми парами вершин графа. Алгоритм Флойда.
- •Практическая работа №3
- •Практическая работа №4 Нахождение потока заданной величины минимальной стоимости. Алгоритм Басакера-Гоуэна
- •Практическая работа №7 Оптимизация проекта по времени.
- •Практическая работа №8
- •Практическая работа №9 Оптимизация целевой функции с помощью двухфазного симплекс метода.
- •Практическая работа №10 Решение двойственных задач. Экономическая интерпретация задач линейного программирования.
- •Практическая работа №11 Решение транспортных задач.
- •Практическая работа №12 Дополнительные условия в транспортных задачах
- •Практическая работа №13 Метод Гомори для решения задачи целочисленного линейного программирования.
- •Практическая работа №14
- •Практическая работа №15 Решение матричных игр в чистых стратегиях
- •Практическая работа №16 Графический метод решения матричных игр.
- •Каркас минимального веса. Метод р. Прима.
- •Кратчайшие пути
- •Лабораторная работа №2 Кратчайшее расстояния от заданной вершины до всех остальных вершин графа.
- •Алгоритм Дийкстры.
- •Пути в бесконтурном графе.
- •Лабораторная работа №3 Кратчайшие пути между всеми парами вершин графа.
- •Алгоритм Флойда.
- •Лабораторная работа №4 Построение потока максимальной мощности.
- •Потоки в сетях.
- •Метод построения максимального потока в сети.
- •Лабораторная работа №5 Симплекс метод
- •Лабораторная работа №6 Транспортная задача
- •Список литературы
СИСТЕМНЫЙ АНАЛИЗ
И МОДЕЛИРОВАНИЕ
методическое пособие
МИНСК 2009
Министерство образования республики беларусь
Учреждение образования
«Минский государственный высший
радиотехнический колледж»
СИСТЕМНЫЙ АНАЛИЗ И МОДЕЛИРОВАНИЕ
Методическое пособие
для студентов специальности 1-08 01 01 07
«Профессиональное обучение. (Информатика)»
для учащихся специальности 2-40 01 01
«Программное обеспечение информационных технологий»
МИНСК 2009
Рекомендовано к изданию кафедрой информатики и Научно-методическим советом Учреждения образования «Минский государственный высший радиотехнический колледж»
С о с т а в и т е л и
Г. Н. Соловей, ассистент кафедры информатики
С. Н. Кудина, ассистент кафедры информатики
И. Г. Смолер, ассистент кафедры информатики
Р е ц е н з е н т
Ю. А. Скудняков, зав. кафедрой информатики МГВРК, канд. техн. наук, доцент
Системный анализ и моделирование : методическое пособие для студентов специальности 1-08 01 01 07 «Профессиональное обучение. (Информатика)» для учащихся специальности 2-40 01 01 «Программное обеспечение информационных технологий» / сост. Г. Н. Соловей, С. Н. Кудина, И. Г. Смолер – Мн. : МГВРК, 2009. – с.
Цель пособия – обеспечить учащихся и студентов необходимым теоретическим и практическим материалом, позволяющим самостоятельно решать задачи с использованием основных алгоритмов курса «Системный анализ и моделирование»
Предназначено для учащихся, студентов и преподавателей колледжа.
Предисловие
Учебная дисциплина «Системный анализ и моделирование» занимается исследованием, моделированием сложных систем различной природы: технических, экономических, экологических. При этом проводится исследование, как отдельных элементов системы, так и всей системы в целом.
Обязательным элементом при проведении современных системных исследований является использование вычислительной техники.
Результатом системных исследований является принятие конкретных решений, обеспечивающих оптимальное функционирование системы, выдача рекомендаций для эффективного использования полученных результатов на практике.
Данное учебное пособие предназначено для учащихся и студентов ……специальностей, специализирующихся в области разработки и использования информационных технологий для решения широкого круга экономических задач, в том числе – связанных с моделированием экономических процессов.
В пособии представлены разделы, посвященные построению математических моделей для решения ряда экономических задач. В результате изучения данного пособия учащиеся истуденты приобретают навыки построения экономико-математических моделей, их использования для объяснения поведения исследуемых экономических показателей, и их взаимосвязи.
В учебном пособии представлены следующие разделы одноименной учебной дисциплины: теория графов, линейное программирование, теория двойственности, транспортная задача, дискретное программирование, динамическое программирование, матричные игры.
Данное пособие содержит материал для подготовки и проведения практических работ.
Для учащихся и студентов, стремящихся достичь высокого профессионального уровня в области программирования, предлагается лабораторный практикум, реализация задач которого возможна на языках программирования высокого уровня: Pascal, Delphi, Си.
1. Теория графов
Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение, как в программировании, так и в моделировании. Это связано с тем, что теория графов предоставляет удобный язык для описания программных моделей. Логически упорядоченная система специальных терминов и обозначений теории графов позволяет просто и доступно описывать сложные задачи.
Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. Например, задача о Кенигсбергских мостах (Эйлер, 1736 г.), задача о трех домах и трех колодцах (К. Куратовский, 1930 г.), задача о четырех красках (Апель и Хекен, 1976 г.). Решение некоторых задач «программным путем» является прецедентом, породившим бурную дискуссию, которая до настоящего времени еще незакончена.
1.1 Остовные деревья минимального веса.
Алгоритмы Прим, Краскал.
Определение. Пусть - неориентированный связный граф. Любой связный подграф , содержащий все вершины графа и не имеющий циклов (то есть являющийся деревом) называется остовом или остовным деревом.
Постановка задачи. Имеется связный граф, каждому ребру которого поставлено в соответствие неотрицательное число, называемое весом ребра. Требуется найти остовное дерево минимального веса (вес дерева равен сумме весов ребер, входящих в него).
Алгоритм Прим
Шаг 1. На первом шаге в качестве подграфа выбирается граф, вершинами которого являются вершины графа , имеющие минимальный вес.
На каждом последующем шаге к уже построенному графу добавляется одно ребро.
Шаг k. Если граф уже построен, то граф получается из добавлением ребра l, обладающего следующими свойствами:
l инцидентно какому-либо ребру графа ;
при добавлении l к графу не образуется циклов;
l имеет минимальный вес среди ребер, удовлетворяющих условиям 1) и 2).
Теорема. Пусть G = (V, E) и V = n. Тогда граф - остовное дерево минимального веса для графа G.
Алгоритм Краскал
Шаг 1. Тот же, что и в алгоритме Прим.
Шаг k. Если граф уже построен, то граф получается из добавлением ребра l, обладающего следующими свойствами:
при добавлении l к графу не образуется циклов;
l имеет минимальный вес среди ребер, удовлетворяющих условию 1).
Пример. Дан граф с заданными весами ребер (рис. 1.1). Найти остовное дерево минимального веса.
Рис. 1.1
Решение
Приведем два решения с помощью алгоритмов Прим и Краскал.
1) С помощью алгоритма Прим получаем, например, такое остовное дерево минимального веса (рис. 1.2).
Последовательность выбираемых ребер:
(a, b), (a, f), (a, e), (e, q), (q, h), (h, d), (h, c).
Вес дерева: 1+2+2+1+2+1+4=13.
Рис. 1.2
2) С помощью алгоритма Краскал получаем, такое остовное дерево минимального веса (рис.1.3).
Рис. 1.3
Последовательность выбираемых ребер: (a, b), (d, h), (e, q), (q, h), (a, f), (a, e), (b, c).
Вес дерева: 1+2+1+1+2+2+3+3=14.