Бронов С.А. Исследование операций

Подождите немного. Документ загружается.

Бронов, С. А. Исследование операций: конспект лекций

Прямая задача заключается в том, чтобы при заданных входных пере-

менных

определить значения выходных переменных

)

(



Обратная задача заключается в том, чтобы определить, какими должны

быть входные значения

, чтобы обеспечить желаемые значения

)(

yfx



 .

В простейшем случае это просто, если уравнения разрешимы относи-

тельно своих входных переменных. Но это бывает не всегда. Тогда для реше-

ния обратной задачи приходится многократно решать прямую и выбирать те

решения, которые оказываются наиболее подходящими — близкими к жела-

емым.

Таким образом, прямая задача является основной и наиболее часто ре-

шаемой. Она относится к анализу систем. Именно эта прямая задача и назы-

вается моделированием. Обратная задача является задачей синтеза. Она не

всегда может быть решена аналитически, т. е. в виде формулы. Формально

невозможность решения обратной задачи связана с тем, что не всегда исход-

ные уравнения математического описания могут преобразовываться так,

чтобы выделить входную величину в виде )(

yfx



 , т. е. определить об-

ратную функцию. Например, из уравнения





)sin(

2cos

xay

 невозможно

выразить

в функции от

Для решения обратной задачи часто приходится упрощать исходные вы-

ражения с учётом реального соотношения параметров. Например, если в вы-

ше приведённом выражении параметр мал:

00001



, то выражение можно

упростить: )sin(

xy  , и уже из него получить обратную функцию:

)sin( yx  . Поэтому часто задача синтеза может дать лишь приближённое

решение. Для его проверки используется анализ по полному исходному вы-

ражению. При этом оказывается возможным учитывать те факторы, которые

при синтезе не учитывались. Поэтому в реальности после решения задачи

синтеза всегда решается задача анализа полученного синтезированного ре-

шения.

Рассмотренный пример связан с попытками аналитического решения

задач анализа и синтеза. Но не всегда даже задачу анализа можно решить

аналитически (выводом формул): например, не находятся аналитически кор-

ни уравнения больше 4-й степени и т. д. Тогда приходится использовать чис-

ленные методы и ЭВМ.

Дополнительные проблемы возникают, если математическая модель

представляет собой дифференциальные или интегральные уравнений. Реше-

Бронов, С. А. Исследование операций: конспект лекций

нием дифференциальных уравнений является функция, а процесс решения

представляет собой операцию интегрирования. Известно, что далеко не все-

гда возможно выполнить интегрирование в аналитическом виде. В этом слу-

чае приходится использовать численное интегрирование.

С точки зрения моделирования, технические и организационные объек-

ты существенно различаются. Примерами технических объектов являются:

станки, самолёты, космические аппараты, атомные реакторы, электронные

устройста и т. д. В основе их математического описания лежат физические

законы.

Примерами организационных объектов являются: организации различ-

ных организационно-правовых форм (предприятия, банки, общественные

объединения, государственные учреждения и т. п.), органы власти (исполни-

тельной и законодательной, федеральной и муниципальной), конкретные ме-

роприятия (конгрессы, встречи, аукционы, митинги, шествия, спортивные

соревнования и т. п.), суды, адвокатские конторы, средства массовой инфор-

мации и др. Они функционируют, производя промышленную продукцию,

услуги, законодательные акты, управленческие решения и т. д. Каждый такой

организационный объект имеет свою структуру, т. е. взаимосвязанные и вза-

имодействующие элементы. Через эти элементы внутри организации проте-

кают различные потоки — материальные, финансовые, информационные и

др. Каждый организационный объект для выполнения своих функций ис-

пользует различные ресурсы — материальные, финансовые, человеческие,

интеллектуальные, информационные и др. В большинстве случаев организа-

ционные объекты взаимодействуют с внешней средой и получают от неё воз-

действия различного рода, способствующие или препятствующие выполне-

нию их функций. В обществе организационные объекты взаимодействуют

между собой и таким образом образуют организационные системы. В основе

их математического описания лежат не столько физические законы, сколько

логические правила, причинно-следственные связи и т. п.

Рассмотрим пример организационного объекта.

Промышленное предприятие занимается производством определённо-

го вида продукции, например, хлеба. После производства хлеб развозят по

магазинам и реализуют. Требуется проанализировать процесс производства и

реализации хлеба с точки зрения отсутствия сбоев в производстве, загружен-

ности складских помещений, достаточности транспортных средств, времени

доставки в магазины и т. д. При этом возможна постановка как задачи анали-

за, т. е. исследования существующих процессов на действующем предприя-

тии, так и задача синтеза, т. е. выбора параметров этих процессов — числа

автомобилией, размера оплаты работникам и т. д. Для обеих задач требуется

создание моделей.

Бронов, С. А. Исследование операций: конспект лекций

Всю цепочку производства-сбыта можно разделить на следующие эта-

пы:

 производство;

 хранение готовой продукции;

 транспортировка продукции в магазины;

 продажа продукции;

 получение дохода и прибыли.

Каждый этап можно детализировать.

Этап производства. Продукцию получают путём последовательной пе-

реработки исходного сырья в нескольких цехах через некие технологические

цепочки. При этом поступает сырьё, функционирует оборудование, работает

персонал, продукция накапливается в цехах. Соответственно этому выпол-

няются отдельные операции. Всё это занимает определённое время и требует

определённого объёма сырья, числа сотрудников, загрузки оборудования.

Хранение готовой продукции. Готовая продукция поступает на склад и

там хранится до отправки в магазины. При этом осуществляются операции

транспортировки продукции из цехов на склад, размещение на складе, учёт,

контроль времени нахождения на складе. Для этого задействованы средства

транспортировки (внутризаводской транспорт), персонал, складские площади

(в частности, места хранения). Возможны определённые ограничения, свя-

занные с размерами продукции, использованием специальных приспособле-

ний и т. д. Возможно, что некоторые виды продукции должны храниться раз-

дельно.

Транспортировка продукции в магазины. Продукция продаётся через

сеть магазинов в городе и вывозится со склада специальным транспортом по

расписанию. Продукция вырабатывается в определённое время суток, а раз-

возится в другое время суток. При этом задействован персонал, а также

транспортные средства — завода или магазинов. Транспортировка должна

быть согласована с магазинами и выполняться в определённой последова-

тельности: желательно проложить маршруты перевозки продукции так, что-

бы уменьшить число поездок и количество задействованного транспорта.

Продажа продукции осуществляется в определённое время суток, при-

чём интенсивность продажи меняется в течение дня. Продукция временно

хранится на складе магазина или в торговом зале, занимая некоторое время.

Получение дохода и прибыли в целом связано с успешностью продажи

продукции и необходимостью учёта множества факторов, часть которых

имеет случайный характер: наличие, объём и поступление исходного сырья,

время работы оборудования в различных режимах, возможность его полом-

ки, необходимость покупки запасных частей и время ремонта (с использова-

нием соответствующего ремонтного персонала), скорость транспортировки

Бронов, С. А. Исследование операций: конспект лекций

из цехов на склад и со склада в магазины, последовательность передвижения

транспорта от магазина к магазину, затрачиваемое время на погрузку и раз-

грузку, заработная плата всех работников, налоговые отчисления и др.

Для правильного планирования работы необходимо иметь возможность

проанализировать все рассмотренные процессы в их взаимосвязи. Интерес

могут представлять доходы фирмы, ритмичность её работы, достаточность

задействованных ресурсов (оборудования, исходного сырья и т. д.), износ

оборудования и др.

В настоящее время можно говорить о проектировании организационных

систем по аналогии с проектированием технических систем. Для технических

систем существует хорошо развитый аппарат теории автоматического управ-

ления, который предоставляет не только набор формальных методов проек-

тирования, но также методологическую основу и общесистемные принципы

к проектированию систем различной природы. Поэтому целесообразно рас-

смотреть особенности организационных систем в сравнении с техническими

системами.

В процессе проектирования организационных систем, также как и тех-

нических, выбирают структуру, параметры, переменные состояния (из кото-

рых может формироваться набор выходных переменных) и внешние воздей-

ствия (из которых выделяют управляющие воздействия). В процессе проек-

тирования решаются две задачи — анализа и синтеза. Под анализом понима-

ют определение поведения переменных состояния (и связанных с ними вы-

ходных переменных) при заданных управляющих воздействиях. Под синте-

зом понимают определение вида управляющих воздействий, позволяющих

реализовать желаемое изменение переменных состояния.

Конечной целью проектирования обычно является синтез, но выполнить

его сложно, так как задача синтеза с точки зрения математики связана с ре-

шением той или иной системы уравнений. В моделях технических систем

обычно используются алгебраические, дифференциальные или логические

уравнения. При определённом их виде (например, в случае линейности)

имеются соответствующие методы решения, т. е. синтез может быть выпол-

нен аналитически или численно. Но большинство технических систем опи-

сываются нелинейными уравнениями, в том числе дифференциальными, что

существенно зактрудняет выполнение синтеза.

Анализировать систему проще, так как анализ с точки зрения математи-

ки часто сводится к более простым математическим операциям, например, к

табулированию функций или к их численному решению известными метода-

ми. При этом математические модели могут быть существенно более слож-

ными и включать, например, алгоритмические фрагменты, таблично задан-

ные значения и др.

Бронов, С. А. Исследование операций: конспект лекций

Поэтому при проектировании сложных в математическом описании си-

стем, как правило, исходное математическое описание упрощают и по нему

осуществляют приближённый синтез. А затем по исходному детальному ма-

тематическому описанию выполняют моделирование и проверку корректно-

сти выполненного синтеза. В процессе анализа обычно приходится подстраи-

вать моделируемую систему, уточняя ранее синтезированные параметры или

управляющие воздействия (в зависимости от целей синтеза).

Кроме использования на завершающем этапе синтеза, этап анализа мо-

жет быть самостоятельным, когда необходимо исследовать поведение уже

существующей системы при различных внешних воздействиях и различных

параметрах.

Таким образом, анализ является неотъемлемой частью синтеза (на его

завершающем этапе) и также отдельным этапом исследований. В данном

курсе рассматриваются вопросы анализа.

При анализе объекта главным является вопрос управления им через воз-

действие. Управление организационными объектами существенно отличает-

ся от управления техническими объектами. В частности, для технических

объектов часто возможно построение опытных образцов и отладка принятых

технических решений на макетах, а эксперименты над организационными

объектами, как правило, невозможны. В то же время, неправильные решения,

принятые при управлении организационными системами, могут иметь весьма

тяжёлые последствия, в том числе для участвующих в них людей. Поэтому

единственной возможностью проверки правильности принимаемых решений

является использование моделей в той или иной форме.

Особенностью организационных систем как объекта моделирования яв-

ляется неопределённость, связанная как с некоторыми внутренними парамет-

рами, так и с внешними воздействиями. Эта неопределённость приводит к

тому, что оказывается невозможным использовать классические математиче-

ские модели и следует искать другие формы. Одной из таких форм является

представление организационных систем в терминах теории массового об-

служивания (систем с очередями). В таких системах используется дискретно-

событийный характер представления процессов, когда любой процесс состо-

ит из последовательности событий. Оказывается, что в таких моделях появ-

ляется возможность использовать параметры, характеризующие, например,

сложность исследуемых явлений, их значимость и т. д. Эти и другие анало-

гичные свойства (характеристики) существенны, прежде всего, для организа-

ционных систем.

Характерной чертой организационной системы является то, что её дея-

тельность многообразна и соответствующие процессы могут протекать по

различным сценариям, зависящим от многочисленных случайных факторов.

Это многообразие отражается алгоритмически (через соответствующие

Бронов, С. А. Исследование операций: конспект лекций

условные операторы) и мешает аналитическому исследованию таких систем,

которые становятся, таким образом, системами с переменной структурой и

переменными параметрами — т. е. самыми сложными с точки зрения анали-

за.

В настоящее время многие свойства организационных объектов являют-

ся трудно формализуемыми, т. е. не сводятся к однозначно понимаемым ма-

тематическим выражениям. Например, качество работы организационного

объекта не может определяться как минимизация или максимизация некото-

рого формального критерия качества, например, степени удовлетворения

клиентов этой организации. Тем не менее, для принятия управленческих ре-

шений требуется в какой-то мере формализовать эти критерии, заменяя их

другими (возможно, несколькими). Например, вместо удовлетворённости

может использоваться критерий отсутствия ожидания обслуживания и др.

Таким образом, имитационное моделирование является важнейшим ин-

струментом исследования (анализа и синтеза) сложных организационно-

технических объектов. Владение этим инструментом позволяет создавать си-

стемы поддержки принятия решений, в которых синтез осуществляется по

некоторым алгоритмам с учётом упрощающих предположений, а затем вы-

полняется анализ с учётом большинства реально воздействующих факторов.

2.2 Имитационное моделирование как метод исследования

организационно-технических объектов

Имитационное моделирование характеризуется, прежде всего, сочетани-

ем двух факторов — неопределённости и возможности ветвления процессов

в зависимости от конкретных реализаций этой неопределённости.

При имитационном моделировании система представляется потоком со-

бытий, происходящих в отдельные моменты времени, т. е. дискретно. Такое

представление и такое моделирование называют дискретно-временным. Его

отличие от функционального моделирования (например, на основе решения

систем алгебро-дифференциальных уравнений) в том, что события происхо-

дят в соответствии с заданными интервалами времени и, возможно, в зави-

симости от уже произошедших событий. Интервалы времени (моменты со-

вершения событий) вычисляются, как правило, с помощью генераторов слу-

чайных чисел с тем или иным законом распределения вероятностей.

При имитационном моделировании все события в системе происходят в

соответствии с продвижением некоего индикатора времени, который назы-

вают транзактом. Транзактов может быть много, но в каждый момент вре-

мени активным является только один, который и вызывает то или иное собы-

тие (иногда бывают одновременно активными и несколько транзактов, рас-

смотрение такой возможности является отдельной проблемой имитационного

моделирования). При этом движение транзакта может сопровождаться и не

Бронов, С. А. Исследование операций: конспект лекций

сопровождаться изменением времени. Физический смысл каждого транзакта

может быть различным. Это могут быть люди, внешние воздействия, различ-

ного рода сигналы и т. п. Имитационная модель может проследить траекто-

рии прохождения транзактов при различных условиях, собрать статистиче-

скую информацию о них (среднее время нахождения в том или ином блоке,

количество прошедших через блок транзактов и др.). Современные системы

имитационного моделирования могут включать в себя также блоки функцио-

нального моделирования (например, язык имитационного моделирования

GPSS World содержит специальное расширение — язык PLUS, немного

напоминающий сильно упрощённый язык Паскаль).

Таким образом, имитационное моделирование может обеспечить реше-

ние различных исследовательских задач:

 определение реального алгоритма работы той или иной системы с учё-

том вероятностных характеристик отдельных элементов и сигналов при раз-

личных условиях;

 вычисление статистических характеристик (средние, максимальные и

минимальные значения, коэффициент использования);

 оптимизация структуры или параметров исследуемой системы;

 поиск сбоев и неисправностей в реальной системе и причин их возник-

новения;

 создание компьютерных деловых игр как компонентов систем под-

держки принятия решений.

Имитационное моделирование может применяться для любых типов си-

стем, но именно организационно-технические объекты наиболее удобно ис-

следовать методами имитационного моделирования.

2.3 Вероятностные характеристики в имитационном

моделировании

В теории вероятностей различают следующие случайные явления:

 случайные события;

 случайные величины;

 случайные процессы.

Случайное событие может произойти или не произойти в рассматрива-

емый момент времени или при рассматриваемых обстоятельствах.

Случайная величина принимает какое-то значение, которое невозмож-

но рассчитать или заранее предвидеть.

Случайный процесс связан с последовательностью случайных событий

или с последовательным изменением значений случайной величины во вре-

мени.

Бронов, С. А. Исследование операций: конспект лекций

Для имитационного моделирования характерно рассмотрение именно

случайных процессов, которые состоят из последовательности случайных

событий и (или) значений случайных величин. Это может быть: возникнове-

ние или отсутствие события; выбор одного события из нескольких возмож-

ных; задание промежутка времени между событиями; задание значения како-

го-либо параметра и т. д. В зависимости от возникновения события или от

значения какой-либо величины выбирается направление развития моделиру-

емого процесса. Именно это сочетание случайности и зависящего от неё вы-

бора создаёт в сложных объектах большое число возможных траекторий

процесса (реализаций), что затрудняет его аналитическое исследование и

приводит к необходимости имитационного моделирования.

При имитационном моделировании задают случайным образом какое-

либо событие или значение какой-либо величины (т. е. причину), а затем

прослеживают всю цепочку связанных с этой причиной следствий. Таким

образом, имитационная модель в целом отражает причинно-следственные

связи, но хотя при этом одна и та же причина вызывает одни и те же след-

ствия, сами эти причины появляются случайным образом. Кроме того, на от-

дельных участках траектории процесса могут появляться дополнительные

случайные воздействия и непредвиденным заранее образом менять направ-

ление развития процесса. Это повторяется большое число раз, и таким обра-

зом создаётся выборка результатов моделирования при различных входных

случайных явлениях. Характерно то, что при имитационном моделировании

всегда имеют дело не с отдельными случайными явлениями, а с их совокуп-

ностью — потоком. Фактически, в процессе имитационного моделирования

ищется выборка выходных случайных явлений (событий, величин) в зависи-

мости от заданной выборки входных случайных явлений.

Потоки случайных явлений (величин и событий) наиболее полно пред-

ставляются самой выборкой, т. е. совокупностью всех состоявшихся событий

и принятых значений. Понимание одинаковости и различия случайных про-

цессов отличается от такового для детерминированных процессов. Детерми-

нированные процессы тогда являются одинаковыми, когда все реализации

двух сравниваемых выборок попарно одинаковы (фактически, это означает,

что две функции должны быть равны, если равны их значения при любом

одном и том же для обеих функций аргументе). Но это возможно только для

произошедших явлений. Вообще, то, что произошло, уже не может в полном

смысле слова считаться случайным, так как в момент реализации случайного

явления неопределённость его появления снимается.

Чтобы можно было как-то охарактеризовать будущие процессы, исполь-

зуют специальные вероятностные характеристики (параметры), позволяющие

различать их основные статистические свойства.

Бронов, С. А. Исследование операций: конспект лекций

Но в некотором смысле выборки могут быть одинаковыми, даже если их

частные реализации не совпадают попарно.

В имитационной модели должны быть источники случайных величин, а

их вероятностные характеристики должны соответствовать реальным не-

определённостям в объекте моделирования.

Во многих случаях возможен переход от случайных величин к случай-

ным событиям и наоборот. Например, если какая-то величина принимает

случайное значение, то рассматривается случайная величина. Если рассмат-

ривается принятие величиной того или иного значения, то это — случайное

событие.

Если рассматривается последовательность случайных событий, то может

оказаться, что все события происходят одинаковое число раз, или же некото-

рые события происходят чаще, а некоторые — реже. То же самое может про-

исходить со случайными величинами: случайная величина принимает любое

из возможных значений одинаковое число раз или некоторые значения —

чаще, а некоторые — реже.

Это свойство случайных событий (и случайных величин) можно отобра-

зить с помощью специального графика — гистограммы. По оси абсцисс от-

кладываются виды событий (или значения случайной величины), а по оси

ординат — число этих событий (или число принятия случайной величиной

соответствующего значения). Такой график даёт представление о распреде-

лении вероятностей и его называют плотностью распределения вероятно-

стей. Чем выше график в какой-то точке абсциссы, тем чаще происходит со-

ответствующее событие или встречается соответствующее значение случай-

ной величины. По оси ординат можно откладывать абсолютные значения или

относительные, рассчитанные относительно общего числа событий или об-

щего числа возможных значений случайной величины.

Можно проанализировать предельные случаи гистограмм.

Невероятные события представляют собой горизонтальную прямую,

совпадающую с осью абсцисс (вероятность равна 0).

Однозначно определённые события представляют собой вертикальную

прямую в точке, соответствующей этому определённому событию (вероят-

ность равна 1).

Равновозможным событиям, которые происходят одинаково часто, соот-

ветствует горизонтальная кривая, параллельная оси абсцисс и соответствую-

щая значению

по оси ординат, где

— число событий.

Плотность распределения вероятностей называют также дифференци-

альной функцией распределения. Если её проинтегрировать, то будет получе-

на интегральная функция распределения (или — просто функция распределе-

ния). Смысл интегральной функции распределения в том, что она показывает,

Бронов, С. А. Исследование операций: конспект лекций

как часто случаются все событий левее рассматриваемой точки (или прини-

маются соответствующие значения случайной величиной).

Обе функции распределения (интегральная и дифференциальная) связа-

ны между собой операциями дифференцирования и интегрирования, а пото-

му несут обычно одну и ту же информацию. Но эта информация представля-

ется различным образом и в разных случаях бывает нагляднее та или иная

функция.

Основой для создания неопределённости являются встроенные датчики

случайных чисел (точнее, генераторов псевдослучайных числовых последо-

вательностей). Реально эта псевдослучайная последовательность — одна, но

можно обращаться к ней, задавая разные начальные значения. При разных

начальных значениях будут формироваться разные реализации псевдослу-

чайных последовательностей.

2.4 Общие принципы имитационного моделирования

2.4.1 Метод Монте-Карло как основа имитационного

моделирования

Метод Монте-Карло (другое название — метод статистических ис-

пытаний) предназначен для изучения процессов с учётом случайного факто-

ра. Случайным фактором может быть случайное значение какой-либо вели-

чины (например, время прихода клиента, количество свободных мест в подъ-

ехавшем к остановке автобусе, рост покупателя в магазине готового платья и

т. п.) или случайное событие (например, болезнь сотрудника, наличие нуж-

ного товара в магазине, прибытие в аэропорт самолёта и т. п.).

В теории вероятностей и математической статистике разработаны ана-

литические методы исследования такого рода процессов с помощью формул,

если известны законы распределения вероятностей, т. е. если они могут быть

заданы приближёнными аналитическими выражениями. Но это не всегда

возможно. Например, если в зависимости от случайного события изменяется

направление процесса, то такую систему проанализировать аналитически (с

помощью формул) может оказаться затруднительно. В этом случае следовало

бы рассчитать все возможные варианты протекания процесса, а их может

оказаться много сотен и тысяч. Поэтому даже если такие расчёты в принципе

возможны, полученные результаты могут стать необозримыми и практически

бесполезными. Именно для этого случая целесообразно применять метод

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

Суть метода Монте-Карло заключается в том, что в модель (туда, где

проявляет себя неопределённость) вводят датчики случайных чисел. В ре-

зультате с их помощью в нескольких местах модели производится розыгрыш

случайной величины или случайного события, в зависимости от которых ме-