О двух задачах оптимальной упаковки гомотетических эллипсоидов

Abstract

Рассматриваются две задачи упаковки гомотетичных одинаково ориентированных эллипсоидов: в прямоугольном параллелепипеде минимального объема и в эллипсоиде с минимальным коэффициентом гомотетии. Строятся математические модели в виде задач нелинейного программирования. Предлагается два подхода к поиску эффективных локально оптимальных решений. Первый подход основан на r-алгоритме Шора. Второй подход использует гомотетические преобразования эллипсоидов, и оптимизационную процедуру, позволяющую свести задачу с большим числом неравенств к последовательности задач с меньшим числом неравенств. Предлагается алгоритм доупаковки. Приводятся результаты численных экспериментов.