Завдання про упаковку

Санкт-Петербурзький Державний Технічний Университет.

Факультет Технічною Кибернетики.

Кафедра Системний Аналіз і Управление.

ПРИЙНЯТТЯ РЕШЕНИЙ.

Розрахунковий задание.

Тема: «Завдання про упаковці «.

Дата:_____________.

Санкт-Петербург.

2001 г.

1.Постановка завдання… …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. Алгоритм «кращий з з убыванием ». Алгоритм аналогічний «до кращої з », але об'єкти упорядковані від великих до меньшим.

Упаковываемые об'єкти мають оцінки якості за багатьма критеріям. Потрібна упакувати максимальну кількість об'єктів, а чи не отримати мінімальне число контейнерів. Введемо такі обозначения:

[pic] vij — j-й фізичний параметр i-го об'єкта; Vlj — j-й фізичний параметр l-го контейнера; Ui — загальна цінність i-го об'єкта. Означимо через I=1, 2, …, М безліч номерів об'єктів, а через.

[pic].

Безліч тих упакованих об'єктів, котрим бракуватиме більш цінних серед не упакованих. Формальна завдання має наступний вид:

[pic], [pic].

При ограничениях:

[pic], j = 1, …, P, l = 1, …, K; [pic].

Алгоритм рішення поставленого завдання включає у собі алгоритми рішення допоміжних завдань: 1. Упаковка багатомірних об'єктів у контейнери; 2. Получение інформації від ЛПР, що дозволяє визначити порядок упаковки многокритериальных объектов.

3.Решение задачи.

1. Шляхом попарного порівняння упаковываемых об'єктів визначається асиметричне транзитивное ставлення доминирования:

[pic] де Q — кількість критериев.

2. Відповідно до ставленням P0 на безлічі упаковываемых об'єктів можна назвати підмножина недоминируемых об'єктів. Після їхнього видалення можна назвати друге підмножина тощо. до вичерпання безлічі. Виділені підмножини називаються паретовыми слоями.

3. Застосовуємо алгоритм упаковки з відкиданням при чергуванні, пакуючи по верствам об'єкти у контейнеры.

К побудованому квазипорядку упаковываемых об'єктів итеративно застосовуємо алгоритм упаковки з відкиданням для послойной упаковки об'єктів. Нехай об'єкти перших (i-1)-го верств упаковуються, а елементи і верств не упаковуються. Серед об'єктів, які входять у перші (i=1) верстви, виділяється підмножина кращих об'єктів, переважаючих кожен із інших упаковываемых об'єктів (якщо таке є). Це підмножина вважається поки що виконання завдання підлягає обов’язкової упаковці. Одержимо жодну з можливих упаковок, найкращих з погляду О2.

Будемо упаковувати, використовуючи алгоритм з відкиданням при чергуванні, об'єкти перших і верств. Послідовно видаляємо при упаковці об'єкти 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(суммарная корисність упакованих элементов).

[pic].

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 З++ 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;

NDom=false;

}; void ObjectInit (int m, int з, 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);

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 ].