- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Методы сопряженных направлений
Как и метод Ньютона, методы сопряженных направлений основаны на свойствах квадратичных функций. В связи с этим говорят о сопряженных направлениях относительно квадратичной функции.
Пусть дана матрица Нnn. Направления d1, d2, ..., dk (k n) называются сопряженными или Н-сопряженными, если они линейно независимы и
. (8.52)
Э ти векторы определяют сопряженные направления. Для квадратичной функции двух переменных сопряженные направления получаются следующим образом. Возьмем произвольное направление d1 и на нем найдем минимум, двигаясь из точки X1. Повторим поиск минимума на d1 из точки X2 X1 (рис. 8.36). Направление d2, определяемое прямой, проходящей через найденные минимумы, является сопряженным с направлением d1. При этом направление d2 проходит через искомый минимум функции f. Следовательно, при любой начальной точке минимум квадратичной функции двух переменных достигается за два одномерных поиска вдоль сопряженных направлений.
Пример 8.6. Используя сопряженные направления, найти минимум функции (точка минимума X*=(2,4)).
Запишем матрицу Гессе .
За первое направление возьмем . Компоненты d2 найдем из условия (8.52):
.
П оложив а = 1, получаем b = 2 и . Возьмем начальную точку X0=(-1;1). Найдем минимум на направлении d1. Для этого подставим в функцию X = X0+hd1, то есть x1= x10+h = -1+ h, x2=x20=1. Тогда f = h2-3h-3 и минимум по h будет при h*=1,5. Следовательно, минимум на d1 достигается в точке X1=(0,5;1). Приняв ее за начальную для поиска вдоль d2 и подставляя в функцию x1= 0,5+ h, x2=1+2h, получаем f = 3h2-9h-5,25. Находим h*=1,5 и соответствующую новую точку X2=(2;4). Как видим, второй одномерный поиск привел в точку искомого минимума f (рис. 8.37).▲
Для квадратичной функции n переменных сопряженные направления позволяют найти минимум не более чем за n одномерных поисков. В случае нелинейной функции, отличной от квадратичной, конечное число итераций дает только приближенное решение.
Методы, основанные на концепции сопряженных направлений, различаются способами построения таких направлений. Ряд из них относятся к прямым методам, например, метод Пауэлла и его модификация – метод Зангвилла. Другие используют первые производные, например, метод сопряженных градиентов (метод Флетчера-Ривса). Одним из самых эффективных является метод Дэвидона-Флетчера-Пауэлла. В нем генерируются сопряженные направления с использованием градиента и матрицы D, аппроксимирующей обратную матрицу H-1. Поэтому его относят также к квазиньютоновским методам. Рассмотрение этих методов выходит за рамки настоящего пособия.
43. Методы случайного поиска
Рассматриваемые здесь методы основаны на использовании случайного механизма задания начальной точки и выбора направления движения. Так как в процессе поиска вычисляются значения только целевой функции, эти методы можно отнести к классу прямых.
Случайный механизм выбора направления реализуется с помощью датчика случайных чисел , равномерно распределенных на интервале [-b, b]. Направление задается случайным вектором
= (1, 2, 3, ..., n),
компоненты которого вычисляются по формуле
,
где n случайных чисел i генерируются датчиком. Очевидно, что такой случайный вектор имеет единичную длину и определяет только направление. При этом все направления равновероятны.
Приведем несколько простых алгоритмов случайного поиска.