Выдержка из текста работы
1. Основные понятия и основные этапы операционного исследования Операция совокупность действий направленная на достижение заданных целей Управляемая операция это операция которая может быть реализована во многих вариантах Оперирующая сторона совокупность людей и автоматов, стремящихся в данной операции достигнуть поставленных целей Исследователь операций один человек или группа людей Активные средства это те ресурсы, которыми располагает оперирующая сторона люди, финансы, оборудование Стратегии способы действий оперирующей стороны, направленные на достижение поставленных целей в данных реальных обстоятельствах Критерий эффективности целевая функция это математическая модель цели Фазовые переменные набор величин, которые с достаточной точностью показывают протекание операции во времени Неконтролируемые факторы факторы, независящие о оперирующей стороны, но зависят от исхода операции, делятся на детерминированные, стохастические, неопределенные.
Содержательная постановка Осознание цели Построение модели Идентификация, верификация модели Формирование класса стратегий Поиск методов решения Решение Анализ результатов Внедрение решения Обработка решения 2. Обобщенная схема операций Zt вектор фазовых переменных характеризующих состояние операции Xt набор управляющих воздействий величины находящихся в нашей власти A0 a0i ресурсы имеющиеся в нашем распоряжении Atait вектор ресурсов фактически используемых Yt неопределенные, неконтролируемые факторы построение модели операции как влияют внешние факторы Y и X на поведение операции Zt ft, X, Y,0,T, f вектор-функционал, моделирующий операцию как мы потребляем ресурсы At t, X, Y, 0,T вектор функционал решаем проблему целеполагания формируем функционал предпочтения определяем критерий определяем целевую функцию Результатом решения операции является стратегия оперирующей стороны Xt t, Z, Y, 0,T 3. Критерий эффективности — это правило, которым мы руководствуемся при выборе вариантов, он отражает наши цели и предпочтения сложный критерий много целей Для неопределенных факторов Заранее знаем Yt на промежутке 0,T это определенный критерий, наша задача Wmax Процесс Yt является элементом некоторого множества процессовY , известного нам множества. Выводим целевую функцию M min YtYWmax лучшее поведение в худших условиях.
Для Yt случайная величина MW max, PWW0 P4. Марковские процессы один из видов случайных простых процессов, это процесс при котором будущее не зависит от прошлого при известном настоящем.
Устанавливает связь между будущим и текущим.
Может быть дискретным, если Xt дискретно, и непрерывным, если Xt непрерывным.
Он может быть процессом с дискретным или непрерывным временем.Марковский процесс с дискретными состояниями называется Марковскими цепями. 5. Марковские процессы с непрерывным временем и их числовые характеристики Система в момент t находится в состоянии nti. Рассмотрим величину nttj, ij. Pnttj nti — интенсивность перехода система из состояния i в j. Если хотя бы одна зависит от t, то процесс неоднородный, т.е. зависит от времени. Если все ij константы, то процесс однородный.
Если t достаточно мал, то имеем Pijt, t ijt t вытекает из формулы в рамке, тем точнее, чем меньше t. Для того чтобы описать марковский процесс необходимо записать матрицу t ijtNN, запретные переходы ijt0, iit. Достаточное условие существования финальных вероятностей если система имеет конечное число состояний и за конечное число шагов может перейти из одного состояния в любое другое, это означает, что существуют финальные вероятности состояний процесс стационарный. 6. Уравнения Колмогорова для Марковских процессов с непрерывным временем. Sn, n1N, PntiPit вероятность того что состояние будет с номером i. Колмогоров доказал, что процесс Pit детерминирован и определяется уравнениями Колмогорова.
Пусть процесс находиться в состоянии Si процесс может выйти и войти в него. Уравнения Колмогорова для неоднородного. -однородный процесс не зависит от t. Через продолжительное время процесс успокаивается и вероятности станут константами.
Марковский процесс при t вырождается в стационарный Марковский процесс.Через длительное t — вырожденное уравнение К. Достаточное условие вырождение МП в стационарный число состояний системы конечно из любого состояния за конечное число шагов можно попасть в любое другое 8. Схема гибели и размножения. Основание рост популяции.
S0 Нижний предел числен.SN верхний предел. n1 N номера состояний. Если все известны, то можем найти Р, если знаем Р0 делим на р9. Вероятностные свойства перехода МП из состояния в состояние. Известно, что процесс вышел из состояния i, какова вероятность того, что он попадет в j Рассмотрим следующие события А на интервале t,tt произошел выход из состояния i В происходит выбор одного из состоянийSi и переход в него Рассмотрим вероятность совпадения событий А и В PAB ijt PBAPA где — интенсивность выхода из i В состоянии Si процесс пребывал случайное время и мы знаем что это МП. Каковы статистические свойства этого случайного времени Т случайное время пребывания в Si, FiPT , 0 nti процесс в состоянии находился в течении Т, nt0i через Тt процесс покинет состояние.
Мы наблюдали за процессом в течении 0 и он не вышел из состояния.PT T0 0 PT-0 -0 Fi-0. из условий , следует, что . Рассмотрим вероятность того, что МП покинул состояние на интервале 0, 0t 10. Основные понятия теории массового обслуживания МО Система МО структура из обслуживающих приборов, потоков заявок и очередей.
Источник Входящий поток заявок интенсивность входящего потока . Исходящий поток интенсивность входящего потока . Канал обслуживания число каналов n, среднее число занятых k, производительность . Очередь среднее число заявок z, среднее время пребывания одной заявки t . Дисциплина обслуживания правила, по которым действуют СМО. в порядке поступления случайно fifo lifo с приоритетом абсолютный, относительный по условиям ожидания с отказами с очередью по условиям организации очереди с ограниченной очередью с ограниченным временем пребывания в очереди по месту нахождения источников заявок закрытые источник в системе и оказывает на нее влияние открытые вне системы и не оказывает влияния по фазам однофазные один этап обслуживания многофазные два и более этапов по числу каналов одноканальные многоканальные 11. Потоки событий Каждому событию соответствует момент t в который это событие произошло.
Т интервал между двумя моментами времени СВ. Поток событий независимая последовательность моментов t. по случайности регулярные Т-const случайные Т-СВ. по постоянности вероятностных свойств стационарные нестационарные по связи будущего поведения с прошлым с последействием без последействия по числу заявок в одном событии ординарные событию соответствует одна заявка неординарные — событию соответствует случайное число заявок 12. Простейший Пуассоновский поток t2 t1, t2-t1, Pnk t2 t1pk, вероятность того, что на интервале произошло k событий Самый случайный из всех случайных ординарных потоков Свойства случайный, стационарный, ординарный, без последействия, имеет распределение Пуассона Содержательный смысл параметра, распределение времени м.д. заявками — интенсивность потока, то есть среднее число заявок в единицу времени.
Функция распределения — вероятность того, что время м.д. заявками будет меньше t. Вероятность наступления хотя бы одного события на малом интервале времени Pn1t2-t1t1-p0 Мы установили, что в t0 произошло последнее событие.
Какова вероятность того, что следующее случиться позднее чем t0. Обозначим Т СВ интервал времени м.д. событиями.
Какова вероятность того, что Т. PT значит что на событий не произошло. Закон распределения времени обслуживания 14. Потоки Пальма и Эрланга Пальма.Интервалы м.д. событиями взаимонезависим статистическая взаимосвязь, случаен и имеет одинаковое распределение.
Распределение интервалов могут быть любыми. Ординарный. Пуассоновский поток частный случай потока Пальма. пример системы, где соблюдаются интервалы движения. Эрланг. Применяем операцию просеивания к простейшему потоку. Оставляем каждое k-ое событие поток Эрланга k-го порядка. Функция распределения — Тк интервал времени м.д. событиями.Тк — вероятность этого события — вероятность того, что на произошло к-1 событие. Известна интенсивность простейшего потока из которого получили поток Эрланга к-го порядка.
Хотим, чтобы на интервале произошло к-1 событие, а на — 1 событие чтобы Тк произошло одно событие на . Функция плотности распределения . TkkT средняя продолжительность интервалов м.д. событиями kk интенсивность потока Эрланга к-го порядка 2кк2 дисперсия интервалов времени — коэффициент вариации. С ростом порядка потока Эрланга Сv 0, поток становиться более упорядоченным.Подбирая порядок потока Эрланга мы обеспечиваем более высокую реалистичность. 15. Простейшая Марковская многоканальная, однофазная СМО часть заявок не обслуживается. m каналов обслуживания.
Входящий поток простейший с интенсивностью , интервалы м.д. событиями распределены ft e Приборы статистически одинаковы и всегда исправны, отказов в связи с поломкой нет. Время обслуживания прибором случайно, но у всех приборов это время имеет плотность распределения f0te- статистически независимо.Интервалы времени обслуживания заявок взаимонезовисимы.
Дисциплина обслуживания если все приборы заняты заявка встает в очередь и ждет обслуживания. в модели безразлично в каком порядке будут обслужены заявки. освободившийся прибор сразу приступает к обслуживанию заявки в очереди, если таковая имеется. если величина очереди достигла N-m предельной величины, очередная заявка получает отказ.Характеристики состояния — вероятность того, что система будет простаивать вероятность того, что в системе будет определенное число заявок Характеристики функционирования — вероятность отказа системы — относительная пропускная способность вероятность — заявка обслужена — абсолютная пропускная способность среднее число заявок с системе — среднее число занятых каналов 16. Оптимизация А рубприбор инвестиции в 1 прибор рубчас прибор эксплуатационные затраты на 1 прибор В рубзаявка инвестиции омертвленные в заявке, находящейся в системе рубчас заявка текущие эксплуатационные расходы С рубместо — инвестиции в 1 место на стоянку рубчас место затраты на поддержание 1 места в очереди ремонт, очистка и т.п. рубзаявка упущенная выгода от отказа заявке в обслуживании Ен 1час нормативный коэффициент эффективности Мы совершили инвестицию в прибор и имеем потери ЕнАmmЕнВkВkЕнСN-m N-m PNF1m,N, приведенные затраты min Другой вариант оптимизируемая величина m,N Минимизация издержек на 1 заявку. 17. Простейшая Марковская одноканальная, однофазная СМО m1, N 1 -система в среднестатистическом смысле справляется с потоком заявок. Если условие не выполняется, очередь будет расти безгранично. k1 Факторы повышения запаса дискретность поставок при непрерывном спросе случайные колебания в спросе, в объеме поставок, в интервале м.д. поставками предполагаемые изменения в конъюнктуре сезонность Факторы снижения запаса плата за хранение упущенный доход потери в количестве запасов испарение, усыхание моральный износ 19. Управление запасами при постоянном спросе и регулярных поставках задача Джонсона gi затраты на переналадку или на доставку i-го товара партия. si затраты на хранение i-го вида запаса шт. fi площадь склада под i-й вид запаса шт. Yi максимальный запас на складе i-го вида запаса шт. QiYi объем заказываемой партии i спрос на i-го вида запаса.
Ci стоимость единицы i-го вида запаса шт. С кап. вложения. F емкость склада Функция Лагранжа , Q1,n множитель Лагранжа показывает как изменится функция Лагранжа L, целевая функция LQ при изменении емкости склада F от сюда находим Qio, Fo При ограничении на кап. вложения вывод аналогичен, только fici, FC. 20. Задача продавца газет Партии товара Q поступают регулярно через Т, через этот промежуток продается случайное количество товара R, к моменту поставки новой партии старый товар теряет свои потребительские свойства.
Т интервал времени м.д. поставками Q объем заказываемой партии R объем продаж СВ С1 рубед потери от не реализации товара.
С2 рубед упущенная выгода в случае нехватки товара. Функция предпочтения , Q,Rmin. Критерий Средняя величина убытков за достаточно долгий период минимальна MQ,R min Предполагается, что мы провели исследования и знаем функцию спроса Для того, чтобы найти минимум необходимо решить уравнение 21. Система управления запасами N,n типа. N- верхняя оптимальная отметка выкл n нижняя оптимальная отметка вкл Заявки простейший поток с интенсивностью , Заявки простейший поток с интенсивностью . Очередь не ограничена иначе очередь безгранично растет.
Состояние системы может быть охарактеризовано двумя параметрами 1 поставки вкл. или выкл. 2 k N уровень запасов, если k0 то уровень запасов, если k 0 то длинна очереди.
Sk состояние системы при запасах k и вкл. поставках, Sk состояние системы при запасах k и выкл. поставках. Pk вероятность того, что система в состоянии Sk, Pk — вероятность того, что система в состоянии Sk . Уравнения Колмогорова 1. P-m1 Pm 0 k -m 2. Pk1 Pk Pk Pk-1 0 -m1 k n1 3. Pn1 Pn1 Pn-1 Pn Pn 0 k n 4. Pk1 Pk Pk Pk-1 0 Верхний блок n1 k N-1 5. Pk1 Pk 0 Нижний блок n1 k N-1 6. Pk-1 Pk Pk 0 k N 7. Pk Pk 0 k N 8. 22. Модель N,n типа, оптимизация a, Решение этой системы дает Р как функцию от N, n, a N,n,a Pk kN,n,a Pk k N,n,a l длинна очереди, Рl Pk -l , где Рдоп и l заданные нами величины вероятность того, что длинна очереди не превысит l. Cy рубденьед штраф за ожидание в очереди Сz рубденьед плата за хранение запаса CyyN,n,a CzEHCZN,n,a min PlN,n,aPдоп. 23. Сетевые модели В 1955 году зародились методы и модели сетевого планирования.
PERT метод оценки и пересмотра планов.
СПУ сетевое планирование и управление.
Применяется планирование и управление крупными техническими проектами, учебным процессом.
Назначение системный анализ сложных комплексов работ и осознание их в взаимосвязи регулирование процесса выполнения комплекса работ, путем пересмотра плана. Событие завершение выполнения всех предшествующих работ. Ни одно событие, кроме истока, не может произойти до тех пор, пока не будут закончены все входящие в него работы.Ни одна работа выходящая из данного события не может начаться раньше, чем произойдет данное событие.
Ни одна последующая работа не может начаться раньше, чем закончатся все предшествующие ей работы. Сетевая модель не должна содержать циклов Ранг наибольшее количество работ от истока до данного события.Алгоритм упорядоченной нумерации события наступающие позже имеют больший номер 1. Исходу началу присваивается ранг k0 и номер i0. 2. Вычеркиваем выходящие из исхода работы 3. Присваиваем ранг k1 всем событиям в которые входят вычеркнутые работы и не входят никакие другие. 4. Пронумеруем все события ранга k1 в произвольном порядке продолжая нумерацию. 5. и т.д. Процедура продолжается до последнего события стока.
Это произойдет в том случае, если нет циклов.Если множество событий к-го ранга оказалось пустым, и не все события оказались пронумерованы это значит, что в ходе нумерации мы подошли к событиям образующим цикл. 24. Детерминированный анализ сетевой модели Ti — раннее время наступления события i Все работы руководствуются правилом работа tij начинается ка только произошло событие i раннее время. Tj , j1 I, T00. Работа i начинается сразу после окончания события j. Ti — позднее время наступления события i. Работа i должна быть закончена к моменту начала j. Ti , iI-1 0. R резерв времени события.
TI TI T0 T0 Критический путь последовательность событий, в которых работы плотно прилегают одна к другой.Как только заканчивается одна, сразу же начинается другая. Путь идет от начала до конца rij — свободный резерв времени работы rij — полный резерв rij частный резерв. 1го рода для увеличения продолжительности данной работы и последующих, не меняя предыдущие. 2го рода для увеличения продолжительности данной работы и предыдущих, не меняя последующие.
Полный резерв сокращает продолжительность всего комплекса работ.Свободный резерв не сокращает продолжительность всего комплекса работ, изменяет только данную. 25. Вероятностный анализ сетевой модели Fij PTij 1. строим плотность распределения 2. отсечем хвосты, чтобы сумма была равна 0,0027 tij MTij вычисляется по эмпирической формуле, выработанной годами исследований и испытаний Флюктуации продолжительности работ не приведут к изменению критического пути. Работы в сетевом графике статистически взаимонезависимы.
Теорема Ляпунова сумма бесконечного большого числа статистически независимых случайных слагаемых, асимптотически стремится к нормальному распределению.Длительность критического пути имеет нормальное распределение, мат. ожидание Т и дисперсию . Тогда функция распределения выглядит , введем подстановки получим . Стандартные функции табулированы PT p PXx 1 Фх плановое, Т фактическое, Р вероятность того, что продолжительность комплекса работ не превысит заданную величину. 26. Оптимизация плана комплекса работ Управлять продолжительностью работ мы можем через выделение каждой работе определенного объема ресурсов.
Каждая работа потребляет множество ресурсов, часть из них взаимонезаменяема.
Имеет смысл управлять теми ресурсами, которые можно перебросить с одной работы на другую.В основе метода лежит идея о том, что продолжительность работы зависит от количества выделенного на нее ресурса. xij количество мобильного ресурса, задействованного в работе ij. xi момент наступления события i. x00 момент начала работ Т заданная величина интервала времени, отведенного на выполнение комплекса работ Сколько ресурсов нужно потратить, чтобы уложиться в Т. И при этом потратить минимум.
Нужно установить модуль tij fijxij .Как зависит продолжительность работы от выделенного на нее ресурса. С ростом количества ресурсов, время убывает . Линейная зависимость tij aij — bijxij , a,b положительные величины Сокращение комплекса работ смысл в том, чтобы все пути стали критическими. Задача перераспределения ресурса.Установили, что требуется Х мобильного ресурса, мы не хотим уменьшить этот ресурс, но хотим перераспределить, так, чтобы сократить время комплекса работ мы не требуем больше чем Х ресурсов. xi fijxij xi, iBj , j1 I Xmin минимизируем момент наступления послед. события x0 0, xij 0, iBj , j1 I — это задача мат. программирования, получим xij, xi — решение носит численный характер 27. Динамическое программирование а — Шаговый эффект wn Sn состояние системы на n-ом шаге. Sn Sn множество состояний системы на n-ом шаге. Wn Sn-1, Sn шаговый эффект зависит от того, из какого состояния вышла система и в какое вошла. xn xnSn-1,Sn управление wn wnxn-1,xn шаговый эффект Snnxn,Sn-1 Управление Xx1,x2 xnxN вектор, совокупность всех действий на всех шагах , если wmax, то Wmax, wn 0 Мультипликативный эффект 28. Принцип оптимальности, уравнение Беллмана 1. траектория Adоптимальная, переход совершен оптимальным образом 2. Целевая функция аддитивна, т.е. WADwABwBCwCD Всякий отрезок оптимальной траектории оптимален.
Оптимизация многошагового процесса WSn эффективность движения из Sn в SN конечное.
Рассчитывают для каждого состояния, двигаясь из конечного в начальное. WSN0, nN 0. Правило носит название уравнения Беллмана ,WnnSn-1,Sn шаговый эффект.
Задаем Sn-1 и ищем такое Sn в которое нам эффективней двигаться и ищем WSn-1. Уравнение Беллмана нужно решать столько раз, сколько N. На каждом шаге столько, сколько состояний 29. задача о распределении ресурсов Нам дано N объектов, с номерами n1 N. Выделено некоторое число ресурсов R WnRn сколько прибыли принесет ресурс, если будет выделен определенному объекту эффект.Задача . n-ый шаг выделение ресурсов n-му объекту.
Управление xn Rn количество ресурсов, которые мы выделим n-му объекту.Sn количество нераспределенного ресурса после завершения n-го шага. S0R, SN0. 30. Задача планирования и управления запасами tn набор моментов отгрузки оборудования t0 момент начала работы Rn плановый объем продукции, которые мы должны отгрузить в tn R00, Rn целочисленен продукция дискретна xn предельная производительность на n-ом интервале. 0xn xn В разное время производительность различна wn издержки производства и хранения на n-ом интервале параметры an издержки на производство единицы продукции рубшт bn издержки на наладку оборудования рубпартия cn издержки хранения еденицы продукта рубшт Ограничения zn величина запаса в момент tn0 z00 Целевая функция Средний уровень запасазапас в начале запас в конце2 — функция управления 31. Модель замены оборудования Мы покупаем какую-либо единицу оборудования, исходя из того, что бизнес продлится N лет. n0 N порядковый номер года k1 N-n срок службы оборудования его купили на k лет wn,nk суммарные издержки на приобретение, эксплуатацию и ремонт оборудования за всю службу. wn,nk pn bn,k cn,nk pn стоимость оборудования bn,k остаточная стоимость оборудования, купленного в году n и проданного в году k cn,nk суммарные затраты на эксплуатацию и ремонт оборудования купленного в году n за весь срок rn,i расходы на эксплуатацию оборудования, купленного в году n на i-м году. В каком году мы бы не находились, насколько нам выгодно покупать станок.
При том, что суммарные издержки wn,nk были бы минимальными. WN минимальные 32. Бесконечношаговое динамическое программирование N, число шагов бесконечно Список состояний не меняется.
S состояние в начале шага, S состояние в конце. w S,S уравнение для некоего обезличенного шага, решается один раз для всех шагов. 0 1 учитывает фактор времени, т.е. с течением времени эффект теряет свою ценность. Решение имеется не всегда, если нашли функцию WS удовлетворяющую данному уравнению задача решается методом бесконечношагового динамического программирования.
Если нет решения, то нужно решать конечношаговые задачи, увеличивая число шагов.
Если функция стабилизируется с числом шагов, то можно считать ее приближенным решением, если нет то необходим другой мат. аппарат.
