close

Вход

Забыли?

вход по аккаунту

?

1119.Математика-4

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Казанский институт (филиал)
Российского государственного торгово-экономического университета
_______________________________________________________
кафедра информатики и высшей математики
ТАЛЫЗИН В.А.
МАТЕМАТИКА-4
учебно-методическое пособие
КАЗАНЬ-2003г.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Тема 1. Модели управления товарными запасами
Задачи управления запасами составляют многочисленный класс экономических задач.
При этом используются различные модели управления запасами. Рассмотрим некоторые из
них.
Модель управления одно-номенклатурными запасами без дефицита.
Пополнение склада товаром одной номенклатуры происходит партиями объема s (ед.
товара) дискретно во времени с интервалом поставок  . Завоз товара выполняется без задержек, мгновенно. Дефицит товара исключается, а объем склада считается неограниченным.
Затраты на доставку одной партии товара не зависят от объема партии и составляют
k денежных ед., а затраты на хранение одной единицы товара в единицу времени равны c1
денежных ед. За плановый период T единиц времени требуется осуществить поставку Q
единиц товара. Спрос на товар является постоянным и поэтому объем продаж в единицу
Q
времени (интенсивность)    const .
T
Задача управления товарными запасами состоит в определении такого объема партии
s , при котором суммарные затраты на создание и хранение товарного запаса были бы мин имальными.
Обозначим через C суммарные затраты, C з - затраты на доставку товара, C х - затраты
на хранение. Тогда после формализации получим следующую математическую модель задачи: требуется найти значение переменной s так, чтобы функция
Q
sT
(1)
C  C з  C х  k  c1
s
2
принимала наименьшее значение.
Оптимальное решение задачи определяется формулой Уилсона
2kQ
so 
.
(2)
c1T
По найденному оптимальному объему партии находятся другие оптимальные параметры товароснабжения:
Q
- число поставок за плановый период n o  o ;
s
T
- интервал между поставками  o  o ;
n
so
o
- средний текущий запас на складе z 
;
2
- минимальные суммарные затраты C o  2kc1QT .
Задача 1. Потребность микрорайона г. Казани, обслуживаемого торговым предприятием, в сахаре определена на плановый период T  2 года в объеме 640 т. Стоимость
организации заказа и доставки одной партии в магазин равна k  45 рублей за партию. Издержки хранения товара составляют c1  0,08 руб за 1 кг в год. Полагая, что спрос на сахар
стабильный, определить оптимальные показатели управления товарными запасами:
s o , n o , z o , o , C o .
Решение. Оптимальные значения искомых показателей находим из условия минимума
суммарных затрат (1). Единицей времени будем считать год.
Размер одной поставки определим по формуле Уилсона (2)
2kQ
2  45  640000
so 

 18974 (кг)
c1T
0,08  2
и далее вычислим другие параметры:
- число поставок за планируемый период T  2 года
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Q 640000

 33,73  34 ;
18974
so
- объем одной поставки в пересчете для целого значения n o
Q 640000
so  o 
 18823,5  18824 (кг);
34
n
- средний текущий запас на складе
1
18824
z o  so 
 9412 (кг);
2
2
- интервал между поставками в днях
T  365 2  365
o 

 21,47  21,5 (дн.);
34
no
- затраты на хранение
so
18824
C xo  c1 T  0,08 
 2  1505 ,9 (руб);
2
2
- затраты на транспортировку сахара
Q
640000
C зo  k o  45 
 1529,9 (руб);
18824
s
- минимальные суммарные издержки
C o  2kc1QT  2  45  0,08  640000  3036 (руб).
no 
Оптимальные значения C xo и C зo , согласно теории, должны совпадать, однако полученные расчетные значения C xo  1505 ,9 и C зo  1529 ,9 не равны, что связано с округлением
числа поставок n o до целого значения.
Модель управления одно-номенклатурными запасами с дефицитом.
В отличие от содержательной постановки предыдущей задачи на складе допускается
наличие дефицита, который при очередной поставке мгновенно ликвидируется, а величина
потерь на единицу товара в единицу времени из-за неудовлетворенного спроса составляет c д
денежных единиц.
В данной модели в функцию суммарных затрат C наряду с C з и С х необходимо ввести С д - затраты на штраф из-за дефицита.
В итоге после формализации суммарные издержки за плановый период T можно выразить функцией двух переменных
Q
z 2T
(s  z) 2 T
C ( z , s)  k  c1
 cд
,
(3)
s
2s
2s
где z - максимальный запас товара на складе, s - объем завозимой партии товара,
(s  z ) - объем накопленного дефицита между поставками товара  .
Оптимальные значения s и z находятся из условия минимума функции (3):
s дo 
2kQ
,
c1T д
z o  s дo  д ,
где  д 
(4)
(5)
cд
- величина, называемая плотностью убытков из-за неудовлетворенного
с д  с1
спроса.
Отсюда определяются оптимальные значения других параметров товароснабжения
для модели управления запасов с дефицитом:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
-
число поставок за плановый период nдo 
-
интервал поставок  дo 
-
время наличия дефицита t дo 
Q
;
s дo
T
;
n дo
sдo  z o o
д ;
sдo
- суммарные издержки C o  2kc1QT д .
Задача 2. В задаче 1 определить показатели управления запасами сахара при наличии дефицита, если потери из-за несвоевременной реализации единицы товара составляют cд  0,38
руб. за 1 кг в год.
Решение. В данной модели решение находится из условия минимума суммарных затрат (3). Определим вначале плотность убытков из-за дефицита
cд
0,38
д 

 0,826 .
c1  cд 0,08  0,38
Далее вычислим оптимальные параметры товародвижения:
- объем партии sдo 
- число поставок
2kQ

c1T д
nдo 
2  45  640000
 20877 (кг);
0,08  2  0,826
Q 640000

 30 ,65  31 ;
20877
s дo
- объем партии в пересчете для целого числа поставок s дo 
Q 640000

 20645 (кг);
31
nдo
- максимальный запас сахара на складе z дo   д  s дo  0,826  20645  17053 (кг);
1 o 1
z д   17053  8526,5 (кг);
2
2
T

365
2

365
 дo 

 23,5 (дн.);
31
nдo
z дo 
- средний текущий запас сахара на складе
- интервал поставок в днях
o
- время наличия дефицита t д 
o
sд  z д
o
sд
o
 д 
20645  17053
 23,5  4,09 (дн.);
20645
z дo
17053
 T  0,08 
 2  1364 ,2 (руб);
2
2
- затраты на транспортировку C зo  k  nдo  45  31  1395 (руб).
- затраты на хранение C xo  c1

T sдo  z дo
- убытки из-за дефицита C  cд 
2sдo
o
д

2
220645  17093
 237,5 (руб);
2  20645
2
 0,38
- суммарные издержки C o  C xo  C зo  C дo  1364 ,2  1395  237 ,5  2996 ,7 (руб).
Из приведенных расчетов видно, что оптимальный объем поставки в задаче с дефицитом больше, чем в задаче без дефицита. Это приводит к снижению затрат на транспортировку товара. В данном примере для задачи с дефицитом также меньше затраты на хранение,
что связано с уменьшением среднего текущего запаса сахара ( z дo < z o ) . Убытки из-за дефицита в рассматриваемом примере невелики из-за небольшого значения удельного коэффициента c д . Поэтому и суммарные издержки (2996,7) в задаче с дефицитом меньше, чем в задаче без дефицита (3036). Например, если коэффициент cд  0,7 , то убытки из-за дефицита
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
составят уже величину 437,5 руб и общие затраты в 3312,7 руб будут больше, чем в задаче
без дефицита.
Модель управления многономенклатурными запасами.
Номенклатура товаров, поступающих на склад в течение планового периода T , включает n наименований. Спрос по каждому виду номенклатуры является постоянным и за указанное время требуется поставить Q i единиц товара i -го вида номенклатуры (i  1,2,...,n) .
Предполагается, что поставки осуществляются мгновенно с интервалом поставок  i
для i -го вида номенклатуры, дефицит товаров не допускается и заказы по разным видам
номенклатуры товаров выполняются независимо. Удельные затраты за доставку составляют
k i (ден. ед.), а на хранение c i (ден. ед.) по i -у виду номенклатуры товаров. Средний текущий суммарный уровень запасов по всем видам номенклатуры товаров не должен превышать
G единиц, что связано с ограниченностью емкости склада.
Пусть si - объем завозимой партии для i -го вида номенклатуры товаров. Тогда общие
затраты по всем видам номенклатуры за время T определятся выражением
n
n
Q
c sT
C   ki i   i i .
(4)
si i 1 2
i 1
Требуется найти минимум функции (4) при следующем ограничении
1 n
(5)
 si  G .
2 i 1
Вначале задача решается без учета ограничений (5) и определяется оптимальный размер партий каждого вида номенклатуры по формуле Уилсона
2k i Qi
sio 
, i  1,2,...,n .
(6)
ci T
Если условие (5) для объемов si  sio выполняется, тогда найденные по формуле (6)
значения объемов партий являются решением задачи. В противном случае методом множителей Лагранжа решается задача (4),(5) на условный экстремум. В этом случае наилучшее
решение находится по формуле
si 
2k i Qi
, i  1,2,...,n ,
(ci  2 )T
(7)
где множитель Лагранжа  определяется путем решения нелинейного уравнения
n
2k i Qi
 2G  0 .
(8)

(ci  2 )T
i 1
Задача 3. На базу АО «Спортинвентарь» в течение двух лет должны быть поставлены
велосипеды в следующем ассортименте, затратах на поставку одной партии k i , затратах на
хранения одной единицы в течение месяца c i и объемах поставок Q i (ед.):
Велосипеды
Дорожные
Спортивные
Гоночные
Детские
Подростковые
k i (руб)
1000
1500
1800
800
900
c i (руб)
1,0
1,5
2,0
0,5
0,8
Q i (ед.)
200
90
70
150
100
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Емкость склада ограничена 150 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
Решение. В качестве единицы времени выберем один месяц. Тогда плановый период
составит T =24 месяца. По формуле (6) найдем оптимальные объемы партий по каждому виду ассортимента (в ед.):
s1o 
2  1000  200
 129,1  129 ;
1,0  24
s3o 
2  1800  70
 72,45  72 ;
2,0  24
2  1500  90
 86,6  87 ;
1,5  24
s 2o 
s 4o 
2  800  150
 141,4  141 ;
0,5  24
2  900  100
 96,8  97 .
0,8  24
Найдем средний текущий суммарный уровень запасов по всей номенклатуре товаров
(левую часть неравенства (5))
1 5 o 129  87  72  141  97
 263 .
 si 
2 i 1
2
Поскольку неравенство (5) не выполняется ( 263  G  150 ) , то решим задачу (4),(5)
s5o 
на условную оптимизацию. Вначале определим множитель Лагранжа  из уравнения
5
2k i Qi
 2G  300 .

(ci  2 )T
i 1
Распишем левую часть уравнения
2  1000  200
2  1500  90
2  1800  70
2  800  150
2  900  100




 300 .




(1  2 )  24
(1,5  2 )  24
(2  2 )  24
(0,5  2 )24
(0,8  2 )24
После выполнения простых арифметических действий имеем:
91,29
75,0


72,45
2  1800  70
 51,17  51;
( 2  2  1,01 )24

70,71
s 4 

61,24
(9)
 300 .
0,5  
0,75  
1  
0,25  
0,4  
Получить точное решение данного уравнения очень сложно. Для его приближенного
решения применим следующий прием. Заменим каждое постоянное слагаемое в подкоренных выражениях формулы (9) их средним геометрическим
5
0,5  0,75 1 0,25  0,4  0,517 .
Тогда общий для всех слагаемых радикал можно вынести за скобку
1
(91,29  75,0  72,45  70,71  61,24)  300 .
0,517  
Отсюда уже нетрудно найти приближенное решение уравнения (9)
  1,01 .
По формуле (7) вычислим наилучшие объемы партий:
2  1000  200
2  1500  90
s1 
 74,28  74 ;
s 2 
 56,53  56 ;
(1  2  1,01)24
(1,5  2  1,01)24
s3 

2  800  150
 62,99  63 ;
(0,5  2  1,01)24
2  900  100
 51,57  52 .
(0,8  2  1,01)24
Определим средний текущий суммарный уровень запасов для найденных объемов
партий
s5 
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1 5  1
 si  ( 74  56  51  63  52 )  148 .
2 i 1
2
Теперь ограничение (5) выполняется. Вычислим оптимальные параметры товародвижения по группе дорожных велосипедов:
Q
200
 2,70 ;
- число поставок за планируемый период n1  1 
74
s1
T
24
- интервал между поставками  1   
 8,9 (мес.);
n1 2,7
s1 74

 37 (ед.);
2
2
-
средний текущий запас на складе z  
-
минимальные суммарные затраты
C1  2k1c1Q1T  2 1000 1 200  24  3098 (руб).
Задачи для контрольной работы
№№ 1-5. Потребность микрорайона Москвы, обслуживаемого торговым предприятием, в товаре
определена на плановый период T в объеме Q кг. Стоимость организации заказа и поставки одной
партии в магазин равна k руб. Издержки хранения единицы товара составляет c1 руб. за один кг
в год. Полагая, что спрос на эти товары стабильный, определить оптимальные показатели управления товарными запасами: s o , n o , z o ,  o , C o Определить показатели управления запасами этого же товара при наличии дефицита, если потери из-за несвоевременной реализации единицы товара, т. е.
издержки, составляют c д руб. за 1 кг в год:
cд
T
( руб.
(лет)
кг/год)
1
Мука
680000
60
0,06
0,20
2,5
2
Рис
340000
55
0,09
0,25
2,0
3
Крупа
580000
65
0,05
0,24
1,5
4
Сахар
640000
45
0,08
0,38
2,0
5
Масло
450000
50
0,25
0,44
1,5
№ 6. На оптовую базу в течение года были поставлены спортивные товары в нижеприведенном ассортименте, затратах на доставку одной партии k i , затратах на хранение единицы товара в течение
Номер
варианта
Наименование
товара
Q
(кг)
k (руб.
партия)
c1 (руб.
кг/год)
месяца c i , годовых объемах поставок Q i :
k i (руб)
c i (руб)
Q i (ед.)
Спортивные товары
Обувь
1000
6,0
6300
Туристские товары
1500
5,0
3200
Трикотаж
1200
7,0
4000
Швейные товары
1400
4,0
2300
Спортивный инвентарь
2000
9,0
2000
Емкость склада ограничена 600 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
№ 7. На оптовую базу в течение года были поставлены музыкальные инструменты в нижеприв еденном ассортименте, затратах на доставку одной партии k i , затратах на хранение единицы товара в
течение месяца c i , годовых объемах поставок Q i :
Музыкальные товары
k i (руб)
c i (руб)
Q i (ед.)
Смычковые
Щипковые
3000
2500
30
25
200
160
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Баяны
2300
20
270
Гармони
2000
15
180
Духовые
1500
10
140
Емкость склада ограничена 140 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
№ 8. На оптовую базу в течение года были поставлены радиотовары в нижеприведенном ассортименте, затратах на доставку одной партии k i , затратах на хранение единицы товара в течение месяца
c i , годовых объемах поставок Q i :
Радиотовары
k i (руб)
c i (руб)
Q i (ед.)
Радиоприемники
100
1
800
Телевизоры
200
2
2300
Магнитофоны
180
1,5
1600
Электрофоны
120
2
1400
Видеомагнитофоны
250
2,5
1200
Емкость склада ограничена 300 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
№ 9. На оптовую базу в течение года были поставлены часы в нижеприведенном ассортименте, затратах на доставку одной партии k i , затратах на хранение единицы товара в течение месяца c i , годовых объемах поставок Q i :
k i (руб)
c i (руб)
Q i (ед.)
Часы
Наручные
1000
8
1200
Карманные
600
10
150
Настенные
1800
15
300
Будильники
800
5
500
Настольные
1500
12
400
Емкость склада ограничена 200 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
№ 10. На оптовую базу в течение года были поставлены товары бытовой химии в нижеприведенном ассортименте, затратах на доставку одной партии k i , затратах на хранение единицы товара в
течение месяца c i , годовых объемах поставок Q i :
Товары бытовой химии
k i (руб)
c i (руб)
Q i (ед.)
Моющие средства
500
2
2000
Лаки
600
3
1500
Краски
800
3,5
3000
Чистящие средства
700
4
2500
Аэрозоли
1000
5
1000
Емкость склада ограничена 400 единицами. Определить наилучшие объемы поставок
по всему ассортименту товаров, а также наилучшие параметры товародвижения по одному
из видов ассортимента.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Тема 2. Модели массового обслуживания
Системы массового обслуживания (СМО) характеризуются многоразовым использованием для решения однотипных задач. Примерами таких систем являются магазины, парикмахерские, билетные кассы, телефонные пункты и т.п.
Обслуживающие единицы СМО (продавцы, кассиры, линии связи и т.д.) называют
каналами обслуживания. По числу каналов СМО подразделяются на одноканальные и многоканальные.
Заявки на обслуживание поступают в СМО случайно, образуя случайный поток заявок. Время обслуживания заявок также является случайным и обслуженные заявки образуют случайный поток обслуживаний. Случайный поток характеризуется интенсивностью –
средним числом появления событий в единицу времени.
Если длительность обслуживания заявки как случайная величина имеет показательный закон распределения
t  0,
0,
f (t )    t
e , t  0,
то параметр  равен обратной величине среднего времени обслуживания одной заявки
1
.

t обс
Поток событий называется:
- стационарным, если его вероятностные характеристики не зависят от времени;
-ординарным , если вероятность попадания на малый временной интервал двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события;
- потоком без последействия , если для любых двух непересекающихся интервалов времени
число событий, попавших на один из них, не зависит от числа событий, п опавших на другой.
Поток событий называется простейшим (пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия.
Случайный характер потоков заявок и обслуживаний приводит к неравномерности
загруженности СМО, поэтому в какие-то периоды времени может скопиться большое количество заявок. В связи с этим СМО делят на два класса: СМО с отказами и СМО с очередями. В СМО с отказами заявка, поступившая в момент, когда все обслуживающие каналы заняты, получает отказ и покидает СМО не обслуженной. В СМО с очередями заявка, пришедшая в момент, когда все каналы обслуживания заняты, не уходит, а становится в очередь
на обслуживание. При этом различают: СМО с ограниченной или неограниченной длиной
очереди, СМО с ограниченным или неограниченным временем ожидания в очереди. Рассмотрим различные модели СМО.
Одноканальная СМО с отказами.
Система имеет один канал, на который поступает поток заявок с интенсивностью  ,
поток обслуживаний имеет интенсивность  . Оба потока простейшие. В качестве показателей эффективности такой СМО рассматриваются:
- абсолютная пропускная способность, т. е. среднее число заявок, обслуживаемых в един и
цу времени A 
;

- относительная пропускная способность, т. е. средняя доля пришедших заявок, обслужен
ных системой Q 
;

- вероятность отказа, т. е. вероятность того, что заявка покинет систему не обслуженной

Pотк 
.

Многоканальная СМО с отказами (задача Эрланга).
В системе имеется n каналов, на которые поступает пуассоновский поток заявок с
интенсивностью  . Все каналы доступны в равной степени всем заявкам. Обслуженные за-
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
явки образуют пуассоновский поток с интенсивностью  , где  является обратной величиной среднему времени обслуживания одной заявки t обс .
Обозначим через S i состояние системы, когда i каналов заняты обслуживанием поступивших заявок. Тогда в любой момент времени система может находиться в одном из п еречисленных состояний: S 0 , S1 ,..., S n . Когда система находится в установившемся, стационарном режиме, вероятности p i нахождения системы в состоянии S i называются предельными (финальными). Они имеют четкий смысл: вероятность p i показывает относительное
время пребывания системы в состоянии S i . Например, если p 0  0,5 , то в среднем половину
времени система простаивает (состояние S 0 ).
Среднее число заявок, приходящееся на среднее время обслуживания одной заявки,

называют интенсивностью нагрузки каналов. Можно получить следу
ющие формулы для предельных вероятностей состояний системы:
- вероятность того, что все каналы свободны, характеризующую среднее время простоя
2
k
 n 1
 ... 
 ... 
) ;
системы, p 0  (1   
т.е. величину  
2!
k!
n!
- вероятность пребывания в системе ровно k заявок p k 
k
p 0 , k  1,2,..., n .
k!
Для многоканальной СМО рассматривают следующие показатели эффективности:
- вероятность отказа Pотк очередной заявке в обслуживании равна вероятности того, что
все n каналов заняты Pотк 
n
p0 ;
n!
- относительная пропускная способность – это вероятность того, что заявка будет обслужена (доля обслуженных заявок) Q  1  Pотк ;
- абсолютная пропускная способность A  Q   (1 
- среднее число занятых каналов k системы k 
n
n!
p0 ) ;
A
.

Задача 1. На коммутатор, имеющий три внешние линии связи, поступает в среднем в час 60
требований на связь. Средняя продолжительность разговора 3 мин. Определи ть предельные
вероятности состояний системы, вероятность отказа абоненту и среднее число занятых линий связи. При каком минимальном числе внешних линий связи среднее число занятых линий будет больше 2?
Решение. Система является многоканальной СМО. По условию n  3,   60 треб./час,
t обс  3 мин. Найдем интенсивность потока обслуживаний  , приведя характеристики к
единому времени (час). Тогда t обс  0,05 часа и
1
 20 треб./час.
t обс 0,05
Отсюда определим интенсивность нагрузки каналов
 60
 
3
 20
и предельные вероятности системы
 2  3 1
9 27
1
p 0  (1   

)  (1  3   ) 1 
 0,077 ;
2!
3!
2 6
13
2
9
p1    p0  3  0,077  0,231 ;
p2 
p 0   0,077  0,346 ;
2!
2

1

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3
27
 0,077  0,346 .
3!
6
Таким образом, коммутатор в стационарном режиме в среднем 7,7% времени простаивает, 23,1% времени обслуживает одну заявку, по 34,6% времени у него заняты две и три
внешние линии связи.
Вероятность отказа абоненту (заняты все 3 линии) совпадает с вероятностью p 3 , т.е.
p3 
p0 
Pотк  0,346 , а отсюда находится относительная пропускная способность Q  1  Pотк  0,654 .
Далее вычисляется абсолютная пропускная способность A    Q  60  0,654  39,24 , т.е.
в час в среднем обслуживается 39,24 требования на связь. Среднее число занятых линий соA 39 ,24
ставит величину k  
 1,962 , тем самым каждая из внешних линий связи будет

20
k
1,962
 100 % 
 100 %  65,4% времени.
n
3
Если число линий связи уменьшить до двух, то среднее число занятых линий будет
меньше двух. Поэтому увеличим число линий связи до четырех и вычислим показатели эффективности коммутатора при n  4 :
3 2 33 3 4 1
p0  (1  3 
  )  (1  3  4,5  4,5  3,375 ) 1  0,0611 ;
2! 3! 4!
81
p4 
 0,0611  0,206 ; Q  1  p 4  1  0,206  0,794 ;
24
A 47 ,63
 2,38 .
A  Q  60  0,794  47,63 ; k  

20
Из полученных результатов видно, что при 4 внешних линиях связи среднее число занятых линий превышает 2.
Одноканальная СМО с неограниченной очередью.
Рассматривается одноканальная СМО с очередью, на которую не наложены никакие
ограничения. Потоки заявок и обслуживаний являются простейшими с интенсивностями  и
 соответственно. Система может находиться в одном из следующих состояний: S 0 - канал
занята в среднем
свободен; S 1 - канал занят (обслуживает заявку), очереди нет; S 2 - канал занят, одна заявка
стоит в очереди; … S k - канал занят, (k  1) заявок стоит в очереди т. д.
Доказано, что если   1, то предельные вероятности состояний существуют, а при
выполнении условия   1 очередь растет до бесконечности и предельных вероятностей не
существует. При   1 предельные вероятности вычисляют по формулам:
p 0  1   , p1   (1   ) , p 2   2 (1   ) ,…, p k   k (1   ) ,… .
(1)
При выполнении условия   1 любая заявка, пришедшая в систему, будет обслужена,
поэтому Pотк  0, Q  1, A   . Среднее число заявок, находящихся в системе Lсис и в
очереди Lоч вычисляются по формулам
2
Lоч 
Lсис 
,
.
(2)
1 
1 
Среднее время пребывания заявки в системе Tсис и в очереди Tоч определяются по
формулам Литтла

Tсис 
1
Lсис ,
Tоч 
1
Lоч .
(3)


Задача 2. Поток поступлений неисправной аппаратуры в мастерскую гарантийного
ремонта является простейшим с интенсивностью   9 ед/сутки. В мастерской работает один
мастер и средняя продолжительность ремонта одной единицы аппаратуры равна 2 часам.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Очередь может быть неограниченной. Найти показатели эффективности работы мастерской,
а также вероятность того, что имеется очередь, но в ней не более двух заявок.
Решение. Приведем исходные характеристики к одной размерности. Время обслужи1
1
вания t обс =2час=
суток. Отсюда     t обс  9   0,75 . Так как   1 , то предельные
12
12
вероятности существуют. Вероятность простаивания мастерской в установившемся режиме
равна p0  1    0,25 . Вероятность наличия в мастерской одной, двух, трех заявок (ожидают обслуживания 0,1,2 заявки) находится по формулам (1):
p1  0,75  0,25  0,1875 ; p 2  0,75 2  0,25  0,140 ; p 3  0,75 3  0,25  0,105 .
Вероятность того, что имеется очередь и ожидают обслуживания не более чем две заявки, определится как сумма вероятностей
p  p 2  p3  0,14  0,105  0,245 .
Средняя длина очереди и среднее время пребывания в очереди вычисляются по формулам (2),(3):
L
2,25
0,75 2
 0,25 (суток)=6(час).
Lоч 
 2,25 (заявки); Tоч  оч 
0,25

9
Среднее число заявок, находящихся в мастерской, и среднее время пребывания заявки
в ней определяются по этим же формулам:
L
3 1
0,75
Tсис  сис   (суток)=8 (час).
Lсис 
 3 (заявки);

9 3
0,25
Многоканальная СМО с неограниченной очередью.
В СМО имеется n каналов. Поток заявок, поступающих в систему, имеет интенсивность  , а поток обслуживаний – интенсивность  . Оба потока простейшие. Очередь является неограниченной.
Система может находиться в одном из следующих состояний: S 0 - заявки в системе
отсутствуют; S 1 - занят один канал, остальные свободны; … S n - заняты все n каналов, очереди нет; S n 1 - заняты все n каналов, в очереди одна заявка;… S n  r - заняты n каналов, r
заявок находится в очереди; ... .
Показано, что при выполнении условия   n предельные вероятности перечисленных состояний существуют, а в противном случае (   n) стационарного режима не существует, так как очередь растет до бесконечности.
Предельные вероятности вычисляются по формулам:
2
n
 n 1 1
p 0  (1   
 ... 

) ;
2!
n! n!(n   )
p1  p 0 ;
p2 
2
2!
p n 1 
p 0 ;… p k 
 n 1
k
k!
p 0 ;… p n 
p0 ; … p n  r 
n
n!
p0 ;
(4)
 nr
p0 ; … .
n  n!
n r n!
Так же как и для одноканальной СМО при   n Pотк  0, Q  1,
Другие параметры эффективности СМО находятся:
A.
- вероятность того, что поступившая заявка окажется в очереди Pоч 

;

 n 1  p 0
- среднее число заявок в очереди Lоч 

 n 1
n!( n   )
- среднее число занятых каналов k 
n  n!(1 
n
;
)
2
(5)
p0 ;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
- среднее число заявок в системе Lсис  Lоч   .
(6)
Среднее время пребывания заявки в очереди и системе вычисляются по формулам
Литтла (3).
Задача 3. В ремонтную мастерскую поступает в среднем 46 заказов в час. Среднее
время исполнения заказа составляет 3 мин. Определить:
1. Минимальное количество рабочих-ремонтников, при котором очередь не будет расти до бесконечности и характеристики обслуживания для n  nmin .
2. Оптимальное количество рабочих-ремонтников, при котором уровень суммарных
потерь C п , связанный с простоем среднего числа рабочих nсв и пребыванием в очереди
среднего числа клиентов-заказчиков Lоч следующей формулой C п  nсв  Lоч , будет минимальным.
3. Вероятность того, что в очереди будет не более 3 клиентов при оптимальном числе
рабочих.
Решение. 1. Выбирая в качестве единицы времени 1 мин., найдем интенсивность п о46
тока заявок  
 0,77 заказ./мин. Тогда определится интенсивность нагрузки каналов
60
    t обс  0,77  3  2,3 . Очередь в мастерской не будет расти до бесконечности, если
  2,3  n . Отсюда определяем минимальное количество рабочих nmin  3 . Определим показатели эффективности СМО для n  3 .
По формуле (4) найдем вероятность того, что все каналы свободны
2,3 2 2,33
2,3 4
p 0  (1  2,3 


) 1  (1  2,3  2,645  2,028  6,663 ) 1  0,068 .
2!
3!
3!(3  2,3)
Таким образом, в среднем 6,8% времени рабочие будут простаивать.
Вероятность того, что в мастерской будет очередь, равна
2,3 4
Pоч 
 0,068  0,453 .
3!(3  2,3)
Среднее число клиентов, находящихся в очереди, и среднее время ожидания в очереди определятся по формулам (5) и (3):
2,3 4  0,068
1,94
Lоч 
 1,94 ; Tоч 
 2,52 (мин).
2,3 2
0
,
77
3  3!(1 
)
3
Среднее число клиентов в мастерской и среднее время их нахождения в ней найдутся
по формулам (6) и (3):
4,24
Lсис  1,94  2,3  4,24 ; Tсис 
 5,51 (мин).
0,77
Среднее число рабочих, занятых обслуживанием заявок, равно k    2,3 , отсюда
вычисляем среднее число свободных рабочих nсв  n  k  3  2,3  0,7 .
2. Уровень суммарных потерь при n  3 составит
C п  nсв  Lоч  0,7  1,94  2,64 .
Рассчитаем уровень суммарных потерь при других значениях n и результаты сведем
в таблицу:
Число рабочих-ремонтников
Характеристики обслуживания
3
4
5
6
Вероятность простоя p 0
0,068
0,093
0,099
0,1
Среднее число простаивающих рабочих nсв
0,7
1,7
2,7
3,7
Среднее число клиентов в очереди Lоч
1,94
0,345
0,084
0,021
Суммарные потери C п
2,64
2,04
2,784
3,721
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Из таблицы следует, что минимальные суммарные потери будут, когда число рабочих-ремонтников составляет n  n опт  4 .
3. Вероятность того, что в очереди будет не более 3 клиентов при числе рабочих
n  4 , определяется как сумма вероятностей несовместных событий:
P(r  3)  ( p0  p1  p 2  p3  p 4 )  p 41  p 4 2  p 43  (1  Pоч )  p 41  p 4 2  p 43 .
Выражение в скобках определяет вероятность того, что, либо заявок нет, либо обслуживается одна, две, три или четыре заявки, т.е. вероятность события, когда в мастерской отсутствует очередь. Остальные слагаемые определяют вероятность того, что в очереди стоят
от одного до трёх клиентов. Вычислим указанные вероятности по формулам (4):
2,3 2 2,33 2,3 4
2,35
p 0  (1  2,3 



) 1  0,093 ;
2!
3!
4!
4!(4  2,3)
5
2,3
Pоч 
 0,093  0,147 ;
4!(4  2,3)
2,35
2,36
2,37
 0,093  0,062 ; p 4 2  2
 0,093  0,036 ; p 43  3
 0,093  0,021 .
4  4!
4  4!
4  4!
Искомая вероятность найдется
P(r  3)  (1  0,147)  0,062  0,036  0,021  0,972 .
Многоканальная СМО с ограниченной очередью.
Рассмотрим n - канальную систему с очередью, когда количество заявок, находящихся в очереди, ограничено числом m . В этом случае заявка, нашедшая все n каналов занятыми, становится в очередь, если длина очереди меньше m , и покидает систему, если длина
очереди равна m .
В системе действует два основных потока: входящий простейший поток с интенси вностью  и поток обслуженных заявок, когда время обслуживания распределено по показательному закону с параметром  .
Тогда основные формулы для установившегося режима СМО запишутся:
- вероятность того, что все каналы свободны и очереди нет
p 41 
n
p 0  (
k 0

k
k!


 n 1 (1  ( ) m )
n
n!n(1 

) 1 ;
)
n
- вероятность того, что занято ровно k (k  n) каналов, очереди нет
pk 
k
p0 ;
k!
- вероятность того, что n каналов занято и r (r  m) заявок стоит в очереди
pnr 
- вероятность отказа
 nr
n r  n!
Pотк  p n  m 
p0 ;
 nm
n m  n!
- относительная пропускная способность
Q  1  Pотк ;
- абсолютная пропускная способность
A  Q ;
- среднее число заявок в очереди
p0 ;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Lоч 
  

 n 1 p 0 1  (m  1  m )( ) m 

n
n  n!(1 

n
)
n

;
2
-среднее число занятых каналов
k   (1 
- среднее число заявок в системе
 nm
n m  n!
p0 ) ;
Lсис  Lоч  k .
Среднее время пребывания заявки в очереди и системе определяются по формулам
Литтла (3).
Задача 4. Автозаправочная станция состоит из трех бензоколонок. Обслуживание машин производится в порядке их прибытия. Входящий поток заявок – простейший с интенсивностью  =2 маш./мин. Время обслуживания распределено по показательному закону, а
среднее время обслуживания одной заявки равно 3 мин. Длина очереди машин не должна
превышать 3 машин. Найти:
1) вероятность того, что все бензоколонки свободны;
2) вероятность того, что все бензоколонки заняты и очереди нет;
3) относительную пропускную способность системы;
4) среднюю длину очереди.
Решение. Для рассматриваемой СМО с ограниченной длиной очереди исходные данные равны: n =3; m =3;  =2; t обс =3. Отсюда находим интенсивность нагрузки каналов

   t обс  2  3  6 ,

а через неё искомые характеристики системы:
6
6 4 (1  ( ) 3 )
2
3
6
6
3 ) 1  (565) 1  0,0018 , т. е. время простоя очень


1) p0  (1  6 
6
2! 3!
3!3(1  )
3
мало (из 10000 часов только 18 часов станция простаивает);

63
 0,0018  0,0668 ;
2) p n 
3!

3) Pотк  p n ( ) m  0,0668  2 3  0,534 , Q  1  Pотк  1  0,534  0,466 , т.е. станция удоn
влетворяет 47% всех заявок;
6 4 1  (4  3  2)  2 3
4) Lоч  0,0018 
 2,2 (машины).
3!3(1  2) 2


Задачи для контрольной работы
№№ 1-3. Универсам получает ранние овощи и зелень из теплиц пригородного совхоза. Машины с товаром прибывают в универсам в неопределенное время. В среднем пребыв ает  автомашин в день. Подсобные помещения и оборудование для подготовки овощей к
продаже позволяют обработать и хранить товар объемом не более m машин одновременно.
В универсаме работают n фасовщиков, каждый из которых в среднем может обработать товар с одной автомашины в течение t обс . Определить вероятность обслуживания приходящей
автомашины Pобс . Какова должна быть емкость подсобных помещений, чтобы вероятность


обслуживания удовлетворяла неравенству Pобс  Pобс
, где Pобс
- заданная величина (<1).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

1.   3 авт./день, t обс =0,5 дня, n =2, m =2, Pобс
=0,92.

2.   3 авт./день, t обс =0,3 дня, n =2, m =2, Pобс
=0,97.

3.   6 авт./день, t обс =0,25 дня, n =4, m =2, Pобс
=0,93.
№№ 4-6. В магазин самообслуживания поступает пуассоновский поток покупателей с
интенсивностью  человек в минуту. Средняя продолжительность обслуживания на расчетном узле составляет t обс . Уровень суммарных потерь S п связан с простоем среднего числа
свободных контролеров-кассиров nсв и пребыванием среднего числа покупателей в очереди
Lоч следующей зависимостью S п = nсв + Lоч . Определить оптимальное число контролеровкассиров, при котором суммарные потери будут минимальными.
4.  =1,0 пок./мин, t обс =2 мин.
5.  =2,0 пок./мин, t обс =1,4 мин.
6.  =0,5 пок./мин, t обс =1,8 мин.
№№ 7-8. В магазин самообслуживания поступает пуассоновский поток заявок с интенсивностью  покупателей в час. В течение дня их обслуживают n контролеров-кассиров
с интенсивностью  покупателей в час. Интенсивность входного потока покупателей в час
«пик» возрастает до величины  m ax , а в часы «спада» уменьшается до величины  m in . Определить вероятность образования очереди в магазине Pоч и среднюю длину очереди Lоч в течение дня, а затем необходимое число контролеров-кассиров в часы «пик» n m ax и часы «спада» n m in , обеспечивающих такую же вероятность образования очереди Pоч .
7.  =200 пок./ч.,  =90 пок./ч., n =3,  m ax =400 пок./ч.,  m in =100 пок./ч.
8.  =300 пок./ч.,  =180 пок./ч., n =3,  m ax =500 пок./ч.,  m in =140 пок./ч.
№№ 9-10. В пункте химической чистки работают две приёмщицы. В среднем за 40 –
часовую рабочую неделю в приемный пункт обращается m клиентов, всегда дожидающихся
обслуживания. Среднее время обслуживания t обс . Считая, что поток клиентов простейший, а
время обслуживания распределено по показательному закону, найти вероятность полного
простоя пункта и вероятность наличия очереди. Установить, при каком числе приемщиц в ероятность наличия очереди Pоч будет меньше заданной P  оч .
9. m =480, t обс =5 мин., P  оч =0,1.
10. m =560, t обс =6 мин., P  оч =0,15.
Тема 3. Модели сетевого планирования и управления
Планирование и управление сложными комплексами работ (проектами), объединенных общностью цели, осуществляется методами сетевого планирования и управления (СПУ).
СПУ основано на моделировании процесса с помощью сетевого графика, который с математической точки зрения представляет собой ориентированный граф без контуров и петель.
Основными понятиями СПУ являются работа и событие. Под работой понимается,
во-первых, действительная работа, требующая затрат ресурсов. Во-вторых, ожидание –
протяженный во времени процесс, не требующий затрат трудовых ресурсов (твердение бетона, сушка после покраски и т.п.). В-третьих, фиктивная работа, которая не требует затрат
никаких ресурсов.
Под событием понимают результат завершения одной или нескольких работ.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
События на сетевом графике изображаются кружками (вершины графа), в которых
указан порядковый номер или шифр события. Работы изображаются направленными отрезками прямых (стрелками), рядом с которыми проставляется либо продолжительность работы, либо её шифр. Например, если работа связывает события с номерами i и j , то для работы используется шифр (i, j ) . Среди событий сетевого графика выделяют исходное и завершающее. Первое из них не имеет предшествующих работ, а второе – последующих работ и
событий.
Сетевые графики составляются с соблюдением определенных правил: он должен
иметь только одно исходное и одно завершающее события; любые два события должны быть
связаны не более чем одной работой (стрелкой); в графике не должно быть замкнутых контуров и петель, «тупиковых» и «хвостовых» событий (кроме исходного и завершающего события).
При составлении сетевого графика для нумерации событий используют метод вычеркивания дуг. Исходному событию присваивают нулевой ранг и номер 0. Далее мысленно в ычеркивают дуги (стрелки), выходящие из исходного события. Тогда события, не имеющие
входящих стрелок, относят к событиям 1-го ранга. Им в произвольном порядке присваивают
номера 1,2,…, k . Затем мысленно удаляют стрелки, выходящие из всех событий 1-го ранга.
События, не имеющие после этого входящих дуг, относят к событиям 2-го ранга. Им присваивают следующие по порядку номера k  1, k  2,...,l и т.д. В результате завершающее событие получает некоторый номер n .
Путь на сетевом графике – это любая последовательность работ, в которой конечное
событие каждой работы совпадает с начальным событием следующей работы. Если начало
пути совпадает с исходным событием, а конец – с завершающим, то такой путь называется
полным. Длительностью пути называют суммарную продолжительность всех входящих в
него работ.
Наиболее продолжительный по срокам полный путь в сетевом графике называется
критическим, а его длительность обозначают t кр . Это основной параметр сетевого графика.
Работы и события, расположенные на этом пути, называются критическими. Если выполн ение какой-либо критической работы будет задержано, то это вызовет задержку выполнения
всего комплекса. Некритические работы допускают некоторое запаздывание их вып олнения
без нарушения критического пути.
Чтобы определить время, на которое можно задержать выполнение некритической
работы, вводят понятие резервов времени событий и работ, которые, в свою очередь, выражаются через ранние и поздние сроки свершения событий.
Под свершением события понимается момент, к которому заканчиваются все входящие в событие работы, и может быть начата любая выходящая из него работа.
Ранним сроком t р (i ) свершения события i называется самый ранний момент времени,
к которому завершаются все работы, предшествующие этому событию. Если событие i имеет несколько предшествующих путей, связывающих его с исходным событием 0, а, следов ательно, несколько непосредственно предшествующих ему событий, то t р (i ) можно найти по
формуле
t р (i)  max(t р (k )  t (k , i)) ,
k
(1)
где t (k , i ) - продолжительность предшествующей работы, связывающей события k и i .
Поздним сроком t п (i ) свершения события i называют самый поздний момент времени, после которого остается ровно столько времени, сколько необходимо для завершения
всех работ, следующих за этим событием. Если событие i имеет несколько последующих
путей, связывающих его с завершающим событием n , а, следовательно, несколько непосредственно последующих за ним событий, то t п (i ) удобнее находить по формуле
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
t п (i)  min (t п ( j )  t (i, j )) ,
(2)
j
где t (i, j ) - продолжительность последующей работы, связывающей события i и j .
Резерв времени R(i ) события i определяется как разность
R (i )  t п (i )  t р (i ) .
(3)
Резерв R(i ) показывает, на какой предельно допустимый срок можно задержать
свершение события i без изменения t кр . Очевидно, что критические события резервов времени не имеют.
Зная сроки свершения событий i и j для работы (i, j ) можно ввести в рассмотрение
следующие параметры работы:
- ранний срок начала работы t рн (i, j )  t р (i ) ;
(4)
- ранний срок окончания работы t ро (i, j )  t р (i )  t (i, j ) ;
(5)
- поздний срок окончания работы t по (i, j )  t п ( j ) ;
(6)
- поздний срок начала работы t пн (i, j )  t п ( j )  t (i, j ) .
(7)
Для работ выделим два основных вида резервов времени:
- полный резерв времени Rп (i, j ) работы (i, j ) - это максимальное количество времени, на которое можно задержать начало работы или увеличить ее длительность, не нарушая длительность критического пути Rп (i, j )  t п ( j )  t р (i )  t (i, j ) ;
- независимый резерв времени Rн (i, j ) работы (i, j ) - это часть полного резерва, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а
все последующие работы начинаются в ранние сроки Rн (i, j )  t р ( j )  t п (i )  t (i, j ) .
Построение сетевого графика не является самоцелью. Его используют для улучшения
всего комплекса работ, в частности, для решения ряда оптимизационных задач. Примерами
служат: задача сокращения длительности критического пути, задача рационального использования ресурсов и другие.
За счет переноса части ресурсов с некритических работ на критические можно сократить срок их выполнения и тем самым уменьшить критический путь. Время выполнения работы a i можно найти по формуле
A
ti  i .
bi
Здесь Ai - объем работы, например, в человеко-днях, b i - ресурсы, например, число
человек в бригаде, выполняющей данную работу.
Изменив количество ресурсов на величину x i , можно получить новое время выполнения работы
Ai
t i 
.
bi  xi
Сокращение времени выполнения работы a i за счет увеличения ресурсов на величину
x i составит
Ai
Ai
Ai  xi
Ai
1



  xi .
bi bi  xi bi (bi  xi ) bi  xi bi
1
Введем в рассмотрение коэффициент пересчета c i 
и предположим, что выполняbi
ется условие
1
xi  bi  .
(8)
ci
t i  t i  t i 
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Тогда bi  xi  bi и окончательно получаем формулу
t i  t i ci xi .
(9)
Задача. На основе анализа некоторого проекта была получена следующая структурновременная таблица комплекса входящих в него работ (опорной называется работа, если она
непосредственно предшествует некоторой работе, и без её выполнения та не может быть
начата).
Таблица 1
Обозначение Опорные ра- Коэффициенты пере- Продолжительность
боты
работы a i
счета c i
работ t i
c1  0,1
t1  7
a1
a1
c2  0,2
c3  0,3
t2  9
t3  5
a4
a3
c4  0,4
t4  4
a5
a1
c5  0,5
t5  7
a6
a5
c6  0,6
t6  4
a7
a4
c7  0,7
t7  2
a8
a4
c8  0,8
t8  6
a9
a6 , a7
c9  0,9
t9  5
a10
c10  1,0
t10  6
a11
a 2 , a8
a 9 , a10
c11  1,1
t11  2
a12
a13
a11
a12
c12  0,1
c13  0,1
t12  1
t13  1
a2
a3
-
Требуется:
1. Построить сетевой график, найти все его полные и критические пути.
2. Рассчитать временные параметры событий и работ, вычислить их резервы времени.
3.На основе сетевой модели выполнить перераспределение ресурсов так, чтобы минимизировать время выполнения всего комплекса работ.
Решение. 1. Работы a1 , a 2 не имеют опорных работ и реализация проекта начинается с
этих работ. Они изобразятся стрелками, выходящими из одного кружка – исходного события.
Масштаб при этом не соблюдается, поэтому длина стрелок и их расположение являются
произвольными. В конце стрелки ставится кружок – конечное событие работы.
Работе a 3 предшествует работа a1 , поэтому стрелка a 3 на сети изобразится вслед за
конечным событием работы a1 . Для работы a 4 опорной является a 3 , отсюда стрелка a 4 следует за a 3 . Стрелка a 5 располагается вслед за a1 , а a 6 - вслед за a 5 . Работа a 9 может
начаться только после работ a 6 , a 7 , поэтому изобразим работы a 6 , a 7 стрелками, которые
сводятся в одно событие, из которого затем следует стрелка a 9 . Аналогично поступаем с работами a 2 и a 8 , после которых выполняется работа a10 . Стрелки a11 , a12 , a13 следуют одна
за другой, они моделируют заключительные работы проекта, и стрелка a13 сводится в завершающее событие проекта.
a6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a5
a7
a3
a1
a9
a11
a4
a12
a8
a13
a10
a2
Рис. 1
Пронумеруем события, используя метод вычеркивания дуг. Присвоим исходному событию номер 0. Мысленно вычеркнем стрелки, исходящие из этого события. Тогда событие,
из которого исходят стрелки a 3 , a 5 , не будет иметь входящих стрелок. Это событие 1-го ранга и ему присваиваем номер 1. Далее мысленно вычеркиваем стрелки a 3 , a 5 , выходящие из
события 1, получим два события 2-го ранга. Присвоим им номера 2 и 3. Выполняя нумерацию событий по приводимому правилу, в итоге получим следующую сетевую модель с завершающим событием 10:
a6
2
5
a9
a5
0
a1
1
a7
a3
3
a2
a4
7
4
a8
a11
8
a12
9
a13
10
a10
6
Рис. 2.
Полных путей, связывающих исходное (0) и завершающее событие (10), в данном
графе четыре:
L1 : a1 , a5 , a6 , a9 , a11 , a12 , a13 ;
L2 : a1 , a3 , a 4 , a7 , a9 , a11 , a12 , a13 ;
L3 : a1 , a3 , a 4 , a8 , a10 , a11 , a12 , a13 ;
L4 : a 2 , a10 , a11 , a12 , a13 .
Найдем длительность полных путей как суммарную продолжительность входящих в
них работ (числовые данные из таблицы 1):
t ( L1 )  T1  t1  t 5  t 6  t 9  t11  t12  t13  27 ;
t ( L2 )  T2  t1  t 3  t 4  t 7  t 9  t11  t12  t13  27 ;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
t ( L3 )  T3  t1  t 3  t 4  t 8  t10  t11  t12  t13  32 ;
t ( L4 )  T4  t 2  t10  t11  t12  t13  19 .
Третий путь L3 является наиболее длительным (32 суток) и будет единственным критическим путем сетевого графика с t кр =32.
2. Найдем вначале ранние и поздние сроки свершения событий. Для этого составим
таблицу 2.
Таблица 2
Номер события
Сроки свершения событий
Резерв времени
события R(i )
(i )
Ранний срок t р (i )
Поздний срок t п (i )
0
1
2
3
4
5
6
7
8
9
10
0
7
14
12
16
18
22
28
30
31
32
0
7
19
12
16
23
22
28
30
31
32
0
0
5
0
0
5
0
0
0
0
0
Для определения ранних сроков свершения событий t р (i ) двигаемся по сетевому графику слева направо и используем формулу (1).
Для i  0 (исходное событие) очевидно, что t р (0)  0 .
При i  1 : t р (1)  t р (0)  t (0,1)  0  7  7 (суток), так как для события 1 существует
только один предшествующий путь (из события 0 в событие 1). Аналогично для события 2:
t р (2)  t р (1)  t (1,2)  7  7  14 , события 3: t р (3)  t р (1)  t (1,3)  7  5  12 и события 4:
t р (4)  t р (3)  е(3б 4)  12  4  16 .
Для события 5 существуют два пути, связывающих его с исходным событием: 0-1-2-5
и 0-1-3-4-5, т.е. два непосредственно предшествующих события 2 и 4. Поэтому
t р (5)  max t р (2)  t (2,5); t р (4)  t (4,5)  max 14  4; 16  2  18 .
И далее:
t р (6)  max t р (0)  t (0,6); t р (4)  t (4,6)  max 9; 22  22 ;
t р (7)  max t р (5)  t (5,7); t р (6)  t (6,7)  max 23; 28  28 ;
t р (8)  t р (7)  t (7,8)  28  2  30 ; t р (9)  t р (8)  t (8,9)  30  1  31 ;
t р (10 )  t р (9)  t (9,10 )  31  1  32 .
Для определения поздних сроков свершения событий t п (i ) двигаемся по сети справа
налево, начиная с завершающего события 10, а вычисления производим по формуле (2).
Для i  10 поздний срок свершения события совпадает с ранним сроком свершения
этого события: t п (10 )  t р (10 )  32 (суток). Для события 9 существует только один последующий путь к событию 10, поэтому t п (9)  t п (10 )  t (9,10 )  32  1  31 . Аналогично находим:
t п (8)  t п (9)  t (8,9)  31  1  30 ; t п (7)  t п (8)  t (7,8)  30  2  28 ;
t п (6)  t п (7)  t (6,7)  28  6  22 ; t п (5)  t п (7)  t (5,7)  28  5  23 .
Для i  4 имеются два последующих пути: 4-5-7-8-9-10 и 4-6-7-8-9-10. Отсюда
t п (4)  min t п (5)  t (4,5); t п (6)  t (4,6)  min 23  2; 22  6  16 .
Далее по тем же правилам определим:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
t п (3)  t п (4)  t (3,4)  16  4  12 ; t п (2)  t п (5)  t (2,5)  23  4  19 ;
t п (1)  min t п (2)  (1,2); t п (3)  t (1,3)  min 12;7  7 ;
t п (0)  min t п (1)  t (0,1); t п (6)  t (0,6)  min 0;13  0 .
Затем по формуле (3) вычисляем резервы времени каждого события. Резерв времени
события 2 равен 5. Это означает, что время свершения события 2 может быть задержано на 5
суток без увеличения общего срока выполнения работ.
После заполнения таблицы 2 найдем по формулам (4)-(7) временные параметры работ, а результаты расчетов сведем в таблицу 3.
Таблица 3
Работа
(i, j )
Продолжительность
работы t (i, j )
Сроки начала и окончания работ
Резервы времени
t рн (i, j )
t ро (i, j )
t пн (i, j )
t по (i, j )
Rп (i, j )
Rн (i, j )
(0,1)
(0,6)
(1,2)
(1,3)
(2,5)
(3,4)
(4,5)
(4,6)
(5,7)
(6,7)
(7,8)
(8,9)
(9,10)
7
9
7
5
4
4
2
6
5
6
2
1
1
0
0
7
7
14
12
16
16
18
22
28
30
31
7
9
14
12
18
16
18
22
23
28
30
31
32
0
13
12
7
19
12
21
16
23
22
28
30
31
7
22
19
12
23
16
23
22
28
28
30
31
32
0
13
5
0
5
0
5
0
5
0
0
0
0
0
13
0
0
0
0
0
0
0
0
0
0
Вычисление временных параметров работы (i, j ) покажем на примере работы (1,2):
- ранний срок начала работы находим по формуле (4) t рн (1,2)  t р (1)  7 ;
- ранний срок окончания определяем по формуле (5) t ро (1,2)  t р (1)  t (1,2)  7  7  14 ;
- поздний срок начала работы вычислим по формуле (7) t пн (1,2)  t п (2)  t (1,2)  12 ;
- поздний срок окончания находим по формуле (6) t по (1,2)  t п (2)  19 .
Работа (1,2) должна начаться в интервале 7,14  , а закончиться в интервале 12,19  суток от начала выполнения проекта. Полный резерв работы (1,2) составит величину
Rп (1,2)  t п (2)  t р (1)  t (1,2)  19  7  7  4 . Таким образом, срок выполнения данной работы
можно увеличить на 4 суток и это не вызовет увеличение срока выполнения всего проекта.
Независимый резерв времени равен Rн (1,2)  t р (2)  t п (1)  t (1,2)  14  7  7  0 .
Если резерв Rн (i, j ) получается отрицательным, то в таблице 3 на его месте ставят
прочерк (работа (2,5)).
3. Из таблицы 3 видно, что работы a2 , a6 , a7 , a9 имеют полный резерв времени, и на
этих работах происходит простаивание ресурсов. Сокращение длительности всего комплекса
работ можно достичь за счет переноса части ресурсов с указанных работ. Ресурсы перен осятся на такие работы критических путей, которые не входят в полный путь, с работ которого переносят часть ресурсов.
Перенос начинается с работы некритического пути, длительность которого менее всего отличается от длительности критического пути. В нашем случае это два пути L1 и L2 , для
которых t ( L1 )  t ( L2 )  27 .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Перенесем часть ресурсов с работы a 9 , входящей в оба пути L1 , L2 и имеющей шифр
(5,7). Ресурсы можно перенести на работы a 8 или (и) a10 , лежащие на критическом пути, но
нельзя переносить ресурсы на работы a1 , a3 , a 4 , a11 , a12 , a13 , которые входят в пути L1 и L2 .
Перенесем часть простаивающих ресурсов в объеме x 9 с работы a 9 на работу a10 . Тогда время выполнения работы a 9 согласно формуле (9) увеличится на величину (при выполнении условия (8))
t 9  t 9  c9  x9 .
В свою очередь, время выполнения работы a10 уменьшится на величину
t10  t10  c10  x10 .
Длительность путей L1 , L2 увеличится на величину t 9
T1  T2  T1  t 9 c9 x9 ,
а длительность критического пути уменьшится на t10
  t кр  t10 c10 x10 .
t кр
Величины x 9 и x10 находятся из условия равенства длительности путей L1 , L2 и L3 :
 .
T1  T1  t 9 c9 x9  t кр  t10 c10 x10  t кр
В нашем случае x 9 полностью переносится на работу a10 , поэтому получаем систему
для нахождения неизвестных величин x9 , x10 :
T1  t 9 c9 x9  t кр  t10 c10 x10 ,

x9  x10 .

Подставляя в систему численные значения, получим
27  5  0,9  x9  32  6  1  x9 , x9  x10  0,475 .
1
1
 1,1 ; x10 
 1 и использоваУбеждаемся, что выполняются условия (8): x9 
c9
c10
ние формулы (9) является корректным. Далее находим:
t 9  t 9 c9 x9  5  0,9  0,475  2,15 ;
t10  t10 c10 x10  6  1  0,475  2,85 .
Пересчитаем длительность всех полных путей после переноса ресурсов:
T1  T2  T1  t 9  27  2,15  29 ,15 ;
  T3  t10  32  2,85  29 ,15 ;
T3  t кр
T4  T4  t10  19  2,85  16 ,15 .
Таким образом, в результате перераспределения ресурсов работ a 9 и a10 длительность выполнения всего проекта сократилась с 32 суток до 29,15. Пути L1 , L2 и L3 стали
критическими, а путь L4 остался некритическим.
Временные параметры событий и работ изменятся. Чтобы определить на каких работах в новых условиях происходят простои ресурсов, построим новую сетевую модель в масштабе времени. В этом случае выбирается ось времени и модель строится так, чтобы проекция длины стрелки на ось была равна длительности соответствующей работы.
2
a6
9
a5
5
a13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a1
0
1
a3
a9
3
a2
a12
a7
a4
7
10
a11
4
a 8 a10
r2
8
6
6
t
(сутки)
0 2
4
6
8 10 12 14 16 18 20 22 24 26 28 30
Рис. 3.
Построение графа начинается с критических путей. Затем строится путь L4 . Так, как
  29 ,15 суток, то на графе изображается фиктивное событие 6
его длительность меньше t кр
и фиктивная работа r2 , связывающая событие 6 с событием 6 (пунктирная стрелка).
Из графика видно, что простой ресурсов будет только на работе a 2 , и резерв времени
равен длительности фиктивной работы r2  13 . Части ресурсов с работы a 2 можно переносить на все работы, кроме работ a10 , a11 , a12 , a13 , которые входят в путь L4 . Выполним перенос ресурсов на работу a1 , так как она входит во все три критические пути.
Увеличим t 2 на величину t 2  t 2 c 2 x 2 и уменьшим время выполнения работы a 2 на
t1  t1c1 x1 . Очевидно, что x1  x 2 . Длительность L4 и всех критических путей после переноса части x1 ресурса должны быть равны
  t кр
  t1c1 x1  T4  t 2 c 2 x 2 .
t кр
Подставляя численные значения, получаем
29,15  7  0,1  x1  16,15  9  0,2  x1 или x1  5,2 .
Новые длительности выполнения работ a1 и a 2 составят:
t1  t1  t1c1 x1  7  7  0,1  5,2  3,36 ;
t 2  t 2  t 2 c2 x2  9  9  0,2  5,2  18,36 .
Длительности пути L4 и критических путей L1 , L2 , L3 совпадут
T4  T4  t 2 c2 x2  16,15  9,36  25,51 ,
  t1c1 x1  29 ,15  3,64  25,51 .
T1  T2  T3  t кр
Таким образом, достигнуто полное выравнивание длительности всех полных путей и
время выполнения всего комплекса уменьшилось на величину
  32  25,51  6,49 (суток).
t  t кр  t кр
Оптимальная сетевая модель имеет вид
a5
1
2
a6
5
8
10
a1
a3
a7
a9
a11
a12
0
3
7
4
a4
a8
a13
a10
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a2
6
t
(сутки)
0
2
4
6
8
12 14 16 18 20 22 24 26
Рис. 4.
При переносе ресурсов с работы некритического пути на работы нескольких критических путей иногда не оказывается общей для них работы, на которую можно переносить ресурсы. В этом случае забираемый ресурс переносится на несколько работ, каждая из которых
входит либо в свой критический путь, либо в часть критических путей. Для определения неизвестных величин составляется система линейных уравнений. Например, если на последнем
шаге рассматриваемой задачи осуществить перенос ресурсов с работы a 2 на работы
a 6 , a 7 , a8 , которые входят в критические пути L1 , L2 , L3 соответственно, то x 2  x6  x7  x8 и
система для определения неизвестных примет вид:
T4  t 2 c 2 x 2  T1  t 6 c6 x6 , T4  t 2 c 2 x 2  T2  t 7 c7 x7 , T4  t 2 c 2 x 2  T3  t 8 c8 x8 .
Возможны и другие варианты переноса ресурсов с работы a 2 .
Задачи для контрольной работы
Дан перечень работ (таблица 4) по организации выставки-продажи товаров и продолжительность этих работ (таблица 5). Требуется построить сетевой график, определить
полные и критические пути, временные параметры сетевого графика и выполнить оптимизацию сетевого графика с целью сокращения критического пути.
Содержание работ
Заказ на оборудование и товары
Разработка системы учета спроса
Отбор товаров и выписка счетов
Завоз товара
10
Обозначение
работы
a1
a2
a3
a4
Таблица 4
Опорные рабо- Коэффициент
ты
пересчета
c1 =0,1
c 2 =0,2
a1
c 3 =0,3
a3
c 4 =0,4
Завоз оборудования
a5
a1
c 5 =0,5
Установка оборудования
a6
a5
c 6 =0,6
Выкладка товаров
a7
a4
c 7 =0,7
Учет наличия товара
a8
a4
c 8 =0,8
Оформление зала и витрины
a9
a6 , a7
c 9 =0,9
Изучение документов учета
a10
a 2 , a8
c10 =1,0
Репетиция выставки-продажи
a11
a12
a13
a9 , a10
c11 =1,1
c12 =0,1
c13 =0,1
Проведение выставки
Анализ результатов
a11
a12
Таблица 5
№ варианта
1
2
3
4
t1
10
8
9
7
t2
12
15
11
14
t3
2
6
4
5
t4
3
3
4
6
Продолжительность работы в сутках
t5
t6
t7
t8
t9
t10
5
6
6
5
5
4
4
5
5
5
3
3
6
5
3
6
6
5
6
7
5
5
5
5
t11
2
2
3
2
t12
1
1
1
1
t13
1
1
1
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5
6
7
8
9
10
12
9
14
10
11
13
12
7
16
11
13
15
1
5
2
5
3
5
5
4
3
6
2
6
4
9
3
5
5
7
7
7
7
7
10
8
2
6
5
1
6
4
4
7
5
6
7
6
5
8
7
4
4
5
6
8
3
5
7
6
1
3
4
2
3
2
1
1
1
1
1
1
1
1
1
1
1
1
Литература
1. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое
программирование. Мн.: Высш. Школа, 1994.
2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование.
М.: Высшая школа, 1980.
3. Исследование операций в экономике. Под ред. Н.Ш. Кремера. М.: Банки и биржи,
ЮНИТИ, 1997.
4. Зайченко Ю.П. Исследование операций. Киев: Вища школа, 1975.
Правила выполнения и оформления контрольной работы
1.
Выбор вариантов осуществляется в соответствии с последней цифрой учебного шифра студента (например, если последняя цифра «3», то выполняется вариант номер 3, если «0», то - вариант номер 10).
2.
Контрольная работа пишется чернилами любого цвета (кроме красного) в тонкой тетради, для замечаний рецензента оставляются поля. На обложке тетради указывают фамилию,
имя, отчество студента, номер студенческой группы, учебный шифр (серия и номер зачетной
книжки), название кафедры, наименование дисциплины и номер контрольной работы, а также домашний адрес.
3.
Решение задач следует располагать в порядке следования номеров, указанных в задании, сохраняя номера задач. Условия задач выписывать обязательно. Если несколько задач
имеют общую формулировку, то при переписывании общие условия заменяют конкретными
данными.
4.
Решения задач требуется оформлять аккуратно, подробно объясняя все действия и и спользуемые формулы. В конце работы приводится список использованной литературы, указывается дата выполнения работы и ставится подпись исполнителя.
Документ
Категория
Экономика
Просмотров
52
Размер файла
727 Кб
Теги
1119, математика
1/--страниц
Пожаловаться на содержимое документа