Антюхов В.И.

Тема 1. Нелинейное программирование Лекция 1. Введение в теорию игр и исследование операций Учебные вопросы: 1. Предметная область теории игр и исследования операций 2. Основные понятия и определения исследования операций 3. Основные понятия и определения теории игр

Лекция 1. Введение в теорию игр и исследование операций Учебный вопрос 1. Предметная область теории игр и исследования операций

Введение Исследование операций возникло в годы второй мировой войны из потребностей наилучшей организации боевых действий В дальнейшем исследование операций нашло широкое применение в: - науке (для перспективного и текущего планирования НИР и ОКР); - экономике (для проектирования различных объектов); - социологии; - политике и др.

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

Области применения исследования операций в ГПС МЧС РФ Обоснование программ оснащения Разработка новых образцов специальной техники Разработка планов подготовки спасателей Оперативное управление силами ГПС и др.

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

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

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

Предметная область ТИ и ИО Объектом исследования операций в области ГПС являются: - программы развития специальной техники; - все виды оперативной и боевой деятельности; - все виды обеспечения боевых действий; - подготовка кадров и т.д.

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

Предметная область ТИ и ИО Области приложения теории игр: - экономика; - политика; - военные действия и т. д.

Лекция 1. Введение в теорию игр и исследование операций Учебный вопрос 2. Основные понятия и определения теории исследования операций

Как и всякое научное направление, исследование операций имеет свой понятийный аппарат.

Понятие «операция» Одним из основных понятий теории исследования операций является понятие «операция» Операция - это этап функционирования системы, связанный с достижением конкретной цели Примеры операций: - тушение пожара; - следование к месту проведения аварийно-спасательных работ; - обучение в ВУЗе МЧС и др.

Понятие «цель» Цель - это конечный результат, который требуется достичь в результате операции Цель, как правило, является качественным понятием Примеры целей операций: - Цель операции «тушение пожара» – сохранение жизней и материальных средств - Цель следования к месту проведения аварийно- спасательных работ - тренировка личного состава - Цель обучения в ВУЗе МЧС – подготовка специалистов высшей квалификации для МЧС Наряду с целями, фигурирующими в явном виде, на практике, могут иметь место цели, которые непосредственно в постановке задачи исследования операций не отражены

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

Понятие «оперирующая сторона» Оперирующая сторона – это совокупность лиц, которые стремятся в данной операции к достижению одной цели Пример оперирующей стороны: личный состав караула пожарной части. В операции могут участвовать одна или несколько оперирующих сторон, преследующих различные несовпадающие цели Несовпадение целей создает конфликтную ситуацию. Подобные операции называются «многосторонними» или «конфликтными» При тушении пожара одна оперирующая сторона - расчет караула, и другая - стихия, имеют различные, обычно противоположные цели

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

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

Понятие «стратегия» Оперирующая сторона управляет операцией, выбирая те или иные способы использования ресурсов – «стратегии» (способы действий, альтернативы, решения, управления) Возможности оперирующей стороны по управлению операцией всегда ограничены, поскольку всегда ограничены ее ресурсы. Этот факт проявляется в наличии ограничений на выбор способа действий оперирующей стороны Стратегии, удовлетворяющие этим ограничениям, называются допустимыми

Реализация той или иной стратегии оперирующей стороны обычно приводит к различным исходам операции Чтобы сравнивать между собой качество различных стратегий, нужно иметь возможность оценивать соответствующие исходы операций Исход операции оценивается с помощью критериев эффективности

Понятие «критерий эффективности» Критерий эффективности – это математическое выражение, позволяющее количественно оценить степень достижения цели операции Переход от качественного понятия, каким является цель, к количественному понятию – критерий, содержит определенное противоречие Критерий, как правило, отражает только некоторые, наиболее существенные стороны цели операции Формулировка критерия, как можно более полно соответствующего цели операции, является одной из наиболее сложных творческих задач операционного исследования

Понятие «оптимальная стратегия» Стратегия, наилучшая в смысле выбранного критерия эффективности, то есть доставляющая ему экстремальное (максимальное или минимальное), значение, называется оптимальной стратегией Оптимальной стратегии вообще не существует Всякая оптимальная стратегия является наилучшей лишь в смысле, определенном выбранным критерием эффективности

Понятие «показатель эффективности» В теории исследования операций наряду с понятием критерий эффективности широко используется понятие показатель эффективности Показатель эффективности – это количественная оценку какого-то отдельного свойства изучаемого объекта или явления Свойства технических, экономических, военных объектов и явлений обычно многогранны. Для их количественной оценки используется совокупность многих показателей

В зависимости от цели операции тот или иной показатель (или совокупность тех или иных показателей) могут быть выбраны в качестве критерия эффективности, а остальные - вынесены в ограничения Главное условие, необходимое для применения математических методов исследования операций, заключается в принципиальной возможности разработки корректной математической модели изучаемого объекта или явления

Понятие «математическая модель» Математическая модель - упрощенное представление характеристик реального процесса в виде совокупности уравнений (алгоритмов). Степень упрощения должна быть такая, чтобы вычисления на модели могли быть проведены с требуемой точностью за время не более заданного В связи с этим возникает необходимость учета в модели не всех, а только существенно значимых (релевантных, доминирующих) свойств моделируемого объекта, явления Среди математических моделей по методам, лежащим в их основе, можно выделить: - аналитические модели; - численные модели; - имитационные модели.

Аналитической моделью называется формализованное описание объекта или явления, позволяющее получить соотношения между входными и выходными величинами в явном виде Численная модель характеризуется такой зависимостью между входными и выходными величинами, которая допускает только численные решения для конкретных начальных условий и количественных параметров модели

В имитационных моделях зависимости между входными и выходными величинами носят вероятностный характер Для получения достаточно точных и надежных результатов имитационную модель приходится решать с одними и теми же исходными данными неоднократно

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

Лекция 1. Введение в теорию игр и исследование операций Учебный вопрос 3. Основные понятия и определения теории игр

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

Существенной чертой любой игры является то, что выигрыш каждого игрока зависит не только от его действий, но и от действий, предпринимаемых другими игроками Каждый игрок должен учитывать эту зависимость при выборе стратегии

Понятие «стратегия» в теории игр Стратегия – это набор, сформулированных до начала игры, правил выбора каждого хода (шага) игрока в зависимости от возникшей ситуации. Если игра состоит из N шагов и на i-м шаге игрок может сделать выбор из M i альтернатив, то общее число его стратегий подсчитывается по формуле:

Классификация игр по числу ходов; по числу игроков; по числу стратегий; по свойствам платежной функции; по характеру переговоров игроков до начала игры; по количеству ходов и т. д.

Классификация игр по числу ходов Если рассматривать конфликтную ситуацию во времени, то она может состоять из одного или нескольких этапов Математическая модель ситуации, состоящей из нескольких этапов, отображается многоходовой игрой В одних многоходовых играх время, когда игрок делает очередной ход дискретно, в других – непрерывно

Классификация игр по числу ходов в зависимости от числа игроков Игры с двумя игроками (парные игры); Игры с тремя и более игроками (игры многих лиц или многосторонние игры) Когда число игроков равно 3 и более, могут создаваться коалиции – группы из двух и более игроков, имеющих сходные цели и координирующих свои стратегии Будем считать множество игроков конечным, хотя в теории игр рассматриваются и игры с бесконечным числом игроков Число игроков обозначим I, I=(1, 2, …, n).

Классификация игр по числу стратегий Различают: - конечные игры; - бесконечные игры Обозначим число стратегий игрока i через Si Конкретную стратегию игрока i обозначим si.

Классификация игр по числу стратегий Процесс игры состоит в выборе каждым игроком одной своей стратегии В результате каждой партии игры складывается система стратегий s = (s 1, s 2,…, s n ), которая называется ситуацией Множество всех ситуаций обозначается S = S 1, S 2, …, S n и представляет собой декартово произведение множеств, стратегий всех игроков В каждой ситуации игроки получают некоторые выигрыши. Платежная функция, характеризующая выигрыш игрока i в ситуации s обозначается H i (s)

Понятие «бескоалиционная игра» Бескоалиционной игрой называется система, в которой число игроков I и стратегии игрока S i являются множествами, а платежная функция H i – функция на множестве S, принимающая вещественные значения

Понятие «игра с постоянной суммой» Среди явлений, описываемых посредством бескоалиационных игр, много таких, которые сводятся к распределению между игроками некоторого постоянного количества Сумма величин платежных функций всех участников такой игры является постоянной, а сама игра называется игрой с постоянной суммой

Понятие «игра с постоянной суммой» Бескоалиционная игра Г называется игрой с постоянной суммой, если существует такое постоянное число с, что где n – число игроков Среди игр с постоянной суммой выделяются игры с нулевой суммой, для которых

Понятие «антогонистическая игра» Игра называется антагонистической, если число игроков в ней равно 2, а значения функций выигрышей этих игроков в каждой ситуации равны по величине и противоположны по знаку

В антагонистической игре для всех Следовательно, антагонистическая игра также является игрой с нулевой суммой

Понятие «матричная игра» Антагонистические игры, в которых каждый игрок имеет конечное число стратегий, называются матричными играми Изучением матричных игр мы будем заниматься в дальнейшем больше всего