- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
Тема 12. Программирование на сетях
План лекции:
1. Основные понятия теории графов (ТГ)
2. Экстремальное дерево графа
3. Матричные способы задания графов. Упорядочение элементов
орграфа
4. Потоки на сетях. Постановка задачи о максимальном потоке
5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи
о максимальном потоке
1. Основные понятия теории графов
Исторически теория графов, как самостоятельное научное направление возникла из задачи о семи кенигсбергских мостах, соединяющих берега и два острова на реке Преголи (рис. 12.1).
Рис. 12.1
Можно ли пройти по всем семи мостам, не проходя ни по одному из них дважды?
Граф для задачи выглядит следующим образом (рис. 12.2):
Рис. 12.2
Здесь: – берега реки; – острова; линии, соединяющие точки – мосты.
Отрицательное решение этой задачи в 1736г. получено Эйлером. Со временем, результаты теории графов стали находить все более широкое применение, в том числе для решения экономических задач.
Определение 12.1. Теория графов – это раздел математики, основной особенностью которого является геометрический подход к изучению объектов.
Основным объектом теории графов является граф, который определяется заданием двух конечных дискретных множеств:
1) множество вершин ;
2) множество линий связи между ними .
Линии связи называются ребрами, если не указана их ориентация; если же задано направление связи, то - дугами.
Граф, состоящий из дуг, называется ориентированным графом (орграфом), а образованный ребрами – неориентированным.
Например, 1) ориентированный граф (рис. 12.3)
Рис. 12.3
2) неориентированный граф (рис 12.4)
Рис. 12.4
Вершины и , связанные дугой/ребром , называются концевыми вершинами этой дуги/ребра. Если концевые вершины совпадают, то дугу/ребро называют петлей. Дуги/ребра с одинаковыми концевыми вершинами называются параллельными. Граф без петель и параллельных линий связи называется простым. Концевые вершины одной дуги/ребра или дуги с общей вершиной называются смежными. Простой граф, в котором каждая пара вершин смежна называется полным. Ребро/дугу называют инцидентным вершине, если оно соединено с ней.
Вывод: смежность – это отношение связности между однородными элементами (вершинами или дугами/ребрами), а инцидентность – между разнородными.
Вершина, не имеющая отношений смежности, называется изолированной. Графы с одинаковым отношением инцидентности, называются изоморфными и отличаются друг от друга только геометрической конфигурацией.
Примеры. На рисунке 12.5 представлены изоморфные графы:
Рис. 12.5.а
Рис. 12.5.б
Рис. 12.5.в
Степенью P(xi) вершины xi называется число дуг/ребер графа, инцидентных данной вершине.
В орграфе без петель различают полустепени захода P+(xi) вершины xi – количество дуг, входящих в xi, и полустепени исхода P–(xi) – количество дуг, исходящих из вершины xi. Понятно, что P+(xi)+P–(xi)=P(xi).
В различных приложениях теории графов дугам/ребрам графов, моделирующим реальные процессы, ставят в соответствие числовые характеристики: (длина пути, время выполнения работы, пропускная способность), называемые весом дуг/ребер. В таких случаях граф называют взвешенным.
Путем в орграфе называется последовательность дуг, в которой конец любой предыдущей дуги совпадает с началом следующей. Путь, проходящий через все вершины, и притом только по одному разу, называют гамильтоновым. Путь, содержащий все дуги графа, и притом только по одному разу, называют эйлеровым. Конечный путь, у которого начальная вершина совпадает с конечной, называют контуром. Контур, проходящий через каждую вершину графа только по одному разу (за исключением начальной и конечной вершин), называют гамильтоновым.
В неориентированном графе путь называют цепью, контур – циклом. Орграф/неориентированный граф называют связным, если каждые две его вершины можно соединить путем/цепью. Орграф называют сильно связным, если между любыми двумя его вершинами существует хотя бы один путь.
Пример. а) Сильно связный граф (рис. 12.6.а)
Рис. 12.6.а
б) Несвязный граф (рис. 12.6.б)
Рис. 12.6.б
Примерами графов могут служить схемы железных или шоссейных дорог, схемы связи поставщиков и потребителей, структурные формулы молекул и т.д.