- •Тема 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. Алгоритм расчета параметров сг:
4. Многокритериальная оптимизация
Реальные ситуации бывают настолько сложными, что нередко приходиться учитывать несколько целевых функций, которые должны принимать экстремальные значения. Например, дать продукции больше, высокого качества и с минимальными затратами. Задачи, где находят решение по нескольким целевым функциям, относятся к задачам многокритериальной оптимизации. В процессе многокритериальной оптимизации формируется область согласований. В этой области любое решение нельзя улучшить ни по одному из критериев, не ухудшая его по какому-либо другому. Совокупность значений частных целевых функций в области согласования называется множеством Парето, а любое оптимальное состояние , где , для многокритериальной задачи называется оптимумом по Парето.
5. Основные понятия теории оптимизации
Определение 1.4. Функция , где имеет в точке - локальный экстремум, если существует двусторонняя окрестность этой точки, где для любого этой окрестности будет выполняться: 1) в случае максимума; 2) в случае минимума. Если неравенства строгие, то экстремум называется сильным, если нестрогие – слабым.
Точки локального экстремума обязательно должны быть внутренними точками области Q определения функции .
Определение 1.5. Функция имеет в точке области Q глобальный экстремум (оптимум), если неравенства выполняются для любой точки из области Q.
Точка глобального экстремума может быть как внутренней, так и граничной точкой области Q.
Теорема 1.1. (Необходимое условие существования локального экстремума). Если функция имеет экстремум в точке , то , .
Теорема 1.2. (Достаточное условие существования локального экстремума). Если в точке все частные производные равны нулю, то, чтобы в этой точке функция имела экстремум, достаточно, чтобы квадратичная форма была положительно определенной для минимума и отрицательно определенной для максимума.
Определение 1.6. Квадратичная форма называется положительно определенной, если для любых , хотя бы одно из которых отлично от нуля, квадратичная форма принимает значение большее нуля.
Теорема 1.3. (Теорема Вейерштрасса). Непрерывная функция, определенная на непустом, замкнутом, ограниченном множестве, достигает экстремума, по крайней мере, в одной точке этого множества.
Определение 1.7. Множество S называется выпуклым, если отрезок, соединяющий любые две точки этого множества, целиком содержится в этом множестве.
Определение 1.8. Функция на выпуклом множестве S называется выпуклой, если ее график на любом отрезке целиком оказывается не выше хорды, соединяющей соответствующие точки графика (функция выпукла вниз) или не ниже этой хорды (функция выпукла вверх); в противном случае – функция не является выпуклой.
Теорема 1.4. Пересечение выпуклых множеств является выпуклым множеством.
Теорема 1.5. Сумма выпуклых функций является выпуклой функцией.
Теорема 1.6. (Основное свойство выпуклых функций). Любой локальный экстремум выпуклой функции является и глобальным, но не наоборот.
Определение 1.9. Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции в соответствующей точке
.