Ответы
.doc
Величины a и b называются нижней и верхней ценой игры в ч.с. |
Матричная игра при любой матрице А всегда разрешима в смешанных стратегиях, т.е. существует x*€M, y€N, I1=I2=I – цена игры, x*, y* - оптимальные равновесные стратегии. |
Смешанной стратегией игрока в матричной игре называется вероятностное распределение на множестве его ч.с. Если i=1,…,m - чистые стратегии игрока 1, а j=1,…,n - чистые стратегии игрока 2, то с.с. игрока 1 - это вероятностный вектор x=(x1,…,xm), где xi - вероятность выбора игроком 1 чистой стратегии i, i=1,…,m. Вектор x должен удовлетворять условиям: |
|
Игроку 1 выгодно выбрать x так, чтобы max увеличить U(x): |
игроку 2 выгодно минимизировать v(y):. |
Математическая модель задачи о назначениях является задачей целочисленного линейного программирования вида: при ограничениях:, , |
|
|
|
Количество независимых нулей становится равным n, задача о назначениях решена: оптимальный вариант определяется позициями независимых нулей в последней из матриц, эквивалентных исходной матрице c.
|
Находим максимальный элемент в каждом столбце матрицы С. Для каждого столбца все его элементы последовательно вычитаем из max, а результат оставляем в соответствующей позиции. Из всех элементов каждой строки вычитаем min элемент этой строки. В результате получаем матрицу С0 с неотрицательными элементами, в каждой строке и в каждом столбце которой имеется по меньшей мере один нуль. Помечаем независимые нули символом "*" по схеме: а) в первом столбце помечаем произвольный нуль; б) во втром столбце помечаем (если найдется) тот нуль, в строке которого нет нуля, помеченного "*"; в) аналогично просматриваем один за другим все столбцы матрицы С0. |
|
Имеется n городов. Расстояния м/у любой парой городов известны и состаляют cij i,j = 1,….,n. Если между городами i и j нет дороги, то cij=∞. Путь в одну сторону не обязательно совпадает с путем, пройденным в обратную сторону cij≠cji. Коммивояжер, выезжая из какого-либо города, должен посетить все города один раз, и вернуться в исходный город. Объезд городов, удовлетворяющий этим требованиям, называется маршрутом коммивояжера. Необходимо определить маршрут минимальной длины. |
. Тогда для j и . . Тогда для i и. |
На первом шаге это множество D. Его нижняя оценка . На остальных шагах из числа кандидатов на ветвление (из множества висячих вершин дерева ветвления) выбирается множество D` с наименьшей оценкой.
|
Для каждой дуги (k,l) такой, что ekl=0 В качестве дуги (p,q) выберем ту, для которой . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
52. Уравнение Беллмана для задачи о пожаре |