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

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

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

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

Г.Н. Бояркин, О.Г. Шевелева

ТЕОРИЯ СИСТЕМ И СИСТЕМНЫЙ АНАЛИЗ

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

Омск

Издательство ОмГТУ

2008

Составители: Г.Н. Бояркин, О.Г. Шевелева

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

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

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

Тема 1. МОДЕЛИ УПОРЯДОЧЕНИЯ

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

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

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

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

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

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

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

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

Пример:

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

---

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

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

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

(в нашем случае ).

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

Для нахождения оптимальной последовательности порядка обслуживания “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	4	5	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

Время обработки на 2-й машине

Время простоя на 2-й машине

tn1=4

tn2=1

Т_min=23+4+1=34

Задачи (для самостоятельного решения)

Определить оптимальный порядок обработки изделий:

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

---

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

Тема 2. МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ

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

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

Оптимальное значение заказа (формула Вильсона)

(2.1)

Здесь – затраты на оформление заказа;

– интенсивность спроса;

– затраты на хранение в ед. времени.

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

(2.2)

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

(2.3)

б) модель с равномерным пополнением запаса

y

(2.4)

в) модели с дефицитом

– уровень потребляемой продукции; – поступающая продукция

По графику можно составить следующее соотношение

Пусть – удельные потери от дефицита

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

(2.5)

Решая совместно систему (2.5), получим

(2.6)

(2.7)

Нетрудно доказать, что если модель с равномерным пополнением запаса допускает дефицит, то формулы (2.6) и (2.7) преобразуются в формулы (модель «смешанного типа»)

(2.8)

(2.9)

Примеры

1. Ежедневный спрос на некоторый товар составляет около 50 ед. Затраты на размещение каждого запаса постоянны и равны 100 руб. Ежедневные затраты на хранение ед. запасы составляют 0,05 руб./день. Определить оптимальный размер заказа и интервал времени между моментами размещения заказов.

Решение: Используя формулу (2.1) имеем

Оптимальные затраты (см.2.3) равны

2. Усложним условия задачи. Пусть запасы пополняются равномерно с интенсивностью .

Тогда

3. Еще раз скорректируем условия задачи. Пусть в первоначальной модели допускается дефицит. Причем удельные потери от дефицита составляют . Тогда, используя формулы (2.6) и (2.7) получим:

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

4. Еще раз усложним условия задачи. Пусть в предыдущей модели, допускающей дефицит, запасы пополняются равномерно с интенсивностью . Тогда, используя формулы (2.8) и (2.9), при , получим

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

Задачи (для самостоятельной работы)

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

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

3. Фирма может производить изделие или покупать его. Если фирма сама выпускает изделие, то каждый запуск его в производство обходится в 20 руб. Интенсивность производства составляет 100 ед. в день. Если изделие закупается, то затраты на размещение каждого заказа равны 15 руб. Затраты на
   содержание изделия в запасе независимо от того, закупается оно или производится, равны 0,02 руб. в день. Потребление изделия предприятия оценивается в 26 000 ед. в год. Предполагая, что фирма работает без дефицита, определить, что выгоднее закупать или производить изделие?

4. Решить задачу 1, взяв за предположение, что в модели допускается дефицит с удельными потерями от него .

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

---

Тема 3. МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ

И УПРАВЛЕНИЯ (СПУ)

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

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

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

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

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

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

: или

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

,

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

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

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

.

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

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

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

П

5

4

1

5

4

3

8

6

ример:

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

1, 2, 3, 5, 6

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

1→2→3→5→6

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

№ п/п	Работа (i,j)	Продолжение работы (i,j)	Сроки начала и окончания работ				Резервы времени
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

---

Номера событий	Сроки совершения событий		Резервы врем. событий
1 2 3 4 5 6	0 5 6 10 14 20	0 5 6 16 14 20	0 0 0 6 0 0

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

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

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

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

Очевидно

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

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

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

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

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

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

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

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

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

или

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

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

или

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

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

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

или

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

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

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

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

---

Смотрите также файлы

• Вдовин Суркова Валентинов Теория систем и системный анализ.pdf

• Практическое занятие № 1 (маркетинг).docx

• Практическое занятие № 2 (маркетинг).docx

• Практическое занятие № 3 (маркетинг).docx

• Практическое занятие № 4 (маркетинг).docx