Научный архив: статьи

Исследуется задача последовательного обхода мегаполисов (непустых конечных множеств) в условиях декомпозиции: на множестве заданий указана система кластеров, очередность обслуживания которых задана. Каждый кластер определяет частичную задачу маршрутизации с условиями предшествования и функциями стоимости, допускающими зависимость от списка заданий. Постановка ориентирована на инженерные приложения, связанные с листовой резкой на машинах с ЧПУ; имеется в виду задача резки зонами, которые определяются технологическими требованиями. Построена процедура оптимизации композиционных решений, базирующаяся на раздельном применении широко понимаемого динамического программирования и специального правила, связывающего условия частичных задач посредством назначения терминальных компонентов аддитивных критериев, исходя из функций экстремума этих частичных задач. Построенный алгоритм реализован на многоядерной ПЭВМ; вычислительный эксперимент при решении задач ощутимой размерности (сотни мегаполисов) показал возможность решения за приемлемое для инженерной практики время.

Рассматриваются абстрактные задачи о достижимости с ограничениями асимптотического характера (ОАХ), в которых результат (аналог множества достижимости) определяется в виде множества притяжения (МП) в топологическом пространстве. Сами ОАХ порождаются при этом непустыми семействами подмножеств исходного множества обычных (доступных для реализации) решений. Среди этих семейств выделяются фильтры: семейство всех возможных МП получается добавлением пустого множества к аналогичному семейству МП, отвечающим каждое ОАХ, порождаемым фильтром; при этом ультрафильтрам всякий раз сопоставляется единственный элемент притяжения. Это позволяет установить ряд важных свойств семейства всех МП, порождаемых фильтрами. Так, в частности, установлено, что данное семейство замкнуто относительно конечных объединений, указаны условия, при которых конечное объединение фильтров порождает МП упомянутого семейства, указано семейство синглетонов, являющихся МП, порождаемыми фильтрами. Само же появление непустых неодноэлементных МП удается истолковать в терминах немаксимальности фильтра, порождающего ОАХ: непустые МП, не являющиеся синглетонами, непременно соответствуют ОАХ, порождаемыми фильтрами, не являющимися ультрафильтрами.

Рассматривается задача о последовательном обходе мегаполисов с условиями предшествования и функциями стоимости, допускающими зависимость от списка заданий. Предполагается, что все множество заданий разбито в сумму непустых подмножеств (групп); требуется последовательно решать частичные задачи о посещении мегаполисов в каждой из групп. Очередность посещения самих групп задана априори. Предполагается, что условия предшествования общей задачи локализуются в упомянутых группах. Постановка ориентирована на инженерную задачу управления инструментом при фигурной листовой резке деталей зонами на машинах с ЧПУ. В качестве основного метода используется динамическое программирование в условиях декомпозиции, когда оптимальные процедуры реализуются для каждой из частичных задач в отдельности, после чего осуществляется специальная склейка полученных решений. Тем самым решается вопрос о декомпозиции исходной «большой» задачи в систему частичных задач умеренной размерности. На основе теоретических конструкций построен работоспособный алгоритм, реализованный на ПЭВМ. Приведено решение модельных примеров.