Решение транспортных задач

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение

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

«Российский государственный профессионально-педагогический университет»

Машиностроительный институт

Кафедра высшей математики

КОНТРОЛЬНАЯ РАБОТА

по дисциплине

«Математические методы исследования экономики»

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

группы Тц-211С ГМУ

Мурашкина Н.П.

Проверил: преподаватель

канд. физ.мат. наук, доцент

Филиппов С.Д.

Екатеринбург

2015



1. Найти максимальное значение целевой функции методом Гомори (методом отсечений) , при условиях:

.

Дать геометрическую интерпретацию решения задачи.

Решение.

Необходимо найти максимальное значение целевой функции F = 3x₁+x₂ > max, при системе ограничений:

2x1+x2?15	(1)
-3x1+x2?9	(2)
x1?0	(3)
x2?0	(4)

где x₁, x₁ - целые числа.

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

Границы области допустимых решений

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = 3x₁+x₂ > max.

Построим прямую, отвечающую значению функции F = 0: F = 3x₁+x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (3; 1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.



Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (3) и (1), то ее координаты удовлетворяют уравнениям этих прямых:

x₂=0

2x₁+x₂=15

Решив систему уравнений, получим: x₁ = 7.5, x₂ = 0

Откуда найдем максимальное значение целевой функции:

F(X) = 3*7.5 + 1*0 = 22.5

Оптимальное значение переменной x₁=7.5 оказалось нецелочисленным.

Разбиваем задачу 1 на две подзадачи 11 и 12.

В первой из них к условиям задачи 11 добавляется условие х₁ ? 8, а к задаче 12 -- условие х₁ ? 7.

Эта процедура называется ветвлением по переменной х₁.

Решим графически задачу 11 как задачу ЛП.

2x1+x2?15	(1)
-3x1+x2?9	(2)
x1?8	(3)
x1?0	(4)
x2?0	(5)

Задача не имеет допустимых решений. ОДР представляет собой пустое множество (рис. б).



Многоугольные области: а - ограниченное множество; б - пустое множество; в - неограниченное множество

Несмотря на то, что полученное значение f=22.5 превышает нижнюю границу целевой функции для целочисленного решения, дальнейшее ветвление из вершины не позволяет улучшить нижнюю границу, поскольку f(x) - z < 1 и все коэффициенты целевой функции являются целыми числами.

Задача 11 не имеет решения, поэтому для нее процесс ветвления прерываем.

Решим графически задачу 12 как задачу ЛП.

2x1+x2?15	(1)
-3x1+x2?9	(2)
x1?7	(3)
x1?0	(4)
x2?0	(5)



Прямая F(x) = const пересекает область в точке E. Так как точка E получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

2x₁+x₂=15

x₁=7

Решив систему уравнений, получим: x₁ = 7, x₂ = 1

Откуда найдем максимальное значение целевой функции:

F(X) = 3*7 + 1*1 = 22

Решение задачи получилось целочисленным.

Новое значение текущего рекорда будет равно F(X) = 22.

Так как найденная точка является первым целочисленным решением, то ее и соответствующее ей значение ЦФ следует запомнить. Сама точка называется текущим целочисленным рекордом или просто рекордом, а оптимальное значение целочисленной задачи -- текущим значением рекорда. Это значение является нижней границей оптимального значения исходной задачи Z*.

F(X) = 22

x₁ = 7

x₂ = 1

Дерево решения задачи

Или



2. Решить транспортную задачу, заданную таблицей.

Поставщики и их запасы	Потребители и потребительский спрос
	В1	В2	В3	В4
	120	60	80	60
А1	90	11	3	7	14
А2	160	7	3	6	9
А3	70	9	4	8	11

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

Решение.

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

	1	2	3	4	Запасы
1	11	3	7	14	90
2	7	3	6	9	160
3	9	4	8	11	70
Потребности	120	60	80	60

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 90 + 160 + 70 = 320

?b = 120 + 60 + 80 + 60 = 320

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	11	3	7	14	90
2	7	3	6	9	160
3	9	4	8	11	70
Потребности	120	60	80	60



Этап I. Поиск первого опорного плана

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

	1	2	3	4	Запасы
1	11	3[60]	7	14[30]	90
2	7[80]	3	6[80]	9	160
3	9[40]	4	8	11[30]	70
Потребности	120	60	80	60

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*60 + 14*30 + 7*80 + 6*80 + 9*40 + 11*30 = 2330

Этап II. Улучшение опорного плана

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₄ = 14; 0 + v₄ = 14; v₄ = 14

u₃ + v₄ = 11; 14 + u₃ = 11; u₃ = -3

u₃ + v₁ = 9; -3 + v₁ = 9; v₁ = 12

u₂ + v₁ = 7; 12 + u₂ = 7; u₂ = -5

u₂ + v₃ = 6; -5 + v₃ = 6; v₃ = 11

	v1=12	v2=3	v3=11	v4=14
u1=0	11	3[60]	7	14[30]
u2=-5	7[80]	3	6[80]	9
u3=-3	9[40]	4	8	11[30]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j >c_ij

(1;1): 0 + 12 > 11; ?₁₁ = 0 + 12 - 11 = 1

(1;3): 0 + 11 > 7; ?₁₃ = 0 + 11 - 7 = 4

max(1,4) = 4

Выбираем максимальную оценку свободной клетки (1;3): 7

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	Запасы
1	11	3[60]	7[+]	14[30][-]	90
2	7[80][+]	3	6[80][-]	9	160
3	9[40][-]	4	8	11[30][+]	70
Потребности	120	60	80	60

Цикл приведен в таблице (1,3 > 1,4 > 3,4 > 3,1 > 2,1 > 2,3).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	11	3[60]	7[30]	14	90
2	7[110]	3	6[50]	9	160
3	9[10]	4	8	11[60]	70
Потребности	120	60	80	60

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₃ = 7; 0 + v₃ = 7; v₃ = 7

u₂ + v₃ = 6; 7 + u₂ = 6; u₂ = -1

u₂ + v₁ = 7; -1 + v₁ = 7; v₁ = 8

u₃ + v₁ = 9; 8 + u₃ = 9; u₃ = 1

u₃ + v₄ = 11; 1 + v₄ = 11; v₄ = 10

	v1=8	v2=3	v3=7	v4=10
u1=0	11	3[60]	7[30]	14
u2=-1	7[110]	3	6[50]	9
u3=1	9[10]	4	8	11[60]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ? c_ij.

Минимальные затраты составят: F(x) = 3*60 + 7*30 + 7*110 + 6*50 + 9*10 + 11*60 = 2210

Анализ оптимального плана

Из 1-го склада необходимо груз направить в 2-й магазин (60), в 3-й магазин (30)

Из 2-го склада необходимо груз направить в 1-й магазин (110), в 3-й магазин (50)

Из 3-го склада необходимо груз направить в 1-й магазин (10), в 4-й магазин (60)



3. Решить задачу о распределении ресурсов методом динамического программирования. Составить оптимальный план распределения капиталовложений между четырьмя предприятиями, обеспечивающий максимальное увеличение выпуска продукции, при исходных данных относительно и , приведенных в таблице, а также с учетом того, что общий объем капиталовложений S=100 усл. ед.

Объем \ капиталовложений,	Прирост выпуска продукции в зависимости от объема капиталовложений
	предпр.1	предпр. 2	предпр. 3	предпр. 4
0	0	0	0	0
20	12	14	13	18
40	33	28	38	39
60	44	38	47	48
80	54	56	62	65
100	68	80	79	82

Решение.

I этап. Условная оптимизация

1-ый шаг. k = 4.

Предположим, что все средства в количестве x₄ = 100 отданы предприятию №4. В этом случае, максимальный доход, как это видно из таблицы, составит f₄(u₄) = 82, следовательно, F₄(e₄) = f₄(u₄)

e3	u4	e4 = e3 - u4	f4(u4)	F*4(e4)	u4(e4)
20	0	20	0
	20	0	18	18	20
40	0	40	0
	20	20	18
	40	0	39	39	40
60	0	60	0
	20	40	18
	40	20	39
	60	0	48	48	60
80	0	80	0
	20	60	18
	40	40	39
	60	20	48
	80	0	65	65	80
100	0	100	0
	20	80	18
	40	60	39
	60	40	48
	80	20	65
	100	0	82	82	100

2-ый шаг. k = 3. маршрут срок стоимость гомори

Определяем оптимальную стратегию при распределении денежных средств между предприятиями №3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F₃(e₃) = max(x₃ ? e₃)(f₃(u₃) + F₄(e₃-u₃))

e2	u3	e3 = e2 - u3	f3(u3)	F*3(e2)	F2(u3,e2)	F*3(e3)	u3(e3)
20	0	20	0	18	18	18	0
	20	0	13	0	13
40	0	40	0	39	39	39	0
	20	20	13	18	31
	40	0	38	0	38
60	0	60	0	48	48
	20	40	13	39	52
	40	20	38	18	56	56	40
	60	0	47	0	47
80	0	80	0	65	65
	20	60	13	48	61
	40	40	38	39	77	77	40
	60	20	47	18	65
	80	0	62	0	62
100	0	100	0	82	82
	20	80	13	65	78
	40	60	38	48	86	86	40
	60	40	47	39	86
	80	20	62	18	80
	100	0	79	0	79

3-ый шаг. k = 2.

Определяем оптимальную стратегию при распределении денежных средств между предприятиями №2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F₂(e₂) = max(x₂ ? e₂)(f₂(u₂) + F₃(e₂-u₂))

e1	u2	e2 = e1 - u2	f2(u2)	F*2(e1)	F1(u2,e1)	F*2(e2)	u2(e2)
20	0	20	0	18	18	18	0
	20	0	14	0	14
40	0	40	0	39	39	39	0
	20	20	14	18	32
	40	0	28	0	28
60	0	60	0	56	56	56	0
	20	40	14	39	53
	40	20	28	18	46
	60	0	38	0	38
80	0	80	0	77	77	77	0
	20	60	14	56	70
	40	40	28	39	67
	60	20	38	18	56
	80	0	56	0	56
100	0	100	0	86	86
	20	80	14	77	91	91	20
	40	60	28	56	84
	60	40	38	39	77
	80	20	56	18	74
	100	0	80	0	80

4-ый шаг. k = 1.

Определяем оптимальную стратегию при распределении денежных средств между предприятиями №1, 2, 3, 4. При этом рекуррентное соотношение Беллмана имеет вид: F₁(e₁) = max(x₁ ? e₁)(f₁(u₁) + F₂(e₁-u₁))

e0	u1	e1 = e0 - u1	f1(u1)	F*1(e0)	F0(u1,e0)	F*1(e1)	u1(e1)
20	0	20	0	18	18	18	0
	20	0	12	0	12
40	0	40	0	39	39	39	0
	20	20	12	18	30
	40	0	33	0	33
60	0	60	0	56	56	56	0
	20	40	12	39	51
	40	20	33	18	51
	60	0	44	0	44
80	0	80	0	77	77	77	0
	20	60	12	56	68
	40	40	33	39	72
	60	20	44	18	62
	80	0	54	0	54
100	0	100	0	91	91	91	0
	20	80	12	77	89
	40	60	33	56	89
	60	40	44	39	83
	80	20	54	18	72
	100	0	68	0	68

Поясним построение таблиц и последовательность проведения расчетов.

Столбцы 1 (вложенные средства), 2 (проект) и 3 (остаток средств) для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 4-го шага столбцы 5 и 6 отсутствуют).

В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация

Из таблицы 4-го шага имеем F*₁(e⁰ = 100) = 91. То есть максимальный доход всей системы при количестве средств e⁰ = 100 равен 91

Из этой же таблицы получаем, что 1-му предприятию следует выделить u*₁(e⁰ = 100) = 0

При этом остаток средств составит:

e¹ = e⁰ - u¹

e¹ = 100 - 0 = 100

Из таблицы 3-го шага имеем F*₂(e¹ = 100) = 91. То есть максимальный доход всей системы при количестве средств e¹ = 100 равен 91

Из этой же таблицы получаем, что 2-му предприятию следует выделить u*₂(e¹ = 100) = 20

При этом остаток средств составит:

e² = e¹ - u²

e² = 100 - 20 = 80

Из таблицы 2-го шага имеем F*₃(e² = 80) = 77. То есть максимальный доход всей системы при количестве средств e² = 80 равен 77

Из этой же таблицы получаем, что 3-му предприятию следует выделить u*₃(e² = 80) = 40

При этом остаток средств составит:

e³ = e² - u³

e³ = 80 - 40 = 40

Последнему предприятию достается 40

Итак, инвестиции в размере 100 необходимо распределить следующим образом:

1-му предприятию выделить 0

2-му предприятию выделить 20

3-му предприятию выделить 40

4-му предприятию выделить 40

Что обеспечит максимальный доход, равный 91



4. Рассмотрите сеть, заданную следующими условиями:

Номер дуги	Имя дуги	Начальный узел	Конечный узел	Расстояние
1	С21	2	1	1
2	С31	3	1	4
3	С41	4	1	4
4	С61	6	1	8
5	С64	6	4	3
6	С65	6	5	2
7	С72	7	2	8
8	С76	7	6	1
9	С43	4	3	1
10	С54	5	4	2
11	С85	8	5	6
12	С86	8	6	4
13	С87	8	7	1
14	С74	7	4	5

Найти кратчайшие маршруты из всех узлов в узел 1 и определить их длину.

Решение.

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

Для определения резервов времени по событиям сети рассчитывают наиболее ранние t^p и наиболее поздние t^п сроки свершения событий. Любое событие не может наступить прежде, чем свершаться все предшествующие ему события и не будут выполнены все предшествующие работы. Поэтому ранний (или ожидаемый) срок tp(i) свершения i-ого события определяется продолжительностью максимального пути, предшествующего этому событию:

t^p(i) = max(t(L_ni))



где L_ni - любой путь, предшествующий i-ому событию, то есть путь от исходного до i-ого события сети.

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

t^p(j) = max[t^p(i) + t(i,j)]

Задержка свершения события i по отношению к своему раннему сроку не отразится на сроке свершения завершающего события (а значит, и на сроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этого события и продолжительности (длины) максимального из следующих за ним путей не превысит длины критического пути. Поэтому поздний (или предельный) срок t^п(i) свершения i-ого события равен:

t^п(i) = t_kp - max(t(L_ci))

где L_ci - любой путь, следующий за i-ым событием, т.е. путь от i-ого до завершающего события сети.

Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле:

t^п(i) = min[t^п(j) - t(i,j)]

Резерв времени R(i) i-ого события определяется как разность между поздним и ранним сроками его свершения:

R(i) = t^п(i) - t^p(i)



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

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

При определении ранних сроков свершения событий tp(i) двигаемся по сетевому графику слева направо и используем формулы (1), (2).

Расчет сроков свершения событий

Для i=1 (начального события), очевидно tp(1)=0.

i=5: t^p(5) = t^p(1) + t(1,5) = 0 + 6 = 6.

i=6: t^p(6) = t^p(1) + t(1,6) = 0 + 4 = 4.

i=7: t^p(7) = t^p(1) + t(1,7) = 0 + 1 = 1.

Длина критического пути равна раннему сроку свершения завершающего события 7: t_kp=tp(7)=0

При определении поздних сроков свершения событий t_п(i) двигаемся по сети в обратном направлении, то есть справа налево и используем формулы (3), (4).

Для i=7 (завершающего события) поздний срок свершения события должен равняться его раннему сроку (иначе изменится длина критического пути): t^п(7)= t^р(7)=0

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 6. Просматриваются все строчки, начинающиеся с номера 6.

(6,1): 0 - 8 = -8;

(6,4): 0 - 3 = -3;

(6,5): 0 - 2 = -2;

i=6: min(t^п() - t;t^п() - t;t^п() - t) = min( - ; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Просматриваются все строчки, начинающиеся с номера 4.

(4,1): 0 - 4 = -4;

(4,3): 0 - 1 = -1;

i=4: min(t^п() - t;t^п() - t) = min( - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 2. Просматриваются все строчки, начинающиеся с номера 2.

(2,1): 0 - 1 = -1;

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Просматриваются все строчки, начинающиеся с номера 5.

(5,4): 0 - 2 = -2;

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Просматриваются все строчки, начинающиеся с номера 4.

(4,1): 0 - 4 = -4;

(4,3): 0 - 1 = -1;

i=4: min(t^п() - t;t^п() - t) = min( - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 1. Просматриваются все строчки, начинающиеся с номера 1.

(1,5): 0 - 6 = -6;

(1,6): 0 - 4 = -4;

i=1: min(t^п(7) - t(1,7);t^п() - t;t^п() - t) = min(4 - 1; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 4. Просматриваются все строчки, начинающиеся с номера 4.

(4,1): 0 - 4 = -4;

(4,3): 0 - 1 = -1;

i=4: min(t^п() - t;t^п() - t) = min( - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 3. Просматриваются все строчки, начинающиеся с номера 3.

(3,1): 0 - 4 = -4;

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 1. Просматриваются все строчки, начинающиеся с номера 1.

(1,5): 0 - 6 = -6;

(1,6): 0 - 4 = -4;

i=1: min(t^п(7) - t(1,7);t^п() - t;t^п() - t) = min(4 - 1; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 1. Просматриваются все строчки, начинающиеся с номера 1.

(1,5): 0 - 6 = -6;

(1,6): 0 - 4 = -4;

i=1: min(t^п(7) - t(1,7);t^п() - t;t^п() - t) = min(4 - 1; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 1. Просматриваются все строчки, начинающиеся с номера 1.

(1,5): 0 - 6 = -6;

(1,6): 0 - 4 = -4;

i=1: min(t^п(7) - t(1,7);t^п() - t;t^п() - t) = min(4 - 1; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 6. Просматриваются все строчки, начинающиеся с номера 6.

(6,1): 0 - 8 = -8;

(6,4): 0 - 3 = -3;

(6,5): 0 - 2 = -2;

i=6: min(t^п() - t;t^п() - t;t^п() - t) = min( - ; - ; - ) = 0.

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 5. Просматриваются все строчки, начинающиеся с номера 5.

(5,4): 0 - 2 = -2;

Далее просматриваются строки, оканчивающиеся на номер предпоследнего события, т.е. 1. Просматриваются все строчки, начинающиеся с номера 1.

(1,5): 0 - 6 = -6;

(1,6): 0 - 4 = -4;

i=1: min(t^п(7) - t(1,7);t^п() - t;t^п() - t) = min(4 - 1; - ; - ) = 0.

Перечень работ и их продолжительность перенесем во вторую и третью графы. При этом работы следует записывать в графу 2 последовательно: сначала начиная с номера 1, затем с номера 2 и т.д.

Во второй графе поставим число, характеризующее количество непосредственно предшествующих работ (КПР) тому событию, с которого начинается рассматриваемая работа.

Так, для работы (1,5) в графу 1 поставим число 0, т.к. на номер 1 оканчиваются 0 работы: (2,1),(3,1),(4,1),(6,1).

Графу 4 получаем из таблицы 1 (t^p(i)). Графу 7 получаем из таблицы 1 (t^п(i)).

Значения в графе 5 получаются в результате суммирования граф 3 и 4.

В графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3);

Содержимое графы 8 (полный резерв времени R(ij)) равно разности граф 6 и 4 или граф 7 и 5. Если R(ij) равен нулю, то работа является критической

Таблица 1 - Анализ сетевой модели по времени

Работа (i,j)	Количество предшествующих работ	Продолжительность tij	Ранние сроки: начало tijР.Н.	Ранние сроки: окончание tijР.О.	Поздние сроки: начало tijП.Н.	Поздние сроки: окончание tijП.О.	Резервы времени: полныйRijП	Независимый резерв времени RijН	Частный резерв I рода, Rij1	Частный резерв II рода, RijC
(1,5)	0	6	0	6	-6	0	-6	0	-6	0
(1,6)	0	4	0	4	-4	0	-4	0	-4	0
(1,7)	0	1	0	1	3	4	3	3	3	3
(2,1)	0	1	0	1	-1	0	-1	-1	-1	-1
(3,1)	0	4	0	4	-4	0	-4	-4	-4	-4
(4,1)	0	4	0	4	-4	0	-4	-4	-4	-4
(4,3)	0	1	0	1	-1	0	-1	-1	-1	-1
(5,4)	1	2	6	8	-2	0	-8	-2	-2	-8
(6,1)	1	8	4	12	-8	0	-12	-8	-8	-12
(6,4)	1	3	4	7	-3	0	-7	-3	-3	-7
(6,5)	1	2	4	6	-2	0	-6	4	-2	0
(7,2)	1	8	1	9	-8	0	-9	-9	-9	-9
(7,4)	1	5	1	6	-5	0	-6	-6	-6	-6
(7,6)	1	1	1	2	-1	0	-2	2	-2	2

Следует отметить, что кроме полного резерва времени работы, выделяют еще три разновидности резервов. Частный резерв времени первого вида R₁ - часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. R₁ находится по формуле:

R(i,j)= R^п(i,j) - R(i)

Частный резерв времени второго вида, или свободный резерв времени Rc работы (i,j) представляет собой часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом раннего срока ее конечного события. Rc находится по формуле:

R(i,j)= R^п(i,j) - R(j)

Значение свободного резерва времени работы указывает на расположение резервов, необходимых для оптимизации.

Независимый резерв времени Rн работы (i,j) - часть полного резерва, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие начинаются в ранние сроки. Rн находится по формуле:

R(i,j)= R^п(i,j)- R(i) - R(j)

В данном случае имеются несколько критических путей:

Продолжительность критического пути: 0

Размещено на Allbest.ru

...