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. Марковские процессы с непрерывным временем и их числовые характеристики Система в момент t находится в состоянии n(t)=i. Рассмотрим величину n(t+Dt)=j, i№j. P{n(t+Dt)=j | n(t)=i} - интенсивность перехода система из состояния i в j. Если хотя бы одна 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. Через продолжительное время процесс успокаивается и вероятности станут константами. Марковский процесс при t®Ґ вырождается в стационарный Марковский процесс. Через длительное t: - вырожденное уравнение К. Достаточное условие вырождение МП в стационарный: число состояний системы конечно
из любого состояния за конечное число шагов можно попасть в любое другое 8. Схема гибели и размножения.
Основание – рост популяции. S0 – Нижний предел числен. SN – верхний предел. n=1...N – номера состояний. Если все l известны, то можем найти Р, если знаем Р0. , , делим на р0 :
9. Вероятностные свойства перехода МП из состояния в состояние. Известно, что процесс вышел из состояния i, какова вероятность того, что он попадет в j? Рассмотрим следующие события: А – [на интервале [t, t+Dt] произошел выход из состояния i]
В – [происходит выбор одного из состоянийSi и переход в него] Рассмотрим вероятность совпадения событий А и В:
P(AB) = lijDt = P(B/A)P(A), , где - интенсивность выхода из i... В состоянии Siпроцесс пребывал случайное время и мы знаем что это МП. Каковы статистические свойства этого случайного времени? Т– случайное время пребывания в Si, Fi(t)=P{T0, , . n(t)=i – процесс в состоянии находился в течении Т, n(t+t0)=i – через (Т+t) процесс покинет состояние. Мы наблюдали за процессом в течении t0 и он не вышел из состояния. P{T 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 событий... Самый случайный из всех случайных ординарных потоков.
Свойства: случайный, стационарный, ординарный, без последействия, имеет распределение Пуассона.
13. Содержательный смысл параметра, распределение времени м. д. заявками l - интенсивность потока, то есть среднее число заявок в единицу времени. Функция распределения - вероятность того, что время м. д. заявками будет меньше t.
Вероятность наступления хотя бы одного события на малом интервале времени: P{nі1|t2-t1=Dt=Dt}=1-p(0, Dt)=. Мы установили, что в t0произошло последнее событие. Какова вероятность того, что следующее случиться позднее чем t0+Dt. Обозначим : Т – СВ интервал времени м. д. событиями. Какова вероятность того, что Тіt. P{Tіt} – значит что на t событий не произошло. Закон распределения времени обслуживания: 14. Потоки Пальма и Эрланга
Пальма. Интервалы м. д. событиями взаимонезависим (статистическая взаимосвязь), случаен и имеет одинаковое распределение. Распределение интервалов могут быть любыми. Ординарный. Пуассоновский поток–частный случай потока Пальма. (пример: системы, где соблюдаются интервалы движения).
Эрланг. Применяем операцию просеивания к простейшему потоку. Оставляем каждое k-ое событие – поток Эрланга k-го порядка. Функция распределения - Тк – интервал времени м. д. событиями. tЈ Тк Јt+Dt - вероятность этого события – - вероятность того, что на t произошло (к-1) событие. Известна интенсивность l простейшего потока из которого получили поток Эрланга к-го порядка. Хотим, чтобы на интервале t произошло (к-1) событие, а на Dt - 1 событие чтобы tЈ Тк Јt+Dt. lDt - произошло одно событие на Dt. Функция плотности распределения . `Tk=kЧ`T – средняя продолжительность интервалов м. д. событиями lk=l/k – интенсивность потока Эрланга к-го порядка s2к=кЧs2 – дисперсия интервалов времени - коэффициент вариации.
С ростом порядка потока Эрланга Сv ®0, поток становиться более упорядоченным. Подбирая порядок потока Эрланга мы обеспечиваем более высокую реалистичность. 15. Простейшая Марковская многоканальная, однофазная СМО.
L>l - часть заявок не обслуживается. m – каналов обслуживания. Входящий поток – простейший с интенсивностью l, интервалы м. д. событиями распределены f(t)= le-lt. Приборы статистически одинаковы и всегда исправны, отказов в связи с поломкой нет. Время обслуживания прибором случайно, но у всех приборов это время имеет плотность распределенияf0(t)=me-mt(статистически независимо). Интервалы времени обслуживания заявок взаимонезовисимы. Дисциплина обслуживания
если все приборы заняты заявка встает в очередь и ждет обслуживания. в модели безразлично в каком порядке будут обслужены заявки. освободившийся прибор сразу приступает к обслуживанию заявки в очереди, если таковая имеется.
если величина очереди достигла (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)... Минимизация издержек на 1 заявку. 17. Простейшая Марковская одноканальная, однофазная СМО
m=1, N=Ґ, m>l, r=l/m ; Факторы повышения запаса: дискретность поставок при непрерывном спросе
случайные колебания в спросе, в объеме поставок, в интервале м. д. поставками предполагаемые изменения в конъюнктуре (сезонность) Факторы снижения запаса: плата за хранение упущенный доход потери в количестве запасов (испарение, усыхание…) моральный износ
19. Управление запасами при постоянном спросе и регулярных поставках (задача Джонсона)
gi – затраты на переналадку или на доставку i-го товара (партия). si – затраты на хранение i-го вида запаса (шт). fi – площадь склада под i-й вид запаса (шт). Yi – максимальный запас на складе i-го вида запаса (шт). Qi=`Yi – объем заказываемой партии mi – спрос на i-го вида запаса. Ci – стоимость единицы i-го вида запаса (шт). С – кап. вложения. F – емкость склада. .
Функция Лагранжа: , QО[1, n], Q - множитель Лагранжа –показывает как изменится функция Лагранжа (L), целевая функция (L(Q)) при изменении емкости склада (F).
; , от сюда находим Qio, Fo… При ограничении на кап. вложения вывод аналогичен, только fi=ci, F=C. 20. Задача продавца газет
Партии товара Q поступают регулярно через Т, через этот промежуток продается случайное количество товара R, к моменту поставки новой партии старый товар теряет свои потребительские свойства. Т – интервал времени м. д. поставками Q – объем заказываемой партии R – объем продаж (СВ) С1 [руб/ед] – потери от не реализации товара. С2 [руб/ед] – упущенная выгода в случае нехватки товара. Функция предпочтения: , j(Q, R)®min.
Критерий: Средняя величина убытков (за достаточно долгий период) минимальна: M[j(Q, R)] ®min Предполагается, что мы провели исследования и знаем функцию спроса: , , Для того, чтобы найти минимум необходимо решить уравнение: 21. Система управления запасами (N, n) – типа.
N- верхняя оптимальная отметка (выкл. ). n – нижняя оптимальная отметка (вкл. ). Заявки: простейший поток с интенсивностью l, Заявки: простейший поток с интенсивностью m. Очередь не ограничена. m>l- иначе очередь безгранично растет. Состояние системы может быть охарактеризовано двумя параметрами: 1) поставки вкл. или выкл. 2) k=(-Ґ, N) – уровень запасов, если kі0 то уровень запасов, если k P-m+1Чl – PmЧm = 0 ; k = -m Pk+1Чl – PkЧm – PkЧl + Pk-1Чm = 0 ; -m+1 Ј k Ј n+1 Pn+1’Чl + Pn+1Чl + Pn-1Чm – PnЧm – PnЧl = 0 ; k = n
Pk+1Чl – PkЧm – PkЧl + Pk-1Чm = 0 ; Верхний блок n+1 Ј k Ј N-1 Pk+1’Чl – Pk’Чl = 0 ; Нижний блок (n+1)’ Ј k’ Ј (N-1)’ Pk-1Чm – PkЧl – PkЧm = 0 ; k = N PkЧm – Pk’Чl = 0 ; k = N’ 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} = , где Рдоп и l – заданные нами величины – вероятность того, что длинна очереди не превысит l. Cy [руб/деньЧед] – штраф за ожидание в очереди; Сz [руб/деньЧед] – плата за хранение запаса;
CyЧ`y(N, n, a) + (Cz+EHC)Ч`Z(N, n, a) ® min; Pl*(N, n, a)ЈPдоп. 23. Сетевые модели
В 1955 году зародились методы и модели сетевого планирования. PERT – метод оценки и пересмотра планов. СПУ –сетевое планирование и управление. Применяется: планирование и управление крупными техническими проектами, учебным процессом. Назначение: системный анализ сложных комплексов работ и осознание их в взаимосвязи; регулирование процесса выполнения комплекса работ, путем пересмотра плана. Событие – завершение выполнения всех предшествующих работ.
Ни одно событие, кроме истока, не может произойти до тех пор, пока не будут закончены все входящие в него работы.
Ни одна работа выходящая из данного события не может начаться раньше, чем произойдет данное событие.
Ни одна последующая работа не может начаться раньше, чем закончатся все предшествующие ей работы. Сетевая модель не должна содержать циклов
Ранг – наибольшее количество работ от истока до данного события. Алгоритм упорядоченной нумерации (события наступающие позже имеют больший номер): Исходу (началу) присваивается ранг k=0 и номер i=0. Вычеркиваем выходящие из исхода работы
Присваиваем ранг k=1 всем событиям в которые входят вычеркнутые работы и не входят никакие другие.
Пронумеруем все события ранга k=1 в произвольном порядке продолжая нумерацию. и т. д. Процедура продолжается до последнего события – стока. Это произойдет в том случае, если нет циклов. Если множество событий к-го ранга оказалось пустым, и не все события оказались пронумерованы– это значит, что в ходе нумерации мы подошли к событиям образующим цикл. 24. Детерминированный анализ сетевой модели
TiЪ- раннее время наступления события i; Все работы руководствуются правилом: работа tij начинается ка только произошло событие i – раннее время. TjЪ = , j=1...I, T0Ъ=0. Работа (i) начинается сразу после окончания события (j). TiЩ- позднее время наступления события i. Работа (i) должна быть закончена к моменту начала (j).
TiЩ = , i=(I-1)...0. R – резерв времени события. TIЪ = TIЩ; T0Ъ = T0Щ Критический путь –последовательность событий, в которых работы плотно прилегают одна к другой. Как только заканчивается одна, сразу же начинается другая. Путь идет от начала до конца... rijЪ - свободный резерв времени работы; rijЩ - полный резерв; rij’ – частный резерв.
1го рода –для увеличения продолжительности данной работы и последующих, не меняя предыдущие.
2го рода –для увеличения продолжительности данной работы и предыдущих, не меняя последующие.
Полный резерв сокращает продолжительность всего комплекса работ. Свободный резерв не сокращает продолжительность всего комплекса работ, изменяет только данную. 25. Вероятностный анализ сетевой модели Fij(t) = P{Tij строим плотность распределения отсечем хвосты, чтобы сумма была равна 0, 0027
tij = M[Tij] –вычисляется по эмпирической формуле, выработанной годами исследований и испытаний. ,
Флюктуации продолжительности работ не приведут к изменению критического пути. Работы в сетевом графике статистически взаимонезависимы. Теорема Ляпунова–сумма бесконечного (большого) числа статистически независимых случайных слагаемых, асимптотически стремится к нормальному распределению. Длительность критического пути имеет нормальное распределение, мат. ожидание`Т и дисперсию s. Тогда функция распределения выглядит: , введем подстановки ; ; ; получим: . Стандартные функции табулированы: P{Tіt} = p = P{Xіx} = 1 – Ф(х); t – плановое, Т – фактическое, Р –вероятность того, что продолжительность комплекса работ не превысит заданную величину. 26. Оптимизация плана комплекса работ
Управлять продолжительностью работ мы можем через выделение каждой работе определенного объема ресурсов. Каждая работа потребляет множество ресурсов, часть из них взаимонезаменяема. Имеет смысл управлять теми ресурсами, которые можно перебросить с одной работы на другую. В основе метода лежит идея о том, что продолжительность работы зависит от количества выделенного на нее ресурса. xij – количество мобильного ресурса, задействованного в работе ij. xi – момент наступления события i. x0=0 – момент начала работ
`Т – заданная величина интервала времени, отведенного на выполнение комплекса работ Сколько ресурсов нужно потратить, чтобы уложиться в `Т. И при этом потратить минимум. Нужно установить модуль tij = fij(xij). Как зависит продолжительность работы от выделенного на нее ресурса. С ростом количества ресурсов, время убывает. Линейная зависимость: tij = aij - bijxij , a, b – положительные величины... Сокращение комплекса работ (смысл в том, чтобы все пути стали критическими). Задача перераспределения ресурса. Установили, что требуется Х мобильного ресурса, мы не хотим уменьшить этот ресурс, но хотим перераспределить, так, чтобы сократить время комплекса работ. - мы не требуем больше чем Х ресурсов.
xi + fij(xij) Ј xi, iОBj , j=1...I X®min –минимизируем момент наступления послед. события x0 = 0, xij і 0, iОBj , j=1...I - это задача мат. программирования, получим xij*, xi* - решение носит численный характер 27. Динамическое программирование а - Шаговый эффект (wn) 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) – вектор, совокупность всех действий на всех шагах , если w®max, то F(W)®max, wn>0 , . Мультипликативный эффект: 28. Принцип оптимальности, уравнение Беллмана
траектория Adоптимальная, переход совершен оптимальным образом Целевая функция аддитивна, т. е. WAD=wAB+wBC+wCD Всякий отрезок оптимальной траектории – оптимален. Оптимизация многошагового процесса:
W(Sn) – эффективность движения из Sn в SN (конечное). Рассчитывают для каждого состояния, двигаясь из конечного в начальное. W(SN)=0, n=N...0. Правило носит название уравнения Беллмана: , Wn=jn(Sn-1, Sn) – шаговый эффект. Задаем Sn-1 и ищем такое Sn в которое нам эффективней двигаться и ищем W(Sn-1). Уравнение Беллмана нужно решать столько раз, сколько N. На каждом шаге столько, сколько состояний. . 29. задача о распределении ресурсов
Нам дано N объектов, с номерами n=1...N. Выделено некоторое число ресурсов R , . Wn(Rn) –сколько прибыли принесет ресурс, если будет выделен определенному объекту (эффект). Задача: . n-ый шаг – выделение ресурсов n-му объекту. Управление (xn = Rn) – количество ресурсов, которые мы выделим n-му объекту. Sn – количество нераспределенного ресурса после завершения n-го шага. S0=R, SN=0. 30. Задача планирования и управления запасами tn – набор моментов отгрузки оборудования t0 – момент начала работы
Rn – плановый объем продукции, которые мы должны отгрузить в tn R0=0, Rn – целочисленен (продукция дискретна)
`xn – предельная производительность на n-ом интервале. 0ЈxnЈ xn В разное время производительность различна wn – издержки производства и хранения на n-ом интервале параметры: an – издержки на производство единицы продукции (руб/шт) bn – издержки на наладку оборудования (руб/партия) cn – издержки хранения еденицы продукта (руб/шт) Ограничения: zn – величина запаса в момент tn+0, , z0=0
Целевая функция: Средний уровень запаса=(запас в начале + запас в конце)/2 - функция управления. , 31. Модель замены оборудования
Мы покупаем какую-либо единицу оборудования, исходя из того, что бизнес продлится 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 за весь срок. , rn, i –расходы на эксплуатацию оборудования, купленного в году n на i-м году. В каком году мы бы не находились, насколько нам выгодно покупать станок. При том, что суммарные издержки (wn, n+k) были бы минимальными. WN – минимальные 32. Бесконечношаговое динамическое программирование
N®Ґ, число шагов бесконечно... Список состояний не меняется. S – состояние в начале шага, S’ – состояние в конце. w = j(S, S’). , уравнение для некоего обезличенного шага, решается один раз для всех шагов. 0