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

- Комбинаторный анализ

- Статистическое моделирование

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

Задача математического программирования имеет вид:

ƒ(x1, x2 … xn) 􀃆 max, min – целевая функция

gi(x1, x2 … xn) ≤ bi, i = 1, m – ограничения.

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

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

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

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

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

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

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

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

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

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

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

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

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.