- •Исследование операций
- •Учебный план
- •Тематические планы лекций Лекция № 1. Исследование операций как методологическая основа теории принятия управленческих решений. Основные термины, определения, формализация
- •Лекция № 2.Моделирование целевых установок развития сложных системах
- •Лекция № 3. Примеры моделей операций
- •Лекция № 4. Элементы выпуклого анализа
- •Лекция № 5. Основы выпуклого программирования. Теория Куна-Таккера
- •Лекция № 6. Линейное программирование
- •Лекция № 7. Игровые методы обоснования решений
- •Лекция № 8. Моделирование операций на основе марковских случайных процессов
- •Лекция № 9. Элементы теории массового обслуживания
- •Список источников и литературы
- •2. Дополнительная литература
- •Лекция № 1. Исследование операций как методологическая основа теории принятия управленческих решений. Основные термины, определения, формализация
- •1.1Цели и задачи курса «Исследование операций»
- •1.2Системный подход в решении проблем управления
- •1.2.1Формальное определение системы и примеры систем
- •1.2.2Основные понятия целевого подхода в управлении
- •1.2.3Концептуальная постановка проблемы
- •1.2.4Понятие структуризации проблемы
- •1.2.5Основные понятия объектно-субъектного подхода в управлении
- •1.2.6Формализация системы и фаз процесса принятия решений
- •1.2.6.1Выявление проблемы — анализ ее существования
- •1.2.6.2Постановка проблемы
- •1.2.6.3Поиск решения проблемы
- •1.2.6.4Принятие решения
- •1.2.6.5Исполнение решения
- •1.2.6.6Оценка выполненного решения
- •1.3Формализм теории исследования операций (модель операции)
- •1.4Оценка эффективности стратегии
- •1.4.1Оценка неопределенности стратегии
- •1.4.2Функциональная оптимизация стратегий
- •1.4.3Смешанные стратегии
- •Лекция № 2.Моделирование целевых установок в сложных системах (2 ч.)
- •2.1Классификация целей систем
- •2.2Графы целей и способы их построения
- •2.3Методы свертки показателей эффективности
- •2.3.1.1Экономический способ формирования критериев
- •2.3.1.2Критические состояния объекта
- •2.3.1.3Последовательное достижение частных целей
- •2.3.1.4Логическое объединение критериев
- •2.3.1.5Обобщенное логическое объединение
- •2.3.1.6Случайное и неопределенное объединение
- •2.3.1.7Единицы измерения целей
- •2.3.1.8Полнота системы элементарных действий над критериями
- •2.4Экспертная оценка эффективности
- •2.5Критерии эффективности организационного управления
- •Лекция № 3. Примеры моделей операций (2 ч.)
- •3.1Модель анализа технологических процессов
- •3.2Аппроксимация функций полиномами
- •3.3Модель численного поиска экстремума
- •3.4Модель действий нападения против защиты в военных операциях
- •3.5Модель производства продукции в условиях конкуренции
- •3.6Модель оценки надежности неремонтируемых систем
- •3.6.1Параллельное дублирование системы в целом
- •3.6.2«Холодное резервирование» системы в целом
- •3.6.3Параллельное дублирование агрегатов системы
- •3.6.4«Холодное резервирование» агрегатов
- •3.7Модель для выбора дальности стрельбы в дуэльной ситуации
- •3.8Линейная обработка измерений (фильтрация) координат движущихся объектов
- •3.8.1Случайное блуждание координат движущегося объекта
- •3.8.2Зависимое блуждание координат движущегося объекта
- •3.8.3Ограниченное блуждание координат движущегося объекта
- •Лекция № 4.Элементы выпуклого анализа
- •4.1Вспомним основные понятия высшей алгебры
- •4.2Определение и примеры выпуклых множеств.
- •-Мерный куб с центром в точке и ребром :
- •-Мерный шар радиуса с центром в точке :
- •4.3Проекция точки на множество. Свойства.
- •4.4Теоремы отделимости выпуклых множеств.
- •4.5Крайние точки выпуклых множеств.
- •4.6Альтернативы Фредгольма.
- •4.7Выпуклые функции и их свойства.
- •4.8Связь между выпуклыми функциями и выпуклыми множествами
- •4.9Свойства выпуклых функций.
- •4.9.1Дифференцируемость скалярной выпуклой функции.
- •4.9.2Дифференцируемость по направлению.
- •4.9.3Непрерывность.
- •4.10Выпуклые дифференцируемые функции и их экстремальные свойства
- •4.11Критерии оптимальности
- •Лекция № 5.Основы выпуклого программирования. Теория Куна-Таккера
- •5.1Основная задача выпуклого программирования
- •5.2Формальная постановка задачи выпуклого программирования
- •5.3 Классические способы отыскания решения экстремальных задач
- •5.4Условие регулярности
- •5.5Функция Лагранжа. Условия оптимальности
- •5.6Теорема (Куна-Таккера).
- •5.7Дифференциальные условия Куна-Таккера
- •5.8Общая схема решения задачи выпуклого программирования
- •Лекция № 6.Линейное программирование
- •6.1Примеры моделей операций, приводящих к злп
- •6.1.1Задача о диете
- •6.1.2Общая задача планирования выпуска продукции (распределительная задача)
- •6.1.2.1Общая задача планирования выпуска продукции
- •6.1.2.2Выпуск комплектной продукции
- •6.1.3Транспортная задача
- •6.1.3.1Классическая транспортная задача
- •6.1.3.2Транспортная задача с фиксированными доплатами
- •6.2Различные виды злп и их эквивалентность
- •6.2.1Стандартная задача линейного программирования
- •Лекция № 7. Игровые методы обоснования решений
- •7.1Теория игр как теория обоснования решений в условиях конфликта интересов
- •7.2Конфликт и его формальная модель
- •7.3Формализация принятия решения в условиях конфликта
- •7.4Оптимальность в конфликтной ситуации
7.2Конфликт и его формальная модель
Конфликтом естественно называть всякое явление, применительно к которому имеет смысл говорить, кто и как в этом явлении участвует, каковы его возможные исходы, кто в этих исходах заинтересован и, наконец, в чем состоит эта заинтересованность. Таким образом, в формальное определение конфликта должны входить те или иные формальные задания только что перечисленных его компонент. Достаточно общая постановка вопроса состоит в том, чтобы описать наиболее простым образом каждую из пяти указанных компонент конфликта в терминах первичных математических понятий, а именно—в терминах абстрактных множеств и отношений.
Будем в соответствии с этим считать, что принимающие участие в конфликте стороны суть элементы некоторого абстрактного множества. (Это значит, что мы априори не предполагаем, что они наделены какими-либо содержательными или хотя бы формальными свойствами.) Часто оказывается целесообразным считать их подмножествами некоторого универсального множества; элементы последнего принято называть игроками, а подмножества игроков, которые являются действующими сторонами в конфликте,—коалициями действия (различные коалиции действия могут пересекаться и даже содержаться одна в другой).
Множество всех коалиций действия в конфликте далее будет обозначаться через ^д.
Каждая из коалиций действия К принимает некоторое решение из некоторого множества 8к доступных для нее решений .Будем пока считать, что множество 8ц является абстрактным, и процесс принятия решения сводится к формальному и притом произвольному выбору элемента из этого множества. Элементы множества 8к называются стратегиями коалиции АС.
Выбор каждой из коалиций действия некоторой стратегии определяет то, что естественно назвать исходом конфликта. При этом не обязательно, чтобы этот исход понимался как однозначно определенное детерминированное явление. Допустимо, чтобы тот или иной из этих исходов был множеством физических явлений или же случайным явлением, т. е. множеством явлений с вероятностной мерой на нем. Кроме того, некоторые комбинации выбранных коалициями действия стратегий могут оказаться несовместимыми и потому неосуществимыми. В этом случае можно считать, что конфликт не состоялся (в применении к салонным или спортивным играм это может выражаться в появлении некоторой помехи, воспрепятствовавшей окончанию игры).
Все исходы конфликта называются ситуациями. Из сказанного выше следует, что ситуации составляют некоторое множество 8, являющееся подмножеством множества всех комбинаций стратегий коалиции действия, т. е. декартова произведения множеств стратегий: 5с: П §
По поводу заинтересованных в исходах конфликта сторон можно повторить почти все, сказанное в связи с коалициями действия. Их естественно называть коалициями интересов, и они считаются элементами некоторого абстрактного множества, которое далее будет обозначаться через ^,г Обычно достаточно считать, что коалиции интересов суть подмножества того же множества игроков, что и коалиции действия.
В нашем изложении множества коалиций действия и множества коалиций интересов рассматриваются как различные. Это сделано не ради одной лишь формальной общности. Во многих реальных конфликтах могут встречаться коалиции действия, не являющиеся коалициями интересов, и наоборот. Например, наблюдающий за футбольным матчем по телевидению болельщик заинтересован в исходе матча, но не может влиять на его ход. Наоборот, судья этого матча может весьма существенно влиять на его ход, но не имеет права обнаруживать заинтересованность в его исходе.
Рассмотрим, наконец, форму выражения заинтересованности для коалиций интересов. Эта заинтересованность проявляется в том, что каждая из этих коалиций предпочитает одни исходы конфликта другим. Это описывается в виде некоторого отношения предпочтения — абстрактного бинарного отношения ^>к на множестве всех ситуаций. Тот факт, что коалиция интересов К. предпочитает. ситуацию х ситуации у, обозначается как х^>кУ-
Вообще говоря, никаких свойств у отношения ^>к (кроме его» бинарности) не предполагается, хотя обычно оно считается транзитивным - (т. е. из х^кУ и у^-кг следует ^^>я2). В частности, не требуется, чтобы отношение было линейным, т. е. чтобы любые две ситуации были сравнимы друг с другом (в формальной записи для любых двух .различных ситуаций х и у либо х^>кУ, либо У^кх). Допускается даже, чтобы некоторые ситуации вообще не поддавались сравнению по предпочтительности с какими-либо другими ситуациями.
Нередко отношение предпочтения задается следующим образом. На множестве ситуаций 5 определяется функция Нц, принимающая вещественные значения и называемая функцией выигрыша коалиции интересов К.- Ее значение Нк(х) понимается как выигрыш, который коалиция К. получает в ситуации х. Естественно принять, что х^-кУ, если Нк(х}> Нк{у}-
Итак, формальное описание конфликта состоит в задании системы
где перечисленные в ломаных скобках множества и отношения связаны друг с другом, как это было описано выше. Такая система является формальной моделью конфликта. Она называется игрой. Теория игр занимается изучением игр именно в этом понимании.
Разумеется, приведенное определение игры является чрезвычайно общим. Фактически приходится иметь дело со значительно более узкими классами игр. Некоторые из этих классов рассматриваются в книге Оуэна.
Физическая и социальная природа компонент игры и, в частности коалиций действия, коалиций интересов и игроков, может быть весьма разнообразной: юридические лица, спортивные команды, конкурирующие фирмы, воюющие стороны, биологические виды в борьбе за существование и т. д.
Некоторые заинтересованные стороны могут даже не существовать реально, а являться лишь отражением определенных представлений, которые могут возникать в тех или иных условиях у реальных заинтересованных сторон. Этот случай, как это ни покажется на первый взгляд странным, является достаточно распространенным.
Предположим для простоты, что мы имеем дело с единственным субъектом, принимающим решения и притом недостаточно осведомленным об обстановке, в которой ему приходится это делать. Он допускает наступление различных последствий в результате. принятия каждого своего решения, и эти последствия имеют для него различную предпочтительность. На самом деле наступление тех или иных последствий зависит от некоторой неизвестной ему закономерности природы. Поэтому он может допустить, что истинная закономерность природы является для него наименее благоприятной. Это значит, что субъект представляет себе дело так, как будто вместо объективной, но непознанной природы ему противостоит сознательный противник, стремящийся к ситуациям, наименее предпочитаемым субъектом. В этом смысле мы можем иногда причислять к участникам конфликта природу. Очевидно, в этом не заключено никакой антропоморфизации природы. Описанная форма принятия решения обычно называется принятием решений в условиях неопределенности. Оно носит конфликтный характер и формализуется в виде игры. Таким образом, математическое моделирование принятия оптимальных решений в условиях неопределенности также можно естественным образом отнести к теории игр («игры против природы»).
Столь же разнообразной может быть и природа отношений предпочтения. Очевидно, что при рассмотрении вопроса в наиболее общем виде доказательствам поддаются лишь отдельные, и притом не слишком глубокие утверждения. В целях построения содержательной теории желателен переход к более конкретным отношениям предпочтения. Очень часто в теории игр отношения предпочтения сводятся к функциям выигрыша. Некоторые вопросы, касающиеся возможности такого сведения, рассматриваются в гл. VI.
Вопрос о природе стратегий действующих сторон рассматривается в следующем параграфе.