Бояркин Г.Н., Шевелева О.Г. Теория систем и системный анализ
Подождите немного. Документ загружается.
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Омский государственный технический университет»
Г.Н. Бояркин, О.Г. Шевелева
ТЕОРИЯ СИСТЕМ И СИСТЕМНЫЙ АНАЛИЗ
Методические указания к практическим занятиям
Омск
Издательство ОмГТУ
2008
Составители: Г.Н. Бояркин, О.Г. Шевелева
Методические указания для практических занятий по дисциплине «Теория
систем и системный анализ» направлены на получение и закрепление знаний по
применению методов, изложенных в данной дисциплине для решения
практических задач экономической направленности. Методические указания
предназначены для студентов специальности 080801 «Прикладная информатика
(в экономике)» как дневной, так и заочной форм обучения.
Печатается по решению редакционно-издательского совета
Омского государственного технического университета
2
Тема 1. МОДЕЛИ УПОРЯДОЧЕНИЯ
Модели упорядочения характеризуются следующими особенностями.
Например, имеется множество различных деталей с определенными
технологическими маршрутами, а также несколько единиц оборудования
(фрезерный, токарный, шлифовальный станки), на которых эти детали
обрабатываются, т. к. одновременно обрабатывать более одной детали
невозможно – у некоторых станков может образоваться очередь, т. е. деталей,
ждущих обработки. Время обработки каждой детали известно. Определить
такую очередность обработки деталей на каждом станке, при котором
минимизируется некоторый критерий оптимальности, например, суммарная
продолжительность завершения комплекса работ. Такая задача называется
задачей календарного планирования или составления расписания, а выбор
очередности запуска деталей в обработку – упорядочением.
В качестве примера рассмотрим упрощенный вариант этой задачи, для
которой разработан удобный алгоритм.
Пусть имеется несколько изделий, каждая из которых должна быть
обработана на 2-х машинах (станках). Известны время обработки и
последовательность обработки каждого изделия на каждой машине. Требуется
выбрать такой порядок обработки изделий, при котором суммарное время
обработки будет минимальным.
Основные ограничения:
а) время перехода от одной машины к другой незначительно и им можно
пренебречь;
б) каждое изделие обрабатывается в определенном технологическом порядке;
в) каждое обслуживание должно быть завершено прежде, чем начнется
следующее.
Обозначим
j
t
1
– время обработки j-го изделия на 1-й машине,
j
t
2
– на 2-й
машине.
Пример:
t
11
t
12
t
13
t
14
t
15
t
16
Время обработки
1-й машины
t
21
t
22
t
23
t
24
t
25
t
26
Время обработки
2-й машины
t
п1
t
п2
t
п3
t
п4
Время простоя
2-й машины
Номер изделия
j 1 2 3 4 5 6
Время обработки на
1-й машине
t
1j
6 4 6 5 7 4
3
Время обработки на
2-й машине
t
2j
5 2 3 6 6 7
Построение модели.
Пусть
Пj
t
– время простоя 2-й машины между концом выполнения работы по
обработке j-1-го изделия на 2-й машине и началом обработки j-го изделия на
той же самой машине. Тогда суммарное время обработки изделий составит:
m
j
m
j
Пjj
ttT
1
1
2
411229
Так как сумма
m
j
j
t
1
2
известна, то надлежит минимизировать
m
j
Пj
t
1
(в нашем случае
12
6
1
j
Пj
t
).
Построение алгоритма.
Для нахождения оптимальной последовательности порядка обслуживания
“m” требований на 2-х пунктах обслуживания наибольшую известность
получил «алгоритм Джонсона». Включает следующие этапы:
а) поиск наименьшего элемента:
Рассмотрим все
j
t
1
и
j
t
2
и среди них выберем минимальное, т. е.
1 2
min ,
j j
t t
. В нашем случае это
2
2
j
t
.
б) перестановка изделий:
Если выбранная величина находится в 1-й строке (относится к 1-й машине),
то соответствующее изделие помещается на обслуживание в первую
возможную очередь. Если – во 2-й строке (относится ко 2-й машине) – то в
последнюю очередь.
в) исключение из рассматриваемого выбранного изделия:
Выбранному изделию присваивается новый номер в очереди, который в
дальнейшем считается занятым. Из последующего рассмотрения оно
исключается.
Далее осуществляется переход к этапу а).
После определения оптимального порядка обработки изделий на машинах
графически определяется время простоя и работы 2-й машины, которое
является минимальным из всех возможных.
Номер изделия
j
1 2 3 4 5 6
Время обработки
на 1-й машине
j
t
1
6 4 6 5 7 4
Время обработки
на 2-й машине
j
t
2
5
(4)
2
(6)
3
(5)
6
(2)
6
(3)
7
(1)
Номер изделия 4 1 2 4 5 3
4
Номер изделия
j
6 4 5 1 3 2
Время обработки
на 1-й машине
j
t
1
4 5 7 6 6 4
Время обработки
на 2-й машине
j
t
2
7 6 6 5 3 2
t
16
=4 t
14
t
15
t
11
t
13
t
12
Время обработки
на 1-й машине
t
26=7
t
24
t
25
t
21
t
23
Время обработки
на 2-й машине
Время простоя
на 2-й машине
t
n1
=4 t
n2
=1
Т
min
=23+4+1=34
Задачи (для самостоятельного решения)
Определить оптимальный порядок обработки изделий:
Номер изделия
j
1 2 3 4 5
Время обработки
на 1-й машине
j
t
1
3 7 4 5 7
Время обработки
на 2-й машине
j
t
2
6 2 7 3 4
Номер изделия
j
1 2 3 4 5 6
Время обработки
на 1-й машине
j
t
1
8 3 4 7 2 6
Время обработки
на 2-й машине
j
t
2
4 5 2 8 7 1
Тема 2. МОДЕЛИ УПРАВЛЕНИЯ ЗАПАСАМИ
а) однопродуктовая модель простейшего типа
Оптимальное строение модели предусматривает заказ
*
y
ед. продукции
через каждые
*
*
0
y
t
ед. времени.
5
Оптимальное значение заказа (формула Вильсона)
(2.1)
Здесь
K
– затраты на оформление заказа;
– интенсивность спроса;
h
– затраты на хранение в ед. времени.
Оптимальные затраты:
hyU
2)(
*
(2.2)
В стратегию размещения заказа должна входить и точка возобновления
заказа. На практике она определяется непрерывным контролем уровня запаса.
Ltt
LttL
U
з
00
00
*
,
,)(
(2.3)
б) модель с равномерным пополнением запаса
1
;
y
t
d
y
y
( ) (1 )
2
h
U y y
y
0
t
точка возобновле-
ния заказа
Момент
поступления
Урове
нь
запаса
y
1
t
t 0
t1
y
t1
t1t1
t
6
*
2
y
h
y
*
2
(1 )
y
h
(2.4)
в) модели с дефицитом
y
– уровень потребляемой продукции;
y
– поступающая продукция
По графику можно составить следующее соотношение
1 2
0 0
;
t t
y w w
t y t y
Пусть
p
– удельные потери от дефицита
Тогда суммарные затраты
2 2
1 2
0 0
( ) ( )
( )
2 2 2 2
t tK h y w pw K h y w pw
U y
y t t y y y
(2.5)
Решая совместно систему (2.5), получим
(2.6)
(2.7)
Нетрудно доказать, что если модель с равномерным пополнением запаса
допускает дефицит, то формулы (2.6) и (2.7) преобразуются в формулы (модель
«смешанного типа»)
t2
t1
w
у
0
t
y
7
у
2 2
2 2 2
2( ) ( )
0;
2 2
( )
0.
U K h y w y y w pw
y y y y
U h y w pw
w y y
2
( )
K h
w
p p h
2 ( )K p h
y
ph
2 ( )
;
(1 )
K p h
y
ph
(2.8)
2 1
.
K
w
p p h
(2.9)
Примеры
1. Ежедневный спрос на некоторый товар составляет около 50 ед. Затраты на
размещение каждого запаса постоянны и равны 100 руб. Ежедневные
затраты на хранение ед. запасы составляют 0,05 руб./день. Определить
оптимальный размер заказа и интервал времени между моментами
размещения заказов.
Решение: Используя формулу (2.1) имеем
0
2 400 50
894 .;
0,05
894
18 .
50
y ед
y
t дней
Оптимальные затраты (см.2.3) равны
( ) 2 400 50 0,05 20 5 .U y руб
2. Усложним условия задачи. Пусть запасы пополняются равномерно с
интенсивностью
100 ./ед день
.
Тогда
2 2 400 50
1265 .
0,05 0,5
(1 )
K
y ед
h
3. Еще раз скорректируем условия задачи. Пусть в первоначальной модели
допускается дефицит. Причем удельные потери от дефицита составляют
0,1 ./p руб день
. Тогда, используя формулы (2.6) и (2.7) получим:
8
2 400 50 0,15
1095 .;
0,1 0,05
2 400 50 0,05
365 .
0,1 0,15
y ед
w ед
Оптимальные затраты
2 2
2 2
0 1
( )
( )
2
400 50 0,05(1035 365) 0,1 365
38 ./ ;
1095 2 1095
1095 730
22 ; 15
50 50
K h y w pw
U y
y y
руб день
y
t дней t дней
4. Еще раз усложним условия задачи. Пусть в предыдущей модели,
допускающей дефицит, запасы пополняются равномерно с
интенсивностью
100 ./ед день
. Тогда, используя формулы (2.8) и (2.9),
при
0,1 ./p руб день
, получим
2 ( ) 2 400 50 0,5
1549 .;
0,005 0,5
(1 )
2 (1 )
2 400 50 0,05 0,5
258 .
( ) 0,1 0,15
K p h
y ед
ph
K h
w ед
p p h
Оптимальные затраты
15 7
730365
1095
y
22
t
9
2
2
2
2
(1 )
( )
2(1 )
0,05 775 255 0,1 258
400 50
23,7 ./ .
1543 1549
h y w pw
K
U y
y
y
руб день
1
2
3
4
0 1 2 3 4
1549 258
13 ;
100
1549 258
26 ;
50
258
5 ;
50
258
2,5 ;
100
13 26 5 2,5 46,5 .
y w
t дней
y w
t дней
w
t дней
w
t дней
t t t t t дней
Задачи (для самостоятельной работы)
1. В каждом из следующих случаев пополнение запаса происходит
мгновенно и дефицит не допускается. Найти экономический размер
заказа, соответствующие суммарные затраты и интервал времени между
двумя заказами:
) 100 , 0,05 ; 30 / ;
) 50 , 0,05 ; 30 / ;
) 100 , 0,01 ; 40 / .
а K руб h руб ед день
б K руб h руб ед день
в K руб h руб ед день
t
t0
t4
t3
t2
t1
y
1