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

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

ИНФОРМАТИКА И В ЫЧИС Л ИТЕ ЛЬНА Я ТЕХНИК А

Бронов Сергей Александрович

Красноярск — 2010

УДК 303.094.7

ББК

Бронов, С. А. Исследование операций : учеб. пособие / С. А. Бронов;

ФГАОУ ВПО "Сибирский федеральный университет"; Научно-учебная лабо-

ратория систем автоматизированного проектирования. — Красноярск : СФУ,

2010. — 57 с.

Содержание

Введение ....................................................................................................... 4

1 Задачи и методы исследования операций ............................................ 5

1.1 Историческая справка ............................................................................ 5

1.2 Особенности методологии исследования операций ............................. 5

2 Имитационное моделирование .............................................................. 8

2.1 Основные понятия и принципы имитационного

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

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

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

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

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

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

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

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

2.4.2 Дискретно-событийное моделирование .......................................... 21

3 Метод анализа иерархий Саати .......................................................... 25

4 Принятие решений в условиях риска ................................................ 31

4.1 Критерий ожидаемого значения .......................................................... 31

4.2 Расчёт ожидаемых значений с помощью апостериорных

вероятностей Байеса........................................................................................... 32

4.3 Функции полезности ............................................................................ 35

5 Теория игр .............................................................................................. 38

5.1 Игры с чистыми стратегиями .............................................................. 38

5.2 Матричные игры со смешанными стратегиями .................................. 41

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

6.1 Детерминированное динамическое программирование ..................... 46

6.1.1 Общие принципы детерминированного динамического

программирования .............................................................................................. 46

6.1.2 Задача о загрузке (задача о рюкзаке) ............................................... 51

Список литературы .................................................................................. 57

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

Введение

Учебная дисциплина "Исследование операций" относится к дисципли-

нам специализации и читается на 4 курсе в 7 семестре потоку из специально-

стей 230102.65, 230103.65, 230104.65.

Данный курс является продолжением курса "Методы оптимизации".

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

1 Задачи и методы исследования операций

1.1 Историческая справка

Термин исследование операций применяется к комплексу математиче-

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

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

на методах оптимизации.

Само слово операция исторически восходит ко времени Второй мировой

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

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

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

траты времени и финансов. При этом необходимо было выбирать вид транс-

порта с учётом скорости его перемещения, вместимости и т. д. Впоследствии

эти же методы расчётов оказались применимы в промышленности. И тогда

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

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

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

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

лить на операции. Например, раскройка листового материала для изготовле-

ния деталей включает последовательность выкраивания нескольких деталей

и такое выкраивание можно считать операцией. Перемещение корабля между

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

ных перемещений (отрезков траекторий, отрезков времени) из одного порта в

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

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

тельность операций монтажа каждого комплектующего. И т. д.

Часто оказывается, что к одной и той же цели можно идти различными

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

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

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

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

1.2 Особенности методологии исследования операций

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

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

моделях исследуемых объектов. Математическая модель представляет собой

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

венств, формул. Особенностью исследования операций является явная

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

вида математических расчётов — задачи анализа и задачи синтеза. В обоих

случаях используются математические модели. Они могут быть одними и

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

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

объекта в виде выражения, связывающего переменные

)

(



. (1.1)

Различия между задачами анализа и синтеза в этом случае следующие:

 при анализе задают различные значения аргумента

и определяют

соответствующие ему значения функции

)

(



, например,

)

sin(



;

 при синтезе задают желаемое значение

, а для него определяют со-

ответствующее ему значение )(

yfx



 , где



f обозначает обратную

функцию, например,

)

arcsin(



В общем виде имеется зависимость множества (вектора) одних пере-

менных

от множества (вектора) других переменных

, например:

)

(



, (1.2)

в частности, это может быть система линейных уравнений:



, (1.3)

где

— матрица постоянных коэффициентов.

Для рассматриваемого случая решается задача анализа, если задаются

значения вектора

и находятся значения вектора



. Решается зада-

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

, при котором вектор

соот-

ветствует заранее заданному (желаемому), для этого используется обратная

матрица: yAx



 .

Обычно заранее известен (в той или иной форме) желаемый результат,

т. е. вектор

, и требуется найти решение

, которое его обеспечит. Т. е., как

правило, необходимо решать именно задачу синтеза.

Её можно решать с помощью собственно методов синтеза, используя,

например, для системы линейных уравнений обратную матрицу. Но не для

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

Например, для систем нелинейных уравнений таких методов нет. Отсутству-

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

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

Например, если стоит задача определить, при каком

выполняется

)

sin(



, можно просчитать значения

в диапазоне от 0 до 360° и

среди полученных пар {

} найти искомый

. Это потребует, возможно,

сотен вычислений. Но их число можно уменьшить, если знать, что



располагается в первой четверти синусоиды и тогда просчитать нужно толь-

ко диапазон от 0 до 90°, что в 4 раза уменьшает число рассчитываемых точек.

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

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

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

ствует желаемому. Но часто это приводит к сравнительно большому числу

вычислений, а иногда и к бесконечно большому. Поэтому в рамках исследо-

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

счёт их разумного выполнения.

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

2 Имитационное моделирование

2.1 Основные понятия и принципы имитационного

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

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

ним окружающий мир. Для этого они внимательно наблюдали за природны-

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

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

жающий мир, чтобы обеспечить себе комфортное существование. Так роди-

лась техника — т. е. искусственно созданная часть мира.

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

их будущие свойства.

Чтобы проанализировать поведение объектов, необходимо иметь для

этого соответствующие условия. В частности, достаточное количество вре-

мени, хорошие инструменты наблюдения, возможность "заглянуть внутрь"

объекта, затормозить в нём слишком быстрые процессы или, напротив, уско-

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

и т. д. В реальности большинство этих требований невыполнимо. Поэтому

люди научились исследовать объекты, наблюдая не за ними, а за их моделя-

ми.

Моделью называют некое подобие реального объекта, обладающее су-

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

или влияющими на интересующие свойства. Самая простая модель — его

развёрнутое название. Например, автомобиль — то, что само движется.

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

ветра. Но на самом деле, такие вербальные (словесные) "квазимодели" дают

слишком мало информации о свойствах объекта, а потому, кроме названия, в

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

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

формулами, математическими выражениями, алгоритмами. Словесное (вер-

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

всего, что связано с объектом. Цифровое отражение характеристик объекта

более конкретно и несёт существенно больше информации, но, как правило,

отражает лишь конкретный вариант состояния объекта. Гораздо более ин-

формативными являются математические выражения (например, уравнения)

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

объекта, но и процессы в нём, т. е. ход изменения характеристик. Таким об-

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

выполнении некоторого множества условий.

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

синтеза.

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

Анализ предполагает исследование функционирования существующего

объекта, например, технического устройства, завода или магазина. Цели та-

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

производства продукции, работы в кооперации с другими организационными

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

груженности персонала и оборудования и др. Соответственно этому могут

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

ских ресурсов и т. д.

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

ся заново. При этом требуется определить его структуру (состав элементов и

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

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

и др. Параметрами является количество сотрудников, площадь складских

помещений, размеры финансовых средств, грузоподъёмность автомобилей и

др. При синтезе ставится задача выбрать такую структуру и такие параметры,

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

нии объекта (обычно это те же показатели, что и при анализе).

Таким образом, анализ и синтез — задачи взаимно противоположные:

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

рактеристики функционирования;

 в случае синтеза заданы желаемые характеристики функционирова-

ния, а определяются будущие структура и параметры.

Задачи анализа и синтеза решаются с помощью математических моде-

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

невозможно, особенно, если это — организационный объект (технические

объекты чаще подвергаются экспериментальным исследованиям как в про-

цессе создания, так и в процессе функционирования).

Разделяют математическое описание и математические модели объек-

та.

Математическое описание содержит представление процессов взаимо-

действия между отдельными элементами объекта с помощью формул, урав-

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

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

весь арсенал математики.

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

дели. Различие между математическим описанием и математической моде-

лью следующее. Математическое описание содержит неупорядоченный набор

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

раметры процесса. А математическая модель содержит упорядоченный набор

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

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

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

этих зависимостей. Из одного и того же математического описания можно

получить несколько математических моделей — в зависимости от того, что

считать входом, а что — выходом.

Пример математического описания:

)(

211

zfz



, )(

322

zfz



, )(

433

zfz



Математические модели:

Вариант 1:









)(

43211

zfffz  . Здесь входная величина —

z , выход-

ная —

z .

Вариант 2:









)(

zfffz



 . Здесь входная величина

z , выход-

ная —

z .

Вариант 3:





)(

3211

zffz  . Здесь входная величина

z , выходная —

z ,

z вообще отсутствует.

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

же самого математического описания.

Пусть заданы конкретные функции математического описания:

211

zaz



322

zaz



433

zaz



где

— переменные,

— параметры.

Соответственно, можно записать несколько вариантов моделей:

Вариант 1:









432143211

zaaazaaaz



. Здесь входная величина

z , вы-

ходная —

z .

Вариант 2: .

111111

123

aaa

z 

























 Здесь входная величина

z ,

выходная —

z .

Вариант 3: .

1111

z 













 Здесь входная величина

z , выход-

ная —

z .

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

мер, параметр

a , а входной —

z . Тогда модель имеет вид:

Вариант 4: .

a 













 Здесь входная величина

z , вы-

ходная —

a , параметры —

a ,

z .

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

гается, что эти уравнения должны быть решены. Различают два вида задач —

прямую и обратную.