25. Динамическое программирование. Общая структура задач динамического программирования.

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

26. Стохастическое программирование.

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

В задачах прикладной математики можно различать детерминированные и стохастические задачи. В процессе решения последних развилась обширная в настоящее время математическая дисциплина — теория вероятностей.

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

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

В задаче линейного программирования:

1.1

заданные величины сj, аij,,bi, dj, Dj. Часто на практике величины cj, aij bj, могут быть случайными. Так, если bi — ресурс, то он зависит от ряда факторов. Аналогично, сj — цены — будут зависеть от спроса и предложения, aij — расходные коэффициенты — от уровня техники и технологии. Задачи, в которых сj, аij,,bi — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.

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

Стохастическая постановка целевой функции может быть двух видов: М-постановка и Р-постановка.

П ри М-постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:

1.2

где сj — математическое ожидание случайной величины сj.

П ри Р-постановке целевая функция будет иметь вид:

• при максимизации целевой функции:

1.3

обозначает максимизацию вероятности того, что случайная величина ∑ cj xj будет не меньше некоторого значения r;

• п ри минимизации целевой функции:

1.4

обозначает максимизацию вероятности того, что случайная величина ∑ cj xj будет не больше некоторого значения r.

Н аиболее распространены СТП-постановки в вероятностных ограничениях вида:

1.5

где аi j , bi — случайные величины; ai — заданные уровни вероятности.

Т ак, ограничение (а) означает, что вероятность соблюдения неравенства

1.6

должна быть не меньше, чем ai. Аналогичный смысл и других ограничений.

Д ля случая, когда вероятностные ограничения представлены в виде типа (а), задачу СТП можно записать при М-постановке:

1.7

П ри Р-постановке:

• в случае максимизации целевой функции

1.8

• в случае минимизации целевой функции

1.9

где cj , ai j , bi — случайные величины.

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

Задачи (1.7), (1.8), (1.9) непосредственно решены быть не могут. Одним из возможных методов их решения может быть представление их в виде детерминированного эквивалента.

Практические задания:

1. Симплекс метод табличный.

2. Решение двойственных задач.

3. Нахождение оптимального плана прямой и двойственной задачи.

4. Метод геометрической интерпретация.

5. Решение ЗЛП двойственным симплекс методом.

6. Решение т-задачи.

Литература:

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

2. Дослідження операцій в інформаційних системах.

3. Ю.П. Зайченко, С.А. Шумилова. Исследование операций. Сборник задач. – К., Вища школа. 1990.