- •1.1. Введение.
- •1.2. Оптимизационные задачи в 2.
- •1.4. Понятие о nр-полноте.
- •Условие целочисленности решения задачи лп.
- •Критерий полной унимодулярности.
- •Задача о назначениях.
- •Задача коммивояжера.
- •2. Принятие решений и элементы теории игр.
- •2.1. Задачи многокритериальной оптимизации.
- •2.3. Игры.
- •Дележи.
- •3. Сетевые модели.
- •3.1. Способы задания графов.
- •3.2. Изоморфизм графов.
- •Поиск простейших узких мест графа за o(|e|).
- •3.3. Остовные деревья.
- •Описание алгоритма Прима:
- •Корректность алгоритма Прима.
- •3.4. Кратчайшие пути в графах. Волновой алгоритм построения дкп (Дейкстра)
- •Нахождение кратчайшего пути для ациклического орграфа
- •3.5. Потоковые задачи Задача о максимальном потоке (змп).
- •На входе: матрицы а –пропускных способностей, и c – цен, c ij 0 - стоимость пропуска единицы потока по ребру (I,j), f0 - ограничение на величину потока.
- •3.6. Приближенное решение np-полных задач.
- •Задача о максимальной клике.
- •3.7. Точные методы решения np-полных задач.
- •4. Элементы теории массового обслуживания.
- •4.1. Пуассоновский поток событий
- •4.2. Моделирование простейшего потока.
- •4.3. Процессы гибели и размножения.
- •Классификация систем массового обслуживания:
- •4.4. Открытая система м | м | 1 (один врач).
- •4.5. Замкнутые системы с резервированием. Будем различать горячий и холодный резервы, т.Е. Исправные, но включенные или выключенные приборы.
- •4.6. Задачи проектирования сетей технического обслуживания.
- •3.5. Алгоритм Тарьяна (для планарных графов мод строится за o(n)).
Ярославский государственный университет
Кафедра компьютерной безопасности и математических методов обработки информации
Фокин В.Г.
ТЕОРИЯ ИГР
И
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Модели, алгоритмы, сложность.
Конспект лекций
Ярославль, 2006
Хотели как лучше, а получилось как всегда.
Виктор Черномырдин, премьер России в 1994-1998гг
1.1. Введение.
Термин исследование операций возник в 30-е годы ХХ века как название подразделения британских ВВС, занимавшегося планированием мероприятий противовоздушной обороны. Как самостоятельный предмет выделился в 50-х годах и включил в себя теорию принятия решений, сетевые модели, СМО и др.
Операцией назовем систему действий, объединенных единым планом и направленных на достижение определенной системы целей. Отличительные признаки операции – допустимость (отражает ограниченность ресурсов) и управляемость. Всякий допустимый выбор управляемых параметров называется решением. Цель исследования операций – предварительное количественное обоснование решений, оптимизирующих целевые функции.
ПРИМЕРЫ ЧАСТНЫХ ЗАДАЧ исследования операций:
1) Снабжение предприятий (критерий эффективности – расходы на 1 ед. сырья).
2) Постройка участка магистрали (цели - быстрее закончить, уложиться в срок).
3) Продажа сезонных товаров. 4) Расчистка дорог от снега.
5) Медицинское обследование. 6) Противолодочный рейд.
ОСНОВНЫЕ ЭТАПЫ ОПЕРАЦИОННОГО ИССЛЕДОВАНИЯ.
-
Неформальная постановка задачи.
-
Построение математической модели исследуемой системы, т.е. выбор признаков, существенных для принятия решений, и связей между ними.
-
Выбор критериев оптимизации, т.е. выбор функций fi (x,…).
-
Имеет ли поставленная математическая задача приемлемые методы решения? Если нет упрощаем модель или выбираем другие критерии.
-
Находим решение в рамках модели.
-
Проверка адекватности решения. Если решение неадекватно, то уточняем модель, вводя какие-либо дополнительные ограничения. Здесь требуется эксперт (критерий), способный оценить адекватность получаемых решений.
Даже если в результате исследования удается найти наилучшее решение, окончательный выбор должен делать человек, используя дополнительную информацию, не отраженную в модели. Сложность исследования состоит в подборе подходящей модели и четком формулировании целей операции.
КЛАССИФИКАЦИЯ ЗАДАЧ ИО по постановке и методам решения :
К случаю, когда D – плохо структурировано (например, целочисленно) относится большинство NP-полных задач. Для их решения используется точный метод ветвей и границ или работающие более быстро приближенные методы.
В многокритериальных задачах цели могут оказаться противоречивыми, поэтому внимание сосредотачивается на выборе критериев.
-
Выбор главного критерия, т.е. f i0 extr при ограничениях для ii0.
-
Построение свертки критериев F(x) = · f (x), где i – вес i-го критерия.
-
Принцип Парето (отсечение вариантов, более слабым по всем показателям).
При принятии решений в условиях неопределенности функция f зависит от неизвестного y, от которого можно избавиться следующими способами:
-
Пессимист: F(x) = f (x, y). Пример – строительство моста.
-
Оптимист: F(x) = f (x, y). Пример - снятие вратаря в хоккее.
-
Прагматик: F(x) = My f (x, y), здесь y рассматривается как случайная величина и My – оператор мат.ожидания по y. Теперь xопт=argmax F(x) .
В играх имеется несколько активных сторон (игроков), поведение которых описывается множествами стратегий. Некоторые игроки делают выбор случайно, а остальные стремятся максимизировать свои функции полезности. Для определения наиболее разумного поведения игроков применимы принципы Парето, пессимиста (когда действия других игроков неизвестны) и Нэша (или равновесия) – когда всем игрокам невыгодно играть по-другому.
Модель принятия решений в условиях неопределенности иногда интерпретируется как игра с природой.
Типы рекуррентных уравнений и трудоемкость рекурсивных алгоритмов.
-
Tn = Tn -1 + C·n Tn = O(n2). (сортировка методом пузырька).
-
Tn = 2T + C·n Tn = C·n·log n (быстрая сортировка, диаграммы Вороного).
-
Tn c·n + и = < 1, Tn = O(n) (k-ое число, МОД, ЛП в R2).
-
Tn = Tn -1 + C Tn = C·n (задача Штейнера).
-
Tn = Tn -1 + k·Tn -2. Решение ищется в виде Tn = n n = n –1 +k·n -2 или
2 = + k 1,2 = 1/2 ± , а C1,2 зависят от T1 и T2
Таблица 1. Зависимость трудоемкости алгоритмов от размера задачи.
n |
n · log n |
n2 |
n3 |
n4 |
2n |
nn |
2 |
2 |
4 |
8 |
16 |
4 |
4 |
4 |
8 |
16 |
64 |
256 |
16 |
256 |
10 |
32 |
100 |
1000 |
104 |
1024 |
1010 |
1000 |
104 |
106 |
109 |
1012 |
10300 |
103000 |
Многие оптимизационные задачи небольшого! размера (ЛП, матричные игры, ЦЛП …) легко решаются в EXCEL с помощью команд Сервис и Поиск решения.
Алгоритмы решения многих задач предполагают сортировку данных, минимальная теоретическая трудоемкость которой O(n·log n), т.к. угадывание одной из n! перестановок требует log(n!(n/e)n √2̃̃∙̃ñ ,Стирлинг) вопросов. Метод “пузырька” имеет трудоемкость O(n2).
Алгоритм сортировки с трудоемкостью O (n log n) в худшем случае.
Разобьем множество элементов на пары и упорядочим каждую пару. Затем склеим пары в упорядоченные четверки, потом четверки в восьмерки и т.д. Склейка производится следующим образом: записываем наименьший из меньших элементов из двух склеиваемых множеств, затем записанный элемент вычеркиваем и повторяем операцию, пока не опустеют оба множества (рекуррентное уравнение соответствует нерекуррентному алгоритму!).
Посчитаем трудоемкость: , где Tсклейки=cn, c=const.
Пример: Даны числа: 15 3 6 24 18 13 15 5 7 81 8. Упорядочим пары чисел 3 15 6 24 13 18 5 15 7 81 8 и сольем пары в упорядоченные четверки: 3 6 15 24 5 13 15 18 7 8 81. Формируем упорядоченные восьмерки. Сравниваем первые числа четверок 3 и 5. Минимум слева пишем его в восьмерку и сдвигаем указатель левой четверки. Далее сравниваем 6 и 5, минимум справа в восьмерку пишем 5 и сдвигаем указатель правой четверки и т.д. Когда одна из четверок закончится, остаток другой запишем в хвост восьмерки. На выходе упорядоченные восьмерки: 3 5 6 13 15 15 18 24 7 8 81. Склеивая таким же образом восьмерки, в итоге получим упорядоченное множество: 3 5 6 7 8 13 15 15 18 24 81.
В частных случаях бывают более быстрые методы упорядочения. Например, для массива из 109 элементов с целыми значениями из интервала [1,100] заведем 100 счетчиков и за линейное время посчитаем кратность каждого числа.
№2. ПОИСК k-ого элемента ЗА ЛИНЕЙНОЕ ВРЕМЯ. (Кнут, т.3, стр. 261)
-
Будем считать, что n=7*(2q+1), где q – произвольное натуральное число. Если это не выполнено, то добавим нужное число максимальных элементов.
-
Запишем данные по 7 чисел в строке и упорядочим строки по возрастанию.
-
Найдем медиану Z в среднем столбце.
-
Фильтруем строки по среднему столбцу относительно Z, т.е. делим строки на две части: больше или меньше Z в столбце.
-
Обозначим получившиеся зоны как показано на рисунке. Очевидно, a Z d для всех aA и dD. Остались B и C.
-
Фильтруем все xBC относительно Z: если x Z, то xA*, иначе xD*.
-
Пусть r число элементов множества A+A*. Если k=r, то искомое число равно Z. Если k<r, то ищем k-ое число в A+A*, иначе ищем (k-r)-ое число в D+D*. В обоих случаях остается не более 5n/7 чисел.
Оценим трудоемкость этого рекурсивного алгоритма: Tn c·n + . У нас i = 1/7 + 5/7 = 6/7 < 1, Tn 7·c·n. Если в строки записывать по 5 чисел, то Tn c·n + и i = 1/5 + 7/10 = 9/10 Tn 10·c·n .
7 |
9 |
3 |
1 |
6 |
5 |
18 |
2 |
4 |
8 |
9 |
6 |
|
|
|
|
|
|
|
|
1 |
3 |
6 |
7 |
9 |
2 |
4 |
5 |
8 |
18 |
6 |
9 |
18 |
18 |
18 |
Разобьем массив на пятерки, упорядочим их, и дополним последнюю строку максимальными элементами.
В среднем столбце найдем средний по значению элемент Z=6. Фильтруем строки относительно Z по среднему столбцу и выделяем множества A,B,C,D.
2 |
4 |
5 |
8 |
18 |
1 |
3 |
6 |
7 |
9 |
6 |
9 |
18 |
18 |
18 |
Если мы ищем девятое по значению число массива, то т.к. 9>r надо искать 2-й (=9-r) элемент неупорядоченного множества D*D={8,18,9,7,9}, это 8. Лишние максимальные элементы погашены, т.к. мы знаем, сколько их добавлялось.
Задание. Придумайте алгоритм поиска 1-медианы на прямой с линейной трудоемкостью.
Структуры для хранения постоянно меняющихся данных. Их можно реализовать с помощью указателей или массивов.
Стек (магазин) работает по принципу LastInFirstOut «последним пришел – первым ушел» и обеспечивает поиск «сначала вглубь». У него есть вершина top, в начале равная нулю.
Операции со стеком: Push – добавление элемента в стек if (top == n) error “overflow” else *++top=x, Pop – выборка верхнего элемента стека if (top == 0) error “underflow” else return*top--.
0 |
1 |
top |
3 |
4 |
5 |
м |
а |
м |
а |
|
|
Пример. В стек занесено 4 символа “мама”, а затем выбран 1 символ - “а”, top = 2.
Очередь работает по принципу FirstInFirstOut «первым пришел – первым ушел» и обеспечивает поиск «сначала вширь». У нее есть голова head и хвост tail. В начале head=tail=Q. Массив свернут в кольцо и за n следует 1. Операции с очередью: //отследить overflow и underflow
Enqueue добавление x к очереди {*tail = x; if (tail-Q==n) tail=Q else tail++} // head- tail==1 →over
Dequeue удаление x из очереди { x =*head; if (head-Q==n) head=Q else head++; return x;}
head |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
tail |
9 |
п |
а |
п |
а |
- |
м |
ы |
л |
|
|
0 |
1 |
2 |
tail |
head |
5 |
6 |
7 |
8 |
9 |
у |
к |
и |
а |
- |
м |
ы |
л |
- |
р |
АВЛ-деревья. Двоичное дерево сбалансировано, если для каждой его вершины глубина левого поддерева отличается от глубины правого поддерева не более чем на единицу. При этом занесение в дерево и удаление из него одного элемента требует не более O(log n) операций, где n – число хранящихся в ней элементов. Если после добавления или удаления элемента баланс будет нарушен, то он сразу же восстановливается перестройкой дерева. Проверка баланса и перестройка дерева также требуют не более O(log n) операций.
Вводимый Z сравниваем с корнем K. Если Z=K, то выход с сообщением «Такой элемент у нас уже есть». Иначе идем вниз (направо, если Z >K, или налево), сравнивая Z с корнем соответствующего поддерева. Если сравнивать не с чем, то заносим Z в этом месте и поднимаемся вверх по дереву, пока не встретим первую несбалансированную вершину U. Ее место займет (как показано на рисунке) вершина V, если предыдущие на пути вверх ребра (U,V) и (V,W) напрвлены в одну сторону, или вершина W, если ребра разнонаправлены.
Пример. На вход последовательно поступают цифры 1957684023. Балансировка нужна после ввода 56723. Двоичные кучи позволяют сортировать массив за O(n log n) с дополнительной памятью размера O(1) (вместо O(n) для сортировки слиянием). На их базе эффективно реализуется очередь с приоритетами.
A[1] = корень дерева Parent(i) {return ceil(i / 2)} Left(i) { return 2i } Right(i) { return 2i+1 }
Основное свойство кучи: значение потомка не превосходит значения предка A[Parent(i)]>A[i]
→ максимальный элемент кучи и любого ее поддерева находится в корне (этого поддерева).
Пример -
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
9 |
8 |
7 |
5 |
4 |
6 |
2 |
1 |
3 |
0 |
Heapify(A,i) {l=Left(i); r=Right(i); max = l≤heapSize && A[l]>A[i] ? l : i;
if (r≤heapSize && A[r]>A[max]) max = r; if (max ≠ i) {A[i]↔A[max]; Heapify(A,max)}}
Процедура поддерживает основное свойство кучи. Время работы – O(log n).
BuildHeap(A) { heapSize = length[A]; for (i=ceil(length[A]/2); i>0; i--) Heapify(A,i) }
Процедура cтроит кучу из исходного массива. Время – O(n).
HeapSort(A){BuildHeap(A); for (i=length[A]; i>0; i-=2){A[1]↔A[i]; heapSize--; Heapify(A,1)}}
Процедура сортирует массив, не используя дополнительной памяти. Время – O(n log n).
Процедуры, используемые при моделировании очереди с приоритетами на базе кучи. Время – O(log n).
ExtractMax(A) {if (n<1) Error; max=A[1]; A[1]=A[n--]; Heapify(A,1); return max}
Insert(A,key) { i=++n; while i>1 && A[Parent(i)]<key do A[i]=A[i=Parent(i)]; A[i]= key}
№1. Задача о p-медиане (как пример оптимизационной задачи в 1).
Пусть точки xi – магазины, i – интенсивность продаж в i-ом магазине (). Разместим среди них p центров обслуживания cj (складов), минимизируя функционал или . В первом случае множество C называется P-медианой, а во втором − P-центром.
Рассмотрим наиболее простой случай, когда все точки лежат на прямой, упорядочены, p=1 и единственный центр c размещен на отрезке [xk, xk+1]. Тогда
. Решение задачи свелось к минимизации на отрезке линейной по c функции:
-
если Δk < 0, то размещаем центр в точке xk+1, если Δk > 0, то в точке xk;
-
если же Δk = 0, то центр можно разместить в любой точке отрезка [xk, xk+1].
Отсюда вытекает алгоритм отыскания 1-медианы на прямой: движемся по прямой слева направо, подсчитывая Δk на каждом интервале и перемещая центр в правый конец интервала, пока Δk не станет меньше 0. Т.е. Wk= > S=(Wn / 2).
Отметим, что здесь важны не расстояния между точками, а порядок точек!!
Пример: Пусть 6 пунктов упорядоченны по координате x и общий вес W6 =195.
i |
30 |
15 |
40 |
60 |
18 |
32 |
Wk |
|
45 |
85 |
145 |
|
|
W2=30+15=45<S; W3=45+40=85<S; W4=85+60=145>S размещаем центр в последнем рассмотренном пункте 4.
Можно предположить, что и для p–медианы расстояния не играют роли. Это неверно. Пусть n=6, p=2, все wi=1, xi=i C={2,5}, но если x6=9, то C={3,6}.
i |
wi |
c1 |
Fi1 |
ji2 |
c2 |
Fi2 |
ji3 |
c3 |
Fi3 |
0 |
1 |
5 |
129 |
5 |
2 |
62 |
4 |
2 |
36 |
1 |
8 |
5 |
124 |
5 |
2 |
60 |
|
|
|
2 |
8 |
5 |
92 |
6 |
4 |
44 |
|
|
|
3 |
4 |
6 |
66 |
6 |
4 |
28 |
|
|
|
4 |
8 |
6 |
54 |
7 |
5 |
22 |
|
|
|
5 |
8 |
7 |
32 |
7 |
5 |
14 |
|
|
|
6 |
4 |
7 |
16 |
8 |
7 |
6 |
|
|
|
7 |
8 |
8 |
10 |
8 |
7 |
2 |
|
|
|
8 |
8 |
8 |
2 |
9 |
8 |
0 |
|
|
|
9 |
2 |
9 |
0 |
|
|
|
|
|
|
Значение критерия при оптимальном размещении
1-го центра на интервале [xi, xj) = fij,
k центров на интервале [xj, ∞) = Fjk.
Таблица заполняется слева направо и снизу вверх.
Трудоемкость равна O(n2p), а если использовать выпуклость Fjk по параметру j, то O(np·log n).
Например, F22 = min{3: 0+66, 4: 4+54, 5: 16+32=48, 6: 28+16=44,…} = 44.
F03 = min{1: 0+60, 2: 1+44, 3: 9+28=37, 4: 14+22=36, 5: 30+14,…} = 36.
В скобках до двоеточия стоит j - точка раздела зон, а после двоеточия - fij + Fjk.
Изменив критерий, упростим поиск одного центра: минимум функционала i xi-c2 достигается в точке z = i·xi / i - центре тяжести множества X.
i xi-c2 = i xi-z2 +i z-c2 +2i (xi-z, z-c).
Но z-c не зависит от i, а i (xi-z) = i·xi -i i·xi / I =0 слагаемое3 = 0. Если точки равномерно покрывают компактную область и веса примерно равны, то решения задач с обоими критериями очень близки. ???