К алгоритмам динамического программирования при предположениях монотонности

Формулируется задача дискретного оптимального управления, не рассматривавшаяся ранее и возникающая при проектировании нефтегазосборных сетей. Для этой задачи устанавливаются четыре теоремы, чтобы можно было иметь процесс, оптимальный процесс и оптимальное значение. Необходимые и достаточные условия для этого даются в теореме 1. При этих условиях по теореме 1 получаются интервалы достижимости, которые не пусты. Для каждого интервала выбирается сетка - подмножество его точек, где по произвольной точке интервала находится ближайшая точка слева. При помощи таких приближений определяются на сетках функции Беллмана. С использованием функций Беллмана в теореме 2 даётся процесс и оценивается отклонение его от оптимального процесса. В теореме 2 гарантируется, что процесс, который даётся там, оптимален в случае, когда интервалы достижимости и их сетки совпадают. В других случаях для получения оптимального процесса используются теоремы 3 и теоремы 4. В теореме 3 устанавливается, что процесс, который даётся в теореме 2, минимален в лексикографическом порядке, который вводится с использованием функций Беллмана. В теореме 3 даётся процедура, которая строит, если возможно, в этом порядке следующий процесс, пропуская лишь процессы, которые неоптимальны. Оптимальный процесс и оптимальное значение находятся по теореме 4 исходя из процесса, который даётся в теореме 2, при помощи одного или нескольких вызовов процедуры, которая даётся в теореме 3.

динамическое программирование, функции Беллмана, процедуры, алгоритмы