Исследование операций

1. Исследование операций

Исследование операций связано с такими вопросами
как:
Математические методы оптимизации
Линейное , нелинейное программирование
Динамическое программирование

2. Динамическое программирование

3. Динамическое программирование

Где z1 – выигрыш на 1 шаге
Zi – выигрыш на iом шаге
Т.е. можно подбирать управляющие воздействия на
каждом шаге vi
Тогда оптимальное шаговое управление будет
представлять собой вектор V= (V1 , …vn)
ЗАДАЧА
Программное обеспечение эксплуатируется в
течении 5 лет . В начале каждого года потребитель
может принять следующие решения:
1. Купить новое ПО.

4. Динамическое программирование

5. Динамическое программирование

ЗАДАЧА 2
Как проехать на велосипеде по извилистой дороге
сохранив равновесие
Ответ: при поворотах надо соблюдать
определенные углы наклона
Углы наклона и будут решения на каждом шаге.
Методы решения задач динамического
программирования
1 метод Искать все элементы решения на всех шагах
2 метод Строить оптимальное управление шаг за
шагом, оптимизируя каждый шаг

6. Динамическое программирование

Т.о. идея постепенной оптимизации лежит в основе
динамического программирования
Т.е. легче решать 5 легких задач , чем одну сложную
Но оптимизация на каждом шаге влияет на
оптимизацию в целом
Т.е. решать задачу на каждом шаге , просчитывая к
каким последствиям он приведет.

7. Задачи

В результате опытов и статистического анализа
Получена модель
Z1 = Z01 + 3,5 t1 + 3,73 t2 - 2,7 Δt
Z2 =Z02 + 2,3 t1 + 2,29 t2 -3 Δt
Z3 =Z03 + 2,7 t1 + 3,7 t2 -5 Δt
Где Z1 , Z2 , Z3 – выходные сигналы на выходе
компьютерной сети
t1время нагрузки по 1 участку сети
T2время нагрузки по 2 участку
Δ t – пауза (в c) между нагрузками
W(Z1 , Z2… Zn) → min

8. Динамическое программирование

9. Задача Динамическое программирование

10. Задача Динамическое программирование

11. оптимизация

Т.о. идут по функции пока не найдем экстремум.
Т.о. алгоритм
Вводим границы интервалов поиска по
переменным, шаг перебора, целевую
функцию, ограничения
Находим количество шагов на сетке

12. примеры

.
Цикл для n1 , n2
Счетчик
Вычисляем
Z(x1, x2)
Запоминаем значения координат x1, x2
Находим экстремум
(min z=z( x1, x2)

13. Метод Монте -Карло

Под методом Монте-Карло понимается численный
метод при помощи моделирования случайных величин.
Суть метода: процесс определяется математической
моделью с использованием генератора случайных
чисел.
Модель многократно вычисляется
На основе полученных данных вычисляются
вероятностные характеристики рассматриваемого
процесса.
Напр. чтобы узнать какое будет расстояние между
двумя точками на квадрате: берут случайные пары
точек в границах данного квадрата и вычисляют для
каждой пары расстояние , а затем определяют
среднее арифметическое

14. Метод Монте-Карло

Методы реализации
1. Выбирается точка X0
2. Выбираются шаги в случайно выбранных направлениях Li на
случайным образом определенное расстояние Si (где i-номер
шага
Т.е. i=1,2,3,… n (где n –заданное число шагов)
Цель : нахождение оптимума
3. Для изменения длинны шага и направления вектора могут
быть использованы различные законы изменения случайных
величин.
В результате осуществляется переход из фиксированной точки
X0 в точки Xi (значения целевой функции в новых точках будут
W(Xi) )

15. Метод Монте-Карло

ПРИМЕЧАНИЯ : некоторые точки могут оказаться за пределами
области допустимых решений , поэтому в алгоритме на
каждом шаге должна быть проверка принадлежности
найденных W(xi) множеству допустимых решений.
Кроме того надо задать фиксированное число N (N –попыток
поиска экстремума)
4. За решение принимают точку Xs в которой W(Xs) будет min
Координаты найденной токи запоминаются.

16. Метод Монте-Карло

Алгоритм
Вводятся границы интервалов по ограничениям
(x1a=0, x1b=1
x2a =0 , x2b=1)
Вводиться уравнение целевой функции
Вводятся ограничения

17. примеры

.
Цикл по i от 1 до N
Счетчик
Вычисляем
Z(x1i, x2i)
В алгоритме проверяем ограничения
Находим экстремум
(min z=z( x1, x2)
Запоминаем значения
координат x1, x2

18. Метод случайного поиска с обучением

Отличается от метода Монте –Карло тем что
последующие действия по поиску экстремума
выполняются с учетом результатов достигнутых на
предыдущих шагах.
1.Из начальной точки x0 делается шаг в случайном
направлении S0.
2. Если точка x1 € X , то в этой точке вычисляется
экстремум.
Если w(x1)<w(x0) то из точки x1 производиться
следующий шаг
Если w(x 1) > w( x0) (или найденная точка X1 не
принадлежит заданному множеству X) , то шаг
считается неудачным и производиться новая попытка
перехода из точки x0 уже в другом напрвлении
.