Математическая энциклопедия - исследование операций

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

Постановка задачи И. о. охватывает прежде всего формальное описание множества допустимых решений Xи критериев оптимальности выбора. Оно должно соответствовать содержательным представлениям о возможном и целесообразном в данных условиях. Напротив, проверка адекватности самих содержательных представлений объективной реальности уже выходит за пределы И. о. Все решения (в том числе оптимальные) принимаются всегда на основе информации, к-рой располагает принимающий решения субъект (или субъекты), и только на ней. Поэтому каждая задача И. о. должна в своей постановке отражать знания принимающего решение субъекта о множестве допустимых решений и о критерии оптимальности. Так, если принятие решения происходит в наперед известном и не изменяющемся информационном состоянии, то задача наз. статической. В таких условиях весь процесс принятия решения может быть сведен к единому мгновенному акту. В противном случае, если приходится иметь дело с несколькими различными информационными состояниями, то решение будет заключаться в установлении соответствия между каждым информационным состоянием и доступной в нем альтернативой, т. е. в выборе функции, выражающей это соответствие. Если информационные состояния в ходе принятия решения сменяют друг друга, то задача наз. динамической; в ней часто целесообразно принимать поэтапные, "многошаговые" решения или даже развертывать принятие решения в непрерывный во времени процесс.

Информационные состояния принимающего решения субъекта могут по-разному характеризовать его истинное ("физическое") состояние. Может оказаться, что одно информационное состояние субъекта охватывает целое множество его физич. состояний. В этом случае задача принятия решений наз. неопределенной. Такие задачи И. о. рассматриваются в игр теории. Если информационное множество содержит несколько физич. состояний, но субъект кроме их множества знает еще и (априорные) вероятности каждого из этих физич. состояний, то задача наз. стохастической. Наконец, если информационное состояние состоит из единственного физич. состояния, то задача наз. детерминированной. Иногда представляет интерес одновременно рассматривать семейства задач, зависящих от численного, векторного или пробегающего значения из к.-л. другого множества параметра, объединяя их в единую параметрическую задачу. Отличие ее от неопределенной задачи состоит в том, что решение первой заключается в решении всех задач, отвечающих конкретным значениям параметра, а решение второй в нахождении такого допустимого решения, к-рое было бы в известной мере желательным, как бы конкретно ни реализовалась неопределенность. Вместе с тем решение стохастич. задачи состоит в нахождении такого допустимого решения, к-рое было бы оптимальным "в среднем;) по всему множеству отдельных задач.

Теоретически мыслимы задачи И. о. с любыми множествами допустимых решений Xи с весьма произвольными критериями оптимальности. Последние могут иметь вид требований о максимизации (или минимизации) значений нек-рой числовой или векторной функции f на X. Эта функция обычно наз. целевой функцией. В первом случае говорят о задаче математического программирования (оптимального программирования, что не следует смешивать с программированием на ЭВМ), а во втором о задаче векторной оптимизации, или о многокритериальной задаче. Рассматриваются также критерии, выражаемые бинарным отношением предпочтения на X. Это отношение не обязано быть отношением линейного или хотя бы частичного упорядочения.

В математич. программировании чаще других рассматриваются задачи, в к-рых Xесть подмножество конечномерного евклидова пространства Е ⁿ. Если при этом Xвыпуклый многогранник с конечным числом вершин, а целевая функция f линейна, то имеют дело с задачами линейного программирования;если Xпроизвольное выпуклое множество, а f выпуклая функция, то с задачей выпуклого программирования. Естественным образом определяются задачи, относящиеся к кусочно линейному программированию, квадратичномy программированию и т. д. Множество допустимых решений Xможет быть также подмножеством, функционального пространства, и формально вариационное исчисление, а также круг вопросов, связанный с принципом максимума Понтрягина, поэтому могут быть также отнесены к оптимальному программированию. В других задачах оптимального программирования X может быть конечным множеством; такие задачи относятся к дискретному программированию. В них допустимые решения могут быть точками целочисленной решетки в Е ^п (целочисленное программирование) или векторами, каждая компонента к-рых принимает лишь два значения (булево программирование). В отдельных задачах элементы Xсуть перестановки конечного числа символов, пути в заданном графе и т. д. Особым случаем задач оптимального программирования является нахождение максимина, т. е. максимального значения функции, имеющей вид минимума (аналогично-минимакса).

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

Одной из тенденций современного (70-е гг. 20 в.) И. о. является переход от рассмотрения отдельных задач И. о. к изучению систем, пространств, исчислений таких задач и исследование связей между различными задачами или сведений одних задач к другим, более просто устроенным. Математич. аппарат, предназначенный и разрабатываемый для целей решения задач И. о., принято называть математич. методами И. о. По своему характеру математич. методы И. о. в принципе не отличаются от математич. методов любой другой математич. дисциплины, имеющей содержательные приложения или хотя бы интерпретации. Разработанность, математич. методов для разных задач И. о. и их классов неод-инакова. Наиболее разработанной является теория линейного и выпуклого программирования.

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

Решение каждой задачи И. о. начинается с выбора принципа оптимальности. Если задача относится к оптимальному программированию, то этот выбор тривиален: принцип оптимальности состоит в максимизации (соответственно минимизации) целевой функции. Таким образом, в этом случае принцип оптимальности задачи формально совпадает с ее критерием оптимальности. В остальных случаях нахождение принципа оптимальности оказывается существенным этапом решения задачи и может реализоваться неоднозначно. Употребительны приемы сведения векторного критерия или отношения предпочтения к численным критериям. Напр., в случае многокритериальной задачи принцип оптимальности может состоять в придании отдельным компонентам векторного критерия тех или иных весов и рассмотрении в качестве целевой функции взвешенной суммы; другой принцип оптимальности в этой задаче может заключаться в максимизации минимальной компоненты вектора критерия (принцип максимина) и т. д. Весьма разнообразными могут быть принципы оптимальности в задачах с отношением предпочтения (см., напр., Игр теория). Возможности и пути замены отношений предпочтения численными критериями составляют один из основных вопросов полезности теории. Т.. о., критерий задачи И. о. есть часть ее условия, а принцип оптимальности часть ответа. Для большинства моделей И. о. принципы оптимальности фиксированы.