Все выпуски

Рассматривается выпуклая задача оптимального управления для параболического уравнения со строго равномерно выпуклым целевым функционалом, с граничным управлением и с распределенными поточечными фазовыми ограничениями типа равенства и неравенства. Образы задающих поточечные фазовые ограничения операторов вкладываются в лебегово пространство суммируемых с $s$-й степенью функций при $s\in(1,2)$. В свою очередь, граничное управление принадлежит лебегову пространству с показателем суммируемости $r\in (2,+\infty)$. Основными результатами работы в рассматриваемой задаче оптимального управления с поточечными фазовыми ограничениями являются регуляризованные, или, другими словами, устойчивые к ошибкам исходных данных, секвенциальные принцип Лагранжа в недифференциальной форме и поточечный принцип максимума Понтрягина.

A convex optimal control problem is considered for a parabolic equation with a strictly uniformly convex cost functional, with boundary control and distributed pointwise state constraints of equality and inequality type. The images of the operators that define pointwise state constraints are embedded into the Lebesgue space of integrable with $s$-th degree functions for $s\in(1,2)$. In turn, the boundary control belongs to Lebesgue space with summability index $r\in (2,+\infty)$. The main results of this work in the considered optimal control problem with pointwise state constraints are the two stable, with respect to perturbation of input data, sequential or, in other words, regularized principles: Lagrange principle in nondifferential form and Pontryagin maximum principle.

Для задачи оптимального управления системой обыкновенных дифференциальных уравнений с поточечным фазовым ограничением типа равенства и конечным числом функциональных ограничений типа равенства и неравенства формулируется устойчивый секвенциальный, или, другими словами, регуляризованный, принцип максимума Понтрягина в итерационной форме. Его главное отличие от классического принципа максимума Понтрягина заключается в том, что он, во-первых, формулируется в терминах минимизирующих последовательностей, во-вторых, имеет форму итерационного процесса в пространстве двойственных переменных и, наконец, в-третьих, устойчиво к ошибкам исходных данных оптимизационной задачи порождает в ней минимизирующее приближенное решение в смысле Дж. Варги, т.е. представляет собою регуляризирующий алгоритм. Доказательство регуляризованного принципа максимума Понтрягина в итерационной форме опирается на методы двойственной регуляризации и итеративной двойственной регуляризации.

The stable sequential Pontryagin maximum principle or, in other words, the regularized Pontryagin maximum principle in iterative form is formulated for the optimal control problem of a system of ordinary differential equations with pointwise phase equality constraint and a finite number of functional equality and inequality constraints. The main difference between it and the classical Pontryagin maximum principle is that, firstly, it is formulated in terms of minimizing sequences, secondly, the iterative process occurs in dual space and, thirdly, it is resistant to errors of raw data and gives a minimizing approximate solution in the sense of J. Warga. So it is a regularizing algorithm. The proof of the regularized Pontryagin maximum principle in iterative form is based on the methods of dual regularization and iterative dual regularization.

Для задачи оптимального управления линейным параболическим уравнением с распределенным, начальным и граничным управлениями и с операторным полуфазовым ограничением типа равенства формулируется устойчивый секвенциальный, или, другими словами, регуляризованный, принцип максимума Понтрягина в итерационной форме. Его главное отличие от классического принципа максимума Понтрягина заключается в том, что он, во-первых, формулируется в терминах минимизирующих последовательностей, во-вторых, имеет форму итерационного процесса в пространстве двойственных переменных и, наконец, в-третьих, устойчиво к ошибкам исходных данных оптимизационной задачи порождает в ней минимизирующее приближенное решение в смысле Дж. Варги, т.е. представляет собой регуляризирующий алгоритм. Доказательство регуляризованного принципа максимума Понтрягина в итерационной форме опирается на методы двойственной регуляризации и итеративной двойственной регуляризации. Приводятся результаты модельных расчетов при решении конкретной задачи оптимального управления, иллюстрирующих работу алгоритма, основанного на регляризованном итерационном принципе максимума Понтрягина. В качестве конкретной оптимизационной задачи рассмотрена задача поиска минимальной по норме тройки управлений при операторном ограничении-равенстве в финальный момент времени, или, другими словами, обратная задача финального наблюдения по поиску ее нормального решения.

The stable sequential Pontryagin maximum principle or, in other words, the regularized Pontryagin maximum principle in iterative form is formulated for the optimal control problem of a linear parabolic equation with distributed, initial and boundary controls and operator semiphase equality constraint. The main difference between it and the classical Pontryagin maximum principle is that, firstly, it is formulated in terms of minimizing sequences, secondly, the iterative process occurs in dual space, and thirdly, it is resistant to error of raw data and gives a minimizing approximate solution in the sense of J. Warga. So it is a regularizing algorithm. The proof of the regularized Pontryagin maximum principle in iterative form is based on the dual regularization methods and iterative dual regularization. The results of model calculations of the concrete optimal control problem illustrating the work of the algorithm based on the regularized iterative Pontryagin maximum principle are presented. The problem of finding a control triple with minimal norm under a given equality constraint at the final instant of time or, in other words, the inverse final observation problem of finding a normal solution is used as a concrete model optimal control problem.

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

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

The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.

The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.

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

We consider a problem of sequential traversal of megalopolises (nonempty finite sets) with travel cost functions depending on the set of pending tasks and precedence constraints. Its formulation is aimed at engineering problems in fission power generation connected with minimizing the exposure of staff to radiation and in machine engineering (routing of a CNC sheet cutting machine's tool). This discrete optimization problem is assumed to be sufficiently large-scale to necessitate the use of heuristics. We consider a procedure of local improvement for heuristics through a successive application of optimizing multi-inserts-finite disjoint sets of inserts. Each insert is assumed to be optimized by means of a broadly understood dynamic programming procedure. We show that in an “additive” routing problem of this kind (with precedence constraints and complex travel cost functions) the result's improvements are also aggregated additively. The proposed construction admits a parallel implementation for multiprocessor systems; in this case, the inserts are distributed to computational nodes and formed in an independent way.

В статье рассматривается общий случай маршрутной задачи дискретной оптимизации, осложненной условиями предшествования; изучается влияние условий предшествования на вычислительную сложность решений таких задач методом динамического программирования. Особенность применяемого метода динамического программирования заключается в его «экономичности»: подзадачи, не соблюдающие условия предшествования и, следовательно, не участвующие в оптимальном решении, не рассматриваются, что позволяет сберечь и вычислительную мощность, и память.

Этот метод c 2004 года используется А.Г. Ченцовым и его соавторами, но степень экономии ресурсов исследовалось мало. Мы предлагаем подход к решению этой проблемы, основанный на комбинаторном анализе числа подзадач, существенных в смысле условий предшествования. Применяя известные комбинаторные правила сложения и произведения, мы получили результат для важных частных случаев условий предшествования: а) «независимые» наборы условий предшествования; б) «цепь» условий предшествования - когда условия задают линейный порядок; в) случай, когда в графе предшествования нет неориентированных циклов, и исходящая степень любой вершины не превышает единицы. Последний случай представляет собой условия предшествования, встречающихся в практической задаче маршрутизации движений инструмента в машинах листовой резки и соответствует требованию вырезать внутренний контур прежде внешнего.

В связи с более сложной структурой случая в) по сравнению с остальными для него вместо аналитической формулы представлен алгоритм; алгоритм реализован на языке C++, зависимость его вычислительной сложности от числа связанных условиями предшествования объектов имеет не более чем квадратичный порядок. В дальнейшем мы предполагаем расширить область применения нашего подхода до более общих вариантов условий предшествования. Отметим также, что наш подход не зависит от критерия оптимальности, соответственно, может применяться для анализа сложности решения методом динамического программирования в произвольных маршрутных задачах с условиями предшествования.

We consider the general case of Precedence Constrained TSP (or a less general case of Sequential Ordering Problem) solved with a special kind of dynamic programming method that uses precedence constraints to significantly reduce the number of subproblems that must be solved to find the optimal solution of the original problem. Our aim is to quantify this reduction, which is necessary to clarify the influence of precedence constraints on computational complexity of dynamic programming solutions of such problems. This variety of the method of dynamic programming has been developed by A.G. Chentsov and his co-authors since 2004 but there was only one attempt at examining the influence of precedence constraints on complexity, which only described the influence of a single precedence constraint in the form of an “address pair” (sender, receiver).

Our approach to studying the complexity of this method is essentially the combinatorial analysis of the number of subproblems that are feasible in the sense of abiding by precedence constraints. Using the well-known combinatorial principles, the rule of product and the rule of sum, we established the estimates of complexity reduction for the following cases: a) “independent” sets of precedence constraints; b) “chains” of precedence constraints, when the precedence constraints define a linear ordering on the objects bound by them; c) precedence constraints expressed by an acyclic directed graph with outdegree (the number of receivers per sender) at most one. The latter case of precedence constraints is the one encountered in real-life problems of optimizing the route of the cutter in various machines used to cut sheet material. Since this is the most complex case of the three analyzed, instead of an analytic formula, we had to develop an algorithm (which we implemented in C++) to quantify the reduction; the computational complexity of the algorithm is less than quadratic with respect to the number of objects constrained by the precedence constraints. We intend to develop our approach to treat other cases of precedence constraints, eventually reaching the general case. We would also like to note that our method is optimization criterion-agnostic and thus applicable to many kinds of TSP, as long as they are precedence constrained and solvable by dynamic programming; in fact, our approach may be used to analyze the complexity of the dynamic programming method solution of any discrete optimization problem that deals with ordering subject to precedence constraints.

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

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

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

Основное внимание в работе уделяется построению оптимизирующих вставок в усложненных условиях: требуется редуцировать фрагмент условий предшествования и трансформировать соответствующие функции стоимости; в последнем случае важно сохранить в надлежащей форме зависимость от списка заданий. Оба упомянутых обстоятельства учитываются при построении процедуры, имеющей смысл алгоритма на функциональном уровне.

The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation.

The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.

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

A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.

Рассматривается задача маршрутизации с условиями предшествования и функциями стоимости, зависящими от списка заданий, что отвечает потребностям инженерных приложений. В частности, упомянутые особенности имеются в постановках некоторых задач, возникающих в атомной энергетике и машиностроении. Исследуются вопросы, связанные с последовательным обходом мегаполисов и выполнением, при их посещении, некоторых (внутренних) работ. Предлагается процедура локального улучшения эвристических решений для задач ощутимой размерности, использующая вставки на основе динамического программирования. Последнее реализуется в виде варианта, не предусматривающего (при наличии условий предшествования) построение «полного» массива значений функции Беллмана. На этапе поиска локализации вставки предполагается ограничиваться вариантом беллмановской процедуры, доставляющей экстремум (локального) критерия без построения соответствующего решения в виде пары «маршрут-трасса». Более полная и более затратная в смысле ресурсов памяти процедура, включающая нахождение упомянутого (локально оптимального) решения, планируется после выбора локализации вставки.

The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.