Рабочая тетрадь ТИ. РанхиГС
 Скачать 0.89 Mb.
|
|
3. Швейное предприятие шьет два вида изделий : шапки из меха и фуражки из ткани Сбыт зависит от состояния погоды осенью По данным наблюдений прошлых лет , в условиях теплой осени предприятие может реализовать 200 шапок и 800 фуражек , а при холодной 300 шапок и 270 фуражек Известно , что затраты на пошив шапок и фуражек соответственно составили 120 и 20 рублей Цена реализации одной шапки 210, фуражки – 30 рублей Определить оптимальную стратегию предприятия , обеспечивающую при любой погоде гарантированную среднюю прибыль 4. Администрация и сотрудники предприятия совместно разработали несколько различных вариантов оплаты труда в зависимости от видов работы и социальных льгот по каждому виду работы Эти варианты представлены в таблице ( руб ./ ч .): Виды социальных льгот 1 2 3 4 Работы , выполняемые сотрудниками 1 75 105 65 45 2 70 60 55 40 3 80 90 35 50 4 95 100 50 55 Предложите компромиссный вариант вида выполняемых работ и предоставляемых социальных льгот Какова величина оплаты труда при таком варианте ? 1.5. РЕШЕНИЕ МАТРИЧНЫХ ИГР В СМЕШАННЫХ СТРАТЕГИЯХ 2 х n Пусть платежная матрица игры 2 х n имеет вид : - 1 B 2 B … n B 1 A 11 a 12 a … n a 1 2 A 21 a 22 a … n a 2 У игрока A - две стратегии , у игрока B - n стратегий Задача такой размерности может быть решена в два этапа : 19 1. Графически для игрока A ( игрок с двумя стратегиями ). 2. Аналитически для игрока B ( игрок с множеством стратегий ). Алгоритм решения рассмотрим на примере Пример 5. Найти решение игры заданной матрицей : - 1 B 2 B 3 B 4 B 1 A 2 2 3 -1 2 A 4 3 2 6 Решение Найдем сначала решение игры с позиции игрока , имеющего две стратегии Пусть 1 x и 2 x - частоты применения игроком A своих первой и второй стратегий соответственно , ν - цена игры Из определения смешанной стратегии следует , что игрок A придерживающийся своей оптимальной смешанной стратегии , выигрывает не менее ν при любых стратегиях игрока B Учитывая последнее утверждение , можно записать систему : ≥ + − ≥ + ≥ + ≥ + = + ν ν ν ν 2 1 2 1 2 1 2 1 2 1 6 2 3 3 2 4 2 1 x x x x x x x x x x Разделим все уравнения и неравенства данной системы на ν и введем обозначения 1 1 t x = ν , 2 2 t x = ν , ν 1 = Z Тогда система примет вид : ≥ + − ≥ + ≥ + ≥ + + = 1 6 1 2 3 1 3 2 1 4 2 2 1 2 2 2 1 2 1 2 1 t t t t t t t t t t Z Так как игрок A стремится максимизировать цену ν выбором значений 1 x и 2 x , то обратная величина ν 1 должна минимизироваться выбором значений 1 t и 2 t Таким образом решение задачи с позиции игрока A сводится к нахождению таких неотрицательных 1 t и 2 t при которых 0 1 6 1 2 3 1 3 2 1 4 2 min 2 , 1 2 1 2 2 2 1 2 1 2 1 ≥ ≥ + − ≥ + ≥ + ≥ + → + = t t t t t t t t t t t Z (*). Таким образом получена задача линейного программирования (*). В случае двух переменных ее можно решить графическим методом Для этого надо выполнить следующее : 1. Заменить все неравенства системы (*) равенствами и построить полученные прямые на графике 20 2. Каждая прямая делит плоскость на две части , одна из которых является решением соответствующего неравенства системы Чтобы определить полуплоскость решения для каждой прямой следует взять точку , не лежащую на ней и подставить в соответствующее неравенство 3. В результате построения прямых по системе (*) и определения полуплоскостей решения будет получена область допустимых решений ( рис .). 4. Из коэффициентов целевой функции Z составить вектор ( ) 1 ; 1 → n Учитывая масштаб рисунка можно построить пропорциональный вектор ( ) 2 , 0 ; 2 , 0 → n Вектор показывает направление возрастания целевой функции 5. Двигаясь по области допустимых решений в направлении , противоположном направлению вектора нормали можно найти минимальное значение целевой функции На рисунке минимальное значение целевой функции будет достигнуто в точке * X 6. Точка * X является пересечением прямых (3) и (4). Чтобы найти ее координаты надо составить систему из их уравнений и решить ее : ⇒ + = − = 6 1 2 3 1 1 2 1 2 t t t t 5 1 1 = t , 5 1 2 = t 7. Найдем минимальное значение целевой функции : 5 2 5 1 5 1 2 1 = + = + = t t Z Тогда цена игры обратная величина : 5 , 2 2 5 = = ν 8. Определим оптимальную стратегию Так как 1 1 t x = ν и 2 2 t x = ν , то 2 1 5 1 2 5 1 1 = ⋅ = ⋅ = t x ν и 2 1 5 1 2 5 2 2 = ⋅ = ⋅ = t x ν Получена оптимальная стратегия игрока A : = ∗ 2 1 ; 2 1 X 9. Прямые линии , на пересечении которых находится точка ∗ X , соответствуют активным стратегиям , остальные стратегии являются пассивными Далее для игрока B решаем задачу 2 х 2 со стратегиями 3 B и 4 B , исключив пассивные стратегии 21 Аналогично решаются задачи m х 2. Задания для работы в аудитории 1. Прибыль сельскохозяйственного предприятия ( млн руб .) от выращивания двух культур в зависимости от состояния погоды представлена в таблице : Лето Засушливое Нормальное Дождливое Вид культуры 1 8 5 3 2 2 3 6 Определите оптимальный план посева культур 22 2. В системе противовоздушной обороны ( ПВО ) города могут применяться три типа средств поражения воздушной цели У противника имеется два типа самолетов Вероятности поражения самолета средством ПВО определяются матрицей : Самолет 1 2 Средства ПВО 1 0,3 0,5 2 0,5 0,3 3 0,1 0,6 Определить оптимальное распределение средств ПВО , обеспечивающее наибольшую вероятность поражения самолетов противника 23 1.6. РЕШЕНИЕ МАТРИЧНЫХ ИГР В СМЕШАННЫХ СТРАТЕГИЯХ m х n Решение матричной игры m х n может быть найдено методом последовательных приближений Брауна - Робинсон Платежная матрица имеет вид : − − − = 5 4 2 3 2 5 6 1 1 А Найдем нижнюю и верхнюю цену игры , определим наличие седловой точки − − − 5 4 2 3 2 5 6 1 1 -1 -3 α = –1 -2 5 4 6 β = 4 Так как α ≠ β , то седловой точки нет Допустим игрок А воспользуется своей минимаксной стратегией А 1, тогда возможные проигрыши второго игрока –1, 1, 6. В этом случае игроку В выгодно использовать свою стратегию В 1, поскольку проигрыш составит –1 ( т е он выигрывает 1). Для стратегии В 1 возможные выигрыши игрока А : –1, 5, –2. Теперь выгодной для игрока А является стратегия А 2 с выигрышем 5. Сведем эту информацию в таблицу : Номер партии Стратегия первого игрока Возможные проигрыши второго игрока Стратегия второго игрока Возможные выигрыши первого игрока ν ν ν В 1 В 2 В 3 А 1 А 2 А 3 1 1 –1 1 6 1 –1 5 –2 –1 5 2 2 2 В столбце ν находится наименьший средний выигрыш –1, полученный вторым игроком в первой партии ; в столбце ν стоит наибольший средний выигрыш 5 первого игрока ; в столбце ν находится среднее арифметическое 2 ) 5 1 ( 2 1 = + − = ν , т е приближенное значение цены игры , полученное в результате проигрывания одной партии игры Рассуждая аналогично далее , получаем : во второй партии игрок А играет стратегией А 2, которая соответствует наибольшему выигрышу 5 и соответственные проигрыши игрока В равны 5, 2, –3. Суммарные проигрыши игрока В составят : –1 + 5 = 4 – при его первой стратегии , 1 + 2 = 3 – при его второй стратегии , 6 – 3 = 3 – при его третьей стратегии Эти суммарные проигрыши записываются во второй строке таблицы Из всех суммарных проигрышей наименьшим является 3. Он получается при 2- й и 3- й стратегиях игрока В , следовательно , в этой партии он должен выбрать стратегию В 2 ( когда имеются два или несколько одинаковых суммарных проигрышей ( выигрышей ) выбирают стратегию с наименьшим номером ). При стратегии В 2 первый выиграет 1, 2, 4, а суммарный выигрыш игрока А за обе партии составит : –1 + 1 = 0 при его 1- й стратегии , 5 + 2 = 7 при его 2- й стратегии , 24 –2 + 4 = 2 при его 3- й стратегии Эти суммарные выигрыши записываются во второй строке таблицы : Номер партии Стратегия первого игрока Возможные проигрыши второго игрока Стратегия второго игрока Возможные выигрыши первого игрока ν ν ν В 1 В 2 В 3 А 1 А 2 А 3 1 1 –1 1 6 1 –1 5 –2 –1 5 2 2 2 4 3 3 2 0 7 2 3/2 7/2 5/2 3 2 Из всех суммарных выигрышей первого игрока наибольшим является 7. Он получается при его второй стратегии , следовательно , в третью партию первый игрок должен применить свою 2- ю стратегию В столбец ν ставится наименьший суммарный проигрыш второго игрока за две партии , деленный на число партий , т е 2 3 ; в столбец ν ставится наибольший суммарный выигрыш первого игрока за две партии , деленный на число партий , т е 2 7 ; в столбец ν ставится среднее арифметическое этих значений , т е 2 5 2 7 2 3 2 1 = + = ν Это число 2 5 принимается за приближенное значение цены игры при двух « сыгранных » партиях Продолжая этот процесс далее , составим таблицу партий до 20- й включительно : Номер партии Стратегия первого игрока Возможные проигрыши второго игрока Стратегия второго игрока Возможные выигрыши первого игрока ν ν ν В 1 В 2 В 3 А 1 А 2 А 3 1 1 –1 1 6 1 –1 5 –2 –1 5 2 2 2 4 3 3 2 0 7 2 3/2 7/2 5/2 3 2 9 5 0 3 6 4 7 0/3 7/3 7/6 4 3 7 9 5 3 12 1 12 5/4 12/4 17/8 5 1 6 10 11 1 11 6 10 6/5 11/5 17/10 6 1 5 11 17 1 10 11 8 5/6 11/6 16/12 7 2 10 13 14 1 9 16 6 10/7 16/7 26/14 8 2 15 15 11 3 15 13 11 11/8 15/8 26/16 9 1 14 16 17 1 14 18 9 14/9 18/9 32/18 10 2 19 18 14 3 20 15 14 14/10 20/10 34/20 11 1 18 19 20 1 19 20 12 18/11 20/11 38/22 12 2 23 21 17 3 25 17 17 17/12 25/12 42/24 13 1 22 22 23 1 24 22 15 22/13 24/13 46/26 14 1 21 23 29 1 23 27 13 21/14 27/14 48/28 15 2 26 25 26 2 24 29 17 25/15 29/15 54/30 16 2 31 27 23 3 30 26 22 23/16 30/16 53/32 17 1 30 28 29 2 31 28 26 29/17 31/17 60/34 18 1 29 29 35 1 30 33 24 29/18 33/18 62/36 19 2 34 31 32 2 31 35 28 31/19 35/19 66/38 20 2 39 33 29 3 37 32 33 30/20 37/20 67/40 Из последней таблицы видно , что в 20- ти проигранных партиях смешанная стратегия игрока А имеет вид : Х *(9/20;10/20;1/20) или Х *(0,45; 0,5; 0,05); стратегия игрока В имеет вид : Y*(9/20;4/20;7/20) или Y*(0,45; 0,2; 0,35); цена игры ν =67/40=1,675. 25 Ответ : Х *(0,45; 0,5; 0,05), Y*(0,45; 0,2; 0,35), ν =1,675. Задания для решения в аудитории 1. Две конкурирующие компании A и B принимают решение о финансировании трех инновационных проектов Каждая компания может инвестировать 100 ден ед Компания B пытается занять рынок , на котором традиционно компания A лидирует В случае разработки и развития одних и тех же проектов компания A получит прибыль , тогда компания B понесет убыток Если инвестиции направляются в разные проекты , компания A понесет убытки , связанные с перераспределением рынка Прибыль предприятия A при разных стратегических ситуациях представлена в таблице Прибыль предприятия B соответствует убытку предприятия A. Найти оптимальные стратегии предприятий ( выполнить десять итераций ). B1 B2 B3 A1 20 -15 -10 A2 -5 10 0 A3 -20 -10 30 26 1.7. СТАТИСТИЧЕСКИЕ ИГРЫ ИЛИ « ИГРЫ С ПРИРОДОЙ » Часто принятие управленческих решений предполагает наличие ситуаций выбора наиболее выгодного варианта поведения из нескольких имеющихся вариантов в условиях неопределённости В этом случае противником игрока ( лица , принимающего решения – ЛПР ) является некоторая объективная действительность , которую принято называть природой . Игра с природой ( статистическая игра ) – это парная матричная игра , в которой сознательный игрок А ( статистик ) выступает против участника , совершенно безразличного к результату игры , называемого природой Объективно система ( природа , окружающая среда ) не заинтересована в проигрыше игрока В процессе принятия решения о выборе варианта поведения игрок имеет информацию о том , что окружающая среда может принять одно из нескольких возможных состояний и сталкивается с неопределённостью относительно того конкретного состояния , которое примет окружающая среда в данный момент времени В общем виде платёжная матрица статистической игры имеет вид : 1 S 2 S … n S 1 A 11 a 12 a … n a 1 2 A 21 a 22 a … n a 2 .… … m A 1 m a 2 m a … mn a В данной игре строки матрицы (A i ) - стратегии ЛПР , а столбцы матрицы (S j ) – состояния окружающей среды Будем считать , что элементы платежной матрицы имеют смысл дохода , то есть чем больше значение , тем лучше для игрока А Хотя в некоторых ситуациях они могут иметь обратный смысл , тогда рассуждения , приведенные ниже , нужно поменять соответствующим образом Начинать анализ платежной матрицы следует с определения « заведомо невыгодных » стратегий игрока А ( доминируемых ), которые исключаются из платежной матрицы Удалять доминируемые стратегии – состояния окружающей среды нельзя , так как они принципиально не могут быть выгодными или невыгодными Нецелесообразно решать такую игру методами решения антагонистических игр , определяя смешанную стратегию игрока А Здесь качественно другая ситуация Поэтому решением является чистая стратегия игрока А , которая определяется с помощью критериев принятия решения На практике часто применяются следующие критерии : Байеса ( максимального математического ожидания выигрыша ), недостаточного основания Лапласа , максиминный критерий Вальда , пессимизма - оптимизма Гурвица , Ходжа - Лемана , минимаксого риска Сэвиджа Согласно каждому критерию всем стратегиям игрока А ставится в соответствие некоторое число W i , среди которых выбирается « наилучшее » в смысле используемого критерия , этому числу соответствует оптимальная стратегия игрока К сожалению , не существует общих правил оценки практической применимости того или иного критерия при принятии решений в условиях неопределенности Скорее всего , это связано с тем , что поведение ЛПР , обусловленное неопределенностью ситуации , по всей видимости , является наиболее важным фактором при выборе подходящего критерия |