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

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

Известно большое число экономических, технических и военных задач, постановки которых укладываются в схему (1.1) —, (1.3). Запись (1.1) — i(1.3), вполне определенная при детерминированных значениях параметров условий задачи, теряет определенность и требует дополнительных разъяснений при случайных значениях параметров исходной информации. Между тем во многих прикладных задачах коэффициенты целевой функции, элементы матрицы условий или составляющие вектора ограничений — случайные величины. Естественный, на первый взгляд, путь анализа стохастических задач — замена случайных параметров их средними значениями и вычисление оптимальных планов полученных таким образом детерминированных задач — не всегда оправдан. При усреднении параметров условий задачи может быть нарушена адекватность модели изучаемому явлению. Решение детерминированной задачи с усредненными параметрами может не удовлетворять условиям задачи при различных реализациях элементов матрицы условий и вектора ограничений. [c.8]
Таким образом, простейшие пути учета случайного характера условий задачи математического программирования — замена случайных переменных их средними значениями или переход к жесткой постановке — не всегда приводят к осмысленному решению задачи стохастического программирования. [c.9]
Заметим, что в задачах стохастического программирования со статистическими условиями связка в ограничениях исключена не во всех случаях, как IB жестких постановках, и не в большинстве случаев, как в задачах с вероятностными ограничениями (при j V2), а в среднем. Это значит, что невязки могут возникнуть при каждой реализации условий. Однако невязки условий, отвечающие различным реализациям состояния природы, компенсируют друг друга так, что средняя невязка условий равна нулю. [c.10]
Среди приложений математических методов управления в условиях неполной информации рассматриваются также условные экстремальные задачи, содержащие как вероятностные, так и статистические и жесткие условия. Такие модели стохастического программирования называют моделями со смешанными условиями. [c.10]
Мы рассматривали стохастические аналоги задач линейного программирования. Как легко видеть, детерминированные эквиваленты задач линейного программирования со случайными параметрами условий, соответствующие, например, моделям с вероятностными ограничениями, представляют собой, вообще говоря, задачи нелинейного, а иногда и невыпуклого программирования. Поэтому в стохастическом программировании обычно несущественно, порождена ли стохастическая задача линейной или нелинейной экстремальной задачей. Если не ограничиваться стохастическими аналогами линейных моделей, можно привести более общую запись задачи стохастического программирования, объединяющую различные постановки стохастических задач. [c.10]
например, в задаче требуется вычислить параметры строительной конструкции минимального веса, сохраняющей несущую способность при случайных нагрузках, статистические характеристики которых известны. Ясно, что планы и решение соответствующей задачи стохастического программирования следует представлять в виде детерминированных векторов, составляющие которых — искомые параметры конструкций. [c.11]
Аналогичные ситуации возникают при разработке алгоритмов управления случайными процессами или процессами, сопровождающимися случайными возмущениями. Оптимальный алгоритм целесообразно рассматривать как решение задачи стохастического программирования. Показатель качества и ограничения задачи определяются конкретным назначением алгоритма и априорными статистическими характеристиками случайных возмущений. Решение задачи естественно представлять в виде решающего правила, связывающего искомые параметры управления со случайными параметрами условий. Каждой реализации случайных параметров условий задачи отвечает реализация параметров управления и соответственно конкретная реализация алгоритма. [c.11]
В общем случае задается лишь функциональное пространство, элементом которого может быть решающее правило. Естественно, что чем шире множество, из которого выбираются допустимые решающие правила, тем шире диапазон изменения целевого функционала задачи. [c.12]
Можно указать задачи, в которых осмыслены и могут быть истолкованы в содержательных терминах решения в смешанных стратегиях (в распределениях вероятностей компонент оптимального плана), зависящих или не зависящих от реализации случайных параметров условий задачи. [c.12]
Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи. [c.12]
При решении задачи в смешанных стратегиях математическое ожидание в соотношениях (1.4) и (1.5) берется по совместному распределению х и со. [c.12]
В задачах стохастического программирования, отвечающих ситуациям,, в которых решение следует принимать до наблюдения реализации случайных условий и нельзя корректировать решение при получении информации о реализованных значениях случайных параметров, естественно определять оптимальный план в виде детерминированного вектора. Так определяется класс стохастических задач, для которых естественные решающие правила — правила нулевого порядка. Решение задач стохастического программирования Б виде случайного вектора позволяет установить связь между компонентами оптимального плана, реализациями параметров условий задачи и их априорными статистическими характеристиками. Каждой реализации условий задачи соответствует, таким образом, реализация решения. Следовательно, решение задачи стохастического программирования в виде случайного вектора целесообразно определять в ситуациях, в которых решение может быть принято после наблюдения реализации условий задачи. [c.12]
Для задач, решение которых содержит детерминированные и случайные составляющие, характерна задача планирования производства в условиях неопределенного спроса на производимую продукцию. Оптимальный план производства должен содержать значения по крайней мере двух групп параметров. [c.13]
Первая группа параметров определяет предварительное решение об объеме продуктов, производимых по тому или иному технологическому способу. Информация об этих параметрах позволяет руководству предприятия подготовить оснастку производства, заключить договоры с соисполнителями, провести всю необходимую организационную и технологическую подготовку и начать выпуск продукции. После установления спроса (после наблюдения реализации случайных параметров условий задачи) вычисляется вторая группа параметров решения — коррекции плана. Коррекция вызывается необходимостью компенсации невязок — несоответствия между спросом и объемом продукции, определяемым предварительным планом. Компенсация невязок производится посредством заранее установленного набора технологических способов. Каждой реализации спроса соответствует свой план компенсации невязок. Естественно полагать, что компенсация невязки связана с большими затратами, чем производство того же объема продукции в соответствии с предварительным планом. Поэтому разработка предварительного плана должна учитывать всю априорную информацию о статистических характеристиках спроса, чтобы свести к минимуму суммарные затраты на производство требуемой продукции. Выбор оптимального плана в задачах подобного рода определяется тем, как будут оценены невязки в условиях задачи и каким образом оценка невязки сопоставляется с затратами на реализацию предварительного плана. Разработка предварительного плана и компенсация невязок — два этапа решения одной задачи. В соответствии с этим задачи рассматриваемого типа называют двухэтапными задачами стохастического программирования. Трудности, с которыми связан анализ двухэтапных задач, в значительной степени определяются необходимостью такого выбора предварительного плана разрешимой задачи, который гарантировал бы существование компенсации невязок при всех реализациях случая. Двухэтапные задачи, структура условий которых обладает тем свойством, что при любом плане первого этапа компенсация невязок всегда оказывается возможной, существенно проще в исследовании. Двухэтапным задачам посвящена богатая литература и для целого ряда частных постановок имеются вполне приемлемые методы построения решения. [c.13]
В многоэтапных задачах упомянутого типа предполагается, что на каждом последующем этапе требуется полностью компенсировать невязки, связанные с принятыми решениями и реализованными значениями параметров условий. Перспективным обобщением многоэтапных задач с жесткими условиями являются многоэтапные задачи стохастического программирования с безусловными и условными вероятностными или статистическими ограничениями. В задачах этого класса требуется,, чтобы на каждом этапе вероятность удовлетворения ограничений превышала некоторую заранее заданную величину или чтобы математические ожидания некоторых функций от невязок условий были бы ограничены заданными числами или функциями от наблюденных на предыдущих этапах значений случайных параметров. Кроме того, на каждом этапе могут быть заданы и жесткие ограничения. [c.14]
Постановки многоэтапных задач и методы их решения существенным образом зависят от информационной структуры моделей — от информации о значениях параметров условий задачи, которой располагают к моменту выбора очередного решения. В задачах с безусловными ограничениями решение определяется на основе совместного распределения случайных параметров условий всех этапов. Между многоэтапными задачами с безусловными и условными ограничениями установлено определенное соответствие. В задачах с условными ограничениями обычно различают два крайних случая, отвечающих двум важным для приложений информационным структурам. В первом случае к моменту выбора решения предполагаются известными только реализованные значения параметров условий предыдущих этапов. Решение принимается до наблюдения параметров условий текущего этапа. Во- втором случае к моменту выбора решения имеется вся информация о значениях параметров условий вплоть до параметров текущего этапа.-Неизвестны, естественно, лишь значения случайных параметров последующих этапов. [c.14]
Оптимальные планы многоэтапных задач с условными статистическими или вероятностными ограничениями представляют собой решающие правила или решающие распределения — зависимости компонент решения или статистических характеристик распределения составляющих решения от реализованных и наблюденных к моменту выбора решения значений случайных параметров условий задачи. [c.14]

Вернуться к основной статье