1. Основные понятия и основные этапы операционного исследования
Операция – совокупность действий направленная на достижение заданных целей
Управляемая операция – это операция которая может быть реализована во многих вариантах
Оперирующая сторона – совокупность людей и автоматов, стремящихся в данной операции достигнуть поставленных целей
Исследователь операций – один человек или группа людей…
Активные средства – это те ресурсы, которыми располагает оперирующая сторона (люди, финансы, оборудование)
Стратегии – способы действий оперирующей стороны, направленные на достижение поставленных целей в данных реальных обстоятельствах
Критерий эффективности (целевая функция) – это математическая модель цели
Фазовые переменные –набор величин, которые с достаточной точностью показывают протекание операции во времени
Неконтролируемые факторы – факторы, независящие о оперирующей стороны, но зависят от исхода операции, делятся на: детерминированные, стохастические, неопределенные.
· Содержательная постановка
· Осознание цели
· Построение модели
· Идентификация, верификация модели
· Формирование класса стратегий
· Поиск методов решения
· Решение
· Анализ результатов
· Внедрение решения
· Обработка решения
2. Обобщенная схема операций
Z(t) – вектор фазовых переменных характеризующих состояние операции
X(t) – набор управляющих воздействий величины находящихся в нашей власти
A0 = (a0i) – ресурсы имеющиеся в нашем распоряжении
A(t)=(ai(t)) – вектор ресурсов фактически используемых
Y(t) – неопределенные, неконтролируемые факторы
ь построение модели операции
· как влияют внешние факторы (Y и X) на поведение операции
Z(t) = f[t, X(t), Y(t)],tО[0,T], f – вектор-функционал, моделирующий операцию
· как мы потребляем ресурсы A(t) = j[t, X(t), Y(t)], tО[0,T] , j - вектор функционал
ь решаем проблему целеполагания
· формируем функционал предпочтения
· определяем критерий
· определяем целевую функцию
ь Результатом решения операции является стратегия оперирующей стороны X(t) = q[t, Z(t), Y(t)], tО[0,T]
3. Критерий эффективности - это правило, которым мы руководствуемся при выборе вариантов, он отражает наши цели и предпочтения; сложный критерий – много целей Для неопределенных факторов:
w Заранее знаем Y(t) на промежутке [0,T] – это определенный критерий, наша задача W®max
w Процесс Y(t) является элементом некоторого множества процессов`Y , известного нам множества. Выводим целевую функцию M = min Y(t)О`Y{W}®max (лучшее поведение в худших условиях). Для
w Y(t) – случайная величина M[W] ®max, P{W³W0} ³ P0
4. Марковские процессы – один из видов случайных простых процессов, это процесс при котором будущее не зависит от прошлого при известном настоящем. Устанавливает связь между будущим и текущим. Может быть дискретным, если X(t) – дискретно, и непрерывным, если X(t) – непрерывным. Он может быть процессом с дискретным или непрерывным временем. Марковский процесс с дискретными состояниями называется Марковскими цепями.
5. Марковские процессы с непрерывным временем и их числовые характеристики
|
Если хотя бы одна l зависит от t, то процесс неоднородный, т.е. зависит от времени. Если все lij – константы, то процесс однородный. Если Dt – достаточно мал, то имеем: DPij(t, Dt)@ lij(t) Dt – вытекает из формулы в рамке, тем точнее, чем меньше Dt. Для того чтобы описать марковский процесс необходимо записать матрицу L(t)=|| lij(t)||N´N, запретные переходы lij(t)=0, lii(t)=¥. Достаточное условие существования финальных вероятностей – если система имеет конечное число состояний и за конечное число шагов может перейти из одного состояния в любое другое, это означает, что существуют финальные вероятности состояний (процесс стационарный).
6. Уравнения Колмогорова для Марковских процессов с непрерывным временем.
Sn, n=1…N, P{n(t)=i}=Pi(t) – вероятность того что состояние будет с номером i. Колмогоров доказал, что процесс Pi(t) детерминирован и определяется уравнениями Колмогорова. Пусть процесс находиться в состоянии Si – процесс может выйти и войти в него.
Уравнения Колмогорова (для неоднородного). -однородный процесс l не зависит от t.
|
Pi |
t |
Pi=1 |
Pi’ |
Pi |
0 |
Pi’*(t) |
Pi, i¹i’ |
Через длительное t:
Достаточное условие вырождение МП в стационарный:
· число состояний системы конечно
· из любого состояния за конечное число шагов можно попасть в любое другое
8. Схема гибели и размножения.
S0 |
S1 |
SN-1 |
SN |
Основание – рост популяции. S0 – Нижний предел числен.SN – верхний предел. n=1..N – номера состояний.
Если все l известны, то можем найти
Р, если знаем Р0.
9. Вероятностные свойства перехода МП из состояния в состояние.
Известно, что процесс вышел из состояния i, какова вероятность того, что он попадет в j? Рассмотрим следующие события:
А – [на интервале [t,t+Dt] произошел выход из состояния i]
В – [происходит выбор одного из состоянийSi и переход в него]
Рассмотрим вероятность совпадения событий А и В:
P(AB) = lijDt = P(B/A)P(A),
10. Основные понятия теории массового обслуживания (МО)
Система МО – структура из обслуживающих приборов, потоков заявок и очередей.
Входящий поток заявок (интенсивность входящего потока l).
Исходящий поток (интенсивность входящего потока m).
Канал обслуживания (число каналов n, среднее число занятых `k, производительность m).
Очередь (среднее число заявок `z, среднее время пребывания одной заявки `t ).
Дисциплина обслуживания – правила, по которым действуют СМО.
· в порядке поступления
· случайно
· fifo
· lifo
· с приоритетом – абсолютный, относительный
по условиям ожидания
· с отказами
· с очередью
по условиям организации очереди
· с ограниченной очередью
· с ограниченным временем пребывания в очереди
по месту нахождения источников заявок
· закрытые – источник в системе и оказывает на нее влияние
· открытые – вне системы и не оказывает влияния
по фазам
· однофазные – один этап обслуживания
· многофазные – два и более этапов
по числу каналов
· одноканальные
· многоканальные
11. Потоки событий
Каждому событию соответствует момент t в который это событие произошло. Т – интервал между двумя моментами времени (СВ). Поток событий – независимая последовательность моментов t.
по случайности:
· регулярные – Т-const
· случайные – Т-СВ.
по постоянности вероятностных свойств
· стационарные
· нестационарные
по связи будущего поведения с прошлым
· с последействием
· без последействия
по числу заявок в одном событии
· ординарные –событию соответствует одна заявка
· неординарные - событию соответствует случайное число заявок
12. Простейший (Пуассоновский) поток
t2>t1, t2-t1=t, P{n=k| t2>t1=t}=p(k, t) – вероятность того, что на интервале t произошло k событий.
Свойства: случайный, стационарный, ординарный, без последействия, имеет распределение Пуассона.
Функция распределения - вероятность того, что время м.д. заявками будет меньше t.
Закон распределения времени обслуживания:
14. Потоки Пальма и Эрланга
Пальма. Интервалы м.д. событиями взаимонезависим (статистическая взаимосвязь), случаен и имеет одинаковое распределение. Распределение интервалов могут быть любыми. Ординарный. Пуассоновский поток – частный случай потока Пальма. (пример: системы, где соблюдаются интервалы движения).
Эрланг. Применяем операцию
просеивания к простейшему потоку. Оставляем каждое k-ое событие – поток Эрланга k-го порядка.
Функция распределения - Тк – интервал времени м.д. событиями. t£
Тк £t+Dt -
вероятность этого события –
`Tk=kЧ`T – средняя продолжительность интервалов м.д. событиями
lk=l/k – интенсивность потока Эрланга к-го порядка
s2к=кЧs2 – дисперсия интервалов времени
С ростом порядка потока Эрланга Сv ®0, поток становиться более упорядоченным. Подбирая порядок потока Эрланга мы обеспечиваем более высокую реалистичность.
15. Простейшая Марковская многоканальная, однофазная СМО.
L>l
Очередь |
П1 |
П2 |
Пn |
Исходящий поток |
L |
Отказы |
Входящий поток |
Дисциплина обслуживания
· если все приборы заняты заявка встает в очередь и ждет обслуживания.
· в модели безразлично в каком порядке будут обслужены заявки.
· освободившийся прибор сразу приступает к обслуживанию заявки в очереди, если таковая имеется.
· если величина очереди достигла (N-m) – предельной величины, очередная заявка получает отказ.
Характеристики состояния
Характеристики функционирования
16. Оптимизация
А [руб/прибор] – инвестиции в 1 прибор
a [руб/час Чприбор] – эксплуатационные затраты на 1 прибор
В [руб/заявка] – инвестиции омертвленные в заявке, находящейся в системе
b [руб/часЧ заявка] – текущие эксплуатационные расходы
С [руб/место] - инвестиции в 1 место на стоянку
x [руб/часЧ место] – затраты на поддержание 1 места в очереди (ремонт, очистка и т.п.)
d [руб/заявка] – упущенная выгода от отказа заявке в обслуживании
Ен [1/час] – нормативный коэффициент эффективности
Мы совершили инвестицию в прибор и имеем потери: (ЕнЧАЧm)+(aЧm)+(ЕнЧВЧ`k)+(ВЧ`k)+(ЕнС(N-m))+ x(N-m)+ dPNЧl=F1(m,N), приведенные затраты ® min
Другой вариант: оптимизируемая
величина L=jL(m,N).
17. Простейшая Марковская одноканальная, однофазная СМО
m=1, N=¥, m>l, r=l/m<1 -система в среднестатистическом смысле справляется с потоком заявок. Если условие не выполняется, очередь будет расти безгранично. k=1.. ¥/
Факторы повышения запаса:
· дискретность поставок при непрерывном спросе
· случайные колебания в спросе, в объеме поставок, в интервале м.д. поставками
· предполагаемые изменения в конъюнктуре (сезонность)
Факторы снижения запаса:
· плата за хранение
· упущенный доход
· потери в количестве запасов (испарение, усыхание…)
· моральный износ
19. Управление запасами при постоянном спросе и регулярных поставках (задача Джонсона)
gi – затраты на переналадку или на доставку i-го товара (партия).
si – затраты на хранение i-го вида запаса (шт).
fi – площадь склада под i-й вид запаса (шт).
Yi – максимальный запас на складе i-го вида запаса (шт).
Qi=`Yi – объем заказываемой партии
mi – спрос на i-го вида запаса.
Ci – стоимость единицы i-го вида запаса (шт).
С – кап. вложения.
F – емкость склада.
Функция Лагранжа:
20. Задача продавца газет
Партии товара Q поступают регулярно через Т, через этот промежуток продается случайное количество товара R, к моменту поставки новой партии старый товар теряет свои потребительские свойства.
Т – интервал времени м.д. поставками
Q – объем заказываемой партии
R – объем продаж (СВ)
С1 [руб/ед] – потери от не реализации товара.
С2 [руб/ед] – упущенная выгода в случае нехватки товара.
Функция предпочтения:
Критерий: Средняя величина убытков (за достаточно долгий период) минимальна: M[j(Q,R)] ®min
Предполагается, что мы провели исследования и знаем функцию спроса:
Для того, чтобы найти минимум
необходимо решить уравнение:
21. Система управления запасами (N,n) – типа.
N- верхняя оптимальная отметка (выкл.). n – нижняя оптимальная отметка (вкл.).
m |
S-m |
S-m+1 |
S-1 |
S0 |
S1 |
Sn-1 |
Sn |
Sn+1 |
SN-1 |
SN |
SN-1’ |
SN’ |
Sn+1’ |
l |
m |
m |
m |
m |
m |
m |
l |
l |
l |
l |
l |
l |
l |
Уравнения Колмогорова:
1. P-m+1Чl – PmЧm = 0 ;k = -m
2. Pk+1Чl – PkЧm – PkЧl + Pk-1Чm = 0 ;-m+1 £ k £ n+1
3. Pn+1’Чl + Pn+1Чl + Pn-1Чm – PnЧm – PnЧl = 0 ;k = n
4. Pk+1Чl – PkЧm – PkЧl + Pk-1Чm = 0 ;Верхний блок n+1 £ k £ N-1
5. Pk+1’Чl – Pk’Чl = 0 ;Нижний блок (n+1)’ £ k’ £ (N-1)’
6. Pk-1Чm – PkЧl – PkЧm = 0 ;k = N
7. PkЧm – Pk’Чl = 0 ;k = N’
8.
22. Модель (N,n) –типа, оптимизация
m/l=a, Решение этой системы дает Р как функцию от N, n, a:
N,n,a; Pk = jk(N,n,a); Pk’ = jk’(N,n,a);
l – длинна
очереди, Рl’ = P{k £ -l} =
Cy [руб/деньЧед] – штраф за ожидание в
очереди;
Сz [руб/деньЧед] – плата за хранение запаса;
CyЧ`y(N,n,a) + (Cz+EHC)Ч`Z(N,n,a) ® min; Pl*(N,n,a)£Pдоп.
23. Сетевые модели
В 1955 году зародились методы и модели сетевого планирования. PERT – метод оценки и пересмотра планов. СПУ – сетевое планирование и управление. Применяется: планирование и управление крупными техническими проектами, учебным процессом. Назначение: системный анализ сложных комплексов работ и осознание их в взаимосвязи; регулирование процесса выполнения комплекса работ, путем пересмотра плана.
Событие – завершение выполнения всех предшествующих работ.
· Ни одно событие, кроме истока, не может произойти до тех пор, пока не будут закончены все входящие в него работы.
· Ни одна работа выходящая из данного события не может начаться раньше, чем произойдет данное событие.
· Ни одна последующая работа не может начаться раньше, чем закончатся все предшествующие ей работы.
· Сетевая модель не должна содержать циклов
Ранг – наибольшее количество работ от истока до данного события.
Алгоритм упорядоченной нумерации (события наступающие позже имеют больший номер):
1. Исходу (началу) присваивается ранг k=0 и номер i=0.
2. Вычеркиваем выходящие из исхода работы
3. Присваиваем ранг k=1 всем событиям в которые входят вычеркнутые работы и не входят никакие другие.
4. Пронумеруем все события ранга k=1 в произвольном порядке продолжая нумерацию.
5. и т.д. Процедура продолжается до последнего события – стока.
Это произойдет в том случае, если нет циклов. Если множество событий к-го ранга оказалось пустым, и не все события оказались пронумерованы – это значит, что в ходе нумерации мы подошли к событиям образующим цикл.
24. Детерминированный анализ сетевой модели
TiЪ - раннее время наступления
события i; Все работы
руководствуются правилом: работа tij начинается ка только произошло событие i – раннее время. TjЪ
=
TiЩ - позднее время наступления события i. Работа (i) должна быть закончена к моменту начала (j).
TiЩ
=
Критический путь –
последовательность событий, в которых работы плотно прилегают одна к другой.
Как только заканчивается одна, сразу же начинается другая. Путь идет от начала
до конца.
rij2 + tij |
rijЩ + tij |
rij1 |
rijЪ |
0 |
TiЪ |
TiЩ |
TjЪ |
TjЩ |
TI |
TIЩ– tjЩ |
Rj |
rijЪ |
tij |
Ri |
TiЪ |
1го рода – для увеличения продолжительности данной работы и последующих, не меняя предыдущие.
2го рода – для увеличения продолжительности данной работы и предыдущих, не меняя последующие.
Полный резерв сокращает продолжительность всего комплекса работ.
Свободный резерв не сокращает продолжительность всего комплекса работ, изменяет только данную.
25. Вероятностный анализ сетевой модели
t |
tijo |
tijв |
tijп |
6Чsij |
1. строим плотность распределения
2. отсечем хвосты, чтобы сумма была равна 0,0027
tij = M[Tij] – вычисляется по эмпирической формуле, выработанной годами исследований и испытаний.
Флюктуации продолжительности
работ не приведут к изменению критического пути. Работы в сетевом графике
статистически взаимонезависимы. Теорема Ляпунова – сумма бесконечного
(большого) числа статистически независимых случайных слагаемых, асимптотически
стремится к нормальному распределению. Длительность критического пути имеет нормальное
распределение, мат. ожидание `Т и дисперсию s.
Тогда функция распределения выглядит:
26. Оптимизация плана комплекса работ
Управлять продолжительностью работ мы можем через выделение каждой работе определенного объема ресурсов. Каждая работа потребляет множество ресурсов, часть из них взаимонезаменяема. Имеет смысл управлять теми ресурсами, которые можно перебросить с одной работы на другую. В основе метода лежит идея о том, что продолжительность работы зависит от количества выделенного на нее ресурса.
xij – количество мобильного ресурса, задействованного в работе ij.
xi – момент наступления события i.
x0=0 – момент начала работ
`Т – заданная величина интервала времени, отведенного на выполнение комплекса работ
Сколько ресурсов нужно потратить,
чтобы уложиться в `Т.
И при этом потратить минимум. Нужно установить модуль tij = fij(xij)
.Как зависит продолжительность работы от выделенного на нее ресурса. С ростом
количества ресурсов, время убывает
Сокращение комплекса работ (смысл в том, чтобы все пути стали критическими).
Задача перераспределения ресурса. Установили, что требуется Х мобильного ресурса, мы не хотим уменьшить этот ресурс, но хотим перераспределить, так, чтобы сократить время комплекса работ.
xi + fij(xij) £ xi, iОBj , j=1..I X®min –минимизируем момент наступления послед. события
x0 = 0, xij ³ 0, iОBj , j=1..I - это задача мат. программирования, получим xij*, xi*
xi* + fij(xij*) = xj* , iОBj , j=1..I |
27. Динамическое программирование
а |
а |
0 |
1 |
2 |
3 |
4 |
5 |
n шаги |
а |
Sn |
S0 |
Sn – состояние системы на n-ом шаге.
` Sn = {Sn} – множество состояний системы на n-ом шаге.
Wn=j( Sn-1, Sn) – шаговый эффект зависит от того, из какого состояния вышла система и в какое вошла.
xn = xn(Sn-1,Sn) – управление; wn = wn(xn-1,xn) – шаговый эффект; Sn=Yn(xn,Sn-1)
Управление: X=(x1,x2,…,xn…xN) – вектор, совокупность всех действий на всех шагах
Мультипликативный эффект:
28. Принцип оптимальности, уравнение Беллмана
1.
A |
B |
C |
D |
2. Целевая функция аддитивна, т.е. WAD=wAB+wBC+wCD
Всякий отрезок оптимальной траектории – оптимален.
Оптимизация многошагового процесса:
W(Sn) – эффективность
движения из Sn
в SN (конечное).
Рассчитывают для каждого состояния, двигаясь из конечного в начальное. W(SN)=0, n=N..0. Правило
носит название уравнения Беллмана:
29. задача о распределении ресурсов
Нам дано N объектов, с номерами n=1..N. Выделено некоторое
число ресурсов R ,
|
30. Задача планирования и управления запасами
tn – набор моментов отгрузки оборудования
t0 – момент начала работы
Rn – плановый объем продукции, которые мы должны отгрузить в tn
R0=0, Rn – целочисленен (продукция дискретна)
`xn – предельная производительность на n-ом интервале. 0£xn£ xn
В разное время производительность различна
wn – издержки производства и
хранения на n-ом
интервале
параметры:
an – издержки на производство единицы продукции (руб/шт)
bn – издержки на наладку оборудования (руб/партия)
cn – издержки хранения еденицы продукта (руб/шт)
Ограничения: zn – величина запаса в
момент tn+0,
Целевая функция: Средний уровень
запаса=(запас в начале + запас в конце)/2
31. Модель замены оборудования
Sn |
n |
n=0..N – порядковый номер года
k=1..(N-n) – срок службы оборудования (его купили на k лет)
wn,n+k – суммарные издержки на приобретение, эксплуатацию и ремонт оборудования за всю службу.
wn,n+k = pn – bn,k + cn,n+k ; pn – стоимость оборудования
bn,k
– остаточная стоимость оборудования, купленного в году n и проданного в году k; cn,n+k – суммарные затраты на эксплуатацию и
ремонт оборудования купленного в году n за весь срок.
32. Бесконечношаговое динамическое программирование
N®¥, число шагов бесконечно.
|
|