Анализ вычислительной сложности задачи трехмерной упаковки в общей постановке, а также основные подходы к ее решению. Содержание задачи математического программирования по размещению ориентированных произвольных невыпуклых многогранников сложных форм.
Аннотация к работе
Упаковкой назовем такой набор параметров размещения объектов , при котором выполняются следующие условия: , т.е. никакие два объекта не пересекаются между собой, и все объекты находятся внутри области размещения. Для обеспечения условий взаимного непересечения объектов между собой и с границей области размещения, требуется построить ГФПР Gij всех пар многогранников и для каждого многогранника построить ГФПР GQI к внешности области зоны размещения (хотя в этом случае эта область является невыпуклой, но ГФПР для нее строится тривиально). Рассмотрим размещение четырех объектов по шагам, при этом на каждом шаге будем размещать объект с соответствующим номером: Шаг 1: Точка локального минимума принадлежит вершине ГФПР объекта T1 к зоне размещения Q - GQ1. Размещение четырех объектов T1, T2, T3 и T4 в области Q: а) годограф GQ1 объекта T1 и области размещения Q, точка занесения, соответствующая точке локального минимума (размещение первого объекта T1 в пустой области Q); в) годограф GQ3 объекта T3 и области размещения Q, годографы G13 и G23 объекта T3 и объектов T1 и T2, точка занесения (размещение третьего объекта T3 в области Q с размещенными объектами T1 и T2). г) годограф GQ4 объекта T4 и области размещения Q, годографы G14, G24 и G34 объекта T4 и объектов T1, T2 и T3, точка занесения (размещение четвертого объекта T4 в области Q с размещенными объектами T1, T2 и T3).