Функционально-матричный метод расчета параметров сетевого графа (вершины – работы)

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 16 (004. 021)
ФУНКЦИОНАЛЬНО-МАТРИЧНЫЙ МЕТОД РАСЧЕТА ПАРАМЕТРОВ СЕТЕВОГО ГРАФА (ВЕРШИНЫ — РАБОТЫ)
Шустова Е. П. 1
ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» Казань, Россия (420 008, г. Казань, ул. Кремлёвская, 18), e-mail: evgeniyashustova@yandex. ru
В настоящей работе предложен новый метод вычисления параметров сетевого графа, в котором вершинами являются работы. Он основан одновременно и на матричном подходе, и на функциональном. Поэтому он и назван здесь функционально-матричным. Предложенный метод обеспечивает вычисление ранних времен начала и окончания работ для любой выборочно взятой работы любого периода проекта без непосредственного последовательного вычисления этих параметров для предыдущих работ, как это требуется в известных методах подсчета параметров сетевого графа. Он так же обеспечивает вычисление поздних сроков начала и окончания работ для любой выборочно взятой работы любого периода проекта без непосредственного последовательного вычисления этих параметров для всех последующих работ, как это требуется в известных методах подсчета параметров сетевого графа. Ключевые слова: сетевой граф, параметры работ, вершины — работы, Mathematica.
FUNCTIONAL-MATRIX METHOD FOR CALCULATING THE PARAMETERS OF THE NETWORK GRAPH (VERTEX — WORKS)
Shustova E.P. 1
Kazan (Volga region) federal university, Kazan, Russia (420 008, Kazan, street Kremlyovskaya, 18), e-mail:
Evgeniyashustova@yandex. ru_
In this paper, we propose a new method for calculating the parameters of the network graph in which the vertices are working. It is based at the same time on matrix and on functional approach. That is why he is here called functional-matrix. It provides the calculation of the early start and end of work without a direct serial calculation of these parameters for the previous works (as in the known methods for calculating parameters of the network graph). This method also allows the calculation of a late start and end of work without a consistent calculation of these parameters for all subsequent work, as required in the known methods of calculation of parameters of the network graph.
Keywords: network graph, parameters of work, vertex — work, Mathematica.
В настоящее время активно разрабатываются различные системы поддержки принятия решений [3- 4], в том числе и в области управления проектами. Но известные системы управления проектами, к сожалению, изначально привязаны к датам (дата начала, дата окончания работы), а не к длительности выполнения работ проекта. Но перед пользователем, как правило, изначально стоит задача определиться как долго (дней, месяцев, часов) должна выполняться работа. К тому же для дальнейшего анализа и оптимизации проекта по срокам выполнения проекта и затратам пользователю необходимо параллельно задавать нормальную, ускоренную или наиболее ожидаемую длительность работ, желаемую длительность выполнения проекта в целом и его этапов. Здесь важно чтобы была возможность динамически изменять эти длительности. А в известных системах управления проектом пользователь не может распараллелить различные варианты
выполнения проекта для фиксированной последовательности работ. Конечно, пользователь может создать на каком-то этапе копию своего проекта, в которой задать другой вариант по длительности работ. Но это неудобно, т.к. пользователю придется помнить во всех ли копиях он одинаково изменил последовательность работ (или вручную сверять эти списки). К тому же это приведет к увеличению объема занимаемой проектом памяти. Поэтому возникла необходимость создания такой системы управления проектом, в которой для одной установленной (динамически изменяемой) пользователем последовательности работ проекта можно было бы распараллеливать различные варианты его выполнения и оптимизации, сравнивать их. Как выяснилось, создавать такую систему на основе уже известной логики подсчета параметров сетевого графа [1- 5] неудобно и сложно. Все это и привело к необходимости в функционально-матричном подходе к вычислению этих параметров.
Заметим, что такую динамическую систему можно создавать как с точки зрения объектно-ориентированного программирования, так и функционального [2]. Заметим также, что для полного анализа проекта неизбежно потребуется пользоваться фундаментальными математическими знаниями. Поэтому для программирования указанной выше системы управления проектом удобно использовать системы компьютерной алгебры, например МаШешайса или МЛТЬЛБ. А предложенный функционально-матричный метод в этих системах прост для программирования.
Цель исследования: обеспечение выборочного (по запросу пользователя) вычисления параметров работы сетевого графа любого этапа проекта (вершины — работы) без непосредственного последовательного расчета, как это делается в известном табличном методе.
Объекты исследования: сетевые графы (вершины работы) проекта.
Алгоритм
Пусть некоторый проект состоит из ко1р периодов. Ниже введем в рассмотрение следующие функции: паек [р]- время, начиная с которого приступили к выполнению р -го периода- кгаЪ [р] - количество работ в р -м периоде- I [р, к] - время выполнения к -й работы р -го периода (р = 1, ко1р).
Будем считать, что работы каждого этапа проекта имеют правильную нумерацию. Пусть для каждого фиксированного периода трг [р] - матрица предшествующих работ. Каждая компонента трг [р][к, г] этой матрицы, т.о., является функцией от номера периода. Будем считать, что к это номер строки, г — номер столбца, строки матрицы предшествующих работ — «работы-потомки», а столбцы — работы, непосредственно предшествующие «работам-потомкам». На позицию (к, г) в этой матрице ставится 1, если
i -я работа непосредственно предшествует к -й работе, и 0, если i -я работа непосредственно не предшествует к -й работе. Обратим внимание на то, что матрицу mpr [p] мы рассматриваем не как массив, а как функцию от [к, i]. Такой подход упрощает написание кода (например, в Mathematica) для нахождения параметров работ.
Заметим, что матрица смежности для графа p -го периода есть транспонированная
матрица предшествующих работ (p = 1, kolp).
Алгоритм функционально-матричного метода расчета параметров для работ p -го периода
1. Нахождение матрицы ранних сроков начала и окончания работ.
Обозначим через ran [p, к] = (к, rannach [p, к], ranokonch [p, к]) — матрицу-функцию ранних сроков начала и окончания к -й работы p -го периода. Первая компонента этого списка — номер работы p -го периода, вторая ran [p, к][[2]] = rannach [p, к] - ранний срок начала этой работы, третья ran [p, к][[3]] = rano^nch [p, к] - ранний срок окончания этой работы.
Матрица-функция ранних сроков начала и окончания к -й работы p -го периода находится следующим образом. Всегда первая компонента этой матрицы-функции — номер работы p -го периода, третья компонента (ранний срок окончания этой работы) получается прибавлением времени выполнения этой работы к уже вычисленной второй компоненте (началу выполнения этого периода). А вторая компонента формируется следующим образом.
— Если к -строка матрицы предшествующих работ нулевая, то вторая компонента (раннее начало к -й работы p -го периода) равна времени начала выполнения этого периода nach[ p].
— Если к -строка матрицы предшествующих работ ненулевая, то вторая компонента (раннее начало к -й работы p -го периода) находится так: берутся к — 1 первых элементов к -й строки матрицы предшествующих работ этого периода, накладываются на одномерную матрицу для этого периода, состоящую из значений третьих компонент матрицы ran [p, r] (r = 1, к — 1). Совпадающие элементы перемножаются. Получаются к — 1 чисел. Из этих чисел выбирается максимальное. Это число и есть вторая компонента одномерной матрицы ran [p, к] для данного периода (раннее начало rannach [p, к] к -й работы p -го периода) в этом случае. Только что предложенный алгоритм нахождения матрицы ранних сроков начала и окончания работ запишем формулами:
(k, nach[p], nach [p] +1[p, k]),
если k — я строка матрицы mpr [p] нулевая
ran [ p, k]=
г Г k-1 ^ г k-1 ^ ^
k, Max I ^ mpr [ p][k,/]• ran[ p, i][[3]], Max I ^ mpr [ p][k,/]• ran [p, i][[3]] +1 [p, k] ,
V i-i у V i-i у у
если k — я строка матрицы mpr [p] ненулевая
Например, код в системе Mathematica 10, реализующий вычисление ранних сроков начала и окончания работ, согласно предложенному здесь функционально-матричному методу можно записать так:
2. Нахождение длины критического пути.
Напомним, что критический путь это максимальный по продолжительности полный путь. Поэтому длина критического пути okonch [p] для сетевого графа p -го периода (т.е. самый ранний момент времени, к которому завершится выполнение всех работ этого периода) равна максимуму из ранних сроков окончания работ этого периода. Запишем это формулами:
okonch [p] = max ran [p, k] [[3]].
k = 1, krab [ p ]
3. Нахождение матрицы поздних сроков начала и окончания работ.
Обозначим через pozdn [p, k] = (k, pozdnnach [p, k], pozdnokonc h [p, k]) — матрицу-функцию поздних сроков начала и окончания k -й работы p -го периода. Первая компонента этого списка — номер работы p -го периода, вторая pozdn [p, k][[2]] = pozdnnach [p, k] -поздний срок начала этой работы, третья pozdn [p, k][[3]] = pozdnokonc h [p, k] - поздний срок окончания этой работы.
Матрица-функция поздних сроков начала и окончания k -й работы p -го периода находится следующим образом. Всегда первая компонента этой матрицы-функции — номер работы p -го периода, вторая компонента (поздний срок начала этой работы) получается вычитанием времени выполнения этой работы от третьей компоненты (позднего окончания выполнения работы этого периода). А третья компонента формируется следующим образом. — Если k -столбец матрицы предшествующих работ нулевой, то третья компонента pozdn [p, k][[3]] (позднее окончание k -й работы p -го периода) равна длине критического пути этого периода.
— Если к -столбец матрицы предшествующих работ ненулевой, то третья компонента рогйп [р, к][[3]] (позднее окончание к -й работы р -го периода) ищется так: сначала от столбца, состоящего из поздних сроков окончания всех непосредственно следующих за к -й работой р -го периода работ, отнимается длительность (время выполнения) этих работ- затем из получившегося столбца выбирается наименьший элемент- этот элемент и есть третья компонента рогйп [р, к][[3]] (позднее окончание к -й работы р -го периода) одномерной матрицы рогйп [р, к] в этом случае.
Заметим, что столбец, состоящий из поздних сроков окончания всех непосредственно следующих за к -й работой р -го периода работ, получается покомпонентным произведением столбца, состоящего из (кгаЪ [р] - к) последних элементов к -го столбца матрицы предшествующих работ на столбец, состоящий из поздних сроков окончания для всех работ, начиная с к + 1-й работы р -го периода. Только что предложенный алгоритм нахождения матрицы поздних сроков начала и окончания работ запишем формулами:
рогёп [р, к] =
(к, окопек[р] -/ [р, к], окопек[р] если к -й столбец матрицы
трг[р] нулевой
(к, ро1^окопекпвпи1 [р, к] -/ [р, к], ро1^окопекпвпи1 [р, к]), если к — й столбец матрицы
трг[р] ненулевой
Здесь
[кгаЪ[ р] Л
Птрг [р][г, к]• (ро2ёп [р, г] - ?[р, г]).
¦ - +
… !-к+1 У
Например, код в системе МаШешайса 10, реализующий вычисление поздних сроков начала и окончания работ, согласно предложенному здесь функционально-матричному методу можно записать так:
4. Нахождение матрицы полного резерва времени выполнения работ. Напомним, что полный резерв времени выполнения работы это максимально возможный запас времени, на который можно отсрочить начало этой работы или увеличить продолжительность её выполнения при условии, что завершение этой работы наступит не
позднее своего позднего срока. Поэтому очевидно, что полный резерв времени Rpo ln [p, k] выполнения k -й работы p -го периода равен разности поздних и ранних сроков окончания (или начала) этой работы, т. е. вычисляется по формуле [1- 5]:
Rpo ln [p, k] = pozdn [p, k][[3]] - ran [p, k][[3]] = = pozdn [p, k][[2]] - ran [p, k][[2]].
Примеры
Пусть проект состоит из двух периодов, в первом периоде четыре работы, во втором -пять. Пусть для каждого из периодов заданы матрицы предшествующих работ и длительности этих работ (рис. 1). Здесь пустая клетка означает нулевое значение.
1 период
2 период
номер работы матрица предшествующих работ длительность работы
1 2 3 4 t (k)
1 10
2 1 20
3 1 42
4 1 1 12
номер работы матрица предшествующих работ длительность работы
1 2 3 4 5 чч
1 10
2 1 20
3 1 42
4 1 1 12
5 1 20
Рис. 1. Матрицы предшествующих работ периодов проекта.
Заметим, что сетевые графики этих периодов работ соответственно будут иметь вид, приведённый на рис. 2.
1 -- 2 -«-3
Рис. 2. Сетевые графики выполнения периодов проекта Параметры работ, вычисленные в системе компьютерной алгебры МаШешайса по указанному выше алгоритму, приведены на рис. 3.
Код Длительность работы Начало работы Окончание работы Полный резерв времени С дней)
раннни срок С дней) поздним срок (дней) раннии срок С дней) позднии срок С дней)
1.1. 10? 0 10 10 0
1.2. 20 10 10 30 30 0
1.3. 42 30 30 72 72 0
1,4. 12 30 60 42 72 30
2J
Код Длительность работы Начало работы Окончание работы Полный резерв времени (дней)
ранний срок (дней) поздним срок (дней) ранним срок (дней) позднии срок (дней)
2.1. 10 0 0 10 10 0
2.2. 20 10 10 30 30 0
2.3. 42 30 30 72 72 0
2.4. 12 30 ВО 42 92 50
2.5. 20 72 72 92 92 0
Рис. 3. Расчет параметров для сетевых графиков выполнения периодов проекта Заключение
В настоящей работе предложен новый метод вычисления параметров сетевого графа, в котором вершинами являются работы. Он основан одновременно и на матричном подходе, и на функциональном. Прост для программирования. Этот метод обеспечивает выборочное (по запросу пользователя) вычисление параметров работы сетевого графа любого этапа проекта (вершины — работы) без непосредственного последовательного расчета, как это делается в известном табличном методе.
Предложенный здесь метод может быть использован в научных исследованиях, а также в учебном процессе при изучении дисциплин «Дискретная математика», «Системы компьютерной алгебры в управлении проектами», «Календарное планирование», «Сетевое планирование и управление».
Список литературы
1. Ефремов В. С. Проектное управление: модели и методы принятия решений // Менеджмент в России и за рубежом. — 1998. — № 6. — URL: http: //www. cfin. ru/press/management/1998−6/1 l. shtml (дата обращения: 28. 05. 2015).
2. Широкова О. А. Особенности обучения программированию на основе общности и различия принципов // Современные проблемы науки и образования. — 2015. — № 1. — URL: http: //www. science-education. ru/ /121−17 896 (дата обращения: 28. 05. 2015).
3. Шустова К. П. Создание приложения для обнаружения движения в помещении со стационарной камеры в Mathematica 8. Сообщение и сигнализация о его существенности (критерий количества движения — коэффициент вариации) // Современные проблемы науки и образования. — 2013. — № 4. — URL: http: //www. science-education. ru/110−9977 (дата обращения: 28. 05. 2015).
4. Шустова К. П. Создание приложения «Оценка кредитоспособности предприятий-заёмщиков» // Современные проблемы науки и образования. — 2013. — № 5. — URL: http: //www. science-education. ru/111−10 018 (дата обращения: 28. 05. 2015).
5. Шустова К. П., Шустова Е. П., Уткина Е. А. Математические методы (сетевое планирование и управление). Практикум: учебное пособие. — 2-е изд., испр., доп. — Казань: Отечество, 2014. — 108 с. — ISBN ISBN 978−5-9222−0808−6.
Рецензенты:
Зарипов Р. Г., д.ф. -м.н., профессор, зам. директора по научной работе, ИММ КазНЦ РАН, г. Казань-
Уткина Е. А., д.ф. -м.н., доцент кафедры информационных систем, ФГАОУ ВПО «Казанский (Приволжский) федеральный университет», г. Казань.

ПоказатьСвернуть
Заполнить форму текущей работой