МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Прізвище: Ім’я: Група: Кафедра: Дисципліна: Перевірив: Шагала Василь КНст-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