Задача об упаковке

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: изложение 4 класс, заключение реферата
| Добавил(а) на сайт: Коньяков.

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

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

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

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

1. Путем попарного сравнения упаковываемых объектов определяется асимметричное транзитивное отношение доминирования:

[pic] где 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(суммарная полезность упакованных элементов).

[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 |