Все выпуски

Рассматривается задача о назначении спектра показателей Ляпунова линейной управляемой системы с дискретным временем $$x(m+1)=A(m)x(m)+B(m)u(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n},\ u\in\mathbb R^{k}, \qquad (1)$$ посредством линейной по фазовым переменным обратной связи $u(m)=U(m)x(m)$ в малой окрестности спектра показателей свободной системы $$x(m+1)=A(m)x(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n}. \qquad (2)$$ Дополнительно требуется, чтобы норма матрицы обратной связи $U(\cdot)$ удовлетворяла липшицевой оценке по отношению к требуемому смещению показателей. Это свойство называется пропорциональной локальной управляемостью полного спектра показателей Ляпунова замкнутой системы $$x(m+1)=\bigl(A(m)+B(m)U(m)\bigr)x(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n}. \qquad (3)$$ Построен пример, показывающий, что найденные ранее достаточные условия пропорциональной локальной управляемости полного спектра показателей Ляпунова системы (3) (равномерная полная управляемость системы (1) и устойчивость показателей Ляпунова свободной системы (2)) не являются необходимыми.

We consider a problem of assigning the Lyapunov spectrum for a linear control discrete-time system $$x(m+1)=A(m)x(m)+B(m)u(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n},\ u\in\mathbb R^{k}, \qquad (1)$$ in a small neighborhood of the Lyapunov spectrum of the free system $$x(m+1)=A(m)x(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n},\qquad (2) $$ by means of linear feedback $u(m)=U(m)x(m)$. We assume that the norm of the feedback matrix $U(\cdot)$ satisfies the Lipschitz estimate with respect to the required shift of the Lyapunov spectrum. This property is called proportional local assignability of the Lyapunov spectrum of the closed-loop system $$x(m+1)=\bigl(A(m)+B(m)U(m)\bigr)x(m),\quad m\in\mathbb N,\ x\in\mathbb R^{n}. \qquad (3)$$ We previously proved that uniform complete controllability of system (1) and stability of the Lyapunov spectrum of free system (2) are sufficient conditions for proportional local assignability of the Lyapunov spectrum of closed-loop system (3). In this paper we give an example demonstrating that these conditions are not necessary.

Построена метрика в пространстве clos(Rⁿ) всех непустых замкнутых (необязательно ограниченных) подмножеств Rⁿ. Сходимость последовательности множеств в этой метрике оказывается равносильной сходимости в метрике Хаусдорфа последовательности пересечений этих множеств с центрированными в нуле шарами любого положительного радиуса, дополненных соответствующими сферами. В этой метрике доказана полнота пространства clos(Rⁿ) и замкнутость подпространства всех непустых замкнутых выпуклых подмножеств Rⁿ. Получены условия равносильности сходимости по предложенной метрике и сходимости по метрикам Хаусдорфа и Хаусдорфа–Бебутова. Полученные результаты могут применяться в задачах управления, теории дифференциальных включений.

In the work, there is presented a new metric in the space clos(Rⁿ) of all nonempty closed (not necessarily bounded) subsets of Rⁿ. The convergence of sets in this metric is equivalent to convergence in the Hausdorff metric of the intersections of the given sets with the balls of any positive radius centered at zero united then with the corresponding spheres. It is proved that, with respect to the metric considered, the space clos(Rⁿ) is complete, and its subspace of nonempty closed convex subsets of Rⁿ is closed. There are also derived the conditions that guarantee the equivalence of convergence in this metric to convergence in the Hausdorff metric, and to convergence in the Hausdorff–Bebutov metric. The results obtained can be applied to studying control problems and differential inclusions.

Рассматривается линейная управляемая система с неполной обратной связью с дискретным временем

x(t+1)=A(t)x(t)+B(t)u(t),   y(t)=C*(t)x(t),   u(t)=U(t)y(t),   t∈Z.

Исследуется задача управления асимптотическим поведением замкнутой системы

x(t+1)=(A(t)+B(t)U(t)C*(t))x(t), x∈Kⁿ.                (1)

Здесь K=C или K=R. Для такой системы вводится понятие согласованности. Это понятие является обобщением понятия полной управляемости на системы с неполной обратной связью. Исследовано свойство согласованности системы (1), получены новые необходимые условия и достаточные условия согласованности системы (1), в том числе в стационарном случае. Для стационарной системы вида (1) исследуется задача о глобальном управлении спектром собственных значений, которая заключается в приведении характеристического многочлена матрицы стационарной системы (1) с помощью стационарного управления U к произвольному наперед заданному полиному. Для системы (1) с постоянными коэффициентами специального вида, когда матрица A имеет форму Хессенберга, а в матрицах B и C все строки соответственно до p-й и после p-й (не включая p) равны нулю, свойство согласованности является достаточным условием глобальной управляемости спектра собственных значений. Ранее было доказано, что обратное утверждение верно для n<4 и неверно для n>5. В настоящей работе доказано, что обратное утверждение верно для n=4.

We consider a discrete-time linear control system with an incomplete feedback

x(t+1)=A(t)x(t)+B(t)u(t),   y(t)=C*(t)x(t),   u(t)=U(t)y(t),   t∈Z.

We study the problem of control over the asymptotic behavior of the closed-loop system

x(t+1)=(A(t)+B(t)U(t)C*(t))x(t), x∈Kⁿ.               (1)

where K=C or K=R. For the above system, we introduce the concept of consistency, which is a generalization of the concept of complete controllability onto systems with an incomplete feedback. The focus is on the consistency property of the system (1). We have obtained new necessary conditions and sufficient conditions for the consistency of the above system including the case when the system is time-invariant. For the time-invariant system (1), we study the problem of arbitrary placement of eigenvalue spectrum. The objective is to reduce a characteristic polynomial of a matrix of the stationary system (1) to any prescribed polynomial by means of the time-invariant control U. For the system (1) with constant coefficients of the special form where the matrix A is Hessenberg, the rows of the matrix B before the p-th and the rows of the matrix C after the p-th are equal to zero (not including p), the property of consistency is the sufficient condition for arbitrary placement of eigenvalue spectrum. It has been proved that the converse proposition is true for n<4 and false for n>5. In present paper we prove that the converse proposition is true for n=4.

В работе рассматривается задача оптимального управления одномерным процессом, заданным стохастическим дифференциальным уравнением, в котором управление воздействует как на коэффициент сноса, так и на коэффициент диффузии, при этом диффузионная составляющая линейна по управлению $$dx(t) = b(t,x(t),u(t))dt +\sigma(t,x(t))u(t)dW(t),\qquad x(0) = x_0.$$ Здесь $x(t)$ - фазовая координата, $u(t)$ - управляющая функция, $W(t)$ - винеровский процесс. Доказана теорема, которая предоставляет структуру решения рассматриваемого уравнения в виде суперпозиции функций $x(t)=Φ(t,u(t)W(t)+y(t))$, в котором $Φ(t,v)$ - известная функция, полностью определяющаяся коэффициентом $σ(t,x)$, и не зависит от управления, а $y(t)$ - решение потраекторно-детерминированного дифференциального уравнения с мерой вида

$$dy(t) = B(t,y(t),u(t))dt - W(t)du(t).$$

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

We consider an optimal control problem for a one-dimensional process driven by stochastic differential equation, which has both drift and diffusion coefficients controlled, diffusion being linear in control

$$dx(t) = b(t,x(t),u(t))dt +\sigma(t,x(t))u(t)dW(t), \qquad x(0) = x_0,$$

where $x(t)$ is the state variable, $u(t)$ is the control variable and $W(t)$ is the Wiener process. We prove a theorem which gives a structure of solution for the considered differential equation as a superposition of functions $x(t)=Φ(t,u(t)W(t)+y(t))$, where $Φ(t,v)$ is the known function, which is completely determined by the diffusion coefficient σ(t,x) and is independent of control, and $y(t)$ is the solution to the pathwise-deterministic measure-driven differential equation

$$dy(t) = B(t,y(t),u(t))dt - W(t)du(t).$$

The revealed structure of the solution enables us to consider a new pathwise-deterministic impulsive optimal control problem with the state variable $y(t)$ which is equivalent to the original stochastic optimal control problem. Pathwise problems may have anticipative solutions, so we propose a method that makes it possible to build nonanticipative optimal solutions. The basic idea of the method is to modify cost functional in new pathwise problem with special integral term, which guarantees nonanticipativity of solutions.

Рассматривается линейная управляемая система с линейной неполной обратной связью с дискретным временем $$x(t+1)=Ax(t)+Bu(t), \quad y(t)=C^*x(t), \quad u(t)=Uy(t),$$ $$t\in\mathbb{Z},\quad (x,u,y)\in\mathbb{K}^n\times\mathbb{K}^m\times\mathbb{K}^k.$$

Здесь $\mathbb K=\mathbb C$ или $\mathbb K=\mathbb R$. Для замкнутой системы $$x(t+1)=(A+BUC^*)x(t), \quad x\in\mathbb K^n, \qquad(1)$$

вводится понятие согласованности. Это понятие является обобщением понятия полной управляемости на системы с неполной обратной связью. Исследуется свойство согласованности системы $(1)$ в связи с задачей управления спектром собственных значений, которая заключается в приведении характеристического многочлена матрицы стационарной системы $(1)$ с помощью стационарного управления $U$ к произвольному наперед заданному полиному. Для системы $(1)$ специального вида, когда матрица $A$ имеет форму Хессенберга, а в матрицах $B$ и $C$ все строки соответственно до $p$-й и после $p$-й (не включая $p$) равны нулю, свойство согласованности является достаточным условием глобальной управляемости спектра собственных значений. В предыдущих работах было доказано, что обратное утверждение верно для $n<5$ и неверно для $n>5$. В настоящей работе открытый вопрос для $n=5$ разрешен. Доказано, что при $n=5$ для системы с коэффициентами специального вида свойство согласованности является необходимым условием глобальной управляемости спектра собственных значений. Доказательство производится перебором всевозможных допустимых значений размерностей $m,k,p$. Свойство согласованности эквивалентно свойству полной управляемости «большой системы» размерности $n^2$. Для доказательства строится большая система, строится матрица управляемости $K$ этой системы размерности $n^2\times n^2mk$. Доказывается, что матрица $K$ имеет ненулевой минор порядка $n^2=25$. Для вычисления определителей больших порядков используется система Maple 15.

We consider a discrete-time linear control system with an incomplete feedback $$x(t+1)=Ax(t)+Bu(t), \quad y(t)=C^*x(t), \quad u(t)=Uy(t),$$ $$t\in\mathbb{Z},\quad (x,u,y)\in\mathbb{K}^n\times\mathbb{K}^m\times\mathbb{K}^k,$$

where $\mathbb K=\mathbb C$ or $\mathbb K=\mathbb R$. We introduce the concept of consistency for the closed-loop system

$$x(t+1)=(A+BUC^*)x(t), \quad x\in\mathbb K^n. \qquad(1)$$

This concept is a generalization of the concept of complete controllability to systems with an incomplete feedback. We study the consistency of the system $(1)$ in connection with the problem of arbitrary placement of eigenvalue spectrum which is to bring a characteristic polynomial of a matrix of the system $(1)$ to any prescribed polynomial by means of the time-invariant control $U$. For the system $(1)$ of the special form where the matrix $A$ is Hessenberg and the rows of the matrix $B$ before the $p$-th and the rows of the matrix $C$ after the $p$-th (not including $p$) are equal to zero, the property of consistency is the sufficient condition for arbitrary placement of eigenvalue spectrum. In previous studies it has been proved that the converse is true for $n <5$ and false for $n> 5$. In this paper, an open question for $ n = 5 $ is resolved. For the system $(1)$ of the special form, it is proved that if $n = 5$ then the property of consistency is a necessary condition for the arbitrary placement of eigenvalue spectrum. The proof is carried out by direct searching of all possible valid values of dimensions $ m, k, p $. The property of consistency is equivalent to the property of complete controllability of a big system of dimension $n^2$. For the proof we construct the big system and the controllability matrix $K$ of this system of dimension $n^2\times n^2mk$. We show that the matrix $K$ has a nonzero minor of order $n^2 = 25$. We use Maple 15 to calculate the high-order determinants.

Понятие равномерной полной управляемости линейной системы, введенное Р. Калманом, играет ключевую роль в задачах управления асимптотическими характеристиками линейных систем управления, замкнутых по принципу линейной обратной связи. Е.Л. Тонков установил необходимое и достаточное условие равномерной полной управляемости для систем с кусочно-непрерывными и ограниченными коэффициентами. Критерий Тонкова можно положить в основу определения равномерной полной управляемости. Если условия на коэффициенты системы ослабить, то определения Калмана и Тонкова перестают совпадать. Здесь установлены необходимые условия и достаточные условия равномерной полной управляемости по Калману и по Тонкову для систем с измеримыми, локально суммируемыми коэффициентами. Введено определение равномерной полной управляемости, которое обобщает определение Тонкова и совпадает с определением Калмана, если матрица $B(\cdot)$ ограничена. Доказаны некоторые известные результаты об управляемости линейных систем, в которых можно ослабить требования на коэффициенты. Доказано, что если линейная управляемая система $\dot x=A(t)x+B(t)u$, $x\in\mathbb{R}^n$, $u\in\mathbb{R}^m$, с измеримой ограниченной матрицей $B(\cdot)$ равномерно вполне управляема в смысле Калмана, то для любой измеримой и интегрально ограниченной $m\times n$-матричной функции $Q(\cdot)$ система $\dot x=(A(t)+B(t)Q(t))x+B(t)u$ равномерно вполне управляема по Калману.

The notion of uniform complete controllability of linear system introduced by R. Kalman plays a key role in problems of control of asymptotic properties for linear systems closed by linear feedback control. E.L. Tonkov has found a necessary and sufficient condition of uniform complete controllability for systems with piecewise continuous and bounded coefficients. The Tonkov criterion can be considered as the definition of uniform complete controllability. If the coefficients of the system satisfy weak conditions then the definitions of Kalman and Tonkov are not coincide. We obtain necessary conditions and sufficient conditions for uniform complete controllability in the sense of Kalman and Tonkov for systems with measurable and locally integrable coefficients. We introduce a new definition of uniform complete controllability that extends the definition of Tonkov and coincides with the definition of Kalman providing the matrix $B(\cdot)$ is bounded. We prove some known results on the controllability of linear systems that allow the weakening of the requirements on the coefficients. We prove that if a linear control system $\dot x=A(t)x+B(t)u$, $x\in\mathbb{R}^n$, $u\in\mathbb{R}^m$, with measurable and bounded matrix $B(\cdot)$ is uniformly completely controllable in the sense of Kalman then for any measurable and integrally bounded $m\times n$-matrix function $Q(\cdot)$ the system $\dot x=(A(t)+B(t)Q(t))x+B(t)u$ is also uniformly completely controllable in the sense of Kalman.

Рассматривается линейная нестационарная управляемая система с наблюдателем с локально интегрируемыми и интегрально ограниченными коэффициентами $$\dot x =A(t)x+ B(t)u, \quad x\in\mathbb{R}^n,\quad u\in\mathbb{R}^m,\quad t\geqslant 0, \qquad (1)$$ $$y =C^*(t)x, \quad y\in\mathbb{R}^p.\qquad (2)$$ Исследуется задача управления асимптотическими инвариантами системы, замкнутой посредством линейной нестационарной динамической обратной связи по выходу. Метод исследования, представленный в работе, базируется на построении системы асимптотической оценки состояния системы (1), (2), введенной Р. Калманом. Для решения задачи используется обобщение понятия равномерной полной управляемости по Калману, предложенное Е.Л. Тонковым для систем с коэффициентами из более широких функциональных классов. Дано определение равномерной полной наблюдаемости (в смысле Тонкова) для системы (1), (2). Для $n=2$ доказано, что свойство равномерной полной управляемости и равномерной полной наблюдаемости системы (1), (2) (в смысле Тонкова) с локально интегрируемыми и интегрально ограниченными коэффициентами является достаточным условием глобальной управляемости верхнего особого показателя Боля, а также характеристических показателей Ляпунова системы, замкнутой посредством линейной динамической обратной связи по выходу. Для доказательства используются установленные ранее результаты о равномерной глобальной достижимости двумерной системы (1), замкнутой линейной нестационарной статической обратной связью по состоянию, при условии равномерной полной управляемости (в смысле Тонкова) открытой системы (1).

We consider a linear time-varying control system with an observer with locally integrable and integrally bounded coefficients $$\dot x =A(t)x+ B(t)u, \quad x\in\mathbb{R}^n,\quad u\in\mathbb{R}^m,\quad t\geqslant 0, \qquad (1)$$ $$y =C^*(t)x, \quad y\in\mathbb{R}^p. \qquad(2)$$ We study a problem of control over asymptotic invariants for the system closed by linear dynamic output feedback with time-varying coefficients. The research method presented in the paper is based on the construction of a system of asymptotic estimation for the state of the system (1), (2), introduced by R. Kalman. For solving the problem, we use the extension of the notion of uniform complete controllability (in the sense of Kalman) proposed by E.L. Tonkov for systems with coefficients from wider functional classes. The notion of uniform complete observability (in the sense of Tonkov) is given for the system (1), (2). For $n=2$, it is proved that uniform complete controllability and uniform complete observability (in the sense of Tonkov) of the system (1), (2) with locally integrable and integrally bounded coefficients are sufficient for arbitrary assignability of the upper Bohl exponent and of the complete spectrum of the Lyapunov exponents for the system closed-loop by linear dynamic output feedback. For the proof, we use the previously established results on uniform global attainability of a two-dimensional system (1), closed by linear time-varying static state feedback, under the condition of uniform complete controllability (in the sense of Tonkov) of the open-loop system (1).

Доказано, что линейная управляемая система $$ \dot x=A(t)x+B(t)u, \quad t\in\mathbb{R}, \quad x\in\mathbb{R}^n, \quad u\in\mathbb{R}^m, \qquad\qquad (1) $$ с коэффициентами в форме Хессенберга при достаточно широких условиях на коэффициенты обладает свойством равномерной полной управляемости в смысле Калмана. Показана существенность для некоторых полученных достаточных условий. Установлены следствия для квазидифференциальных уравнений. Исследуется задача о глобальном управлении асимптотическими инвариантами системы $$ \dot x=(A(t)+B(t)U)x, \quad t\in\mathbb{R}, \quad x\in\mathbb{R}^n, \qquad \qquad \qquad \qquad (2) $$ полученной замыканием системы $(1)$ обратной связью $u=Ux$. В известных результатах С.Н. Поповой ослабляются условия на коэффициенты. Для системы $(2)$ с коэффициентами в форме Хессенберга, с помощью результатов С.Н. Поповой, получены достаточные условия глобальной скаляризуемости и глобальной управляемости показателей Ляпунова, а в случае когда $A(\cdot)$ и $B(\cdot)$ - $\omega$-периодические и достаточные условия глобальной ляпуновской приводимости.

We prove that a linear control system $$ \dot x=A(t)x+B(t)u, \quad t\in\mathbb{R}, \quad x\in\mathbb{R}^n, \quad u\in\mathbb{R}^m, \qquad \qquad (1) $$ with matrix coefficients of the Hessenberg form is uniformly completely controllable in the sense of Kalman under rather weak conditions imposed on coefficients. It is shown that some obtained sufficient conditions are essential. Corollaries are derived for quasi-differential equations. We construct feedback control $u=Ux$ for the system $(1)$ and study the problem of global control over asymptotic invariants of the closed-loop system $$ \dot x=(A(t)+B(t)U)x, \quad t\in\mathbb{R}, \quad x\in\mathbb{R}^n. \qquad \qquad \qquad \qquad (2) $$ The conditions on coefficients are weakened in the known results of S.N. Popova. For the system $(2)$ with matrix coefficients of the Hessenberg form, the obtained results and the results of S.N. Popova are used to receive sufficient conditions for global reducibility to systems of scalar type and for global control over Lyapunov exponents and moreover, for global Lyapunov reducibility in the case of periodic $A(\cdot)$ and $B(\cdot)$.

Рассматривается линейная нестационарная управляемая система с локально интегрируемыми и интегрально ограниченными коэффициентами $$ \dot x =A(t)x+ B(t)u, \quad x\in\mathbb{R}^n,\quad u\in\mathbb{R}^m,\quad t\geqslant 0. \qquad\qquad (1)$$ Управление в системе $(1)$ строится по принципу линейной обратной связи $u=U(t)x$ с измеримой и ограниченной матричной функцией $U(t),$ $t\geqslant 0.$ Для замкнутой системы $$\dot x =(A(t)+B(t)U(t))x, \quad x\in\mathbb{R}^n, \quad t\geqslant 0, \qquad\qquad (2)$$ исследуется вопрос об условиях ее равномерной глобальной достижимости. Наличие последнего свойства у системы $(2)$ означает существование такой матричной функции $U(t),$ $t\geqslant 0,$ которая обеспечивает для матрицы Коши $X_U(t,s)$ этой системы выполнение равенств $X_U((k+1)T,kT)=H_k$ при фиксированном $T>0$ и произвольных $k\in\mathbb N,$ $\det H_k>0.$ Представленная задача решается в предположении равномерной полной управляемости системы $(1),$ соответствующей замкнутой системе $(2),$ т.е. при условии существования таких $\sigma>0$ и $\gamma>0,$ что при любых начальном моменте времени $t_0\geqslant 0$ и начальном состоянии $x(t_0)=x_0\in \mathbb{R}^n$ системы (1) на отрезке $[t_0,t_0+\sigma]$ найдется измеримое и ограниченное векторное управление $u=u(t),$ $\|u(t)\|\leqslant\gamma\|x_0\|,$ $t\in[t_0,t_0+\sigma],$ переводящее вектор начального состояния этой системы в ноль на данном отрезке. Доказано, что в двумерном случае, т.е. при $n=2,$ свойство равномерной полной управляемости системы $(1)$ является достаточным условием равномерной глобальной достижимости соответствующей системы $(2).$

We consider a linear time-varying control system with locally integrable and integrally bounded coefficients $$\dot x =A(t)x+ B(t)u, \quad x\in\mathbb{R}^n,\quad u\in\mathbb{R}^m,\quad t\geqslant 0. \qquad\qquad (1) $$ We construct control of the system $(1)$ as a linear feedback $u=U(t)x$ with measurable and bounded function $U(t),$ $t\geqslant 0.$ For the closed-loop system $$\dot x =(A(t)+B(t)U(t))x, \quad x\in\mathbb{R}^n, \quad t\geqslant 0, \qquad \qquad (2)$$ we study a question about the conditions for its uniform global attainability. The last property of the system $(2)$ means existence of a matrix $U(t),$ $t\geqslant 0,$ that ensure equalities $X_U((k+1)T,kT)=H_k$ for the state-transition matrix $X_U(t,s)$ of the system $(2)$ with fixed $T>0$ and arbitrary $k\in\mathbb N,$ $\det H_k>0.$ The problem is solved under the assumption of uniform complete controllability of the system $(1),$ corresponding to the closed-loop system $(2),$ i.e. assuming the existence of such $\sigma>0$ and $\gamma>0,$ that for any initial time $t_0\geqslant 0$ and initial condition $x(t_0)=x_0\in \mathbb{R}^n$ of the system $(1)$ on the segment $[t_0,t_0+\sigma]$ there exists a measurable and bounded vector control $u=u(t),$ $\|u(t)\|\leqslant\gamma\|x_0\|,$ $t\in[t_0,t_0+\sigma],$ that transforms a vector of the initial state of the system into zero on that segment. It is proved that in two-dimensional case, i.e. when $n=2,$ the property of uniform complete controllability of the system $(1)$ is a sufficient condition of uniform global attainability of the corresponding system $(2).$

В статье рассматривается экстремальная задача маршрутизации с ограничениями. В общей формулировке предполагается, что объектами посещения являются любые непустые конечные множества — мегаполисы. Основной прикладной задачей, рассматриваемой в данном исследовании, является задача оптимизации траектории движения инструмента для станков листовой резки с ЧПУ, известная как проблема пути резания. Эта проблема возникает на этапе разработки управляющих программ для станков с ЧПУ. Возможны и другие приложения. В частности, результаты исследования могут быть использованы в задаче минимизация дозы облучения при демонтаже системы радиационно-опасных элементов после аварий на АЭС и в транспортных проблемах. В качестве ограничений исследуются ограничения предшествования. Они могут быть использованы для уменьшения вычислительной сложности. В качестве основного метода исследования использовалось широко понимаемое динамическое программирование. Предлагаемая реализация метода учитывает ограничения предшествования и зависимость целевых функций от списка задач. Последняя относится к классу очень сложных состояний, которые определяют допустимость маршрута на каждом шаге маршрутизации, в зависимости от уже выполненных или, наоборот, еще не завершенных задач. Применительно к задаче резки зависимость целевой функции от списка задач позволяет уменьшать термические деформации материала при резке. В работе математическая формализация экстремальной задачи маршрутизации с дополнительными ограничениями, описание метода и полученный с его помощью точный алгоритм. Оптимизации подлежат порядок выполнения задач, конкретная траектория процесса, и его начальная точка.

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.