DOI: 10.22184/2499-9407.2026.44.3.30.41
В первой части статьи (см. [1]) приведена постановка и алгоритм решения задачи маршрутизации с элементами декомпозиции. В настоящей работе излагаются тео­ретические построения, из которых, в частности, следует оптимальность данного алгоритма как инструмента для построения композиционного решения, ориентированного на проблему резки зонами на машинах с ЧПУ. Мы рассматриваем здесь простейший вариант, когда все семейство заданий разбито на сумму двух кластеров. Сами задания связаны в конечном итоге с резкой контуров деталей, но реализуются всякий раз в схеме с дискретизацией, что делается в связи с потребностями в компьютерном моделировании. Таким образом, речь идет о последовательном посещении непустых конечных множеств (мегаполисов). Предлагаемая процедура ориентирована на решение диапазонных (в смысле размерности) задач. Это подразумевает, что размерность совокупной задачи является ощутимой, но каждая из частичных задач имеет уже умеренную размерность, что позволяет привлечь для решения аппарат широко понимаемого динамического программирования (ДП) в реализации, восходящей к [2; 3]; имеются в виду процедуры, используемые при решении задачи коммивояжера (ЗК). В связи с исследованиями ЗК и задач типа ЗК отметим [4–8]. Общие конструкции на основе ДП см. в [9; 10]. В настоящем исследовании предлагается специальная схема стыковки частичных (предваряющей и финальной) задач, в рамках которой удается доказать оптимальность алгоритма [1, раздел 3] как процедуры поиска композиционных решений с приемлемым для практики быстродействием. Данная схема обсуждается в настоящей работе; в следующей (третьей) части статьи будут рассматриваться примеры ее применения. Мы используем обозначения и определения [1].