Методы имитационного моделирования

Р(1, 2) Р(1, 2)

Р(1, 3) Р(2, 2)

Р(2, 3)

¯ ¯

В методе динамического программирования таблица вероятностей строится, начиная с правого нижнего угла

1/2	21/32	15/16	15/16
11/32	1/2	11/16	7/8
3/16	5/16	1/2	3/4
1/16	1/8	1/4	1/2
				-

Function ODDS (i, j: integer): real;

var S, K: integer;

begin

for S:=1 to i+j do begin

P[0, S]:=1; P[S, 0]:=0;

end;

for K:=1 to S-1 do

P[K, S-K]:=(P[K-1, S-K]+P[K, S-K-1])/2;

Result:=P[i, j];

end;

Сложность всей программы при n=i+j O(n²).

Пример 3:

Произведение матриц.

Пусть требуется вычислить произведение матриц М=М₁*М₂*М₃*…*М_к, где M_i(i-1, j).

Порядок перемножения матриц может существенно влиять на число операций независимо от выбранного метода умножения.

Для перемножения (p; q)*(q; r) потребуется p*q*r операций. В результате получится матрица (p; r).

Рассмотрим конкретный числовой пример:

М=М₁(10, 20)*М₂(20, 50)*М₃(50, 1)*М₄(1, 100)

Вычисление произведения этих матриц согласно общим правилам (справа налево) М=М₁*(М₂*(М₃*М₄)) потребует 125 тысяч операций.

Умножение другим способом М=(М₁*(М₂*М₃))*М₄ потребует 220 тысяч операций.

Однако процесс перебора всех способов перемножения с целью минимизировать число операций имеет экспоненциальную сложность O(2^n-1-2), что неприемлемо при больших n.

Алгоритм динамического программирования, дающий метод поиска оптимального произведения матриц, имеет полиномиальную сложность O(n²).

Зададим минимальную стоимость произведения матриц М_i*М_i+1*… *М_j, 1 £ i £ j £ n:

Эта формула дает минимально возможную сложность из набора k значений (i, j-1).

В алгоритме динамического программирования m_ij вычисляется в порядке возрастания разностей нижних индексов:

m_ii, " i

m_i,i+1­ и т. д.

При этом в формуле m_ik и m_{k+1, j} оказываются ранее вычисленными на момент поиска m_ij.

Для приведенного примера построим таблицу сложности.

m11=0	m22=0	m33=0	m44=0
m12=10000	m23=1000	m34=5000	-
m13=1200	m24=3000	-	-
m14=2200	-	-	-

Алгоритм может быть реализован в виде функции, вычисляющей минимальную стоимость, и выглядящей следующим образом:

Function MinMatrix(N: integer): longint;

begin

for i:=1 to n do m[i, i]:=0;

for l:=1 to n-1 do

for i:=1 to n-1 do

begin

j:=i+l;

m[i, j]:= min(m[i, k]+m[k+1, j]+r[i-1]*r[k]*r[j]);

end;

Result:=m[1, n];

end;

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

Обычно неизвестно распределение вероятностей случайных переменных, а функции системы являются непрерывными.

Имитационное моделирование (ИМ) – это процесс вычислительного эксперимента над динамической моделью системы.

Конечной целью ИМ является:

· формирование стратегии управления;

· определение оптимальных конфигураций системы;

· установление реальных производственных планов;

· получение оптимальной экономической стратегии.

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

Области применения ИМ включают задачи теории массового обслуживания. Самыми распространенными алгоритмами ИМ являются алгоритмы моделирования очередей.

Дата добавления: 2014-01-07