WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |
Министерство образования Республики Беларусь УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ Рецензенты: кандидат физико-математических наук, доцент кафед«ГРОДНЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ры технической механики и материаловедения ГГАУ ИМЕНИ ЯНКИ КУПАЛЫ» А.А.Денисковец;

кандидат физико-математических наук, доцент кафедры дифференциальных уравнений и оптимального управления ГрГУ им. Я.Купалы В.И.Булгаков.

Рекомендовано советом факультета математики и информатики ГрГУ им. Я.Купалы.

Пчельник В.К.

Исследование операций: методические рекомендации/ В.К. ПЧЕЛЬНИК, И.Н. РЕВЧУК, В.К.Пчельник, И.Н.Ревчук, – Гродно: ГрГУ им. Я.Купалы, 2010. — 104 с.

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ Методические рекомендации для студентов заочного отделения специальности 1-31 03 01-02 «Математика» В методических рекомендациях содержится краткий теоретический материал, примеры решения задач и задания для самостоятельной работы по следующим разделам курса «Исследование операций»: теория игр, теория графов, календарное планирование, расчет временных параметров сетевого графика, имитационное моделирование. Показаны возможности использования электронных таблиц MS EXCEL для решения указанных типов задач.

Гродно 2010 В i Bn B1 B2 … А 1. Теория игр a1n i A1 a11 a12 … Рассмотрим игру двух лиц А и В с противоположными a2n 2 A2 a21 a22 … интересами. Будем обозначать стратегии игрока А через … … … … … … А1, А2,..., Аm, а стратегии игрока В - B1, B,..., B (игра 2 n Am am1 am2 amn m … m n ). Пусть игра состоит только из личных ходов. Тогда выбор стратегий Аi, B однозначно определяет исход игры.

j n 1 2 … j Пусть также известны значения aij выигрыша при каждой Рисунок 2 паре стратегий. Значения aij удобно записать в виде прямоДоказано, что каждая конечная игра имеет, по крайней мере, одно решение (возможно, в области смешанных стратеугольной матрицы, строки которой соответствуют стратегигий). Следовательно, цена игры удовлетворяет соотношеям игрока А, а столбцы – стратегиям игрока В. Такую матринию. Задача состоит в том, чтобы найти две опцу называют платежной матрицей (рис. 1).

тимальные смешанные стратегии игроков A и В В Bn B1 B2 … А A1 A2... Am * B1 B... B 2 n * S = A, S B = q1 q... q, a1n A1 a11 a12 … p1 p... p 2 m 2 n a2n A2 a21 a22 … где p1 + p +... + p = 1, q1 + q +... + q = 1. Опти2 m 2 n … … … … … * мальная стратегия S должна обеспечить игроку А выигAm am1 am2 amn … A рыш, не меньший, а игроку В - проигрыш, не больший.

Рисунок Величина неизвестна, но, по крайней мере, равна некотоЦель теории игр - дать рекомендации разумного поверому положительному числу.

дения игроков в конфликтных ситуациях, то есть, в выработке оптимальной стратегии каждого из них. Оптимальной Если игрок А выбрал свою оптимальную смешанную стратегией считается такая стратегия, которая при много* стратегию S, то его средний выигрыш при оптимальной кратном повторении игры дает игроку максимально возмож- A ный средний выигрыш (или, что то же самое, минимально стратегии B игрока В равен = p1a1 j + p2a2 j +... + pmamj.

j j возможный средний проигрыш). Пусть = min a, i ij j * Оптимальная стратегия S игрока А обладает тем свойстA = max, = max a, = min. Величина наi j ij j i i j вом, что при любом поведении игрока В гарантирует ему вызывается нижней ценой игры, а - верхней ценой игры.

игрыш, не меньший. Следовательно, имеет место система (1.1).

3 тоженный полк противника (эта игра называется игрой полp1 a11 + p a +... + p a, 2 21 m mковника Блотто). Предположим, что у Блотто в наличии три p1 a12 + p a +... + p a, 2 22 m mполка, а у его противника – 2 полка. Найти решение игры.

(1.1)..............................................

Решение. Составим вначале платежную матрицу игры.

Пусть Блотто – это игрок А, а его противник – игрок В. У p1 a1n + p a +... + p a.

2 2n m mn Блотто 4 чистые стратегии:

Разделив каждое неравенство системы (1.1) на положитель- 1) послать 3 полка на пункт и 0 полков – на пункт. Обоное число и введя обозначения (1.2), получим систему (1.3). значим эту стратегию через (3, 0);

2) послать 2 полка на пункт и 1 полк – на пункт – (2, 1);

p1 p12 p m 3) послать 1 полк на пункт и 2 полка – на пункт – (1, 2);

(1.2) =, =,..., =, 1 2 m 4) послать 0 полков на пункт и 3 полка – на пункт – (0, 3).

a11 + a +... + a 1, 1 21 2 m1 m У игрока 2 три чистые стратегии: (2, 0), (1, 1) и (0, 2). На риa + a +... + a 1, сунке 3 приведена платежная матрица игры.

12 1 22 2 m2 m (1.3)..............................................

(2, 0) (1, 1) (0, 2).

(3, 0) 3 1 a1n 1 + a 2n 2 +... + a mn m 1, (2, 1) 1 2 -(1, 2) -1 2 В системе (1.3),,..., - неотрицательные числа. По1 2 m (0, 3) 0 1 скольку p1 + p +... + p = 1, то,,..., удовлетво2 m 1 2 m Рисунок Поясним построение элементов платежной матрицы.

ряют условию + +...,+ =. Следовательно, для 1 2 m Элемент a11 = 3, так как на пункт Блотто посылает 3 полка, нахождения решения игры следует определить неотрицаа его противник – 2. По условию, Блотто уничтожает 2 полка тельные значения,,...,, удовлетворяющие условиям 1 2 m противника, получая при этом 2 единицы и дополнительную (1.3), так, чтобы их сумма L = + +...,+ была ми1 2 m единицу за захват пункта. В пункте нет войск, поэтому в нимальной. При этом мы получили задачу линейного проитоге a11 = 2 +1. Элемент a12 =1, так как на пункт Блотто граммирования.

посылает 3 полка, а его противник – 1 полк. Блотто уничтоПример 1. Два противника ведут борьбу за два стратежает этот полк, получая при этом единицу выигрыша и еще гических пункта. Исход борьбы за пункт в конечном итоге одну единицу - за захват пункта. На пункт Блотто не поопределяется количеством ресурсов, которые используют на сылает войск, а его противник посылает 1 полк и получает данном пункте соперники. Переброска ресурсов производитединицу за захват пункта. При этом Блотто теряет единицу ся скрытно. Армия, которая посылает больше полков на тот выигрыша. В сумме выигрыш Блотто составляет или иной пункт, занимает его и уничтожает все силы противa12 = 2 -1 =1. Остальные элементы платежной матрицы выника в этом пункте. Игрок при этом получает единицу выигчисляются аналогично (рис. 4).



рыша за захват пункта и по одной единице за каждый унич 5 рисунке 7 приведены используемые формулы, а на рисунке - окно диалога надстройки.

Рисунок Рисунок Решим игру приведением к задаче линейного программирования. Для обеспечения условия >0 ( – цена игры) увеличим элементы матрицы платежей на 1. Тогда все ее элементы станут неотрицательными. Новая матрица игры теперь имеет вид как на рисунке 5.

Рисунок 4 2 2 3 A* =.

0 3 1 2 Рисунок Сформулируем соответствующую задачу линейного программирования (1.4).

L = pi min i=4 p1 + 2 p2 + p4 1, (1.4) 2 p1 + 3p2 + 3p3 + 2 p4 1, p1 + 2 p3 + 4 p4 1, pi 0 i = 1,4.

Рисунок На рисунке 9 приведен результат работы надстройки.

Оптимальное решение задачи линейного программирования:

Для решения задачи воспользуемся надстройкой «По* p1 = 7 / 33, p2 = 0, p3 = 1/11, p4 = 5/ 33. Цена игры с иск решения». Разместим данные так, как на рисунке 6. На 7 * платежной матрицей A определяется из соотношения * * 1/ L =, откуда = 11/ 5. Тогда оптимальные стратегии первого игрока определяются так:

* x1 = p1 * = 7 / 33*11/ 5 = 7 /15, * x2 = p2 * = 0, * x3 = p3 * = 1/11*11/ 5 = 1/ 5, * x4 = p4 * = 5 / 33*11/ 5 = 1/ 3. Рисунок Следовательно, A1 A2 А3. A4 B1 B2 B, * S* = 7 1 1 SB = 1 3 1.

A 15 5 3 5 5 Это означает, что полковник Блотто с вероятностью 7/15 использует первую чистую стратегию, с вероятностью Рисунок 1/5 - свою третью чистую стратегию и с вероятностью 1/3 - Цена игры с исходной матрицей А определяется как свою четвертую чистую стратегию. При этом в среднем за * игру Блотто выигрывает 6/5 единиц у своего противника.

= -1 = 11/ 5 -1 = 6 / 5.

Оптимальную стратегию второго игрока можно найти, Задачи для самостоятельного решения решив задачу (1.5).

В задачах 1-11 построить математическую модель как матричную игру и решить ее, используя симплекс-метод или Z = q max j надстройку «Поиск решения».

j = 1. Найти решение игры полковника Блотто, если против4q + 2q + q 1, ники располагают двумя и четырьмя полками 1 2 соответственно.

(1.5) 2q1 + 3q 1, 2 2. Решить игру полковника Блотто, изменив условие сле дующим образом: за захват пункта игрок получает 2 единицы 3q + 2q 1, 2 выигрыша. Игроки располагают двумя полками против трех.

q + 2q + 4q 1, 1 2 3. Решить игру полковника Блотто, изменив условие сле q 0 j = 1,3.

дующим образом: если за пункт сражается одинаковое колиj чество полков, то с вероятностью р полковник Блотто занимает пункт. Число полков равно 2 и 3 соответственно.

На рисунке 10 показан результат работы надстройки «Поиск решения» и оптимальные стратегии второго игрока.

9 4. Игра в прятки. Игрок I прячется в одной из клеток мат- скоростью, каждая в одном из двух возможных направлений вдоль стены дома. У кошки поврежден левый глаз, и когда рицы размерности m n. Если игрок II угадывает номер стромышка появляется слева, то она имеет возможность убежать.

ки i или столбца j, в которой находится игрок I, то игрок I Поэтому если кошка бежит направо, а мышь вниз, то мышь проигрывает pij единиц. В противном случае игрок II выплаоказывается слева и теряет А единиц. Если кошка бежит чивает qij единиц. Положить m=n=2, вверх, а мышь - налево, то мышь теряет В единиц (В>A).

2 3 3 P =, Q =.

1 4 2 5. Решить игру в прятки, изменив условие следующим образом: игрок II выбирает только строки. Использовать числовые данные предыдущей задачи.

6. Опознавание самолета. Самолеты, приближаясь к воздушной базе, должны подавать сигнал наблюдателю, нахоРисунок дящемуся на базе, независимо от того, являются ли они своими или неприятельскими. На основании сигнала наблюда10. Решить предыдущую задачу с измененным условием:

тель должен решить, какой стороне, своей или неприятельесли кошка и мышь встречаются, то кошка теряет С единиц.

ской принадлежит самолет. Пусть выигрыш равен А, если Положить В=3, А=2, С=1.

наблюдатель признает своего за своего; B, если наблюдатель 11. Два производственных объединения выпускают пропризнает своего за неприятеля; С, если наблюдатель признает дукцию одного вида. Сбыт продукции зависит от затрат на неприятеля за своего; D, если наблюдатель признает неприрекламу. Объединение А имеет возможность потратить на ятеля за неприятеля. Здесь A>B, A>D, C>B,C>D.

эти цели 20, либо 50, либо 100 денежных единиц, а объедиСвой всегда подает сигнал «свой». Неприятель может нение В - либо 5, либо 15 единиц. Матрица Р задает дополподавать сигналы «свой» либо «неприятель». Известно, что нительные прибыли предприятия А, которое оно получит за самолет свой с вероятностью р.

счет потерь предприятия В.

7. Два человека играют в следующую игру. Каждый пока-10 - зывает 1 или 2 пальца и одновременно называет число паль P = 5 - 20.





цев, которое, по его мнению, показывает противник. Если один из игроков угадал, то он получает выигрыш, равный -1 сумме пальцев, показанных им и его противником, иначе - В задачах 12-16 построить математическую модель игничья.

ры двух лиц с нулевой суммой. Необходимую дополнитель8. Решить предыдущую задачу при условии, что первый ную информацию ввести самостоятельно.

игрок показывает 1, 2 или 3 пальца.

12. В задаче 7 изменить условие следующим образом: каж9. Одноглазая кошка. Кошка и мышь находятся в противодый игрок записывает произвольное рациональное число из положных углах дома, имеющего в проекции вид квадрата отрезка [1, 2].

(рис. 11). Они начинают бежать одновременно с одинаковой 11 13. В задаче 11 считать, что предприятие А имеет возмож- X = {x1, x2, x3, x4}, ность затратить на рекламу от 20 до 100 единиц, а предприA = {a1 = (x1, x2 ), a2 = ятие В - от 5 до 15 единиц.

(x1, x3 ), a3 = (x3, x4 ), 14. Шумная дуэль. Два игрока стреляют друг в друга из пистолетов. Каждый из них имеет право на один выстрел.

a4 = (x3, x2 )}.

Первоначально они находятся на расстоянии а друг от друга и по сигналу начинают сходиться. Вероятность ожидания b Рисунок противника зависит от расстояния до него. Каждый игрок Граф можно задать матрицами смежности и инцизнает, сделал ли выстрел противник.

дентности. Элементы матрицы смежности S графа 15. Бесшумная дуэль. В предыдущей задаче игроки не зназадаются как:

ют, сделал ли выстрел противник.

если существует ребро (дуга), соединяющее 16. Смешанная дуэль. В задаче 14 один игрок может опре1, вершины хi и xj;

s = делить, выстрелил ли противник, а второй - не может.

ij в противном случае.

2. Теория графов (i, j=1, 2,…, n).

2.1. Основные определения Элементы матрицы инцидентности U = u ij m n Графом G = (X, А) называется пара объектов для графа G, состоящего из n вершин и m дуг, X = {x1, x2, …, xn} и А = {a1, a2, …, am}, где X – множество определяются как:

вершин, а A – множество ребер графа. Если ребра из множе1, если вершина хi - начало дуги aj;

ства A ориентированы, то они называются дугами, а граф на-1, если вершина хi - конец дуги aj;

uij = зывают ориентированным. Если ребра не имеют ориентации, 0, если вершина хi не инцидентна дуге aj то граф называют неориентированным. В противном случае граф является смешанным. На рисунках 12–13 приведены (i=1, 2,…,n; j=1, 2,…, m).

неориентированный и ориентированный графы соответственно.

Если граф содержит петли, то есть дуги вида (хi, xi) то элементы матрицы инцидентности, соответствующие дугам, образующим петли, одновременно равны 1 и –1, что привоX = {x1, x2, x3, x4}, дит к неоднозначности матрицы инцидентности.

A = {a1, a2, a3, a4}.

Пусть G – неориентированный граф. Маршрутом в графе G называется такая последовательность (конечная или бесконечная) ребер a1, a2,... an..., что каждые два соседних ребра ai и ai+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В Рисунок конечном маршруте (a1, a2,... an) имеется первое ребро a1 и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вер 13 шина xn, инцидентная ребру an, но не инцидентная ребру an-1, Понятиям ребра, маршрута, цикла в неориентированназывается концом маршрута. ном графе соответствуют понятия дуги, пути и контура в ориентированном графе.

Длиной маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, скольНеориентированный граф Ориентированный граф ко оно входит в данный маршрут.

дуга ребро Замкнутый маршрут называется циклом.

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

вершин может быть соединена, по крайней мере, одной На рисунке 14 изображены два маршрута из вершины цепью.

x1 в вершину x4: M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6). Длина Ориентированный граф называется нагруженным, если дугам этого графа поставлены в соответствие веса, так маршрута M1 равна 3, а длина маршрута M2 равна 4.

что дуге (xi,xj) сопоставлено некоторое число c(xi, xj) = cij, наПонятия пути и контура в ориентированном графе аназываемое длиной (или весом, или стоимостью дуги). Длиной логичны понятиям маршрута и цикла в неориентированном (весом или стоимостью) пути s, состоящего из некоторой графе.

последовательности дуг (xi, xj), называется число l(s), равное Путем в ориентированном графе называется последосумме длин дуг, входящих в этот путь, т.е.

вательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной слеl(s) =, c ij дующей дуги.

причем суммирование ведется по всем дугам (xi, xj) s.

Матрица C = (cij) называется матрицей длин дуг или матрицей весов.

Подграфом неориентированного графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа. Аналогично определяется Рисунок подграф ориентированного графа.

Компонентой связности неориентированного графа Число дуг пути называется длиной пути.

Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.