Санкт-Петербурзький Державний Технічний Університет
Факультет Технічної Кібернетики
Кафедра Системний Аналіз та Управління
ПРИЙНЯТТЯ РІШЕНЬ
Розрахункове завдання
Тема: "Завдання про упакування"
Дата :_____________
Санкт-Петербург
2001
Зміст
1.Постановказадачі ................................................. .....................< br>...................... ... ... .2
2.Теоретичні частина ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 3
3.Решеніе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 5
4.Алгорітм програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6
5.Результати ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 7
6.Висновки ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7
Додаток ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 8
1.Постановка завдання.
Розглянути задачу про упакування 20 гіпотетичних об'єктів у п'ятьконтейнерів. Об'єкти мають оцінки за п'ятьма критеріями Б, В, Г, Д, Е з порядковимишкалами, що мають три градації (перша - краща, друга - середня, третя
- Гірша), а також дві фізичні параметри (вага та обсяг). Критерії маютьоднакову значимість. Контейнери мають наступні параметри:
. Вантажопідйомність контейнера - 5
. Об'єм контейнера - 7
Далі наведено дані об'єктів:
| Номер | Вага | Об'єм | Б | В | Г | Д | Е |
| 1 | | | | | 3 | | |
| | 3 | 2 | 3 | 3 | | 3 | 3 |
| 2 | | | | | 2 | | |
| | 1 | 1 | 3 | 2 | | 1 | 1 |
| 3 | | | | 1 | 1 | | |
| | 3 | 1 | 2 | | | 1 | 2 |
| 4 | 2 | 3 | 2 | | | | |
| | | | | 1 | 3 | 2 | 3 |
| 5 | 1 | 1 | 1 | 1 | 1 | | |
| | | | | | | 3 | 3 |
| 6 | 3 | 2 | 2 | 2 | 1 | | |
| | | | | | | 1 | 1 |
| 7 | 1 | 2 | 3 | 1 | 3 | | |
| | | | | | | 3 | 1 |
| 8 | 2 | 1 | 1 | 1 | 1 | | |
| | | | | | | 2 | 3 |
| 9 | 3 | 2 | 2 | 2 | 1 | | |
| | | | | | | 3 | 2 |
| 10 | | 1 | 1 | 1 | 2 | | |
| | 2 | | | | | 2 | 2 |
| 11 | 1 | 2 | 3 | 3 | 1 | 1 | |
| | | | | | | | 1 |
| 12 | 3 | 1 | 2 | 1 | 2 | | |
| | | | | | | 3 | 1 |
| 13 | 1 | 1 | 2 | 2 | 3 | | |
| | | | | | | 3 | 1 |
| 14 | 1 | 1 | 3 | 3 | 3 | | |
| | | | | | | 2 | 1 |
| 15 | 2 | 2 | 1 | 2 | 2 | | |
| | | | | | | 1 | 1 |
| 16 | 3 | 2 | 3 | 1 | 2 | | |
| | | | | | | 1 | 3 |
| 17 | 1 | 1 | 2 | 1 | 2 | | |
| | | | | | | 1 | 2 |
| 18 | 2 | 2 | 3 | 1 | 3 | | |
| | | | | | | 2 | 1 |
| 19 | 1 | 1 | 1 | 1 | 1 | | |
| | | | | | | 2 | 1 |
| 20 | 1 | 2 | 1 | 1 | 1 | | |
| | | | | | | 1 | 1 |
2.Теоретичні частину.
Розглянемо наступну задачу: є безліч з М об'єктів, якебажано упакувати в К ємностей для подальшого перевезення, причому Містотно більше К. Кожен об'єкт характеризується Р-кількіснимифізичними параметрами (вагою і об'ємом); кожна ємність характеризуєтьсяцими ж граничними фізичними параметрами (наприклад, загальним обсягом івантажопідйомністю). Крім того, кожен з упаковуємо об'єктів маєоцінки за кількома критеріями, які характеризують його якість іпривабливість для особи, відповідальної за перевезення. Ємністьконтейнерів недостатня для упаковки всіх наявних об'єктів. Бажаноздійснити упаковку найкращим чином, тобто так щоб:
1. Число упакованих об'єктів було б максимально можливим, тому що всі вони в тій чи іншій мірі заслуговують упаковки в ємності (тобто попередній відбір, що виключає абсолютно погані об'єкти, що вже зроблено)
- критерій О1.
2. Серед упакованих об'єктів було б найбільша кількість таких, якість яких перевершувало б якість неупакованих - критерій О2.
Є кінцеве безліч об'єктів, причому розмір кожного з нихзадано раціональним числом. Потрібно упакувати предмети в мінімальноможливу кількість контейнерів так, щоб сумарний розмір об'єктів вкожному контейнері не перевищував його розмір (також раціональне число).
Для вирішення цього завдання пропонується ряд алгоритмів:
1. Алгоритм "в першому відповідний". Нехай є якийсь порядок об'єктів і контейнерів. Перший предмет кладемо в перший-ліпший контейнер.
Другий об'єкт кладемо в перший контейнер, якщо він туди поміщається, а якщо ні - то в другій контейнер. Аналогічно упаковуємо інші об'єкти.
2. Алгоритм "в першому підходящий з убування". Упорядкувати список об'єктів від великих до менших. Далі використовуємо алгоритм "у перший підходящий".
3. Алгоритм "в кращий з відповідних". Нехай є якийсь довільний порядок об'єктів. Ідея упаковки аналогічна алгоритму "в першому підходящий", але з такою різницею: черговий об'єкт кладеться в той контейнер, де є найменше, але достатня для нього невикористане простір.
4. Алгоритм "в кращий з відповідних з убування". Алгоритм аналогічний "в кращий з відповідних", але об'єкти впорядковані від великих до менших.
Упаковується об'єкти мають оцінки якості за багатьма критеріями.
Потрібно упакувати Максимальна кількість об'єктів, а не отримати мінімальнекількість контейнерів. Введемо наступні позначення:
vij - j-й фізичний параметр i-го об'єкта;
Vlj - j-й фізичний параметр l-го контейнера;
Ui - загальна цінність i-го об'єкта.
Позначимо через I = 1, 2, ..., М безліч номерів об'єктів, а через
Безліч тих упакованих об'єктів, для яких не знайдеться більшецінних серед не упакованих. Формальна постановка задачі має наступнийвигляд:
,.
При обмеженнях:
, j = 1, ..., P, l = 1, ..., K; < p> Алгоритм вирішення поставленого завдання включає в себе алгоритми рішеннядопоміжних завдань:
1.Упаковка багатовимірних об'єктів у контейнери;
2.Полученіе інформації від ОПР, що дозволяє визначити порядок упаковкибагатокритеріальних об'єктів.
3.Решеніе завдання.
1. Шляхом попарного порівняння упаковуємо об'єктів визначається асиметрична Транзитивне відношення домінування:
де Q - кількість критеріїв.
2. Відповідно до ставленням P0 на безлічі упаковуємо об'єктів можна виділити підмножина недомініруемих об'єктів. Після їх видалення можна виділити другу підмножина і т.д. до вичерпання безлічі. Виділені підмножини називаються паретовимі шарами.
3. Застосовуємо алгоритм упаковки з відкиданням при чергуванні, упаковивая по шарах об'єкти в контейнери.
До побудованому квазіпорядку упаковуємо об'єктів Ітеративний застосовуємоалгоритм упаковки з відкиданням для шарового упаковки об'єктів. Нехайоб'єкти першого (i-1)-го шарів упаковуються, а елементи i шарів неупаковуються. Серед об'єктів, що входять в першу (i = 1) шари, виділяєтьсяпідмножина кращих об'єктів, що перевершують кожен з іншихупаковуємо об'єктів (якщо є). Це вважається підмножинана даному етапі рішення задачі таким, що підлягає обов'язковій упаковці. Отримаємоодну з можливих упаковок, найкращих з точки зору О2.
Будемо упаковувати, використовуючи алгоритм з відкиданням при чергуванні,об'єкти першого i шарів. Послідовно видаляємо при упаковці об'єкти i-гошару у відповідності з їх порядком у списку з чергуванням (від перших доостаннім) до отримання упаковки. Якщо при цьому в контейнерах залишаютьсявільні місця за всіма фізичними параметрами, то в розгляд включаютьсяоб'єкти (i +1)-го шару, недомініруемие неупакованих об'єктами i-го шару, іздійснюється доупаковка. Якщо і тут залишаються можливості, тоАналогічно здійснюється упаковка деякими об'єктами (i +2)-го шару іт.д. У підсумку отримуємо упаковку з максимальним значенням критерію О2.
Отримаємо тепер упаковку з максимальним значенням критерію О1.
Застосуємо алгоритм АОЧ до всього безлічі упаковуємо об'єктів. Чи невидаляються лише згадані вище найкращі об'єкти, що домінують поякості над усіма іншими (якщо такі є). Ясно, що при цьомуотримаємо упаковку з максимальним значенням критерію О1 за умовизбереження домінуючих об'єктів. Розглядаючи точки на площині О1 - О2,
ОПР визначити найкращий для себе компроміс між критеріями О1 і О2 і тимсамим найкращу упаковку.
4.Алгорітм програми.
5.Результати.
Після виконання програми отримані наступні результати.
Програма розподілила об'єкти з вихідного списку за паретовим верствам.
Нижче наведені ці шари (в таблиці вказані номери ел-тов):
| Шар | Номери об'єктів |
| 1 | 20 | | | | | | | |
| 2 | 3 | 6 | 15 | 19 | | | | |
| 3 | 2 | 8 | 9 | 10 | 11 | 12 | 17 | 18 |
| 4 | 4 | 5 | 7 | | 14 | 16 | | |
| | | | | 13 | | | | |
| 5 | 1 | | | | | | | |
Далі програма відсортувати список об'єктів по черговості макс.вес/Макс.обсяг.
| 1 | 4 | 3 | 6 | 9 | 7 | 12 | 16 | 11 | 15 | 8 | 10 | 18 | 20 | 2 | 5 | 13 | 14 | 17 | 19 |
Нижче наведена таблиця результатів упаковки (за алгоритмом упаковки звідкиданням).
| Кількість |? |
| | Користь |
| 14 | 123 |
| 10 | 83 |
Результати можна відобразити графічно у вигляді площині критеріїв
О1 (сумарна кількість упакованих предметів), О2 (сумарна корисністьупакованих елементів).
6.Висновки.
В результаті виконання завдання була написана програма, упаковуються об'єкти в контейнери. Упаковка виробляється за допомогою двох варіантівупорядкування об'єктів. За критерієм О1 (кількість упакованих) найбільшефективний другий метод (є варіанти упаковки по 14 предметів). Наприклад,були упаковані наступні 14 предметів:
| 16 | 11 | 15 | 8 | 10 | 18 | 20 | 2 | 5 | 13 | 14 | 17 | 19 | 7 |
О1 = 14, О2 = 130.
За критерієм О2 виграє перший метод.
Упаковані об'єкти:
| 14 | 16 | 1 | 20 | 3 | 6 | 15 | 19 | 2 | 8 |
О1 = 10, ПРО2 = 83.
Обидва методи дозволяють ОПР вибрати оптимальний варіант упаковки наплощині критеріїв О1, О2.
Додаток.
Текст програми.
Програма написана на мові програмування С + + в середовищі розробки
Visual C + + 6.0. Вибір мови обумовлений наявністю в його стандарті структуриданих - клас, за допомогою якої зручно моделювати об'єкти завдання.
# include
# include
# include "iostream.h"
# include "stdio.h" class Object (
public: int Mass; int Cap; int vol [5]; int Val; bool Packed; int INN; bool NDom;
Object (){
Mass = 0;
Cap = 0;
Packed = false; vol [0] = 0; vol [1] = 0; vol [2] = 0; vol [3] = 0; vol [4] = 0;
Val = 0;
INN = 0; < p> NDom = false;
); void ObjectInit (int m, int c, int v1, int v2, int v3, int v4,int v5, int inn)
(
Mass = m;
Cap = c;
Packed = false; vol [0 ] = v1; vol [1] = v2; vol [2] = v3; vol [3] = v4; vol [4] = v5;
Val = vol [0] + vol [1] + vol [2] + vol [3] + vol [4];
INN = inn;
NDom = false;
);
);
class Konteiner (
public: int Mass; int Cap;
Konteiner (){
Mass = 0;
Cap = 0;
); void KonteinerInit (int m, int c) (
Mass = m;
Cap = c;
);
); struct Result (int Value; int Num;
); void main (){
Object
Ob [21], ObD [400], ObND [400], ObRs, ObMC1 [20], ObMC2 [20], ObMC [21], ObMCRs [20];
Object ObSlice [10] [ 10]; bool MFLAG [21];
Result Res [20], Res1 [20];
Konteiner Kon [5];
Ob [0 ]. ObjectInit (3,2,3,3,3,3,3, 1);
Ob [1]. ObjectInit (1,1,3,2,2,1,1, 2 );
Ob [2]. ObjectInit (3,1,2,1,1,1,2, 3);
Ob [3]. ObjectInit (2,3 , 2,1,3,2,3, 4);
Ob [4]. ObjectInit (1,1,1,1,1,3,3, 5); < p> Ob [5]. ObjectInit (3,2,2,2,1,1,1, 6);
Ob [6]. ObjectInit (1,2,3,1,3, 3,1, 7);
Ob [7]. ObjectInit (2,1,1,1,1,2,3, 8);
Ob [8]. ObjectInit (3,2,2,2,1,3,2, 9);
Ob [9]. ObjectInit (2,1,1,1,2,2,2,10);
Ob [10]. ObjectInit (1,2,3,3,1,1,1,11);
Ob [11]. ObjectInit (3,1,2 , 1,2,3,1,12);
Ob [12]. ObjectInit (1,1,2,2,3,3,1,13);
Ob [13]. ObjectInit (1,1,3,3,3,2,1,14);
Ob [14]. ObjectInit (2,2,1,2,2,1, 1,15);
Ob [15]. ObjectInit (3,2,3,1,2,1,3,16);
Ob [16]. ObjectInit ( 1,1,2,1,2,1,2,17);
Ob [17]. ObjectInit (2,2,3,1,3,2,1,18);
Ob [18]. ObjectInit (1,1,1,1,1,2,1,19);
Ob [19]. ObjectInit (1,2,1,1 , 1,1,1,20); for (int i = 0; i = Ob [i]. vol [4 ])){
ObD [j] = Ob [l]; ObND [ j] = Ob [i]; j + +;) else (
if ((MFLAG [Ob [i]. INN] == false) & (MFLAG [Ob [l]. INN] == false ) & & (i! = l) & & (Ob [l]. vol [0
]
