3.2 Построение математической модели

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

Пусть вершины пронумерованы так, что дуга (x_i, х_j) всегда ориентирована от вершины x_t к вершине х_j, имеющей больший номер. Для ациклического графа такая нумерация всегда воз­можна и производится очень легко. При этом начальная вершина получает номер 1, а конечная — номер n.

Присвоим вершине x_j пометку l(x_j),— равную длине самого длинного пути от 1 до x_j, используя для этого соотношения

l(x_j) = max [l(x_i) + c_ij]; (*)

Затем присвоим пометку вершине (x_j+ 1), применив снова формулу (8.7), и так далее до тех пор, пока последняя вершина п не получит пометку l(п). В соотношении (*) l(1) полагается равным нулю. Если вершина х_j помечена, то пометки I(x_t) извест­ны для всех вершин x_t Г^-1 (x_j), так как в соответствии со спо­собом нумерации это означает, что x_i < x_j и, следовательно, вер­шины x_i уже помечены в процессе применения алгоритма.

Пометка l(n) равна длине самого длинного пути от 1 до n. Сами дуги, образующие путь, могут быть найдены обычным спо­собом последовательного возвращения. А именно дуга (x_i, x_j) принадлежит пути тогда и только тогда, когда l(x_j) = I (x_i) + c_ij. Начиная с вершины x_j равной n, полагаем на каждом шаге x_j равной такой вершине x_t (скажем, х_i*), для которой выполняется это последнее равенство, и так продолжаем до тех пор, пока не бу­дет достигнута начальная вершина (т. е. пока не будет х_i* = 1).

Совершенно очевидно, что пометка l (x_j) вершины x_j дает длиннейший путь от 1 до х_j, т. е. самое раннее возможное начало выполнения этапа, изображаемого вершиной x_j. Таким образом, если (х_i, x_j) — дуга в графе, то I(x_i ) — I(x_j) — c_ij (неотрицатель­ная величина, как это видно из (*)) дает самое большое возмож­ное время задержки начала этапа i, не оказывающее влияния на время начала этапа j. Из вышесказанного видно, что если i и j — два последовательные этапа в самом длинном пути, то I (х_i) - I (x_j) - c_ij = 0.

3.3 Алгоритм решения задачи

Программа написана на языке Turbo Pascal версии 7.0 Отладка производилась в операционной системе MS Windows ХР на компьютере совместимом с IBM PC с процессором Pentium.

Программа состоит из следующих программных файлов:

kurs.exe – главный файл проекта;

alg.tpu – вычислительный модуль;

graf.txt – текстовый файл, содержащий входные данные (количество вершин графа и матрицу смежности).

Модуль Alg.Tpu

Модуль состоит из шести процедур, четыре из которых доступны пользователю: Smejnost, Svyaznost, Siln_Komponent, BAZ_AND_ABAZ;

Константы:

n0 = 30 – максимальное число вершин обрабатываемого графа.

Типы:

TM – одномерный целочисленный массив максимальной размерностью N0 с элементами от 1 до n0.

TTM – двумерный целочисленный массив максимальной размерностью n0*n0.

Переменные:

n – количество вершин в заданном графе;

A – матрица смежности заданного графа;

R - матрица достижимости;

Q - матрица контрдостижимости;

S – матрица сильной связности;

SK – матрица сильносвязных компонент;

KG – конденсация графа;

BAZ – базы графа;

ABAZ – антибазы графа;

ws – вспомогательная переменная, двумерный массив TTM;

str – вспомогательная переменная, одномерный массив TM:

k – количество сильных компонент;

i, j, l, g – счетчики.

Процедуры:

Procedure Smejnost – Заполнение матрицы смежности из указанного пользователем файла.

Procedure Svyaznost – Построение матрицы достижимости по матрице смежности, а также контрдостижимости и связности графа.

Procedure Siln_Komponent – Поиск сильных компонент.

Procedure BAZ_AND_ABAZ – Построение конденсации графа, поиск баз и антибаз заданного графа.

Procedure Poisk(var m: TTM) – Выполняет посик следующего элемента базы или интибазы. Вызывается процедурой BAZ_AND_ABAZ.

Procedure Vivod(x:integer) – Процедура рекурсия. Завершает поиск следующего элемента базы или антибазы. Вызывается процедурой Poisk.