Реферат: Задача об упаковке
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 |
К-во Просмотров: 1069
Бесплатно скачать Реферат: Задача об упаковке
| |||