Contiguity and Dynamic Programming

Abstract

Some aspects of the principle of optimality [1, p.83] are considered, and a modification is proposed for the derivation of the main functional equations of dynamic programming to demonstrate that those equations are valid also in the case of non-optimal remaining trajectories under certain contiguity condition that is defined and analyzed in the paper. Control systems with incomplete information or structural limitations on controls do not, in general, satisfy the contiguity condition. Control problems for such systems may have optimal solutions which, however, cannot be obtained by dynamic programming. This fact is shown on example of a widely used engineering system for which optimal trajectories have all its remaining parts non optimal and non contiguous to the optimal trajectories. The paper presents theoretical justification of dynamic programming for contiguous systems without the principle of optimality, and discussion of some problems important for applications.

Рассмотрены некоторые аспекты принципа оптимальности [1, с. 83] и предложена его модификация для вывода основных функциональных уравнений динамического программирования, чтобы показать, что эти уравнения справедливы также в случае неоптимальных остаточных траекторий при некотором условии смежности. Приведены определение и анализ этого условия. Системы управления с неполной информацией или структурными ограничениями управления не удовлетворяют условию смежности в общем случае. Задачи управления для таких систем могут иметь оптимальные решения, но их нельзя получить методом динамического программирования. Этот факт продемонстрирован на примере широко применяемой технической системы, для которой все остаточные части оптимальных траекторий не оптимальны и не смежны с оптимальными траекториями. Дано теоретическое обоснование динамического программирования для смежных систем без принципа оптимальности и рассмотрены некоторые важные прикладные задачи.

Розглянуто деякі аспекти принципу оптимальності [1, c.83] і запропоновано його модифікацію для виведення основних функціональних рівнянь динамічного програмування, щоб показати, що ці рівняння є справедливими також у випадку неоптимальних залишкових траєкторій за певною умовою суміжності. Наведено визначення та аналіз цієї умови. Системи управління з неповною інформацією або структурними обмеженнями управління не задовольняють умові суміжності у загальному випадку. Задачі управління для таких систем можуть мати оптимальні розв’язки, але їх не можна отримати методом динамічного програмування. Цей факт показано на прикладі технічної системи, що широко використовується, для якої всі залишкові частини оптимальних траєкторій не оптимальні та не суміжні з оптимальними траєкторіями. Дано теоретичне обґрунтування динамічного програмування для суміжних систем без принципу оптимальності та розглянуто деякі важливі прикладні задачі.