Цель работы – построить циклограмму, которая демонстрирует работу парикмахерской, рассчитать транспортную задачу и задачу линейного программирования и найти ее оптимальное решение.
В процессе работы проводились вычисления и анализ транспортной и линейной задач, ее суть - имея исходные данные о перевозимом грузе, предусмотреть расходы и найти наиболее оптимальный по цене вариант решения.
Содержание
Введение…………………………………………………………………………………………..
4
1. Моделирование процессов в системе G/G/3/3…………………………..…………………..
5
2. Анализ данных единичного эксперимента…………………………………………………..
18
3. Транспортная задача (ТЗ) линейного программирования…………………………………..
25
3.1. Составление опорного плана ТЗ по методу Северо-западного угла (СЗУ)…………….
25
3.2. Составление опорного плана ТЗ по методу минимума стоимостей перевозки………..
26
3.3. Сравнение планов по критерию стоимости………………………………………………
27
3.4. Проверка лучшего опорного плана на оптимальность…………………………………..
28
3.5. Улучшение плана по методу циклических перестановок……………………………….
29
4. Решение задачи линейного программирования……………………………………………..
32
4.1. Условие задачи линейного программирования ………………………………………….
32
4.1.1. Граф-схема решения задачи линейного программирования….……………………..
32
4.1.2. Алгебраическая модель решения задачи линейного программирования…………..
33
4.1.3. Геометрическая форма представления процесса решения………………………….
35
4.1.4. Свойства задач линейного программирования………………………………………
37
4.2. Симплекс-метод решения задачи линейного программирования………………………
38
4.2.1. Иллюстрация процесса поиска решения……………………………………………...
Список использованной литературы…………………………………………………………...
44
Введение
В основе системного анализа лежит системный подход. При системном подходе объект /реальная система/ рассматривается как комплекс систем рационально-эмпирического типа, полнота которого проверяется практикой взаимодействия субъекта с объектом.
Системный анализ как совокупность методов и средств подготовки и обоснования решений применяется к системам, выделенным для описания объекта.
Системный анализ образует базис для изучения наук о системах: «Исследования операций», «Теории систем», «Теории принятия решений» и др.
В курсовой работе мы используем метод имитационного моделирования и метод линейного программирования.
В ходе имитационного эксперимента формируется комплекс эмпирических систем для системного анализа, проводимого в условиях неопределённости, нечёткости или риска.
Имитационное моделирование в широком смысле определяет методологию исследований, в основу которой положен способ имитации реальных процессов и явлений. Методология – это учение о структуре, логической организации, методах и средствах деятельности. Методология имитационного моделирования опирается на теорию вероятностей как науку о принципах построения, формах и способах познания явлений стохастической природы [1].
Линейное программирование – это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. На алгоритмах ЛП (учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач, включая целочисленное, нелинейное и стохастическое программирование[2].
1 Моделирование процессов в системе G/G/3/3.
Представим результаты моделирования одного рабочего дня системы. Описание процессов будем строить в форме циклограмм по каждому часу функционирования системы с указанием и анализом особенностей принимаемых решений.
Циклограмму имитационного процесса будем строить в форме, принятой при описании работы переключающих схем.
Циклограмма работы системы является удобной формой представления процессов имитации для относительно несложных систем при моделировании вручную, на АВМ и гибридных средствах при наличии многоканальных устройств вывода сигналов[1].
При моделировании на ЦВМ следует учитывать особенности средств отображения цифровой информации и устройств ввода-вывода.
На Рис.1-1.4. показана циклограмма работы парикмахерской с тремя рабочими каналами и тремя каналами ожидания за один рабочий день.
В таблице 1 показана выборка случайных чисел.
N(dT)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
r
81
53
77
58
84
28
31
10
10
47
62
93
86
30
7
12
43
N(S)
1
2
3
4
5,6
7
n1
1
1
1
1
1
4
4
4
4
4
n2
2
2
2
2
5
5
5
n3
3
3
3
6
6
6
6
m1
m2
m3
Рис.1. Циклограмма
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
58
71
85
74
54
90
40
69
1
63
12
41
12
70
8
9
10
11,12
13
14
15
16
17
перерыв
перерыв
перерыв
перерыв
перерыв
Перерыв
11
11
11
11
11
15
15
15
8
8
8
10
10
10
10
10
10
перерыв
перерыв
перерыв
перерыв
9
9
9
9
13
13
13
13
14
14
14
14
10
11
14
14
14
15
15
Рис.1.1. Циклограмма
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
37
61
42
87
84
5
8
70
45
75
7
76
27
9
47
38
3
1
18
19
20
21,22
23,24
25
26
27,28
29,3
15
15
19
19
19
22
22
23
23
23
23
23
30
30
30
30
перерыв
перерыв
20
20
20
20
20
20
24
24
27
27
27
27
27
14
18
18
18
21
21
21
21
26
26
26
29
29
29
29
29
29
29
18
19
21
23
23
23
27
30
22
22
24
24
24
24
Рис.1.2. Циклограмма
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
87
30
16
72
54
74
15
85
12
37
49
99
88
29
2
91
2
31
32
33
34
35,36,37
38
39,4
31
31
31
31
33
33
33
33
33
35
35
35
35
35
39
32
32
32
34
34
34
36
36
36
36
38
38
перерыв
перерыв
перерыв
перерыв
перерыв
перерыв
37
37
37
37
37
40
38
38
38
39
40
Рис.1.3. Циклограмма
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
58
94
30
12
81
81
48
76
95
60
15
31
12
76
27
60
90
41,42
43
44
45
46,47
48
49
50
51,52
39
39
42
42
43
43
43
43
46
46
46
49
49
49
51
51
38
41
41
44
44
44
44
48
48
48
48
48
50
50
50
40
40
40
40
45
45
45
52
52
42
Рис.1.4. Циклограмма
86
87
88
51
51
50
50
52
52
52
Рис.1.5. Циклограмма
Таблица 1
Выборка
Rl
Rm
Rr
Rt
1
81
90
7
75
2
53
60
76
45
3
77
27
27
70
4
58
76
9
8
5
84
12
47
5
6
28
31
38
84
7
31
15
3
87
8
10
60
1
42
9
10
95
87
61
10
47
76
30
37
11
62
48
16
70
12
93
81
72
12
13
86
81
54
41
14
30
12
74
12
15
7
30
15
63
16
12
94
85
1
17
43
58
12
69
18
2
2
37
40
19
58
91
49
90
20
71
2
99
54
21
85
29
88
74
22
74
88
29
85
23
54
99
2
71
24
90
49
91
58
25
40
37
2
2
26
69
12
58
43
27
1
85
94
12
28
63
15
30
7
29
12
74
12
30
30
41
54
81
86
31
12
72
81
93
32
70
16
48
62
33
37
30
76
47
34
61
87
95
10
35
42
1
60
10
36
87
3
15
31
37
84
38
31
28
38
5
47
12
84
39
8
9
76
58
40
70
27
27
77
41
45
76
60
53
42
75
7
90
81
43
7
75
44
76
45
45
27
70
46
9
8
47
47
5
48
38
84
49
3
87
50
1
42
51
87
61
52
30
37
53
16
70
54
72
12
55
54
41
56
74
12
57
15
63
58
85
1
59
12
69
60
37
40
61
49
90
62
99
54
63
88
74
64
29
85
65
2
71
66
91
58
67
2
2
68
58
43
69
94
12
70
30
7
71
12
30
72
81
86
73
81
93
74
48
62
75
76
47
76
95
10
77
60
10
78
15
31
79
31
28
80
12
84
81
76
58
82
27
77
83
60
53
84
90
81
Рис.2. Продолжение табл.1
Частота событий
по результатам моделирования в единицах
мин показана в табл.2.
Таблица 2
Частота событий
Tr\Tm
0
1
2
3
4
5
6
7
E
0
7
0
1
9
9
8
1
1
36
1
0
0
1
3
2
3
1
0
10
2
0
0
1
0
0
1
0
0
2
3
0
0
0
1
0
2
0
0
3
4
0
0
1
0
0
0
0
0
1
5
0
0
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
0
0
0
0
E
7
0
4
13
11
14
2
1
52
,
где
- время нахождения заявки в системе;
-время в очереди;
- время на обслуживание.
При
=0 имеем 36 заявок, т.е. те которые не ждали, а сразу поступали на рабочий канал или сразу уходили: 7 ушли сразу, 1 заявка обслуживалась 2 пятиминутных интервала, 9 - по 3 , 9 - по 4, 8 – по 5, 1 – по 6, и 1 заявка обслуживалась 7 пятиминутных интервалов. Самое длительное
= 40 (
= 3,
= 5), самое короткое - =10.
При построении циклограммы одного рабочего дня системы мы придерживались правила последовательной выборки случайных чисел по мере необходимости по системе обусловленных адресов.
При этом для удобства имитации было принято лишь одно соглашение: выборка из таблицы случайных чисел производилась для каждого вида МСВ (Механизм случайной выборки) своего начального адреса.
Можно было бы обойтись и без этого соглашения, выбирая числа последовательно с любого начального адреса вне зависимости от типа МСВ. Назовём подобный путь организации статических испытаний последовательным.
Однако установить соответствие без проведения имитационного эксперимента в этом случае не представляется возможным из-за случайности протекающего процесса, в функции которого производится выборка случайных чисел из таблицы [1].
f({rv};E;P)=Sv
S, где rv- принятая последовательность случайных чисел до шага v; Е-структура системы; Р- правила функционирования, принятые при моделировании; Sv-состояние системы на шаге v, f-функция от случайной последовательности случайных чисел rv и констант Е, Р, определяемых моделью системы и правилами проведения имитационного моделирования [1].
В моделируемый день. В систему поступило 52 заявки.
Первый канал обслужил 17 заявок и из 88 пятиминутных интервалов он был свободен 21 интервалов.
Второй канал обслужил 15 заявок и был свободен 30 интервалов .
Третий канал обслужил 13 заявок и был свободен 33 интервалов.
Всего обслужено 45 заявки. Покинуло систему 7 заявок.
Для анализа средних величин временных параметров
где
среднее время нахождения заявки в системе;
среднее время ожидания в очереди
среднее время обслуживания,
а также связанных с ними параметров, в частности
и
(средняя длина очереди и среднее число занятых каналов), представим результаты моделирования в виде табл.3.
Таблица 3
Число кортежей
w
Tr
Tm
Ts
n
Заявки
1
0
0
0
7
7;12;16;17;25;28;47;
2
0
2
2
1
41;
3
0
3
3
9
3;5;8;26;32;34;45;46;49;
4
0
4
4
9
2;6;9;13;31;36;43;44;51;
5
0
5
5
8
1;4;33;35;37;48;50;52;
6
0
6
6
1
20;
7
0
7
7
1
29;
8
1
2
3
1
42;
9
1
3
4
3
18;19;39;
10
1
4
5
2
21;30;
11
1
5
6
3
11;27;40;
12
1
6
7
1
10;
13
2
2
4
1
22;
14
2
5
7
1
15;
15
3
3
6
1
38;
16
3
5
8
2
14;23;
17
4
2
6
1
24;
Общее время обслуживания и его составляющие определяются суммированием данных, приведённых в табл.2.
где
суммарное время, проведённое заявками в очереди;
суммарное время обслуживания заявок.
Общее число заявок пребывающих в очереди: n(R)= 19.
= (10*1+2*2+3*3+1*4)/16=1,69 пятимин. интервала или 8,45 мин. = (4*2+13*3+11*4+14*5+2*6+1*7)/45=4 пятиминутных интервала или 20 мин.
В очереди потрачено время 45*5 мин = 225; на обслуживание затрачено 180*5=900 мин.; среднее время, проведенное заявкой в системе, составило
=(8,45+20,00)мин=28,45 мин.
Работу отдельных каналов обслуживания можно оценить, представив данные эксперимента в виде табл.4: производительнее всех работал 2-й канал (19,333 мин/s), обслуживший 15 заявок.
Таблица 4
Данные эксперимента
N1 ед.
N1dT
N2 ед.
N2dT
N3 ед.
N3dT
E ед
E dT
Мин
1
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
3
2
4
2
4
0
0
4
8
40
4
4
12
5
15
4
12
13
39
195
5
4
16
3
12
4
16
11
44
220
6
7
35
3
15
4
20
14
70
350
7
0
0
2
12
0
0
2
12
60
E мин
17
67
15
58
13
55
45
180
900
0
335
0
290
0
275
0
20
0
T m
19,706
19,333
21,154
Очевидно, при сдельной оплате труда по затратам времени, если общий фонд зарплаты принять равным единице, заработок q следует распределить:
1-ый канал – 335/Q; q1=0,37;
2-ой канал – 290/Q; q2=0,32;
2-ой канал – 275/Q; q2=0,31;
Q=900 мин.
Для выравнивания загрузки по числу обслуженных за день заявок можно ввести очередь между каналами на обслуживание очередной заявки. Это равносильно изменению правил функционирования системы и потребует проведения самостоятельных имитационных исследований системы.
Среднее число занятых каналов
через коэффициент перегрузки одного канала:
,
где
среднее время обслуживания заявки в моделируемый день.
- среднее время поступления одной заявки.
= 350/52=6,73
(20 мин/s)/(6,73 мин/s)=2,97
По данным эксперимента в системе наблюдается следующие состояния:
S0- система свободна; S1 –один канал занят; S2 –два канала занято;S3-три канала,S4-одно место в очереди занято;S5-два места в очереди занято;S6- три места в очереди занято.
В табл.5 указаны данные о количестве переходов типа Si - Sj.
Таблица 5
Количество переходов
S0
S1
S2
S3
S4
S5
S6
E
P(S)
S0
4
3
0
1
0
0
0
8
0,0909
S1
1
3
7
1
0
0
0
12
0,1364
S2
2
5
6
6
0
0
0
19
0,2159
S3
0
2
6
12
8
1
0
29
0,3295
S4
0
0
0
8
4
2
0
14
0,1591
S5
0
0
0
1
2
1
1
5
0,0568
S6
0
0
0
0
0
1
0
1
0,0114
E
7
13
19
29
14
5
1
88
Рабочий день можно представить в виде случайного процесса показанного на рис.3. Внизу на рисунке суммировано число интервалов
, когда система находиться в данном состоянии.