- •Тема 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. Алгоритм расчета параметров сг:
3. Матричные способы задания графов. Упорядочение элементов орграфа
При большом числе элементов рисунок графа теряет наглядность. В таком случае граф целесообразно задать матричным способом. Этот способ также удобен и для решения задачи на компьютере.
Определение 12.3. Матрицей инцидентности орграфа без петель с n вершинами и m дугами называется матрица, любой элемент которой определяется по следующей формуле:
Для неориентированного графа вместо «–1» ставится «1».
Пример. Для заданного ориентированного графа (рис. 12.10) построить матрицу инцидентности:
Рис. 12.10
Матрица инцидентности орграфа:
.
Определение 12.4. Матрица смежности вершин орграфа – квадратная матрица n-го порядка (n – число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы Sij матрицы равны числу дуг, направленных из i-й вершины в j-ю.
В случае неориентированного графа ему вместе с ребром (xi,xj) принадлежит и ребро (xj,xi), поэтому матрица будет симметрической.
Пример. Для заданного ориентированного графа (рис. 12.11) построить матрицу смежности вершин:
Рис 12.11
Матрица смежности вершин орграфа:
.
Определение 12.5. Матрица смежности дуг орграфа – квадратная матрица m-го порядка (m – число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы qij равны 1, если дуга ui непосредственно предшествует дуге uj, и нулю в остальных случаях.
Для неориентированного графа матрица смежности дуг симметрическая с элементами равными 1, если ребра имеют общую вершину, и 0 в остальных случаях.
Пример. Для заданного ориентированного графа (рис. 12.12) построить матрицу смежности дуг:
Рис.12.12
Матрица смежности дуг орграфа:
.
Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.
Определение 12.6. Вершина xi предшествует вершине xj, если существует путь из xi в xj, тогда xi называется предшествующей вершине xj, а xj – последующей за xi.
Под упорядочением вершин связного орграфа без контуров понимают такое разбиение его вершин на группы, при котором:
1) вершины первой группы не имеют предшествующих, а вершины последней – последующих;
2) вершины любой другой группы не имеют предшествующих в следующей группе;
3) вершины одной и той же группы дугами не соединяются.
В результате упорядочения элементов получают граф, изоморфный данному.
Графический способ упорядочения вершин – алгоритм Фалкерсона:
1) Находят вершины графа, в которые не входит ни одна дуга. Они образуют первую группу.
2) Вершины и исходящие из них дуги исключают из дальнейшего рассмотрения (то есть вычеркивают).
3) Устанавливается следующая группа вершин, в которую не входит ни одна дуга. Этот шаг повторяют до тех пор, пока все вершины не будут упорядочены.
Пример. Упорядочить вершины орграфа (рис. 12.13):
Рис. 12.13
Упорядочим вершины орграфа по алгоритму Фалкерсона (рис. 12.14):
Рис. 12.14
4. Потоки на сетях. Постановка задачи о максимальном потоке
Определение 12.7. Сеть – это взвешенный конечный орграф без циклов и петель, ориентированный в одном общем направлении от вершины I, являющейся входом (истоком) графа, к вершине S, являющейся выходом (стоком) графа.
Для наглядности будем представлять, что по дугам из истока I в сток S направляется некоторое вещество (груз, ресурс, информация и т.п.)
Определение 12.8. Максимальное количество rij вещества, которое может пропустить за единицу времени дуга, идущая из вершины xi в xj называется его пропускной способностью. В общем случае rij ≠ rji .
Определение 12.9. Количество xij вещества, проходящего через дугу из вершины xi в xj в единицу времени, называется потоком по дуге.
Предполагается, что если из вершины xi в xj направляется поток величиной xij , то величина потока из xj в xi равна –xij , то есть xji = –xij. (12.1)
Принимается также, что xii=0. (12.2)
Определение 12.10. Совокупность X={xij} потоков по всем дугам сети называется потоком по сети или просто потоком.
Поток по любой дуге не превышает его пропускную способность:
xij ≤ rij . (12.3)
Если xij<rij , то дугу между вершинами xi и xj называют ненасыщенной.
Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, то есть мощность потока (12.4),
где j – конечные вершины дуг, исходящих из I; i – начальные вершины дуг, входящих в S.
Задача о максимальном потоке формулируется следующим образом: найти совокупность X*={x*ij} потоков x*ij по всем дугам сети, которая удовлетворяет условиям (12.1) – (12.3) и максимизирует линейную функцию (12.4).
К задаче о максимальном потоке сводятся задачи: доставка груза; отыскание минимальной по стоимости плана выполнения комплекса работ при заданной его продолжительности; задачи, связанные с наиболее экономным строительством энергетических сетей и т.д.