Исследование Операций

Построение, разработка и приложения математич. моделей принятия оптимальных решений. Содержанием теоретич. аспекта И. о. являются анализ и решение математич. задач выбора в заданном множестве допустимых решений Xэлемента, удовлетворяющего тем или иным критериям оптимальности и называемого оптимальным решением задачи. При этом иногда выбирается "обобщенный" элемент X:подмножество Xили функция со значениями в X(в том числе случайная величина со значениями в X). Такие задачи наз. оптимизационными. Прикладной аспект И. о. состоит в составлении оптимизационных задач и реализации их решений. Постановка задачи И. о. охватывает прежде всего формальное описание множества допустимых решений Xи критериев оптимальности выбора. Оно должно соответствовать содержательным представлениям о возможном и целесообразном в данных условиях. Напротив, проверка адекватности самих содержательных представлений объективной реальности уже выходит за пределы И. о. Все решения (в том числе оптимальные) принимаются всегда на основе информации, к-рой располагает принимающий решения субъект (или субъекты), и только на ней. Поэтому каждая задача И. о. должна в своей постановке отражать знания принимающего решение субъекта о множестве допустимых решений и о критерии оптимальности. Так, если принятие решения происходит в наперед известном и не изменяющемся информационном состоянии, то задача наз. статической. В таких условиях весь процесс принятия решения может быть сведен к единому мгновенному акту. В противном случае, если приходится иметь дело с несколькими различными информационными состояниями, то решение будет заключаться в установлении соответствия между каждым информационным состоянием и доступной в нем альтернативой, т. е. в выборе функции, выражающей это соответствие. Если информационные состояния в ходе принятия решения сменяют друг друга, то задача наз. динамической; в ней часто целесообразно принимать поэтапные, "многошаговые" решения или даже развертывать принятие решения в непрерывный во времени процесс. Информационные состояния принимающего решения субъекта могут по-разному характеризовать его истинное ("физическое") состояние. Может оказаться, что одно информационное состояние субъекта охватывает целое множество его физич. состояний. В этом случае задача принятия решений наз. неопределенной. Такие задачи И. о. рассматриваются в игр теории. Если информационное множество содержит несколько физич. состояний, но субъект кроме их множества знает еще и (априорные) вероятности каждого из этих физич. состояний, то задача наз. стохастической. Наконец, если информационное состояние состоит из единственного физич. состояния, то задача наз. детерминированной. Иногда представляет интерес одновременно рассматривать семейства задач, зависящих от численного, векторного или пробегающего значения из к.-л. другого множества параметра, объединяя их в единую параметрическую задачу. Отличие ее от неопределенной задачи состоит в том, что решение первой заключается в решении всех задач, отвечающих конкретным значениям параметра, а решение второй — в нахождении такого допустимого решения, к-рое было бы в известной мере желательным, как бы конкретно ни реализовалась неопределенность. Вместе с тем решение стохастич. задачи состоит в нахождении такого допустимого решения, к-рое было бы оптимальным "в среднем;) по всему множеству отдельных задач. Теоретически мыслимы задачи И. о. с любыми множествами допустимых решений Xи с весьма произвольными критериями оптимальности. Последние могут иметь вид требований о максимизации (или минимизации) значений нек-рой числовой или векторной функции f на X. Эта функция обычно наз. целевой функцией. В первом случае говорят о задаче математического программирования (оптимального программирования, что не следует смешивать с программированием на ЭВМ), а во втором — о задаче векторной оптимизации, или о многокритериальной задаче. Рассматриваются также критерии, выражаемые бинарным отношением предпочтения на X. Это отношение не обязано быть отношением линейного или хотя бы частичного упорядочения. В математич. программировании чаще других рассматриваются задачи, в к-рых Xесть подмножество конечномерного евклидова пространства Е n. Если при этом X- выпуклый многогранник с конечным числом вершин, а целевая функция f линейна, то имеют дело с задачами линейного программирования;если X- произвольное выпуклое множество, а f — выпуклая функция, то — с задачей выпуклого программирования. Естественным образом определяются задачи, относящиеся к кусочно линейному программированию, квадратичномy программированию и т. д. Множество допустимых решений Xможет быть также подмножеством, функционального пространства, и формально вариационное исчисление, а также круг вопросов, связанный с принципом максимума Понтрягина, поэтому могут быть также отнесены к оптимальному программированию. В других задачах оптимального программирования X может быть конечным множеством; такие задачи относятся к дискретному программированию. В них допустимые решения могут быть точками целочисленной решетки в Е п (целочисленное программирование) или векторами, каждая компонента к-рых принимает лишь два значения (булево программирование). В отдельных задачах элементы Xсуть перестановки конечного числа символов, пути в заданном графе и т. д. Особым случаем задач оптимального программирования является нахождение максимина, т. е. максимального значения функции, имеющей вид минимума (аналогично-минимакса). Теория решения стохастич. задач линейного программирования составляет предмет стохастического программирования. Многокритериальные задачи, а также задачи с отношением предпочтения по существу относятся к теории игр; их классификация проводится по теоретико-игровым признакам. Одной из тенденций современного (70-е гг. 20 в.) И. о. является переход от рассмотрения отдельных задач И. о. к изучению систем, пространств, исчислений таких задач и исследование связей между различными задачами или сведений одних задач к другим, более просто устроенным. Математич. аппарат, предназначенный и разрабатываемый для целей решения задач И. о., принято называть математич. методами И. о. По своему характеру математич. методы И. о. в принципе не отличаются от математич. методов любой другой математич. дисциплины, имеющей содержательные приложения или хотя бы интерпретации. Разработанность, математич. методов для разных задач И. о. и их классов неод-инакова. Наиболее разработанной является теория линейного и выпуклого программирования. Некоторые параметрич. задачи И. о., выделяемые специфическими содержательными интерпретациями, проблематикой и терминологией, носят название моделей И. о. Обычно каждая модель И. о. имеет присущие ей методы решения. Диапазон калибров моделей И. о. весьма широк: от конкретных задач, различающихся лишь численными значениями входящих в них параметров (к их числу можно отнести задачу о назначениях, транспортную задачу и несколько более сложные задачи о раскрое, задачу о размещении и теорию сетевых графиков), до таких разветвленных дисциплин, как теория управления запасами, теория расписаний (иногда называемая календарным планированием) или теория надежности. Большое число моделей И. о. дает теория игр (игры с выбором момента времени, игры типа Блотто, игры типа покера, дифференциальные игры преследования и др.). К числу моделей И. о. принято несколько авансированно относить теорию массового обслуживания, хотя большинство ее задач пока еще неприобрело оптимизационного характера. Решение каждой задачи И. о. начинается с выбора принципа оптимальности. Если задача относится к оптимальному программированию, то этот выбор тривиален: принцип оптимальности состоит в максимизации (соответственно минимизации) целевой функции. Таким образом, в этом случае принцип оптимальности задачи формально совпадает с ее критерием оптимальности. В остальных случаях нахождение принципа оптимальности оказывается существенным этапом решения задачи и может реализоваться неоднозначно. Употребительны приемы сведения векторного критерия или отношения предпочтения к численным критериям. Напр., в случае многокритериальной задачи принцип оптимальности может состоять в придании отдельным компонентам векторного критерия тех или иных весов и рассмотрении в качестве целевой функции взвешенной суммы; другой принцип оптимальности в этой задаче может заключаться в максимизации минимальной компоненты вектора критерия (принцип максимина) и т. д. Весьма разнообразными могут быть принципы оптимальности в задачах с отношением предпочтения (см., напр., Игр теория). Возможности и пути замены отношений предпочтения численными критериями составляют один из основных вопросов полезности теории. Т.. о., критерий задачи И. о. есть часть ее условия, а принцип оптимальности — часть ответа. Для большинства моделей И. о. принципы оптимальности фиксированы. Следующим после выбора принципа оптимальности этапом решения задачи И. о. является установление его реализуемости (т. е. существование решений задачи в смысле этого принципа). Нереализуемость принципа оптимальности в классе заданных в условиях задачи допустимых решений иногда преодолевается путем введения в том или ином смысле обобщенных решений: подмножеств множества допустимых решений или функций со значениями в этом множестве. Так как существование оптимальных решений задачи И. о. нередко доказывается неконструктивно (напр., на основании тех или иных теорем о неподвижной точке), а иногда конструктивным образом, но обеспечивающим фактическое его нахождение лишь потенциально (но не практически), получение оптимального решения задачи И. о. является третьим этапом ее разработки. Задачи И. о. обладают рядом черт, обусловливающих методику их составления и решения: Во-первых, даже для наиболее простых параметрич. классов задач не удается представить решение в виде единообразного аналитич. выражения от соответствующих параметров. Поэтому задачи И. о. в подавляющем большинстве не поддаются аналитич. решению и должны решаться численно. Во-вторых, большинство практически интересных задач И. о. содержит в своих формулировках весьма большое количество числового материала, не сводящегося аналитич. выражениям, поэтому численное решение этих задач возможно лишь с использованием ЭВМ. В-третьих, процесс решения многих задач И. о. заключается в выполнении простых однотипных операций над числами, составляющих большие массивы. Поэтому задачи И. -о. предъявляют к ЭВМ требования, касающиеся в большей степени их памяти, чем быстродействия. Фактически требования И. о. оказывают значительное влияние на развитие ЭВМ и формирование их парка. Круг приложений И. о. весьма широк. И. о. используется для решения технических (причем не столько конструкторских, сколько технологических), технико-экономических, социально-экономических задач, а также задач управления в различных сферах и на различных уровнях, вытесняя постепенно традиционные "интуитивные" методы принятия решений. Практическое внедрение результатов И. о. встречается с трудностями различного рода. Первая из них, преодолеваемая еще сравнительно легко, связана с построением концептуальной структуры модели реальной задачи принятия решения (или с подбором уже имеющейся структуры модели). Этим устанавливается принципиальная возможность моделирования класса реальных задач, включающего рассматриваемую задачу, нек-рым классом задач И. о. Следующая трудность состоит в выборе из этого класса задач И. о. именно той, к-рая моделирует интересующую исследователя конкретную задачу. Для этого, в частности, необходимо измерить значения параметров, определяющих решаемую задачу. Но поскольку эти параметры имеют не обязательно физический или технический, а часто экономический или даже социально-экономич. характер, их измерение с требуемой точностью может представлять самостоятельную проблему. Эту трудность сбора информация для построения конкретной модели можно считать основным препятствием на пути выработки оптимального решения. Затем, после построения модели, возникают чисто математич. и в том числе вычислительные трудности ее анализа и решения. В сущности именно их преодоление и составляет содержание И. о. Наконец, после нахождения решения возникает последняя трудность, уже организационного и психологич. плана: найденное решение нередко существенно отличается от традиционных и потому может восприниматься с недоверием. Все это ограничивает практич. применения И. о. Для более успешного их преодоления коллективы, работающие в области И. о., формируются как комплексные: в них включаются кроме математиков обычно и инженеры, и экономисты, и специалисты в области конкретных дисциплин, иногда — психологи, администраторы и т. д. Лит.:[1] Морз Ф. М., Кимбелл Д. Е., Методы исследования операций, пер. с англ., М., 1956; [2] Саати Т.-Л., Математические методы исследования операций, пер. с англ., М., 1963; [3] Кофман А., Фор Р., Займемся исследованием операций, пер. с франц., М., 1966; [4] Кофман А., Методы и модели исследования операций, пер. с франц., М., 1966; [5] Черчмен У.,Акоф Р., Арноф Л., Введение в исследование операций, пер. с англ., М., 1968; [6] Чуев Ю. В., в военном деле, М., 1970; [7] ГермейерЮ. Б., Введение в теорию исследования операций, М., 1971; [8] Акоф Р., Сасиени М., Основы исследования операций, пер. с англ., М., 1971; [9] Вентцель Е. С, , М., 1972; [10] Вагнер Г., Основы исследования операций, т. 1-3, пер. с англ., М., 1972- 1973; [11] . Методологические аспекты, М., 1972; [12] Mathematische Standardmodelle der Operations-forschung, В., 1971; [13] Mathematische Standardmodelle der Operationsforschung. Mathematische Grundlagen, Methoden und Modelle, Bd 1 — 3, В., 1971-73. Я. H. Воробьев