- •§1. Постановка задачи.....................................................................46
- •§1. Основные понятия..................................................................61.
- •§1. Основные понятия.................................................................81
- •§1 Основные понятия.
- •§ 2 Классификация моделей
- •§ 3 Классификация решаемых экономических задач.
- •Классификация решаемых экономических задач.
- •Глава 2. Линейное программирование
- •§ 1 Общая постановка задачи
- •§ 2 Двойственность в задачах линейного программирования
- •Правила построения двойственной задачи по имеемой прямой задаче:
- •§ 3 Теоремы двойственности.
- •§4 Решение задач линейного программирования геометрическим методом
- •Алгоритм геометрического метода решения задач лп.
- •Рассмотрим задачу.
- •§ 5 Симплексный метод решения задач лп
- •Глава 3. Транспортная задача
- •§ 1 Постановка задачи.
- •§ 2 Алгоритм решения транспортных задач.
- •Метод наименьшего элемента.
- •Метод потенциалов.
- •§ 3 Примеры решения транспортных задач.
- •1.Проверяем задачу на сбалансированность.
- •Составляем математическую модель прямой и двойственной задач.
- •Решаем задачу по методу максимального элемента.
- •Глава 4 . Целочисленное программирование
- •§ 1 Постановка задачи целочисленного программирования.
- •§ 2 Графический метод решения задач целочисленного программирования.
- •Алгоритм графического решения задачи целочисленного программирования.
- •§ 3 Пример решения задачи целочисленного программирования.
- •Контрольные вопросы.
- •Глава 5 . Динамическое программирование
- •§1. Постановка задачи.
- •§2. Принцип оптимальности Беллмана.
- •§3. Задача распределения средств на 1 год
- •§4. Задача распределения средств на два года
- •Глава 6 . Управление производством.
- •§ 1 Управление производством.
- •§ 2 Управление запасами .Складская задача.
- •Глава 7. Теория игр.
- •§1 Основные понятия.
- •§2 Антагонистические игры.
- •Геометрический способ решения антагонистических игр
- •§3 Игры с « природой».
- •Пример №1
- •2. Критерий Гурвица.
- •3. Критерий Сэвиджа (критерий минимаксного риска).
- •4. Критерий Лапласа. N
- •Пример №2
- •Глава 8. Системы массового обслуживания
- •§I. Формулировка задачи и характеристики смо
- •§2 Смо с отказами
- •2.1 Основные понятия
- •2.2 Формулы для расчета установившегося режима
- •§3 Смо с неограниченным ожиданием
- •3.1 Основные понятия
- •3.2 Формулы для расчета установившегося режима
- •§4 Смо с ожиданием и с ограниченной длиной очереди
- •4.1 Основные понятия
- •4.2Формулы для установившегося режима
- •§5 Примеры решения задач.
- •Глава 9 нелинейное програмирование.
- •§1 Основные понятия.
- •§2 Математическая модель задачи.
- •§3 Безусловный экстремум
- •§4 Условный экстремум
- •Глава 10 . Сетевое планирование.
- •§1 Основные понятия метода сетевого планирования
- •Работа, события, путь.
- •Любая работа соединяет только 2 события.
- •§2 Расчет сетевых графиков
- •Содержание практических занятий
- •Рекомендуемая литература:
Любая работа соединяет только 2 события.
Событие, из которого выходит работа, является для него начальным или последующим, а куда входит – конечным или последующим.
Работы сетевого графика обозначаются большими буквами и кодируются начальными i и конечными j событиями (А04; А01; А23;…).
События сетевого графика обозначаются малыми буквами и нумеруются в порядке последовательности развития операции.
Путь в сетевом графике – любая последовательность работ, в которой конечное событие каждой работы является началом следующей за ней работы.
Наибольший по продолжительности путь называется критическим и обозначается L кр, а его продолжительность Т кр (на рис. 1) критическим является путь a1-А01-а1-А14-а4=25 ед.времени.
Выделение критического пути является важнейшим элементом в сетевом планировании.
Критический путь позволяет:
-
Определить какие работы и события лимитируют выполнение всего комплекса работ;
-
Позволяет сосредоточить внимание руководителя не на всех работах, а прежде всего на лежащих на критическом пути;
-
Помогает ускорить выполнение работ за счет привлечения резервов, скрытых в некритических работах.
§2 Расчет сетевых графиков
На рис. 2 показана одна дуга сетевого графика со всеми величинами, необходимыми для расчета и получаемыми в результате его.
tpi Rnij,R4ij tpj
tni tij tnj
Обозначения:
i – код начального события работы;
j – код конечного события работы;
ij – код работы (дуги);
tij – продолжительность работы ij;
tрi – ранний срок свершения i-го события, самый ранний срок, в который событие может произойти;
tpj – ранний срок свершения j-го события;
tni – поздний срок свершения i-го события, - самый поздний допустимый срок свершения, при котором общая продолжительность работ по графику не увеличится;
tnj – поздний срок свершения j-го события;
tpнij – раннее начало работы ij;
tpoij – раннее окончание работы ij;
tnнij – позднее начало работы ij;
tnoij– позднее окончание работы ij;
Rnij – полный резерв времени работы, время, на которое можно задержать окончание работы, но так, чтобы при это общая продолжительность работ по графику не увеличилась;
Rчij – частный резерв работы, - время, на которое можно задержать окончание работы так, чтобы ранний срок свершения события j не увеличился.
Алгоритм расчета сетевого графика.
-
Для начального события 1 назначается tp1=0.
-
Достигаемая от начального события графика к конечному. Последовательно просматриваются события в порядке возрастания их кодов и вычисляются ранние сроки свершения событий по формуле tpj=max(tpi+tpj). Если в событие j входит несколько дуг, то по каждой их них вычисляется величина tpi+tij и в качестве tpj принимается большая из рассчитанных величин.
-
Для конечного события графика (код его обозначим k) назначается tnk=tpk – поздний срок свершения конечного события равен раннему сроку свершения этого события.
-
Двигаемся от конечного события графика к начальному. Просматриваются события в порядке убывания их кодов и вычисляются поздние сроки свершения событий по формуле: tni=min(tnj-tij). Если из события i выходит несколько дуг. То по каждой их них вычисляется величина tnj-tij и в качестве tnj принимается меньшая. Если расчет произведен без ошибок, то для начального события графика должно оказаться tn1=0.
-
Формулы для вычислений по работам:
tpnij=tpi; tnoij=tnj;
tpoij=tpi+ tij; Rnij= tnj- tpi- tij;
tnнij= tnj- tij; Rчij= tpj- tpi- tij.
Можно ограничится расчетом на графике. Иногда результаты расчета показывают в таблице.
-
i
j
tij
tpnij
tpoij
tnнij
tnoij
Rnij
Rчij
На рис. 3 показан график с рассчитанными сроками свершения событий. Ранние сроки пишутся над событиями, поздние сроки – под событиями. Критический путь показан двойной линией.
28
18
25
39
20
69
24
14
15
21
48
0
10
10
8
8
20
20
28
55
48
14
В следующей таблице показаны результаты графика:
Работа |
tij |
Р.Н. |
Р.О. |
П.Н. |
П.О. |
Резерв |
Rчij |
|
i |
J |
tpnij |
tpoij |
tnнij |
tnoij |
Rnij |
||
(1 |
2) |
10 |
0 |
10 |
0 |
10 |
0 |
0 |
(1 |
3) |
8 |
0 |
8 |
12 |
20 |
12 |
0 |
(2 |
4) |
18 |
10 |
28 |
17 |
35 |
7 |
0 |
(2 |
5) |
14 |
10 |
24 |
10 |
24 |
0 |
0 |
(2 |
6) |
18 |
10 |
28 |
26 |
44 |
16 |
16 |
(3 |
4) |
15 |
8 |
23 |
20 |
35 |
12 |
5 |
(4 |
7) |
20 |
28 |
48 |
35 |
55 |
7 |
0 |
(5 |
6) |
20 |
24 |
44 |
24 |
44 |
0 |
0 |
(5 |
7) |
0 |
24 |
24 |
55 |
55 |
31 |
24 |
(5 |
8) |
15 |
24 |
39 |
33 |
48 |
9 |
0 |
(6 |
9) |
25 |
44 |
69 |
44 |
69 |
0 |
0 |
(7 |
9) |
14 |
48 |
52 |
55 |
69 |
7 |
7 |
(8 |
9) |
21 |
39 |
60 |
48 |
69 |
9 |
9 |
После упорядочения сетевого графика для наглядности рекомендуется дополнить его линейной диаграммой.
В ней критическое время комплекса работ равно координате
на оси времени самого правого конца всех отрезков
диаграммы.
Пример задачи.
Дан перечень работ и время выполнения каждой работы.
Составить сетевой график и определить сколько всего времени
понадобится на выполнение всех работ.
Решение.
-
Составляется сетевой график.
-
Составляется таблица и рассчитываются критические работы и определяются резервы времени.
1
3 5
2
Работа |
tij |
Р.Н. |
Р.О. |
П.Н. |
П.О. |
Резерв |
(ij) |
tpnij |
tpoij |
tnнij |
tnoij |
Rnij |
|
(0,1) |
1 |
0 |
1 |
0 |
1 |
0 |
(1,2) |
2 |
1 |
3 |
1 |
3 |
0 |
(1,3) |
3 |
1 |
4 |
2 |
5 |
1 |
(2,4) |
3 |
3 |
6 |
3 |
6 |
0 |
(3,5) |
5 |
4 |
9 |
5 |
10 |
1 |
(4,5) |
4 |
6 |
10 |
6 |
10 |
0 |
(4,6) |
6 |
6 |
12 |
7 |
13 |
1 |
(5,6) |
3 |
10 |
13 |
10 |
13 |
0 |
(6,7) |
2 |
13 |
15 |
13 |
15 |
0 |
Ответ:
-критический путь – 15 ед. времени;
-резерв в работах (1-3), (3-5), (4-6) по 1 ед. времени.
Контрольные вопросы:
-
В чем состоит задача сетевого планирования?
-
Что является исходной информацией для анализа?
-
Дайте определение сетевого графика.
-
Какие основные элементы сетевого графика?
-
Как строится временной сетевой график?
-
Что такое критический путь?
-
Что такое резерв времени в сетевой задаче и как он определяется?
-
Как построить таблицу для расчета сетевого графика?
-
Какой алгоритм сетевого планирования?
-
Какие оптимизационные задачи ставятся в рамках сетевого планирования?