Интернет конференция по проблемам теории и практики управления

Название: О задачах упаковок неравных шаров
в трехмерном пространстве
Автор: Анна Ананьевна Лемперт
Соавторы:
Казаков А. Л. , Лемперт А. А., Та Ч. Т.
Аннотация:
Статья посвящена построению оптимальных упаковок набора шаров разных радиусов в трехмерное замкнутое множество: требуется найти такое рас-положение фиксированного числа шаров, чтобы их радиусы были максимальными. Данная проблема является NP-трудной. Для решения указанной проблемы предложен вычислительный алгоритм, основанный на использовании оптико-геометрического подхода и метода бильярдного моделирования. Применение данного подхода позволяет решать задачи упаковки не только в евклидовом, но и в других метрических пространствах. Так, рассмотрена задача, в которой вместо расстояния между центрами шаров параметром оптимизации является минимальное время перемещения между ними. Подобные постановки нередко возникают при решении задач охраны периметра, когда время перемещения «нарушителя» до охраняемого объекта играет существенно более важную роль, чем пройденное при этом расстояние, а так-же в логистике, где время доставки имеет первостепенное значение. Алгоритм реализован в виде программного комплекса, с помощью которого проведены вычислительные эксперименты, причем в качестве множества-контейнера выбирались как выпуклые, так и невыпуклые множества. Результаты расчетов позволяют оценить работоспособность и эффективность предложенного алгоритма. Выполнена 3-D визуализация полученных результатов.
Ключевые слова:
упаковка шаров разных типов, трехмерное пространство, оптико-геометрический подход, метод бильярдного моделирования, вычислительный алгоритм, неевклидовая метрика

Название: О задачах построения многократных покрытий и упаковок в двумерном неевклидовом пространстве
Автор: Анна Ананьевна Лемперт
Соавторы:
Казаков А.Л., Лемперт А.А., Ле К.М.
Аннотация:
Статья посвящена изучению двух содержательных задач вычислительной геометрии: задачи построения оптимальных многократных покрытий кругами замкнутого ограниченного множества в двумерном метрическом пространстве и аналогичной задачи упаковки кругов. В обоих случаях число кругов k фиксировано. В первом случае целью является минимизация, а во втором - максимизация радиуса кругов. Рассматриваемая метрика, вообще говоря, неевклидова. Источником такой постановки является транспортная логистика, где встречаются задачи, в которых расстояние между объектами необходимо заменить минимальным временем перемещения между ними, при этом искомый оптимум в силу особенностей местности далеко не всегда достигается при движении по прямой линии.
Для решения задач предложены вычислительные алгоритмы, которые основаны на применении оптико-геометрического подхода, базирующегося на принципах геометрической оптики Ферма и Гюйгенса, и методе K-средних. Ключевым этапом работы в обоих случаях является построение обобщенной диаграммы Вороного порядка k, каждая ячейка которой при фиксированном наборе из n центроидов включает в себя точки, расположенные ближе к некоторым k центроидам, чем к оставшимся n-k. При этом, в отличие от классической диаграммы Вороного, здесь ячейки могут пересекаться. Проведены вычислительные эксперименты, выполнены обсуждение и интерпретация их результатов.
Ключевые слова:
многократное покрытие множества, многократная упаковка кругов, неевклидова метрика, вычислительный алгоритм, оптико-геометрический подход, диаграмма Вороного, численный эксперимент

Название: Математическая модель и программная система для решения задачи размещения логистических объектов
Автор: Анна Ананьевна Лемперт
Соавторы:
Лемперт А.А., Казаков А.Л., Бухаров Д.С.
Аннотация:
В работе исследуется задача о размещении логистических объектов с одновременной сегментацией логистических зон в случае, когда логистические объекты могут располагаться в любой точке рассматриваемой области (непрерывная постановка). При этом предполагается, что в точках расположения потребителей число последних, вообще говоря, различно. Для данной задачи строится математическая модель в виде задачи вариационного исчисления специального вида, предложен численный метод построения решения на основе оптико-геометрического подхода. С использованием разработанных модели и метода решены задачи оптимизации инфраструктуры г. Саянска Иркутской области.
Ключевые слова:
вариационное исчисление, региональная логистика, оптимизация, численные методы

Название: Метод слабого улучшения для дискретной управляемой системы с сетевой структурой
Автор: Анна Ананьевна Лемперт
Соавторы:
В.А. Батурин, А.А. Лемперт
Аннотация:
Работа посвящена построению приближенных методов решения дискретных
задач оптимального управления с сетевой структурой, использующих
достаточные условия оптимальности В.Ф.~Кротова.
Ключевые слова:
дискретная управляемая система, сетевая структура, метод улучшения управления