33.Математ.Модель задачи о кратчайшем пути в сети.

Постановка задачи

рассмотрим орграф G(I,U),каждой дуге которого поставлено число в соответствии l_ij –его длине. Если на графе есть неориентированные ребра,то каждое такое ребро мы заменим на пару противоположно ориентированных дуг такой же длины.Есть две вершины S(источник) T(сток).Требуется найти путь из S в T.

мат модель пусть x_ij=1,если путь проходит по дуге (i,j)и x_ij =0 ,если путь не проходит по дуге(i,j).Тогда l= _i,j*x_i,j →min

34.Алгоритм нах.Кратчайшего пути из источника во все вершины сети.

1. S помечаем(0^* ,S^* ).Все остальные вершины i временными метками(l,s),где l=l_si -длина дуги( s,i),если она существует, l=∞,если не существует.R={S}-вершины с постоянными метками.

2. пусть i –вершина из R(с постоянной меткой),тогда рассм. все вершины с постоянными метками,и выбираем из них i₀ такую,что l_i0-min для всех вершин с временными метками,и делаем ее метку i₀ ( l _{(i0) ,} v _(t0) ) постоянной,если l _(i0) конечное число.Если l _(i0) =∞,то задача решена,и для вершин с оставшимися временными метками нет пути из S в эти вершины.А если l_i <∞,то эту вершину добавляем в вершины спостоянными метками R=R { i₀ }

3. просматриваем все вершины с временными метками, соседние с вершинами, имеющими постоянные метки ,и пересчитываем временные метки след образом:если j –вершина с временнй меткой

j( l_j ,v_j),то ее новая метка l_j=min(l _ij +l^* _{(i) ,} l_j ). v_j= i₀ ,где i₀ -вершина с постоянной меткой,которая достигнет min функции l_j=min(l _ij +l^* _{(i) ,} l_j ).Далее перходим на п.2 пока все вершины не получат постоянные метки или останутся с метками для которых l =∞

35.Нижняя и верхняя цена игры.

Пусть А=(а_ij)-платежная матрица игры,нижней ценой игры(максимин)будем называть α=max_i(min_j a_ij).Верхней ценой игры (минимакс)будем называть число β=min_j(max_i a_ij).

36.Игры с седловой точкой.

Если нижняя и верхняя цена игры совпадают,то найдется a_i0j0=α=ß-седловая точка.

39.Динамическое программирование применяется для нахождения оптимального управления в многошаговых управляемых процессах. Процесс будет многошаговым, если его можно разбить (по времени) на несколько этапов, и на каждый из этапов выбирается оптимальное управление этапом.

Пр.1 Высота Н₀, скорость V₀. Самолет должен подняться на высоту Н_n1 и набрать скорость V_n2 . Известен расход горючего при подъёме самолёта с любой высоты Н_n1 на высоту Н_n2 и при постоянной скорости, где расход горючего при увеличении скорости от V₁ до V₂ при неизменной высоте. Найти оптимальное управление процессами набора высоты и скорости.

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