- •Тема 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. Алгоритм расчета параметров сг:
2. Экстремальное дерево графа
Определение 12.2. Конечный связный неориентированный граф без циклов называется деревом.
Примеры. На рисунке 12.7 представлены примеры деревьев:
Рис.12.7.а
Рис.12.7.б
Дерево, имеющее n вершин, включает в себя n–1 ребро. При составлении дерева используется минимальное число ребер, чтобы граф был связным. При включении в дерево любого дополнительного ребра возникнет цикл. Дерево может быть частью неориентированного графа. Любая совокупность ребер графа попарно связанных отношением смежности и инцидентности и соответствующие им вершины образует дерево графа. Если такое дерево графа содержит все вершины графа, то оно называется покрывающим деревом или остовом графа.
Алгоритм построения экстремального дерева предполагает соединение всех вершин графа с помощью путей наименьшей (наибольшей) длины. Типичной задачей, для решения которой необходим такой алгоритм, является проектирование дорог с твердым покрытием, соединяющих населенные пункты в сельской местности, проведение линии связи, водо- или газопровода с наименьшей суммарной длиной.
Алгоритм решения задачи:
1) Составить план n вершин дерева.
2) Составить таблицу весов всех возможных связей между вершинами.
3) Выбрать ребро с наименьшим (наибольшим) весом и включить в дерево.
4) На следующем шаге рассмотреть минимальное по весу ребро из оставшихся и, если оно не образует цикл с ранее включенными ребрами, то добавить к дереву. Если имеется несколько таких ребер, то выбирается любое, при этом задача имеет альтернативное решение.
5) Построение заканчивается после разбора n–1 ребра.
Задача. Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рисунке 12.8 показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.
Рис 12.8
Решение задачи сводится к построению экстремального дерева графа.
Занесем данные задачи в следующую таблицу:
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
|
1 |
5 |
7 |
9 |
0 |
2 |
|
|
6 |
4 |
3 |
0 |
3 |
|
|
|
0 |
0 |
10 |
4 |
|
|
|
|
8 |
3 |
5 |
|
|
|
|
|
0 |
6 |
|
|
|
|
|
|
Далее, действуя по указанному алгоритму, построим экстремальное дерево графа (рис. 12.9):
Рис. 12.9
Найдем минимальную длину кабеля (км).
Ответ: .