Программа дисциплины  «Исследование операций»

1Область применения и нормативные ссылки

• 
  ФГОС ВПО по направлению 230700.62 «Прикладная информатика» подготовки бакалавра;
  
• 
  Рабочим учебным планом университета по направлению подготовки 230700.62 «Прикладная информатика» подготовки бакалавра, утвержденным в 2012 г.
  

2Цели освоения дисциплины

3Компетенции обучающегося, формируемые в результате освоения дисциплины

• 
  математическую модель антагонистической игры, понятие оптимальных стратегий игроков, основные теоремы матричных игр;
  
• 
  математическую модель бескоалиционной игры n лиц, понятия равновесных по Нэшу и оптимальных по Парето ситуаций, различия в результатах исследования общей бескоалиционной игры и её частного случая – игры антагонистической;
  
• 
  математическую модель кооперативной игры, принципы оптимальности дележа С-ядро и вектор Шепли;
  

• 
  строить и решать матричную игру, применяя теоретические сведения, в сложных случаях прибегая к использованию стандартных программ для решения задач линейного программирования;
  
• 
  строить математическую модель бескоалиционной игры и исследовать ее на предмет равновесных по Нэшу и оптимальных по Парето ситуаций;
  
• 
  строить математическую модель кооперативной игры, вычислять С-ядро и вектор Шепли.
  

4Место дисциплины в структуре образовательной программы

• 
  «Математический анализ»
  
• 
  «Линейная алгебра и аналитическая геометрия».
  
• 
  «Теория вероятностей»
  

• 
  «Основы математического моделирования»
  
• 
  «Основы управления техническими системами»
  
• 
  «Основы информационной безопасности и криптографии».
  
  
  

5Тематический план учебной дисциплины

6Формы контроля знаний студентов

6.1Критерии оценки знаний, навыков

1. 
   Контрольная работа и домашнее задание.
   

7Содержание дисциплины

8Образовательные технологии

• 
  обслуживается i -м способом игрока 1 и j -м способом игрока 2, то выигрыш игрока 1 на этом объекте составит величину cij;
  
• 
  обслуживается i -м способом игрока 1, а игроком 2 не обслуживается, то выигрыш игрока 1 на этом объекте составит величину c_i;
  
• 
  обслуживается j-м способом игрока 2, а игроком 1 не обслуживается, то выигрыш игрока 1 на этом объекте составит величину d_j;
  
• 
  не обслуживается обоими игроками, то выигрыш игроков нулевой. Каждый игрок заранее не знает, какие именно объекты будут обслуживаться противником, и каким способом. Игрок 1 стремится максимизировать свой суммарный выигрыш, игрок 2 противодействует ему. Требуется определить оптимальное распределение ресурсов для каждого игрока.
  

1. 
   Докажите теорему.
   

2. 
   Начните решение вашей задачи со случая небольшого числа позиций l (l=2,3). Занумеруйте позиции и составьте матрицу А игры, перебирая все возможные варианты размещения фишек игроками по разным позициям. Для решения игры воспользуйтесь теоремой 7. Для этого потребуется придать матрице А блочную структуру. Этого можно добиться за счет выбора способа нумерации стратегий игроков. В соответствии с теоремой 7 решение игры сводится к решению игры , которая проще вследствие меньших размеров. По элементам матрицы А вычислите матрицу В. Решите игру , пользуясь сведениями лекционного курса по теории матричных игр (см. раздел «Краткие сведения из теории матричных игр»). По найденному решению игры постройте решение игры в соответствии с теоремой 7.
   
3. 
   Опыт применения теоремы 7 к решению задачи в случае малого числа позиций l проясняет содержательный смысл этой теоремы. Суть заключается в том, что игра также является математической моделью задачи о распределении фишек, только более сложной конструкции. Игру можно считать непосредственной, очевидной математической моделью. Однако её применение для решения задач практически невозможно при значениях l>3 вследствие быстрого неограниченного роста размеров матрицы А с ростом l. Зато в случае l>3 можно решать задачи, пользуясь математической моделью игры . С ростом числа позиций l размеры матрицы В остаются ограниченными, а при больших значениях l определяются только количеством фишек у игроков. Задача заключается в том, чтобы научиться строить матрицу В минуя этап построения матрицы А. Для этого, опираясь на опыт применения теоремы 7 к решению задачи при малых l, ответьте на следующие вопросы. Как определяется понятие стратегии игрока в математической модели, задаваемой игрой , и в чем заключается применение фиксированной стратегии игроком? В чем состоит содержательный смысл элементов b_ij матрицы В?
   
4. 
   Для решения задачи в случае l>3 вычислите непосредственно матрицу В игры. Задачи подобраны таким образом, чтобы решение игры можно было осуществить аналитическими методами, проявляя умение применять теоремы лекционного курса на практике. Применение компьютерных вычислений для решения игры может понадобиться в редких случаях и проводится по согласованию с руководителем курсовой работы.
   
5. 
   Разъясните физический смысл результатов математического исследования предложенной вам игры. Какой денежный выигрыш предрешен правилами игры каждому игроку? В чем заключается оптимальное поведение каждого игрока, полностью реализующее возможности, предоставленные ему правилами игры?
   

1. 
   Один игрок имеет n фишек, другой – m фишек. Каждый игрок независимо от другого распределяет свои фишки по l позициям. Выигрыш игрока складывается из выигрышей, полученных им на каждой позиции. Если на позиции количество размещенных игроками фишек оказалось одинаковым, то выигрыш каждого игрока – ноль. Игрок, разместивший на позиции большее количество фишек, выигрывает эту позицию и все фишки противника, расположенные на ней. Стоимость позиции и стоимость одной фишки – 1 единица.
   

2. 
   Игрок 1 (нападающий) и игрок 2 (защищающийся) имеют по n фишек, которые независимо друг от друга распределяют между l позициями. Если у нападающего на позиции перевес, то он выигрывает позицию (С ед.), если нет – выигрывает фишки противника, расположенные на этой позиции (по 1 ед. за каждую фишку), если на позицию нет нападения – выигрыш ноль. Нападающий стремится максимизировать свой суммарный выигрыш по всем позициям.
   

1. 
   У каждого из двух игроков имеется своя колода из n карт. Игроки независимо друг от друга метят любое количество карт в своей колоде. После этого каждую колоду тасуют, и игроки наугад выбирают по одной карте из своей колоды. Если меченая карта достанется только одному игроку, он выигрывает два рубля у противника. Если меченые карты достанутся обоим, то два рубля выигрывает тот, кто пометил меньшее число карт. В оставшихся случаях никто никому не платит.
   

2. 
   Из трех карт, занумерованных числами 1, 2, 3, наугад сдают по карте каждому из двух игроков. После этого независимо друг от друга игроки принимают решение «пас» или «вист» на основании своей карты. Если оба пасуют, карты сравнивают, и тот, чья карта больше получает 1 ед. от противника. Если оба вистуют, то владелец большей карты получает 2 ед. от противника. Если один вистует, а другой пасует, то пасующий либо верит и платит 1ед. противнику, либо не верит, тогда карты открывают, и тот, чья карта больше, получает 2 ед. от противника.
   

3. 
   Задача о таможенниках и контрабандистах. Имеется n занумерованных урн, в j-й урне находится l_j белых шаров, j=1, …, n. Игрок 2 распределяет m чёрных шаров (m<l_j) по n урнам, подменяя белые шары чёрными. (Общее число шаров в j-й урне остаётся постоянным и равным l_j). Игрок 1 имеет возможность проверить одну из урн. Проверка заключается в выборе наугад (без возвращения) m шаров из урны. Цель игрока 1 – обнаружить возможно большее число чёрных шаров при многократном повторении игры.
   

4. 
   Каждый из двух игроков независимо выбирает любое из целых чисел от 1 до n. Выигрыш игрока 1 равен выбранному им числу, если это число окажется меньше, чем у игрока 2, в противном случае выигрыш игрока 1 будет в раз меньше (здесь s – число, выбранное игроком 2).
   

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

6. 
   Каждый из двух игроков независимо от другого делает ставку на любое из чисел от 1 до n, которые могут выпасть при раскручивании рулетки. Выигрыш в 1 ед. получает у противника тот, чьё число окажется не меньше числа, выпавшего на рулетке. Если оба загаданных числа удовлетворят этому требованию, то 1 ед. выигрывает тот, кто загадал меньшее число, если загаданные числа совпали, выигрыш в 1 ед. разыгрывают справедливым жребием.
   

7. 
   Игрок 1 имеет к единиц средств наступления. Игрок 2 имеет s единиц средств обороны, . Каждый игрок должен распределить свои средства между n пунктами, не зная решения противника. Каждая единица средств обороны, расположенная в любом из n пунктов, уничтожает одну единицу средств нападения, направленную в этот пункт. Неуничтоженные единицы средств нападения прорываются через этот пункт.
   

8. 
   Каждый из двух игроков независимо выбирает целое число от 1 до n. Игрок 1 стремится увеличить разницу между выбранными числами, а игрок 2 – её уменьшить.
   

9. 
   Каждый из двух игроков выбирает одно из целых чисел от 1 до n, не зная выбора противника. Тот, чьё число окажется на единицу больше, проигрывает два рубля. Тот, чьё число окажется хотя бы на две единицы больше, выигрывает рубль. В случае, когда выбор игроков совпал, никто не платит.
   

10. 
    Один из игроков загадывает любое целое число от 1 до n . Если другой игрок угадает это число с погрешностью, не превосходящей единицу, он выиграет 5 рублей у противника, в противном случае его проигрыш составит один рубль.
    

11. 
    Игрок 2 прячет два предмета в n контейнерах (можно оба в одном). Игрок 1 имеет возможность проверить один из контейнеров. Спрятанный в i -м контейнере предмет игрок 1 обнаруживает с вероятностью p_i>0. Обнаружение различных предметов – независимые события. Составьте и решите матричную игру, отождествляя выигрыш игрока 1 с вероятностью обнаружить хотя бы один предмет.
    

12. 
    Фирма “А” производит сезонный товар, имеющий спрос в течение n единиц времени. Товар поступает на рынок в момент i (i=1,…,n). Для конкурентной борьбы с фирмой “А” дочерняя фирма “В” концерна “D” производит аналогичный товар, который поступает на рынок в момент j (j=1,…,n). Цель фирмы “В” – разорить фирму “А”. Для этого нужно правильно выбрать момент поступления товара на рынок. (Занижать цены нельзя). Потребители предпочитают покупать товар, позже поступивший на рынок. Пусть с – доход от продажи товара в единицу времени.
    

1. 
   Задача линейного программирования в стандартной форме. Теорема о достижении экстремума в крайней точке. Свойства взаимодвойственных задач (без доказательства).
   
2. 
   Антагонистическая игра в нормальной форме. Роль седловой точки в понятии решения антагонистической игры. Матричная игра, ее решение в чистых стратегиях.
   
3. 
   Теорема о необходимых и достаточных условиях существования седловой точки.
   
4. 
   Свойства седловых точек: если - седловые точки, то , и - седловые точки.
   
5. 
   Теорема фон Неймана о достаточных условиях существования седловой точки (без доказательства вспомогательных лемм).
   
6. 
   Докажите выпуклость множества седловых точек в условиях теоремы фон Неймана.
   
7. 
   Докажите лемму: если - непрерывна, а , - компакты, то , - непрерывны.
   
8. 
   Докажите лемму: если - непрерывна и строго выпукла по y при любом фиксированном х, - компакт, - выпуклый компакт, то функция непрерывна на Х, где .
   
9. 
   Смешанное расширение матричной игры. Теорема о существовании решения.
   
10. 
    Докажите, что при фиксированной стратегии одного из игроков, экстремум функции выигрыша достигается на чистой стратегии другого игрока (теорема 2,§3).
    
11. 
    Докажите неравенство: .
    
12. 
    Докажите, что , , где v – цена игры.
    
13. 
    Необходимые и достаточные условия оптимальности ситуации в матричной игре (следствия 5, 6 из §3).
    
14. 
    Арифметические преобразования матрицы игры.
    
15. 
    Теорема равновесия (любая существенная стратегия одного из игроков уравновешивает все оптимальные стратегии другого) и следствие из нее.
    
16. 
    Теорема о кососимметричной игре.
    
17. 
    Теорема о доминировании (для матрицы игры).
    
18. 
    Докажите, что чистая стратегия игрока 1 доминируема тогда и только тогда, когда доминируется соответствующая строка в матрице выигрышей.
    
19. 
    Докажите, что существенная стратегия строго недоминируема.
    
20. 
    Докажите, что стратегия, доминирующая оптимальную, сама оптимальна.
    
21. 
    Докажите, что оптимальная стратегия строго недоминируема.
    
22. 
    Теорема о связи матричных игр и линейного программирования.
    
23. 
    Теорема Куна-Таккера в линейном программировании.
    

24. 
    Бескоалиционная игра. Равновесие по Нэшу, оптимальность по Парето. Сравнительный анализ свойств равновесной по Нэшу ситуации в антагонистической игре и в бескоалиционной игре n лиц.
    
25. 
    Равновесие по Штакельбергу в игре двух лиц. Теорема о борьбе за лидерство.
    
26. 
    Свойства ситуации равновесия в смешанных стратегиях в биматричной игре.
    
27. 
    Кооперативная игра. Делёж. Определение и смысл С-ядра существенной игры. Разбиение множества всех игр на классы эквивалентных игр.
    
28. 
    Теорема об эквивалентности существенной игры некоторой игре в 0-1 редуцированной форме. Взаимно-однозначное соответствие между множествами дележей в эквивалентных играх.
    
29. 
    Строение С-ядра в 0-1 игре трех лиц. Геометрическая интерпретация. Необходимые и достаточные условия непустоты С-ядра.
    

30. 
    Теорема о существовании и единственности вектора Шепли для любой кооперативной игры.
    
31. 
    Решение игры о распределении ресурсов: .
    

9Учебно-методическое и информационное обеспечение дисциплины

1. 
   Л.А. Петросян, Н.А. Зенкевич, Е.А. Семина «Теория игр», М. Высшая школа, 1998.
   
2. 
   Э.Г. Давыдов «Исследование операций», М. Высшая школа, 1990.
   
3. 
   А.А.Васин, П.С.Краснощеков, В.В.Морозов «Исследование операций», М. Академия, 2008.
   
4. 
   В.В. Морозов, А.Г. Сухарев, В.В. Федоров «Исследование операций в задачах и упражнениях», М. Высшая школа, 1986.
   

1. 
   Э. Мулен «Кооперативное принятие решений: аксиомы и модели», М. Мир, 1991.
   
2. 
   В.А.Колемаев «Математические методы и модели исследования операций», М. Юнити, 2008.
   
3. 
   С. Карлин «Математические методы в теории игр, программировании и экономике», М. Мир, 1964.
   
4. 
   Г. Оуэн «Теория игр», М. Мир, 1971.
   
5. 
   Г.Н. Дюбин, В.Г. Суздаль «Введение в прикладную теорию игр», М. Наука, 1981.
   
6. 
   Е. С. Вентцель «Исследование операций. Задачи, принципы, методология», М. Высшая школа, 2000.
   
7. 
   Н.Н. Воробьев «Теория игр для экономистов-кибернетиков», М. Наука, 1985.