ПРОГРАММИРОВАНИЕ СТОХАСТИЧЕСКОЕ

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

где целевая функция, X — некоторое мн-во -мерного простр. (см. Пространство абстрактное в функциональном анализе), напр.,

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

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

где математическое ожидание целевой ф-ции, а матем ожидания ф-ций , или нахождение

где . Здесь — некоторые числа

Задачи (2) и (3) — типичные задачи П. с., причем задача (3) легко сводится к задаче (2). По внеш. виду эти задачи напоминают задачу нелинейного программирования (1) при или , но это только чисто внеш. сходство, поскольку в задачах (2) и (3), как правило, не выполняется осн. предпосылка теории нелинейного программирования: при каждом х невозможно вычислить точные значения ф-ций и их производных. В тех случаях; когда вычисляются точно, задачи 2) и (3) решают обычными методами нелинейного программирования. В общем случае эти задачи решают стохастической аппроксимации методом, стохастических квазиградиентов методом на основе информации о случайных величинах .

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

Рассмотрим два важных примера. 1) На складе, вместимость которого равна b, требуется создать запас изделий в расчете на случайный спрос с ф-цией распределения Если величина запаса изделий вида, то затраты, связанные с планом отражаются ф-цией

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

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

План х принимается перед тем, как станет известным состояние природы . После того, как становится известным, невязки в ур-ниях ликвидируются выбором вектора коррекции из (5) при данном

Пусть затраты на реализацию плана равны а затраты на коррекцию

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

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

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

Лит.: Гольштейн Е. Г., Юдин Д. Б. Новые направления в линейном программировании. М., 1966 [библиогр. с. 516—520]; Данциг Дж. Линейное программирование, его применения и обобщения., Пер. с англ. М., 1966 [библиогр. с. 564— 589]. Ю. М. Ермольев.