- •Двусторонние шпоры по файзу
- •Печатай прямо этот файл
- •Теория принятия решений [3, 4]
- •1. Классы задач принятия решений, системный анализ и характеристика его этапов.
- •2. Графы и показатели эффективности смо с простейшими потоками.
- •6. Замкнутые смо.
- •3. Принятие решений в условиях риска, неопределенности и конфликты.
- •Стандартная форма задачи лп
- •Основные понятия лп. Свойства задач лп
- •4. Основы линейного программирования. Область применения. Постановка задачи
- •Каноническая форма задач лп
- •Методы решения задач лп
- •Симплекс-метод. Характеристика метода
- •М одифицированный алгоритм симплекс-метода
- •Модели управления транспортными потоками.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Задачи с неоднородным грузом
- •Многоиндексные задачи
- •Транспортные задачи по критерию времени
- •6. Оптимизация транспортных потоков. Метод потенциалов
- •Построение начального плана перевозок
- •Правило северо-западного угла
- •Переход от одного плана перевозок к другому
- •Признак оптимальности
- •Алгоритм метода потенциалов
- •7. Методы управления проектом.
- •8. Двойственность задач оптимизации. Двойственность задач лп
- •Интерпретация двойственной задачи
- •Запись двойственной задачи в общем случае
- •Теоремы двойственности
- •Двойственный симплекс-метод
- •9. Декомпозиция задач планирования большой размерности.
- •Метод декомпозиции Данцига - Вулфа
- •10. Методы определения целочисленных решений.
- •Метод отсечений
- •Метод ветвей и границ
- •Аддитивный алгоритм
- •11. Основы динамического программирования. Достоинства и недостатки метода.
- •Работа метода дп
- •Функциональное уравнение дп
- •Многомерные задачи динамического программирования
- •Снижение размерности с помощью множителей Лагранжа
- •12. Оптимизация надежности технических систем, систем распределения ресурсов.
- •4.2.3. Сбалансированная транспортная задача
- •13. Классы задач нелинейного программирования и методы их решения. Х арактеристика задач
- •Условия оптимальности
- •Методы решения задач нп
- •14. Задачи нелинейного программирования, сводящиеся к линейным. Квадратичное программирование
- •Сепарабельное программирование (сп)
- •Задачи дробно-линейного программирования
- •15. Классификация и характеристика методов «спуска».
- •Методы одномерной минимизации. Метод деления шага пополам
- •Квадратичная аппроксимация
- •Метод деления интервала пополам
- •Метод золотого сечения
- •Метод Фибоначчи
- •Метод первого порядка
- •Методы второго порядка
- •Многомерный поиск безусловного минимума Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций)
- •Симплексный метод
- •Градиентные методы
- •Метод Ньютона
- •М етоды сопряженных направлений
- •Методы условной оптимизации
- •Метод проектирования градиента
- •Метод штрафных функций
- •Метод барьерных функций
- •16. Методы случайного поиска и генетические алгоритмы.
- •8.8.7. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •8.8.8. Генетические алгоритмы
- •17. Особенности принятия решений при многих критериях.
- •18. Методы свертки и целевого программирования в принятии решений по многим критериям.
- •10.2.1.4. Линейная свертка
- •10.2.1.5. Максиминная свертка
- •10.2.1.7. Целевое программирование (цп)
- •19. Интерактивные методы принятия решений
Алгоритм с обратным шагом
Он построен путем модификации предыдущего алгоритма с целью уменьшить число розыгрышей направлений. Внесено следующее изменение: если сгенерированное направление неудачное, то после возврата в исходную точку Xk делается шаг в противоположном направлении; если же и оно неудачное, то генерируется новое направление из точки Xk. Логика действия очевидна: если в данном направлении функция ухудшается, то можно ожидать, что в противоположном направлении она улучшится. Понятно, что эффект модернизации алгоритма тем выше, чем ближе функция в текущей области к линейной.
Алгоритм наилучшей пробы
Здесь используются два шага: пробный и рабочий h. Величина пробного шага соответствует необходимой точности. Задается также число пробных шагов m, меньшее числа переменных n, причем разница между m и n увеличивается с ростом n.
В текущей точке генерируются m направлений j и на них делаются пробные шаги. Вычисляются изменения функции
.
В направлении с наименьшим (отрицательным) приращением fj выполняется рабочий шаг:
.
Поиск
заканчивается, если
.
По
аналогии с предыдущим алгоритмом можно
рассматривать и неудачные направления:
вычислить
.
Если максимум соответствует положительному
приращению fj,
то рабочий шаг делается в противоположном
направлении.
Алгоритм статистического градиента
Все параметры и начальные действия такие же, как в предыдущем алгоритме. Отличие состоит в выборе направления движения. Оно определяется с учетом всех разыгранных направлений:
. (8.53)
Направление y называется статистическим градиентом. В пределе (m) он стремится к градиенту f. Но определение y требует меньше вычислений, чем f, и тем в большей степени, чем сильнее неравенство m<n.
Согласно (8.53) каждый компонент вектора у вычисляется по формуле
.
Новая точка находится перемещением на рабочий шаг h в направлении статистического антиградиента:
.
Поиск
завершается при выполнении условия
или
▲
Эффективность рассмотренных алгоритмов можно повысить за счет незначительных изменений их отдельных элементов или шагов. Так, при успешном шаге можно продолжать шаги в найденном направлении до тех пор, пока функция улучшается (использование идеи одномерной минимизации).
Другая возможная модификация заключается во введении в алгоритм процедуры самообучения (адаптации). Это касается вероятностных характеристик случайного вектора . Первоначально все направления этого вектора равновероятны. В процессе поиска накапливается информация об эффективности разыгранных направлений, на основе которой корректируется распределение вероятностей направлений случайного вектора. В результате повышается вероятность удачных направлений при одновременном снижении вероятности неудачных.
Как следует из логики алгоритмов случайного поиска, при прочих равных условиях их эффективность выше вдали от экстремума и снижается по мере приближения к нему, так как падает вероятность выпадения удачных направлений.
Целесообразность применения случайного поиска возрастает с увеличением числа переменных, а при средней и большой размерности он становится практически безальтернативным. В отличие от методов, использующих производные, алгоритмы случайного поиска, как и прямые методы, могут применяться в условиях помех (погрешностей вычислений).
