Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Сетевой анализ проектов. Метод PERT

Государственное бюджетное образовательное учреждение

высшего профессионального образования Московской области

Международный университет природы, общества и человека «Дубна»

филиал «Угреша»

Филиал «Угреша»

Кафедра информационных систем и технологий

КУРСОВАЯ РАБОТА (ПРОЕКТ)

ПО

Математическим методам оптимизации и системного анализа

(наименование учебной дисциплины)

ТЕМА: ______Сетевой анализ проектов. Метод PERT_______________

(наименование темы)

Выполнил: студент

ИС-10 группы

____3___ курса

кафедры Информационные системы и технологии

Савченко Виктория Олеговна

(Ф.И.О.)

Руководитель: доцент Соловьев

Эдуард Дмитриевич

(уч.степень, уч.звание, должность)

Дата защиты: «_____»__________20__ г.

Оценка: _______________

______________________

(подпись руководителя)

Государственное бюджетное образовательное учреждение

высшего профессионального образования Московской области

Международный университет природы, общества и человека «Дубна»

филиал «Угреша»

Кафедра: Информационные системы и технологии

Дисциплина: математические методы оптимизации и системного анализа

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

Студент: Савченко Виктория Олеговна

Научный руководитель: доцент Соловьев Эдуард Дмитриевич

ТЕМА: Сетевой анализ проектов. Метод PERT

утверждена на заседании кафедры «____»__________20___г. протокол № ______

Целевая установка: написать программу в среде VBA

Основные вопросы, подлежащие разработке:

1. Построение сетевой модели.

2. Разработка программы ранжирования и расчета временных параметров сетевой модели в среде VBA.

3. Расчет времени выполнения проекта с вероятностью 0,88.

Основная литература:

1) Козлов В.Н. Системный анализ, оптимизация и принятие решений

Государственное бюджетное образовательное учреждение

высшего профессионального образования Московской области

«Международный университет природы, общества и человека «Дубна»

(Филиал «Угреша»)

ОТЗЫВ О КУРСОВОЙ РАБОТЕ

Студент: Савченко Виктория Олеговна

Группа: ИС-10

Тема курсовой работы: Сетевой анализ проектов. Метод PERT

№ п/п	Критерии оценки	Оценка научного руководителя
1.	Соответствие содержания курсовой работы/курсового проекта утвержденной теме
2.	Выполнение поставленных целей и задач
3.	Освоение приемов работы с оборудованием и методов исследования
4.	Освоение теоретического материала при работе над курсовой работой/курсовым проектом
5.	Оформление студентом курсовой работы

Оценка работы: _________________________________________________________________

(отлично, хорошо, удовлетворительно, неудовлетворительно)

Руководитель: __Соловьев Эдуард Дмитриевич_______________________________________

(фамилия, имя, отчество)

«_____»______________20___ г. __________________

(дата) (подпись)

Оглавление

Введение
Задание

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

формирование математической модели

Метод решения

Анализ и исследование результата

Выводы

Использованная литература
Текст программы с комментариями

Введение

60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы.

В нашей курсовой работе, мы рассмотрим и реализуем на языке программирования Visual Basic Applications алгоритм решения задачи о максимальном потоке, предложенный Фордом и Фалкерсоном.

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

Работа	Пред. Работа	t₀	t₁
V	-	4	9
W	V	6	10
Z	W	5	7
U	Z,Y	2	5
X	V	3	8
Y	X,N	4	12
S	-	6	9
N	S	4	7
C	-	5	11
D	S	7	9
R	S	8	12
Q	R,A	2	7
K	Q,B	3	6
L	C	4	5
A	C	1	8
B	L	5	9

Формирование математической модели

W (5,6) Z (4,4)

V (4,2) X (3,4) Y (4,8)

N (3,8) U (2,2)

S(5,4) D(6)

C(5,2) R(7,2) K (3)

A (2,2) Q (2,6)

L (3,4) B (4,8)

Пути:

0→1→4→9→10 = 16,4
0→1→5→9→10 = 14,6
0→2→5→9→10 = 16,2
0→2→10 = 11,4
0→2→6→8→10 = 18,2
0→3→6→8→10 = 13
0→3→7→8→10 = 16,4

Пятый путь – критический

Т_ож мы считаем по формуле :

Дисперсию и квадрат из дисперсии мы считаем по формулам :

;
;

Метод решения

PERT- Program Evaluation and Review Technique.

Метод оценки и обзора программ предназначен:

формировать календарный план реализации некоторого комплекса работ (проекта);
выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы;
управлять по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ;
повышать ответственность исполнителей работ;

Шаги:

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

Анализ и исследование результата

Выводы:

В проделанной нами работе была создана программа, которая при нажатии на кнопку:

-производит ранжирование с помощью алгоритма Форда-Фалкерсона

- рассчитывает значение критического пути;

-рассчитывает значение tож для каждой работы;

-выделяет критический путь на сетевой модели;

-рассчитывает значение дисперсии (так же и в случае нескольких критических путей);

-рассчитывает время выполнения проекта с вероятностью 0,88.

Использованная литература

Батищев П.С. Основы программирования на Visual Basic 6.0. Электронный учебник

Текст программы с комментариями

'функция поиска максимального значения

Function Max(ParamArray avValues() As Variant) As Single

Dim x As Long, vThisItem As Single

For x = 0 To UBound(avValues)

vThisItem = avValues(x)

If vThisItem > Max Then Max = vThisItem

End Function

Private Sub Command1_Click()

' объявление переменных

Dim Tv As Single, TK As Single, TK1 As Single 'объявление переменных для расчета критического путя и времени при определенной вероятности

Dim TOV, TOW, TOZ, TOU, TOX, TOY, TOS, TON, TOC, TOD, TOR, TOQ, TOK, TOL, TOA, TOB As Single 'объявление переменных tожидания для каждой работы

Dim Vt0, Vt1, Wt0, Wt1, Zt0, Zt1, Ut0, Ut1, Xt0, Xt1, Yt0, Yt1, St0, St1, Nt0, Nt1, Ct0, Ct1, Dt0, Dt1, Rt0, Rt1, Qt0, Qt1, Kt0, Kt1, Lt0, Lt1, At0, At1, Bt0, Bt1 As Single 'объявление переменных для t0 и t1

Dim DV, DW, DZ, DU, DX, DY, DS, DN, DC, DD, DR, DQ, DK, DL, DA, DB, D, D1 As Single 'объявление переменных для расчета значения дисперсии

Dim i, z, k As Integer 'переменные, используемые в циклах

Dim w(10), v(10) As Single 'объявление двух массивов

Dim H0, HA, HB, HC, HD, HE, HF, HG, HH, HI, HK As Single ' переменные для хранения значения ранга для каждой работы

Dim Y0 As Integer

'заносим в переменные значения to для каждой работы

Vt0 = CSng(Text1(0).Text) 'работа V

Wt0 = CSng(Text1(1).Text) 'работа w

Zt0 = CSng(Text1(2).Text) 'работа Z

Ut0 = CSng(Text1(41).Text) 'работа U

Xt0 = CSng(Text1(40).Text) 'работа X

Yt0 = CSng(Text1(39).Text) 'работа Y

St0 = CSng(Text1(38).Text) 'работа S

Nt0 = CSng(Text1(37).Text) 'работа N

Ct0 = CSng(Text1(36).Text) 'работа C

Dt0 = CSng(Text1(35).Text) 'работа D

Rt0 = CSng(Text1(34).Text) 'работа R

Qt0 = CSng(Text1(33).Text) 'работа Q

Kt0 = CSng(Text1(32).Text) 'работа K

Lt0 = CSng(Text1(31).Text) 'работа L

At0 = CSng(Text1(30).Text) 'работа A

Bt0 = CSng(Text2.Text) 'работа B

'заносим в переменные значения t1 для каждой работы

Vt1 = CSng(Text1(29).Text) 'работа V

Wt1 = CSng(Text1(28).Text) 'работа w

Zt1 = CSng(Text1(27).Text) 'работа Z

Ut1 = CSng(Text1(26).Text) 'работа U

Xt1 = CSng(Text1(25).Text) 'работа X

Yt1 = CSng(Text1(24).Text) 'работа Y

St1 = CSng(Text1(23).Text) 'работа S

Nt1 = CSng(Text1(22).Text) 'работа N

Ct1 = CSng(Text1(21).Text) 'работа C

Dt1 = CSng(Text1(20).Text) 'работа D

Rt1 = CSng(Text1(19).Text) 'работа R

Qt1 = CSng(Text1(18).Text) 'работа Q

Kt1 = CSng(Text1(17).Text) 'работа K

Lt1 = CSng(Text1(16).Text) 'работа L

At1 = CSng(Text1(15).Text) 'работа A

Bt1 = CSng(Text3.Text) 'работа B

'вычисляем значение tожидания для каждой работы

TOV = (3 * At0 + 2 * At1) / 5 'работа V

TOW = (3 * Bt0 + 2 * Bt1) / 5 'работа W

TOZ = (3 * Ct0 + 2 * Ct1) / 5 'работа Z

TOU = (3 * Dt0 + 2 * Dt1) / 5 'работа U

TOX = (3 * Et0 + 2 * Et1) / 5 'работа X

TOY = (3 * Ft0 + 2 * Ft1) / 5 'работа Y

TOS = (3 * Gt0 + 2 * Gt1) / 5 'работа S

TON = (3 * Ht0 + 2 * Ht1) / 5 'работа N

TOC = (3 * It0 + 2 * It1) / 5 'работа C

TOD = (3 * Jt0 + 2 * Jt1) / 5 'работа D

TOR = (3 * Pt0 + 2 * Pt1) / 5 'работа R

TOQ = (3 * Qt0 + 2 * Qt1) / 5 'работа Q

TOK = (3 * Kt0 + 2 * Kt1) / 5 'работа K

TOL = (3 * Lt0 + 2 * Lt1) / 5 'работа L

TOA = (3 * Mt0 + 2 * Mt1) / 5 'работа A

TOB = (3 * Bt0 + 2 * Bt1) / 5 'работа B

'вывод на экран значения tожидания для каждой из работ

Text1(14).Text = TOV 'работа V

Text1(11).Text = TOW 'работа W

Text1(10).Text = TOZ 'работа Z

Text1(9).Text = TOU 'работа U

Text1(8).Text = TOX 'работа X

Text1(7).Text = TOY 'работа Y

Text1(6).Text = TOS 'работа S

Text1(5).Text = TON 'работа N

Text1(4).Text = TOC 'работа C

Text1(3).Text = TOD 'работа D

Text1(55).Text = TOR 'работа R

Text1(54).Text = TOQ 'работа Q

Text1(53).Text = TOK 'работа K

Text1(52).Text = TOL 'работа L

Text1(51).Text = TOA 'работа A

Text4.Text = TOB 'работа B

'блок ранжирования

'обозначаем узлы графа через переменные и присваиваем им значение 0

H0 = 0

HA = 0

HB = 0

HC = 0

HD = 0

HE = 0

HF = 0

HG = 0

HH = 0

HI = 0

HK = 0

'цикл ранжирования

Y0 = 1 'значение дуги графа

For i = 1 To 100 'номер шага в алгоритме

'вычисляем ранг каждой из вершин.

HA = H0 + Y0

HB = HA + Y0

HC = Max(HB + Y0, HD + Y0)

HD = Max(HA + Y0, HE + Y0)

HE = H0 + Y0

HF = Max(HC + Y0, HE + Y0, HI + Y0)

HG = H0 + Y0

HH = Max(HE + Y0, HG + Y0)

HI = Max(HH + Y0, HK + Y0)

HK = HG + Y0

Next i

'заносим в массив w значения рангов каждой вершины графа

w(0) = H0

w(1) = HA

w(2) = HB

w(3) = HC

w(4) = HD

w(5) = HE

w(6) = HF

w(7) = HG

w(8) = HH

w(9) = HI

w(10) = HK

'алгоритм, позволяющий выстроить все вершины в порядке возростания в зависимости от его ранга

k = 1 'начальный ранг = 1

i = 1

For k = 1 To 10 'цикл, который будет менять значение k(искомый ранг) на 1

For i = 1 To 10

If w(i) = k Then 'если i-ый элемент массива равен рангу, то

z = z + 1 'переменную Z увеличиваем на 1

v(i) = z 'заносим в массив V переменную Z. она выступает в роли порядкового номера вершины

End If

Next i

'как только все элементы проверены(все элементы с рангом K), ранг увеличивается на единицу (строчка ниже)

Next k

'в результате выполнения данного цикла получаем массив V в котором находятся порядковые номера всех вершин

'каждая вершина графа принимает правильный порядковый номер

Label1 = v(1) 'вершина A

Label2 = v(2) 'вершина B

Label48 = v(3) 'вершина C

Label35 = v(4) 'вершина D

Label42 = v(5) 'вершина E

Label47 = v(6) 'вершина F

Label43 = v(7) 'вершина G

Label44 = v(8) 'вершина H

Label46 = v(9) 'вершина I

Label45 = v(10) 'вершина K

'конец блока ранжирования

'блок поиска значения критического пути

'обнуляем значение всех вершин графа

H0 = 0

HA = 0

HB = 0

HC = 0

HD = 0

HE = 0

HF = 0

HG = 0

HH = 0

HI = 0

HK = 0

k = 1 'ранг

'цикл предназначен для того, что бы посчитать пути до вершин в правильном порядке (от меньшего ранга к большему)

For k = 1 To 10 'в этом цикле будет менятся ранг вершины

If w(1) = k Then 'если первый элемент массива (в котором находятся значения ранга) равна рангу k

HA = H0 + TOV 'то находим путь до вершины A

End If

'аналогично для всех остальных вершин

If w(2) = k Then

HB = HA + TOW

End If

If w(3) = k Then

HC = Max(HB + TOZ, HD + TOY)

End If

If w(4) = k Then

HD = Max(HA + TOX, HE + TON)

End If

If w(5) = k Then

HE = H0 + TOS

End If

If w(6) = k Then

HF = Max(HC + TOU, HE + TOD, HI + TOK)

End If

If w(7) = k Then

HG = H0 + TOC

End If

If w(8) = k Then

HH = Max(HG + TOA, HE + TOR)

End If

If w(9) = k Then

HI = Max(HH + TOQ, HK + TOB)

End If

If w(10) = k Then

HK = HG + TOL

End If

Next k

TK = Max(HA, HB, HC, HD, HE, HF, HG, HH, HI, HK) 'находим максимальный путь до какой-либо вершины графа. это и будет значение критического пути

'конец блока поиска значения критического пути

'расчет дисперсии^2 для каждой работы по формуле ((t1-t0))^2

DV = ((Vt1 - Vt0) / 5) ^ 2

DW = ((Wt1 - Wt0) / 5) ^ 2

DZ = ((Zt1 - Zt0) / 5) ^ 2

DU = ((Ut1 - Ut0) / 5) ^ 2

DX = ((Xt1 - Xt0) / 5) ^ 2

DY = ((Yt1 - Yt0) / 5) ^ 2

DS = ((St1 - St0) / 5) ^ 2

DN = ((Nt1 - Nt0) / 5) ^ 2

DC = ((Ct1 - Ct0) / 5) ^ 2

DD = ((Dt1 - Dt0) / 5) ^ 2

DR = ((Rt1 - Rt0) / 5) ^ 2

DQ = ((Qt1 - Qt0) / 5) ^ 2

DK = ((Kt1 - Kt0) / 5) ^ 2

DL = ((Lt1 - Lt0) / 5) ^ 2

DA = ((At1 - At0) / 5) ^ 2

DB = ((Bt1 - Bt0) / 5) ^ 2

'сравниваем значения времени каждого пути со значением времни полученного критического пути ТК

'если значения совпадают,то

'1) сравниваем значение дисперсии пути со значением дисперсии для критического пути, полученного ранее

'2) выбирается минимальное значение дисперсии

D1 = 100000000 'задаем очень большое значение дисперсии, которые практически не недостижимо

'для пути (0-A-B-C-F)

TK1 = TOV + TOW + TOZ + TOU

If TK1 = TK Then

D = (DV + DW + DZ + DU) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-A-D-C-F)

TK1 = TOV + TOX + TOY + TOU

If TK1 = TK Then

D = (DV + DX + DY + DU) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-E-D-C-F)

TK1 = TOS + TON + TOY + TOU

If TK1 = TK Then

D = (DS + DN + DY + DU) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-E-F)

TK1 = TOS + TOD

If TK1 = TK Then

D = (DS + DD) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-E-H-I-F)

TK1 = TOS + TOR + TOQ + TOK

If TK1 = TK Then

D = (DS + DR + DQ + DK) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-G-H-I-F)

TK1 = TOC + TOA + TOQ + TOK

If TK1 = TK Then

D = (DC + DA + DQ + DK) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

'для пути (0-G-K-I-F)

TK1 = TOC + TOL + TOB + TOK

If TK1 = TK Then

D = (DC + DL + DB + DK) ^ (1 / 2)

If D < D1 Then

D1 = D

End If

Label37 = TK 'вывод значения критического пути

Label39 = D1 ' вывод значение дисперсии

Tv = 1.18 * D1 + TK 'расчет значения времени выполнения проекта при вероятности 0,88

Label41 = Tv 'вывод значение времени выполнения проекта при вероятности, равной 0,88

End Sub