Задача об упаковке (стр. 1 из 2)
Санкт-Петербургский Государственный Технический Университет
Факультет Технической Кибернетики
Кафедра Системный Анализ и Управление
ПРИНЯТИЕ РЕШЕНИЙ
Расчетное задание
Тема: "Задача об упаковке"
Дата:_____________
Санкт-Петербург
2001 г.
Содержание
1.Постановка задачи............................................................................................…….2
2.Теоретическая часть………………………………………………………………..3
3.Решение……………………………………………………………………………..5
4.Алгоритм программы………………………………………………………………6
5.Результаты…………………………………………………………………………..7
6.Выводы……………………………………………………………………………...7
Приложение…………………………………………………………………………..8
1.Постановка задачи.
Рассмотреть задачу об упаковке 20 гипотетических объектов в пять контейнеров. Объекты имеют оценки по пяти критериям Б,В,Г,Д,Е с порядковыми шкалами, имеющими три градации (первая - лучшая, вторая – средняя, третья - худшая), а также два физических параметра (вес и объем). Критерии имеют одинаковую значимость. Контейнеры имеют следующие параметры:
· Грузоподъемность контейнера – 5
· Объем контейнера – 7
Далее приведены данные объектов:
| Номер | Вес | Обьем | Б | В | Г | Д | Е |
| 1 | 3 | 2 | 3 | 3 | 3 | 3 | 3 |
| 2 | 1 | 1 | 3 | 2 | 2 | 1 | 1 |
| 3 | 3 | 1 | 2 | 1 | 1 | 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 | 2 | 1 | 1 | 1 | 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; 
Алгоритм решения поставленной задачи включает в себя алгоритмы решения вспомогательных задач:
1.Упаковка многомерных объектов в контейнеры;
2.Получение информации от ЛПР, позволяющей определить порядок упаковки многокритериальных объектов.
3.Решение задачи.
1. Путем попарного сравнения упаковываемых объектов определяется асимметричное транзитивное отношение доминирования:
где Q – количество критериев.
2. В соответствии с отношением P0 на множестве упаковываемых объектов можно выделить подмножество недоминируемых объектов. После их удаления можно выделить второе подмножество и т.д. до исчерпания множества. Выделенные подмножества называются паретовыми слоями.
3. Применяем алгоритм упаковки с отбрасыванием при чередовании, упаковывая по слоям объекты в контейнеры.
К построенному квазипорядку упаковываемых объектов итеративно применяем алгоритм упаковки с отбрасыванием для послойной упаковки объектов. Пусть объекты первых (i–1)-го слоев упаковываются, а элементы i слоев не упаковываются. Среди объектов, входящих в первые (i=1) слои, выделяется подмножество лучших объектов, превосходящих каждый из остальных упаковываемых объектов (если таковое имеется). Это подмножество считается на данном этапе решения задачи подлежащим обязательной упаковке. Получим одну из возможных упаковок, наилучших с точки зрения О2.
Будем упаковывать, используя алгоритм с отбрасыванием при чередовании, объекты первых i слоев. Последовательно удаляем при упаковке объекты i-го слоя в соответствии с их порядком в списке с чередованием (от первых к последним) до получения упаковки. Если при этом в контейнерах остаются свободные места по всем физическим параметрам, то в рассмотрение включаются объекты (i+1)-го слоя, недоминируемые неупакованными объектами i-го слоя, и осуществляется доупаковка. Если и теперь остаются возможности, то аналогично осуществляется упаковка некоторыми объектами (i+2)-го слоя и т.д. В итоге получаем упаковку с максимальным значением критерия О2.