Любая работа соединяет только 2 события

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

Работы сетевого графика обозначаются большими буквами и кодируются начальными i и конечными jсобытиями (А04; А01; А23;…).

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

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

Наибольший по продолжительности путь называется критическим и обозначается L кр, а его продолжительность Т кр (на рис. 1) критическим является путь a1011144=25 ед.времени.

Выделение критического пути является важнейшим элементом в сетевом планировании.

Критический путь позволяет:

1. Определить какие работы и события лимитируют выполнение всего комплекса работ;

2. Позволяет сосредоточить внимание руководителя не на всех работах, а прежде всего на лежащих на критическом пути;

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

Расчет сетевых графиков

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

tpi Rnij,R4ij tpj

       
  Любая работа соединяет только 2 события - student2.ru   Любая работа соединяет только 2 события - student2.ru

Любая работа соединяет только 2 события - student2.ru

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. Для начального события 1 назначается tp1=0.

2. Достигаемая от начального события графика к конечному. Последовательно просматриваются события в порядке возрастания их кодов и вычисляются ранние сроки свершения событий по формуле tpj=max(tpi+tpj). Если в событие j входит несколько дуг, то по каждой их них вычисляется величина tpi+tij и в качестве tpj принимается большая из рассчитанных величин.

3. Для конечного события графика (код его обозначим k) назначается tnk=tpk – поздний срок свершения конечного события равен раннему сроку свершения этого события.

4. Двигаемся от конечного события графика к начальному. Просматриваются события в порядке убывания их кодов и вычисляются поздние сроки свершения событий по формуле: tni=min(tnj-tij). Если из события i выходит несколько дуг. То по каждой их них вычисляется величина tnj-tij и в качестве tnj принимается меньшая. Если расчет произведен без ошибок, то для начального события графика должно оказаться tn1=0.

5. Формулы для вычислений по работам:

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 показан график с рассчитанными сроками свершения событий. Ранние сроки пишутся над событиями, поздние сроки – под событиями. Критический путь показан двойной линией.

Любая работа соединяет только 2 события - student2.ru

В следующей таблице показаны результаты расчета:

Работа tij Р.Н. Р.О. П.Н. П.О. Резерв Rчij
i J tpnij tpoij tnнij tnoij Rnij
(1 2)
(1 3)
(2 4)
(2 5)
(2 6)
(3 4)
(4 7)
(5 6)
(5 7)
(5 8)
(6 9)
(7 9)
(8 9)

После упорядочения сетевого графика для наглядности рекомендуется дополнить его линейной диаграммой.

В ней критическое время комплекса работ равно координате

на оси времени самого правого конца всех отрезков

диаграммы.

Пример задачи.

Дан перечень работ и время выполнения каждой работы.

Составить сетевой график и определить сколько всего времени

понадобится на выполнение всех работ.

Решение.

1. Составляется сетевой график.

2. Составляется таблица и рассчитываются критические работы и определяются резервы времени.

Любая работа соединяет только 2 события - student2.ru


Работа tij Р.Н. Р.О. П.Н. П.О. Резерв
(ij) tpnij tpoij tnнij tnoij Rnij
(0,1) 0
(1,2) 0
(1,3)
(2,4) 0
(3,5)
(4,5) 0
(4,6)
(5,6) 0
(6,7) 0

Ответ:

-критический путь – 15 ед. времени;

-резерв в работах (1-3), (3-5), (4-6) по 1 ед. времени.

Контрольные вопросы:

1. В чем состоит задача сетевого планирования?

2. Что является исходной информацией для анализа ?

3. Дайте определение сетевого графика.

4. Какие основные элементы сетевого графика?

5. Как строится временной сетевой график?

6. Что такое критический путь?

7. Что такое резерв времени в сетевой задаче и как он определяется?

8. Как построить таблицу для расчета сетевого графика?

9. Какой алгоритм сетевого планирования?

10. Какие оптимизационные задачи ставятся в рамках сетевого планирования?

11.Лекция. Нелинейное программирование.

11.1.Основные понятия.

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

Пример простой нелинейной задачи:

Предприятие для производства какого-то продукта расходует два средства в количестве х и y соответственно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а х и y – затраты факторов производства.

Факторы производства считаются взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).

Объем производства, выраженный в натуральных или стоимостных единицах, является функцией затрат производства

Z = f (х, y). Эта зависимость называется производственной функцией.

Совокупные издержки выражаются формулой с1х1 + с2y2 = в.

Требуется при данных совокупных издержках определить количество факторов производства, которое максимизирует объем продукции Z.

Математическая модель задачи:

Определить такие переменные х и у, удовлетворяющие условиям

с1х12у=в, х≥0, у≥0,

при которых функция z=f(х, у) достигнет максимума.

Ограничения могут отсутствовать. В этом случае производится безусловная оптимизация задачи. Как правило, функция z может иметь произвольный нелинейный вид. В теории нелинейной оптимизации выделяют понятие локального экстремума (локального минимума, локального максимума), глобального экстремума, условного экстремума.

Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n≥2).

Разница между глобальным и локальным экстремумами предоставлена на рисунке:

Любая работа соединяет только 2 события - student2.ru

А С В

Точки А и В являются точками локального экстремума, а точка С является точкой глобального экстремума.

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

11.2. Безусловный экстремум

Рассмотрим задачу безусловного экстремума.

Найти экстремум функции z=х²+ху+у²-2х-3у.

Найдем частные производные.

Первая производная по х: z׳х=2х+у-2

Первая производная по у: z׳у=х+2у-3

Любая работа соединяет только 2 события - student2.ru Решим систему уравнений. 2х+у=2

х+2у=3

Получаем критическую точку (1/3; 4/3).

Найдем вторые частные производные.

Вторая производная по х: z׳׳хх=2

Вторая производная по у: z׳׳уу=2

Любая работа соединяет только 2 события - student2.ru Смешанные производные z׳׳ху=z׳׳ух=1

Составим определитель 2 1

Любая работа соединяет только 2 события - student2.ru 1 2 = 4-1=3

Следовательно, экстремум есть. Так как z=2>0, то в точке (1/3; 4/3) точка минимума.

Условный экстремум

Задача на минимум.

Определить матрицы L и все ее главные миноры порядка больше чем m+1 должны иметь знак (-1)m, где m – число ограничений задачи.

Задача на максимум.

Определить матрицы L должен иметь знак (-1)n, где n – число переменных в задаче. Главный минор порядка m+n-1 должен иметь противоположный знак. Последующие миноры должны иметь чередующие знаки.

Пример: Z = f(x)=xy, х²+у²=2.

Критические точки: М1=(1, 1), М2=(-1, -1), =(1, -1), =(-1, 1).

Любая работа соединяет только 2 события - student2.ru Любая работа соединяет только 2 события - student2.ru 0 -2x -2y

L= -2x -2λ 1 Δ3=8 λ(x2+y2)+8xy Δ2=-4x2

-2y 1 -2 λ

Таким образом, максимум в точках М1, М2 (λ=0,5), минимум – в точках М3, М4 λ=-0,5.

Контрольные вопросы:

1.В чем состоит задача нелинейного программирования?

2.Что называется условным экстремумом ?

3.Что называется безусловным экстремумом ?

4.Какая разница между локальным и глобальным экстремумом?

5.Какие методы решения задач НЛП?

Наши рекомендации