Теория систем и системный анализ

Размещено на http://www.allbest.ru//

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

Теория систем и системный анализ

Учебное пособие

Г.Н. Бояркин

О.Г. Шевелева

Рецензенты:

А.А. Колоколов, д. ф.-м. н., профессор;

А.А. Кораблева, к. э. н.

Бояркин, Г.Н.

Б 86 Теория систем и системный анализ: Учеб. пособие / Г.Н. Бояркин, О.Г. Шевелева. - Омск: Изд-во ОмГТУ, 2008.- 80 с.

Учебное пособие по дисциплине «Теория систем и системный анализ» включает теоретический материал по одноименному курсу.

Данное пособие предназначено для студентов специальности 080801 (351400) «Прикладная информатика (в экономике)», изучающих курс «Теория систем и системный анализ» в качестве дисциплины естественно - научного цикла. Пособие может быть использовано студентом как дневной, так и заочной формы обучения.

Печатается по решению редакционно-издательского совета Омского государственного технического университета.

УДК

ББК

© Авторы, 2008

© Омский государственный

технический университет, 2008

1. Введение в системный анализ

системный сетевой график имитационный

Системный анализ - это научная дисциплина, занимающаяся проблемами принятия решений в условиях анализа большого количества информации различной природы.

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

В системном анализе могут быть выявлены:

а) методология;

б) аппаратная реализация;

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

Методология - есть базовое начало системного анализа. Она включает определения используемых понятий, принципы системного подхода, а также постановку и общую характеристику основных проблем организации системных исследований.

Под аппаратной реализацией будем понимать стандартные приемы моделирования принятия решений в сложной системе и общие принципы (способы) работы с этими моделями.

Модель строится в виде связных множеств (цепочек) отдельных процедур. Системный анализ исследует как организацию таких множеств, так и вид отдельных процедур, которые максимально приспосабливают для принятия согласующих и управленческих решений в сложной системе.

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

Третья часть системного анализа - опыт его применения в различных областях - чрезвычайно обширна по содержанию. Важнейшими разделами являются научно-технические разработки и различные задачи экономики.

Смежные области: кибернетика, системотехника, информатика и информационные технологии, исследование операций.

2. Введение в теорию систем

2.1 Основные определения

Элементом называется некоторый объект (материальный, энергетический, информационный), обладающий рядом важных для нас свойств, но внутреннее строение (содержание) которого безотносительно к цели рассмотрения.

Обозначение: , совокупность , .

Связью называется важный для целей рассмотрения обмен между элементами (веществами, энергией, информацией).

Единичным актом связи выступает воздействие.

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

Системой называется совокупность элементов, обладающих следующими признаками:

а) связями, которые позволяют посредством переходов по ним от элемента к элементу соединить два любых элемента совокупности;

б) свойством (назначением, функцией), отличным от свойства отдельных элементов совокупности.

Назовем признак а) связностью системы; б) ее функцией.

Применяя так называемое «кортежное» (т.е. последовательность в виде перечисления) определение системы, можно записать

где - система, - совокупность элементов в ней, - совокупность связей, F - функция (новое свойство системы).

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

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

Сложной системой называется система, состоящая из элементов разных типов и обладающая разнородными связями между ними.

Пример: судно, ракета, ЭВМ, транспортная сеть города.

Автоматизированной системой называется сложная система с определяющей ролью элементов двух типов: а) в виде технических средств; б) в виде действий человека.

2.2 Структуры и иерархия

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

Может иметь материальную (вещественную), функциональную, алгоритмическую и др. основу.

Изображается в виде схемы (структурной) либо символически:

,

где - совокупность групп элементов;

- совокупность связей.

Пример: книга - главы, автомобиль, АСУ.

Примеры связей

Последовательная Обратная Параллельная

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

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

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

Управление, информация

- доминирует элемент Информация

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

2.3 Модульное строение системы и информация

Связь системы с внешней средой осуществляется через входы и выходы системы.

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

Группа элементов системы, описываемая только своими входами и выходами и обладающая определенной цельностью называется модулем.

Понятие модуля близко к концепции «черного ящика» в кибернетике. Кроме этого в различных разделах науки и техники есть другие синонимы: «агрегат», «блок», «узел», «подпрограмма», «программный модуль», «подразделение», «комиссия».

Для сложных искусственных систем следует особо выделить информационные связи. Во-первых, они часто являются преобладающими, а во-вторых, они, как правило, сопровождают и два остальных вида - вещественные и энергетические.

Количественная оценка информации- через число сообщений, число операторов, файлов, знаки, двойные коды («биты») и т.д.

В сложных системах особенно важна передача информации. Она может быть предметом специального рассмотрения; в этом случае выделяют потоки информации, направления передачи и др. ее характеристики. Такие схемы принято называть информационной структурой или информационным графом системы.

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

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

2.4 Процессы в системе

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

Процессом называется набор состояний системы, соответствующий упорядоченному непрерывному или дискретному изменению некоторого параметра, определяющего характеристики (свойства) системы.

Процесс движения (изменения) системы во времени называется динамикой системы.

Символическая запись:

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

2.5 Целенаправленные системы и управление

Под целью системы понимается задача получения желаемого выходного воздействия или достижения желаемого состояния системы.

Пример: задачи линейного программирования.

(2.1)

(2.2)

(2.3)

- целевая функция.

а) задачи планирования производства;

б) задача о рационе и т.д.;

в) задача оптимальной загрузки оборудования.

Постановка цели перед системой (часто говорят глобальной цели) влечет за собой необходимость а) формулировки локальных целей, стоящих перед элементами системы и группами элементов; б) целенаправленного вмешательства в функционирование (строение, создание) системы.

Целенаправленное вмешательство в процесс в системе называется управлением.

Управление - универсальный термин в смысле огромного многообразия его конкретных реализаций:

а) в математических моделях это числа, функции, алгоритмы, графовые структуры;

б) в технических системах - сила, геометрические размеры, различные сигналы (например, команды ЭВМ);

в) в экономике - размеры финансирования, материальные ресурсы и сроки их поставки, расстановка кадров;

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

Управление - чрезвычайно широкий и свободный в употреблении термин. Строгий подход к управлению требует четкого, однозначного определения.

а) того, чем мы распоряжаемся;

б) каковы пределы, в которых мы можем выбирать;

в) каково влияние данного управления на процесс.

На практике по всем перечисленным требованиям могут быть неясности, а двумя последними вовсе пренебрегают. Это может приводить, в частности, к тому, что управление не будет вести к цели. Такое положение возможно, но в строгой трактовке управления - когда отсутствует описание процесса в системе. В этом случае мы просто набираем опыт работы с черным ящиком.

Наконец, следует сказать, что в случае, когда мы исходим из цели (что чаще всего бывает), может быть ситуация, при которой не существует управления, обеспечивающего ее выполнение. Тогда что-то меняют либо в структуре системы либо в области достижимости цели, либо в области управляющих воздействий.

Символическая запись управляемой системы:

- обобщенный вид процесса.

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

Пусть существует момент (или он задан), и существует состояние характеристик , позволяющее достичь цели . Пусть состояние может быть достигнуто управляемым процессом . Тогда управление , позволяющее выполнить цель определяется как часть триады (, , ), управляющее соотношением

Обозначим глобальную цель , набор локальных целей первого иерархического уравнения - через , второго через и т.д. Иерархическая структура целей в системе запишется так:

3. Принципы и процедуры системного анализа

3.1 Принципы системного подхода

- Принцип конечной цели: абсолютный приоритет конечной (глобальной цели).

- Принцип единства: совместное рассмотрение системы как целого и как совокупности частей (элементов).

- Принцип связности: рассмотрение любой части совместно с ее связями с окружением.

- Принцип модульного построения: полезно выделение модулей в системе и рассмотрения ее как совокупности модулей.

- Принцип иерархии: полезно введение иерархии частей (элементов) и (или) их ранжирование.

- Принцип функциональности: совместное рассмотрение структуры и функции с приоритетом функции над структурой.

- Принцип развития: учет изменяемости системы; ее способность к развитию, расширению, замене частей, накапливанию информации.

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

- Принцип неопределенности: учет неопределенностей и случайностей в системе.

3.2 Основные процедуры системного анализа

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

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

- Построение моделей.

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

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

- Определение целей системного анализа.

- Формирование критериев.

- Генерирование альтернатив.

- Реализация выбора и принятия решений.

- Внедрение результатов анализа.

Пример: Экономические критерии - прибыль, рентабельность, себестоимость.Технико-экономические - производительность, надежность, долговечность.Технологические - выход продукта, качество продукта и т.д.

4. Модели и моделирование в системном анализе

4.1 Основные понятия

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

Существуют системы, на которых просто невозможно ставить эксперименты с познавательной целью. К таким системам относится экономика.

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

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

Процесс моделирования включает в себя следующие основные этапы:

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

б) переход от оригинала к модели, т.е. построение модели;

в) экспериментальное исследование модели;

г) перенесение результатов, полученных при исследовании модели на моделируемую систему (оригинал).

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

Пример: самолет.

Возможность переноса различных свойств модели на оригинал обоснована сходством (аналогией) оригинала и модели. Что же касается вида и полноты сходства оригинала и модели, то этот вопрос решается в зависимости от особенностей различных типов моделей.

Модели условно делятся на 2 типа: физические и символические.

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

Символические модели описывают структуру и функции оригинала с помощью символов и соотношений между ними, выражающих определенные зависимости, присущие оригиналу.

Большое место среди символических моделей занимают математические модели (уравнения неравенства, функции, алгоритмы и т.д.), отражающие математические и логические зависимости.

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

- отличается по своей физической природе от оригинала;

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

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

Среди математических моделей важное место занимают экономико-математические модели.

4.2 Экономико-математические модели

Большинство экономико-математических моделей включают в себя систему уравнений и неравенств, состоящих из набора переменных и параметров. Переменные величины характеризуют, например, объем производимой продукции, капитальных вложений, перевозок и т.п., а параметры - нормы расхода сырья, материалов, времени на производство определенной продукции.

Практически в каждой модели можно выделить две группы переменных: 1) внешние переменные - их значения определяются вне данной модели и считаются заданными; 2) внутренние переменные, значения которых определяются в результате исследования модели.

Различают структурные и функциональные экономико-математические модели. Структурные модели исследуют состав системы, взаимосвязи ее элементов. Функциональные модели позволяют оптимизировать поведение системы в различных ситуациях безотносительно к ее внутренней структуре.

Экономико-математические модели используются преимущественно для планирования или прогнозирования системы на будущее (как будет протекать экономический процесс, если в его основу положить определенную систему экономических предпосылок).

Экономико-математические модели делятся также на описательные и оптимизационные. Описательные модели экономических систем представляют собой формализованную с помощью математического аппарата экономическую задачу и используются для более глубокого изучения состояния системы и взаимосвязи ее элементов.

Пример: матричные модели межотраслевого баланса, производственная функция.

Оптимизационные модели обладают условием нахождения оптимального решения (критерий оптимальности), который записывается в виде функционала.

Пример: модели оптимального производства, программы оптимального раскроя, оптимального размещения предприятий, транспортная задача и т.п.

Делятся также на линейные и нелинейные.

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

5. Типичные классы задач системного анализа

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

5.1 Задачи управления запасами

С увеличением запасов увеличиваются расходы на их хранение, но уменьшаются потери из-за возможной их нехватки. Следовательно, одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует следующий критерий: сумму ожидаемых затрат по хранению запасов, а также потерь из-за дефицита.

Суммарные Затраты на Затраты на Затраты на Потери от

затраты = приобретение + оформление + хранение + дефицита

заказа заказа

Размещено на http://www.allbest.ru//

5.1.1 Однопродуктовая модель простейшего типа

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

Пример: осветительные лампы в здании, использование канцелярских товаров крупной фирмой, пром. изделия (болты, гайки), поступление продуктов питания (хлеб, молоко).

Размещено на http://www.allbest.ru//

Пусть - интенсивность спроса (в ед. времени). Уровень запаса достигает нуля спустя единиц времени после получения заказа размером.

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

Тогда суммарные затраты в ед. времени

[затраты на оформление заказа в ед. времени]+[затраты на хранение запасов в ед. времени].

(5.1)

Отсюда

(5.2)

- оптимальное значение размера заказа

(формула Вильсона)

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

Оптимальные затраты:

(5.3)

Для большинства реальных ситуаций существует (положительный) срок выполнения заказа (временное запаздывание) от момента размещения до его действительной поставки. Стратегия размещения заказов должна определить точку возобновления заказа.

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



5.1.2. Модели с равномерным наполнением запаса

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

,

Тогда

(5.4)

5.2 Задачи упорядочения

Характеризуются следующими особенностями. Например, имеется множество различных деталей с определенными технологическими маршрутами, а также несколько единиц оборудования (фрезерный, токарный, шлифовальный станки), на которых эти детали обрабатываются, т.к. одновременно обрабатывать более одной детали невозможно, у некоторых станков может образоваться очередь, т.е. деталей, ждущих обработки. Время обработки каждой детали известно. Определить такую очередность обработки деталей на каждом станке, при котором минимизируется некоторый критерий оптимальности, например, суммарная продолжительность завершения комплекса работ. Также задача называется задачей календарного планирования или составления расписания, а выбор очередности запуска деталей в обработку - упорядочением.

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

Пусть имеется несколько изделий, каждая из которых должна быть обработана на 2-х машинах (станках). Известны время обработки и последовательность обработки каждого изделия на каждой машине. Требуется выбрать такой порядок обработки изделий, при котором суммарное время обработки будет минимальным.

Основные ограничения:

а) время перехода от одной машины к другой незначительно и им можно пренебречь;

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

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

Обозначим - время обработки j-го изделия на 1-й машине, - на 2-й машине. Пример:

Номер изделия	j	1	2	3	4	5	6
Время обработки на 1-й машине	t1j	6	4	6	5	7	4
Время обработки на 2-й машине	t2j	5	2	3	6	6	7
	t11	t12	t13	t14	t15	t16
Время обработки 1-й машины
		t21	t22	t23	t24	t25		t26
Время обработки 2-й машины
	tп1			tп2	tп3	tп4
Время простоя 2-й машины

Построение модели.

Пусть - время простоя 2-й машины между концом выполнения работы по обработке -го изделия на 2-й машине и началом обработки -го изделия на той же самой машине. Тогда суммарное время обработки изделий составит:

Так как сумма известна, то надлежит минимизировать (в нашем случае )

Построение алгоритма.

Для нахождения оптимальной последовательности порядка обслуживания “m” требований на 2-х пунктах обслуживания наибольшую известность получил «алгоритм Джонсона». Включает следующие этапы:

а) поиск наименьшего элемента:

Рассмотрим все и и среди них выберем минимальное, т.е. . В нашем случае это .

б) перестановка изделий:

Если выбранная величина находится в 1-й строке (относится к 1-й машине), то соответствующее изделие помещается на обслуживание в первую возможную очередь. Если - во 2-й строке (относится ко 2-й машине) - то в последнюю очередь.

в) исключение из рассматриваемого выбранного изделия:

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

Далее осуществляется переход к этапу а).

После определения оптимального порядка обработки изделий на машинах графически определяется время простоя и работы 2-й машины, которое является минимальным из всех возможных.

Номер изделия		1	2	3	4	5	6
Время обработки на 1-й машине		6	4	6	5	7	4
Время обработки на 2-й машине		5 (4)	2 (6)	3 (5)	6 (2)	6 (3)	7 (1)
Номер изделия		4	1	2	5	6	3
Номер изделия		6	4	5	1	3	2
Время обработки на 1-й машине		4	5	7	6	6	4
Время обработки на 2-й машине		7	6	6	5	3	2

	t16=4	t14	t15	t11	t13	t12
Время обработки на 1-й машине
		t26=7	t24	t25	t21	t23	t22
Время обработки на 2-й машине
Время простоя на 2-й машине
	tп1=4					tп2=1

Тmin=29+4+1=34

5.3 Сетевые модели

5.3.1 Основные положения

Чтобы завершить создание продукции или строительство объекта к определенному сроку, необходимо увязать выполнение работ всеми исполнителями во времени, стоимости, ресурсам и другим технико-экономическим показателям.

Пример: ленточный график, циклограммы и т.д.

Система СПУ - комплекс графических и расчетных методов, организационных мероприятий с целью моделирования, анализа и оптимизации плана работ по проектированию или изготовлению некоторого изделия.

Основным плановым документом в системе СПУ является сетевой график - (сетевая модель, сеть) - безмасштабное графическое изображение планируемого процесса и отражающее взаимосвязь и последовательность входящих в него работ.

Объект управления в СПУ - коллектив исполнителей, располагающий определенными материальными и денежными ресурсами и выполняющий комплекс работ, направленных на достижение конечного результата в установленные сроки.

Система СПУ охватывает следующие основные этапы планирования и управления комплексом работ.

1) выявление работ, которые необходимо произвести в процессе проектирования или изготовления некоторого изделия и связей между ними;

2) построение сетевого графика процесса на основе 1);

3) установление количественных оценок по каждой работе (время, стоимость, ресурсы);

4) расчет параметров сетевого графика вручную или с помощью ЭВМ;

5) анализ и оптимизация сетевого графика (вручную или с помощью ЭВМ) с целью получения определенных оптимальных показателей (минимальное время выполнения работ, минимальная стоимость, минимальная экономия ресурсов;

6) использование сетевого графика как основного элемента инструмента управления ходом работ.

5.3.2 Теоретические основы СПУ

В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа (блок-схемы, структурных соединений).

Граф - это схема, состоящая из заданных точек - вершин, соединенных определенной системой линий, которые называются ребрами или дугами графа.

Ребра могут быть ориентированными (снабжены стрелками - дуги) и неориентированными.

Имеется несколько типов графов:

а) обыкновенный граф (без дуг, петель и кратных ребер);

б) мультиграф (имеются кратные ребра);

в) ориентированный (обыкновенный с ориентированными ребрами);

г) смешанный (схема движения по улице).

а) б) в)

г)

Графы бывают также конечные и бесконечные, пространственные и плоские.

Основатель теории графов - Л. Эйлер, рассмотревший в 1736 г. задачу о «кененгбергских мостах».

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

Путь - это последовательность дуг, позволяющих пройти из одной вершины в другую и каждая дуга которой встречается один раз.

Замкнутый путь называется контуром.

5.3.3 Основные элементы сетевого графика

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

В сетевом графике имеются два основных элемента - работа и событие.

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

Продолжительность измеряется в ед. времени (часы, сутки, недели и т.п.).

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

Различают действительную работу, ожидание, фиктивную работу.

Действительная работа - работа, требующая затрат времени и ресурсов.

Ожидание - работа, требующая затрат времени, но не ресурсов (твердение бетона, сушка, созревание).

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

Событием называется результат произведенной работы (работ).

Изображается:

возведение

стен

А - фундамент залит, В - стены возведены

А - исходное событие, В - завершающее событие

5.3.4 Порядок и правила построения сетевых графиков

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

2) Длина и наклон стрелок значения не имеют. Однако все они направлены слева направо.

3) В сети не должно быть контуров (т.е. замкнутых путей).

4) Сетевой график - это плоский график, поэтому стрелки в нем не должны пересекаться.

5) Пара событий может быть соединена только одной работой (т.е. сетевой график не может быть мультиграфом). Для устранения этой ситуации вводится дополнительное событие и фиктивная работа.

: или

6) В сети не должно быть (кроме исходного) хвостовых событий, т.е. событий, в которые не входит ни одна работа.

7) В сети не должно быть (кроме завершающего) тупиковых событий, т.е. событий, из которых не выходит ни одна работа.

Нумерация (упорядочение сетевого графика) производится по методу ранжирования.

Пример:

2 - событие 1-го ранга;

3,4 - событие 2-го ранка;

5 - событие 3-го ранга.

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

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

5.3.5 Временные параметры сетевых графиков и их нахождение

Параметры событий:

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

(5.5)

если j имеет несколько предыдущих событий, то

(5.6)

(5.7)

где - любой путь, следующий за -м событием, т.е. путь от -го до завершающего события цепи.

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

(5.8)

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

(5.9)

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

Замечания. Критические события резервов времени не имеют.

Отсюда вывод: определив ранний срок наступления завершающего события сети, мы тем самым определяем длину критического пути, и, выявляя событие с нулевыми резервами времени, определяем его топологию.

Пример:

критические события

1, 2, 3, 5, 6

критический путь

1>2>3>5>6

tкр = 5 + 1 + 8 + 6 = 20

Номера Событий	Сроки совершения событий	Резервы времени событий		№ п/п	Работа (i,j)	Продолжение работы t (i,j)	Сроки начала и окончания работ	Резервы времени
	tp(i)	tП(i)						tpн	tpо	tПн	tПо	RП	Ri	Rс	Rн
1 2 3 4 5 6	0 5 6 10 14 20	0 5 6 16 14 20	0 0 0 6 0 0		1 2 3 4 5 6 7 8	(1,2) (1,3) (2,3) (2,4) (2,5) (3,5) (4,6) (5,6)	5 4 1 5 3 8 4 6	0 0 5 5 5 6 10 14	5 4 6 10 8 14 14 20	0 2 5 11 11 6 16 14	5 6 6 16 14 14 20 20	0 2 0 6 6 0 6 0	0 2 0 6 6 0 0 0	0 2 0 0 6 0 6 0	0 2 0 0 6 0 0 0

Параметры работ

Ранний срок начала работы . Очевидно

(5.10)

Тогда ранний срок окончания работ

 (5.11)

Поздний срок окончания работ

Очевидно

(5.12)

Значит поздний срок начала работ

(5.13)

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

(5.14)

Он показывает, на сколько в сумме могут быть увеличены продолжительность всех работ, принадлежащих этому пути.

Вывод: любая из работ пути на его участке, не совпадающем с критическим путем, обладает резервом времени.

Среди резервов времени выделяют 4 разновидности резервов.

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

(5.15)

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

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

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

(5.16)

или (5.17)

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

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

(5.18)

или (5.19)

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

г) Независимый резерв времени Rн(i,j).

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

(5.20)

или (5.21)

Таким образом, если частичный резерв времени 1-го вида может быть использован на увеличение продолжительности данной и последующих работ без затрат резерва времени предшествующих работ, свободный резерв времени - на увеличение продолжительности данной и предшествующих работ без нарушения резерва времени последующих работ, то независимый резерв времени может быть использован для увеличения продолжительности только данной работы.

Работы, лежащие на критическом пути, так же как и критические события, резервов времени не имеют.

Если на критическом пути лежит начальное событие i, то

(5.22)

Если на критическом пути лежит конечное событие, то

(5.23)

Если на критическом пути лежит начальное и конечное событие i и j, но сама работа не принадлежит этому пути, то

(5.24)

5.3.6Анализ и оптимизация сетевого графика

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

Затем проводится классификация и группировка работ по величинам резервов.

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

Коэффициентом напряженности Кн (i,j) работы называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим - критический путь:

(5.25)

или (5.26)

Пример: для рассматриваемого примера

(2,5) - резервное.

Чем ближе к 1 коэффициент напряженности , тем сложнее выполнить данную работу в установленные сроки. Чем ближе к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.

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

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

Оптимизация сетевого графика - это процесс улучшения организации выполнения комплекса работ с учетом срока его выполнения. Проводится с целью сокращения длины критического пути, выравнивания коэффициентов напряженности работ, рационального использования ресурсов.

В первую очередь принимаются меры по сокращению продолжительности работ, находящиеся на критическом пути. Это достигается:

а) перераспределением всех видов ресурсов, как временных (использование резервов времени некритических путей), так и трудовых, материальных, энергетических (например, перевод части исполнителей, оборудования с некритических путей на работы критического пути), при этом из зон менее напряженных в зоны, объединяющие более напряженные работы.

б) сокращение трудоемкости критических работ за счет передачи части работ на другие пути, имеющие резервы времени.

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

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

Наиболее распространенным методом оптимизации сетевого графика в настоящее время является метод время - стоимость.

В зависимости от полноты решаемой задачи оптимизация может быть условно разделена на частичную и комплексную. Мы рассмотрим частичную оптимизацию, которая может быть следующего вида:

а) минимизация времени выполнения работ при заданной им стоимости;

б) минимизация стоимости комплекса работ при заданном выполнении выполнения проекта;

Для простоты ограничимся рассмотрением случая а). Будем предполагать, что уменьшение продолжительности работы пропорционально возрастанию его стоимости.

Пусть ,

где - нормальная продолжительность работ;

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

При этом стоимость работы

при нормальной при экстремальной

продолжительности продолжительности

работы работы



(5.27)

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

(5.28)

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

уменьшается на величину

 (5.29)

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

6.1 Общие положения

В процессе принятия решений возникают следующие трудности:

а) большое число критериев не всегда согласованы между собой;

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

Любой процесс принятия решений включает следующие элементы:

1. Цель. Необходимость принятия решений определяется целью или несколькими целями, которые должны быть достигнуты.

2. Лицо, принимающее решение, должно нести ответственность за последствия этих решений.

3. Альтернативные решения (различные варианты достижения целей).

4. Внешняя среда (совокупность всех внешних факторов, влияющих на исход решений).

5. Исходы решений.

6. Правила выбора решений (решающие правила).

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

Теория принятия решений использует различные процедуры, позволяющие формализовать предпочтения, т.е. выразить их в единственной количественной мере. Основой для таких процедур является теория полезности, разработанная Дж.фон Нейманом и О. Моргерштерном. Ее математическая основа - система аксиом, в которых утверждается, что существует некоторая мера ценности, позволяющая упорядочить результаты решений. Эта мера называется функцией полезности решений или полезностью.

В зависимости от условий внешней среды и степени информированности лица существует следующая классификация задач принятия решений:

а) в условиях определенности;

б) в условиях риска;

в) в условиях конфликтных ситуаций или противодействия (активного противника).

Остановимся на каждом из них поподробнее.

6.2 Принятие решений в условиях определенности

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

а) пусть имеется совокупность критериев:

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

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

(6.1)

где - вес соответствующего критерия.

В этом случае нужно найти .

Если же критерии измеряются в различных шкалах, то необходимо привести их к одной шкале. Для этого формируют критерий

(6.2)

где .

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

при ограничениях

.

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

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

Пусть - полезность результата при использовании решения .

Пусть заданы условные вероятности . Вводят ожидаемую полезность для каждой стратегии

(6.3)

где

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

(6.4)

6.4 Принятие решений в условиях неопределенности

Одним из определяющих факторов в таких задачах является внешняя среда или природа, которая может находиться в одном из состояний , …, , которое неизвестно лицу, принимающему решение (наблюдатель).

Пусть по-прежнему , полезность результата при использовании стратегии . В зависимости от состояния среды результат достигается с вероятностью .

Кроме того, наблюдателю неизвестно распределение вероятностей . Относительно среды наблюдатель может высказывать определенные гипотезы. Его предположение о вероятном состоянии среды называется субъективными вероятностями . Если бы величина была известна наблюдателю, то мы бы имели задачу принятия решений в условиях риска. В этом случае решающее правило определяется следующим образом:

(6.5)

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

Как выбрать оптимальную стратегию при этом? Существует несколько критериев для выбора оптимальной стратегии.

а) Критерий Вальда (критерий осторожного наблюдателя). Этот критерий оптимизирует полезность в предположении, что среда находится в самом невыгодном для наблюдателя состоянии. При этом критерии решающее правило имеет вид:

(6.6)

где (6.7)

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

б) Критерий Гурвица основан на следующих предположениях: среда может находиться в самом невыгодном состоянии с вероятностью и в самом выгодном - с вероятностью , где - коэффициент доверия. Тогда решающее правило записывается так:

(6.8)

Если , то получаем критерий Вальда.

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

(6.9)

так называя стратегию «здорового оптимизма», который верит в удачу.

в) Критерий Лапласа. Если неизвестны состояния среды, то все состояния среды считают равновероятными.

В результате решающее правило определяется соотношением (6.8) при условии .

г) Критерий Сэвиджа (критерий минимизации сожалений).

«Сожаление» - это величина, равная изменению полезности результата при данном состоянии среды относительно наилучшего возможного состояния.

В этом случае критерий для выбора оптимальной стратегии имеет следующий вид:

(6.10)

где

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

В частности, если даже минимальный риск недопустим, то используют критерий Вальда. Если, наоборот, определенный риск вполне приемлем и заказчик готов вложить в некоторое предприятие столько средств, чтобы он потом не сожалел, что вложено мало, то выбирают критерий Сэвиджа.

7. Принятие решений в условиях конфликтных ситуаций или противодействия

7.1 Общие положения

В отличие от рассмотренных выше задач принятия решений, в которых внешняя среда (природа) предполагалась пассивной, конфликтные ситуации предполагают наличие, по крайней мере, двух противодействующих сторон, интересы которых противоположны. Эти задачи составляют проблематику теории игр.

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

Нашла применение в экономике, в ходе военных действий, анализе надежности и т.п. Характерным примером является довольно распространенная ситуация, когда несколько фирм добиваются права у заказчика на получение выгодного заказа или конфликтуют из-за овладения новыми рынками сбыта.

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

Игроки - это стороны, участвующие в конфликте.

Выигрыш (проигрыш, платеж) - результат конфликта.

Игры бывают парные и множественные.

Ходом в теории игр называется выбор одного из предложенных правилами игры действий и его осуществление.

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

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

7.2 Игра двух лиц с нулевой суммой

Методы теории игр наиболее развиты для конечной одноходовой игры двух лиц с нулевой суммой (т.е. сумма выигрышей игроков равна 0). Такие игры еще называют антагонистическими.

Пусть и - участники игры. Саму игру опишем с помощью так называемой платежной матрицы (матрицы игры) порядка . Строки этой матрицы - это чистые стратегии игрока , а столбцы - чистые стратегии игрока /

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

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

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

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

Bj Ai	B1	B2	B3	…	Bn
A1	б11	б12	б13	…	б1n
A2	б21	б12	б13	…	б2n
…	…	…	…	…	…
Am	бm1	бm2	бm3	…	бmn

Рис. 7.1

Пример:

Игра полковника Блотто

Две армии ведут борьбу за два исходных пункта. Армия полковника Блотто (игрок А) состоит из 4-х формирований, армия противника (игрок В) - из 3-х. Правила игры: армия посылает больше формирований, занимает его и уничтожает посланные туда формирования противника. В случае равенства сил противник очков не получает. Общий выигрыш определяется как сумма выигрышей в 2-х пунктах. Платежная матрица представлена на рис. 7.2.

Bj Ai	3,0	0,3	2,1	1,2
4,0	4	0	2	1	0
0,4	0	4	1	2	0
3,1	1	-1	3	0	-1
1,3	-1	1	0	3	-1
2,2	-2	-2	2	2	-2
	4	4	3	3	3\0

Рис. 7.2

Задачей теории игр является нахождение решения игры, т.е. определение для каждого игрока его оптимальной стратегии и цены игры.

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

Ценой игры называется выигрыш (проигрыш), соответствующий оптимальным стратегиям игроков.

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

Если игрок А выбрал стратегию i, то его выигрыш составит

Отсюда максимальный гарантированный выигрыш

.

Стратегия, соответствующая называется максиминной стратегией, а - нижней ценой игры или максимином.

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

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

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

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

В общем случае отношения между нижней и верхней ценой игры устанавливаются неравенством

Существуют игры, для которых . Элемент платежной матрицы, отвечающей этим стратегиям, называется Седловой точкой. Ей отвечает цена игры :

Если , то игра выгодна игроку А.

При игра выгодна игроку В.

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

7.3 Игра 2-х лиц без седловой точки. Смешанные стратегии

Одна из возможностей расширения стратегий игроков - разнообразить способ выбора своей стратегии, например, «случайно».

Как мы уже отмечали, в отсутствии Седловой точки, игрок А, применяя свою максиминную стратегию, выиграет не менее , а игрок В, применяя свою минимаксную стратегию, проигрывает не более , где . Применение чистых стратегий в каждой партии такой игры не дает возможность игрокам увеличить выигрыш , чем уменьшить проигрыш . Для того, чтобы это было возможным необходимо применять не одну, а несколько чистых стратегий, чередуя их случайным образом с какими-то частотами. Такая стратегия получила название смешанной (ее элементами являются чистые стратегии).

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

Обозначим смешанные стратегии игроков А и В через

и , где

- вероятность (частота) применения игроком А чистой стратегии , - вероятность (частота) принятия игроком В чистой стратегии .

Причем и .

Чистые стратегии игроков А и В, для которых вероятности и отличны от 0, называются активными.

Теорема (основная теорема теории игр) (теорема минимакса).

Любая конечная игра двух лиц с нулевой суммой имеет, по крайней мере, одно решение (т.е. пару оптимальных стратегий, в общем случае смешанных) и соответствующую цену.

Решение игры, не имеющей Седловой точки, может осуществляться различными методами. Рассмотрим наиболее важные из них.

7.3.1 Графическое решение игр вида (2Чn) и (mЧ2)

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

Рассмотрим следующую игру (без Седловой точки)

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

В А			…
			…
			…

Отсюда видно, что ожидаемый выигрыш игрока А линейно зависит от . В соответствии с критерием минимакса игрок А должен выбирать так:

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
1
2
…	…
N

Пример:



Вj Аi	В1	В2	В3	В4
А1	2	4	8	6
А2	1	4	6	4
А3	2	4	8	6
А4	8	6	2	1

Замечания: Стратегии, для которых есть доминирующие и дублирующие стратегии можно отбрасывать.

Вj Аi	В1	В2	В3	В4
А1	2	4	8	6
А4	8	6	2	1

Вj Аi	В1	В2	В4
А1	2	4	6	2
А4	8	6	1	1
	8	6	6	2 6

Размещено на http://www.allbest.ru//

	Чистая стратегия Игрок В	Ожидаемый выигрыш игрока А		- цена игры
	1	-6х1 + 8
	2	-2х1 + 6
	3	5х1 + 1
	Чистая стратегия Игрока А	Ожидаемый выигрыш Игрока В
	1	-4у1+6
	2	7у1+1

Размещено на http://www.allbest.ru//

7.3.2 Решение игр “mЧn” симплекс-методом

Допустим, что все элементы платежной матрицы положительны. Этого можно добиться, добавив ко всем членам матрицы достаточно большое число М. Это приведет к увеличению цены игры на М, а оптимальное решение и не изменится.

B A	q1	q2	…	qn
p1	б11	б12	…	б1n
p2	б21	б12	…	б2n
…	…	…	…	…
pm	бm1	бm2	…	бmn

Найдем сначала . На основе принципа целесообразности.

или

где

Очевидно:

Таким образом, решение игры свелось к следующей задаче

(1)

- это задача линейного программирования

Оптимальная стратегия игрока В находится аналогично. Она является решением задачи.

(2)

Нетрудно видеть, что задачи (1) и (2) - пара двойственных задач. Следовательно, .

8. Проблема оптимизации при принятии решения. Понятие об имитационном моделировании

Идея оптимальности является центральной идеей кибернетики. Понятие оптимальности вышло в практику проектирования и эксплуатации сложных технических систем, получило строгое и точное определение в математических теориях, широко используется в административной практике. Данное понятие сыграло важную роль в формировании системных представлений. Осознавая роль (ведущую) оптимизационного подхода при решении задач выбора, следует остановиться на ряде ограничений, которые необходимо осознавать при применении данного периода.

1. Оптимальное решение часто оказывается чувствительным к незначительным изменениям в условиях задачи. В связи с этим в теории оптимальности развивается такое направление исследований как исследование устойчивости решения, а также анализ результатов решения на чувствительность к изменению входных параметров, условий и предположений.

2. При решении задач оптимизации следует учитывать, что анализируемая система имеет взаимосвязи с другими системами, а зачастую она является подсистемой основной системы. Тогда задача сводится к задаче локальной оптимизации и необходимо увязывать критерии анализируемой системы с критериями другой системы, в частности, с глобальным критерием оптимизации основной системы.

3. При использовании оптимизационного подхода не следует отождествлять цели системы и критерии, с помощью которых решается задача выбора. Критерий и цели относятся друг к другу как модель и оригинал. Многие цели трудно или даже невозможно количественно описать. Количественный критерий является лишь приближением цели. Критерий характеризует цель лишь косвенно, иногда лучше, иногда хуже, но всегда приближенно.

4. В постановке задачи оптимизации наряду с критериями важную роль играют ограничения. Даже небольшие изменения ограничений существенно сказываются на результате решения.

При исследовании социотехнических систем, когда необходимо помимо чисто технических вопросов решать организационные и социальные проблемы ситуация значительно усложняется. Учет подобных вопросов не поддается полной формализации. Ввиду этого оптимизация в системных исследованиях не конечная цель, а промежуточный этап. Чем сложнее система, тем осторожнее следует относиться к ее оптимизации. При исследовании сложных систем неизбежно возникают проблемы, выходящие за пределы формальных математических постановок и задач. В ряде случаев, по мере необходимости обращаются к услугам экспертов, т.е. лиц, чьи суждения, опыт и интуиция могут помочь в решении проблемной ситуации.