Основной принцип динамического программирования

Основной принцип динамического программирования заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции f_k (х_k, ξ _k), а выбирать

оптимальное управление х_k* в предположении об оптимальности всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шаге k условных оптимальных управлений _k (ξ), ξ∊Ξ, обеспечивающих наибольшую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние ξ.

Обозначим Λ _k (ξ) максимальное значение суммы функций f_k на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ. Тогда функции Λ _k (ξ) должны удовлетворять рекуррентному соотношению:

где ξ _{k +1} = φ _k (x_k, ξ)

Соотношение (5.14) называют основным рекуррентным соотношением динамического программирования. Оно реализует базовый принцип динамического программирования, известный также как принцип оптимальности Беллмана:

F Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было

начальное состояние ξ _k на k-м шаге и выбранное на этом шаге управление х_k,, последующие управления (управленческие решения) должны быть оптимальными по отношению к состоянию ξ _{k +1} = φ _k (x_k, ξ _k), получающемуся в результате решения, принятого на шаге k.

Основное соотношение (5.14) позволяет найти функции Λ _k (ξ) только в сочетании с начальным условием, каковым в нашем случае является равенство

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

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом ξ. При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ₁, ξ₂,..., ξ _m, и табулировать значения функций Λ _k (ξ₁, ξ₂,..., ξ _m) необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информацию о них можно найти в специальной литературе [4, 5].

 

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

Пронумеруем все виды ресурсов числами от 1 до m, буквой i будем обозначать номер вида ресурса. Таким образом, i удовлетворяет неравенству 1 £ i £ m. Заметим, что ресурсы разных видов могут измеряться в различных единицах (тоннах, кубометрах, человеко-часах, рублях, штуках и др.).

В течение планового периода предприятие обладает некоторыми доступными объемами ресурса каждого вида. Объем ресурса i-го вида, измеренный в единицах соответствующих данному виду ресурса, обозначим посредством b_i. Индекс i около буквы b указывает, что доступные объемы ресурсов разных видов могут быть различными.

Из этих ресурсов предприятие способно изготавливать различную продукцию (в нашей ситуации – Печенье и Бисквиты). Обозначим буквой n общее число видов продукции, которые может выпустить предприятие из имеющихся ресурсов. Занумеруем все виды продукции числами от 1 до n. Буквой j будем обозначать номер вида продукции, так что выполняется неравенство 1 £ j £ n. Продукция, как и ресурсы, может измеряться в различных единицах.

Пусть c _j - цена, по которой предприятие реализует каждую единицу продукции j-го вида. Индекс j около буквы c указывает, что цена разных видов продукции может быть различной.

Производство продукции требует затрат ресурсов. Объем затрат зависит от вида ресурса, вида продукции и количества единиц продукции. Обозначим посредством a _ij норму затрат ресурса i-го вида на производство продукции j-го вида. Другими словами, a _ij - это количество ресурса i-го вида, затрачиваемое при производстве единицы продукции j-го вида.

Задача оптимального использования ресурсов, задача производственного планирования, состоит в том, чтобы определить, какую продукцию и в каком объеме следует изготовить предприятию из имеющихся ресурсов с тем, чтобы доход от реализации продукции был наибольшим.

Построим математическую модель задачи. Сначала введем переменные. Посредством x_j обозначим искомый объем выпуска продукции j-го вида. Математическую модель можно теперь записать в следующей форме:

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

Фигурная скобка объединяет систему ограничений задачи, неравенства, входящие в систему, соответствуют различным видам ресурсов. Каждое такое неравенство говорит о том, что суммарное количество ресурса, используемое в производстве различных видов продукции, не превосходит общего запаса этого ресурса.

В последней строке системы ограничений указано, что количества производимой продукции не могут быть отрицательными. Заметим, что равенство нулю здесь не запрещено, то есть некоторые (или даже все) виды продукции предприятие может и не выпускать, хотя они и доступны для выпуска.

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

Всякий набор значений переменных (x₁, x₂,..., x_n) называется планом задачи. Те планы, которые удовлетворяют системе ограничений, называются допустимыми планами. Оптимальным планом называется тот из допустимых планов, который дает наибольшее значение целевой функции среди всех ее значений на допустимых планах. Само это наибольшее значение целевой функции, то есть значение целевой функции на оптимальном плане, называется оптимумом задачи.

Решить задачу производственного планирования - значит найти оптимальный план и оптимум для ее математической модели.

 

Основные понятия Марковских процессов

Марковские случайные процессы названы по имени выдающегося русского математика А.А. Маркова (1856-1922), впервые начавшего изучение вероятностной связи случайных величин и создавшего теорию, которую можно назвать “динамикой вероятностей”. В дальнейшем основы этой теории явились исходной базой общей теории случайных процессов, а также таких важных прикладных наук, как теория диффузионных процессов, теория надежности, теория массового обслуживания и т.д. В настоящее время теория Марковских процессов и ее приложения широко применяются в самых различных областях таких наук, как механика, физика, химия и др.

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

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

Как указывалось, Марковские случайные процессы относятся к частным случаям случайных процессов (СП). В свою очередь, случайные процессы основаны на понятии случайной функции (СФ).

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

Такими примерами СФ являются: колебания напряжения в электрической цепи, скорость движения автомобиля на участке дороги с ограничением скорости, шероховатость поверхности детали на определенном участке и т.д.

Как правило, считают, что если аргументом СФ является время, то такой процесс называют случайным. Существует и другое, более близкое к теории принятия решений, определение случайных процессов. При этом под случайным процессом понимают процесс случайного изменения состояний какой-либо физической или технической системы по времени или какому-либо другому аргументу.

Нетрудно заметить, что если обозначить состояние и изобразить зависимость, то такая зависимость и будет случайной функцией.

Случайные процессы классифицируются по видам состояний и аргументу t. При этом случайные процессы могут быть с дискретными или непрерывными состояниями или временем.

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

Отметим, во-первых, что случайный процесс с дискретными состояниями и временем называется случайной последовательностью.

Если случайная последовательность обладает Марковским свойством, то она называется цепью Маркова.

С другой стороны, если в случайном процессе состояния дискретны, время непрерывно и свойство последействия сохраняется, то такой случайный процесс называется Марковским процессом с непрерывным временем.

Марковский случайный процесс называется однородным, если переходные вероятности остаются постоянными в ходе процесса.

Цепь Маркова считается заданной, если заданы два условия.

1. Имеется совокупность переходных вероятностей в виде матрицы:

. (2)

2. Имеется вектор начальных вероятностей

, ….. (3)

описывающий начальное состояние системы.

Кроме матричной формы модель Марковской цепи может быть представлена в виде ориентированного взвешенного графа (рис. 1).

Рис. 1 Ориентированный взвешенный граф

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

1. Невозвратное множество (рис. 2).

Рис.2. Невозвратное множество

В случае невозвратного множества возможны любые переходы внутри этого множества. Система может покинуть это множество, но не может вернуться в него.

2. Возвратное множество (рис. 3).

Рис. 3. Возвратное множество

В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.

3. Эргодическое множество (рис. 4).

Рис. 4. Эргодическое множество

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество (рис. 5)

Рис. 5. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

В некоторых случаях, несмотря на случайность процесса, имеется возможность до определенной степени управлять законами распределения или параметрами переходных вероятностей. Такие Марковские цепи называются управляемыми. Очевидно, что с помощью управляемых цепей Маркова (УЦМ) особенно эффективным становится процесс принятия решений, о чем будет сказано впоследствии.

Основным признаком дискретной Марковской цепи (ДМЦ) является детерминированность временных интервалов между отдельными шагами (этапами) процесса. Однако часто в реальных процессах это свойство не соблюдается и интервалы оказываются случайными с каким-либо законом распределения, хотя марковость процесса сохраняется. Такие случайные последовательности называются полумарковскими.

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