Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ЛАБОРАТОРНА РОБОТА № 2 частина 2. Прийняття рішень в умовах повної інформації. Задача про упакування в контейнери
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
КНІТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет “Львівська політехніка”
Прізвище:
Ім’я:
Група:
Кафедра:
Дисципліна:
Перевірив:
Шагала
Василь
КНст-12
САПР
Математичні методи
Дослідження операцій
Файтас О.І.
ЛАБОРАТОРНА РОБОТА № 2 частина 2. Прийняття рішень в умовах повної інформації. Задача про упакування в контейнери
Мета роботи: Ознайомитись з методами прийняття рішень в умовах повної інформації на прикладі задачі про упакування в контейнери та дослідити особливості їх використання [3-5].
Короткі теоретичні відомості
Задача про упакування в контейнери відноситься до NP–важких комбінаторних задач. Завдання полягає в упаковці об'єктів зумовленої форми в кінцеве число контейнерів зумовленої форми таким чином, щоб кількість використаних контейнерів була найменшою. Іноді розглядають зворотну задачу, щоб кількість або обсяг об'єктів, які упаковують, були найбільшими.
Існує безліч різновидів цієї задачі (двовимірна упаковка, лінійна упаковка, упаковка по вазі, упаковка по вартості і т.і.), які можуть застосовуватися в різних областях, наприклад, в задачі оптимального заповнення контейнерів, завантаження вантажівок з обмеженням по вазі, створення резервних копій на змінних накопичувачах і т.і.
Оскільки задача є NP-важкою, часто використовують алгоритми з евристичним та метаевристичним методом вирішення для отримання оптимальних результатів. Також активно використовуються методи штучного інтелекту, як, наприклад, нейронні мережі.
Математична постановка задачі
Розглянемо умову задачі. Дано:
– нескінчена кількість контейнерів розміром С;
– перелік вантажів розміром (вагою) ci.
1, якщо i-й об’єкт пакується в j-й контейнер
0, в іншому випадку
(2.1)
Бінарна змінна дорівнює 1, якщо j-й контейнер використовується, та 0 в протилежному випадку.
Необхідно так упакувати вантажі в контейнери, щоб загальна кількість контейнерів була найменшою
при наступних обмеженнях
Перша нерівність фіксує, що розмір (вага) вантажів в одному контейнері не буде більшою, ніж його розмір (вантажопідйомність). Друга рівність потребує, щоб всі елементи були розміщені по контейнерах.
Для вирішення цієї задачі розглянемо наступні алгоритми:
– NFA
(Next Fit Algorithm) – алгоритм «заповнення наступного»;
– FFA
(First Fit Algorithm) – алгоритм «заповнення першого, що підходить»;
– WFA
(Worst Fit Algorithm) – алгоритм заповнення «найменш повного»;
– BFA
(Best Fit Algorithm) – алгоритм заповнення «найкращого».
Хоча всі алгоритми націлені на мінімізацію кількості контейнерів, але для різних алгоритмів є відмінності в пошуку контейнера і, відповідно в кількості обчислень, що потребується для цього.
Початкові дані
17
1
90
76
99
52
31
87
77
99
57
66
52
17
41
35
68
98
84
95
76
5
1306
2
66
28
54
28
8
93
78
97
55
72
74
45
51
25
97
83
12
27
82
21
1098
3
93
34
39
34
21
59
85
57
54
61
62
72
41
16
52
50
62
82
99
17
1093
Таблиця результатів
Дані
Аналітичний розрахунок (кількість контейнерів)
1 рядок
7
2 рядок
6
3 рядок
6
1+2+3 рядок
19
Дані
Кількість контейнерів
Обчислювальна складність
Без впорядкування
Без впорядкування
NFA
FFA
WFA
BFA
NFA
FFA
WFA
BFA
1 рядок
6
6
6
6
65
65
65
65
2 рядок
6
6
6
6
54
54
54
54
3 рядок
6
6
6
6
54
54
54
54
1+2+3 рядок
18
18
18
18
173
173
173
173
Дані
З впорядкуванням
З впорядкуванням
NFA
FFA
WFA
BFA
NFA
FFA
WFA
BFA
1 рядок
6
5
5
5
7
7
7
7
2 рядок
6
5
5
5
7
7
7
7
3 рядок
6
5
5
5
7
7
7
7
1+2+3 рядок
18
15
15
15
21
21
21
21
Таблиці обчислень згідно алгоритмів
17
1
90
76
99
52
31
87
77
99
57
66
52
17
41
35
68
98
84
95
76
5
2
66
28
54
28
8
93
78
97
55
72
74
45
51
25
97
83
12
27
82
21
3
93
34
39
34
21
59
85
57
54
61
62
72
41
16
52
50
62
82
99
17
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
90
76
2
99
52
31
87
77
3
99
57
66
52
17
4
41
35
68
98
5
84
95
76
6
5
17
1
2
3
90
66
93
76
28
34
99
54
39
52
28
34
31
8
21
87
93
59
77
78
85
99
97
57
57
55
54
66
72
61
52
74
62
17
45
72
41
51
41
35
25
16
68
97
52
98
83
50
84
12
62
95
27
82
76
82
99
5
21
17
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
90
76
2
99
52
31
87
77
3
99
57
66
52
17
5
4
41
35
68
98
5
84
95
76
6
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
5
2
98
76
76
52
52
17
3
95
68
57
41
4
90
66
35
5
87
6
84
77
31
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
2
98
76
76
52
52
5
3
95
68
57
41
17
4
90
66
35
5
87
6
84
77
31
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
17
2
98
76
76
52
52
31
5
3
95
68
57
41
4
90
66
5
87
6
84
77
35
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
2
98
76
76
52
52
3
95
68
57
41
4
90
66
35
5
87
31
17
5
6
84
77
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
90
76
2
99
52
31
87
77
3
99
57
66
52
17
4
41
35
68
98
5
5
84
95
76
6
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
90
76
2
99
52
31
87
77
3
99
57
66
52
17
5
4
41
35
68
98
5
84
95
76
6
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
17
2
98
76
76
52
52
31
5
3
95
68
57
41
4
90
66
5
87
6
84
77
35
Ряд 2
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
97
97
12
2
93
66
3
83
55
25
21
4
82
54
27
5
78
51
28
28
8
6
74
72
45
Ряд 3
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
17
2
93
54
3
85
50
4
82
52
39
34
34
5
72
61
41
16
6
62
62
57
59
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
5
2
98
76
76
52
52
17
3
95
68
57
41
4
90
66
35
5
87
6
84
77
31
Ряд 2
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
97
97
8
2
93
66
12
3
83
55
25
21
4
82
54
27
5
78
51
28
28
6
74
72
45
Ряд 3
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
2
93
54
16
3
85
50
17
4
82
52
39
34
34
5
72
61
41
6
62
62
57
59
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
99
99
2
98
76
76
52
52
3
95
68
57
41
4
90
66
35
5
87
31
17
5
6
84
77
Ряд 2
№
№ вантажу
конт-ру
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
97
97
2
93
66
3
83
55
25
21
12
8
4
82
54
27
5
78
51
28
28
23.05.2016 19:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора