5. Временные параметры сетевых графиков

1. Ранний срок свершения события: t_p(0) = 0,

t_p(j) = max_i {t_p(i) + t(ij)}, j = 1/N, характеризует самый ранний срок завершения всех путей в него входящих. Этот показатель определяется, начиная с начального события сети.

2. Поздний срок свершения события: t_п(N) = t_p(N),

t_п(i) = min_j {t_п(j) - t(ij) }, i = 1/N-1, характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей следующих за этим событием.

3. Для каждого события определяется резерв времени:

R(i) = t_п(i) - t_p(i). Резерв показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ. Резервы времени для событий на критическом пути равны нулю, R(i)=0.

Характеристики работ (i,j):

1) Ранний срок начала работы: t_pн(i,j)=t_p(i).

2) Ранний срок окончания работы: t_po(i,j)= t_pн(i,j) + t_ij =t_p(i) + t_ij

3) Поздний срок начала работы: t_пн(i,j)=t_п(j) – t_ij.

4) Поздний срок окончания работы: t_по(i,j) = t_п(j).

5) Резерв

• Полный резерв R_п(i,j) = t_п(j) - t_p(i) - t_ij. Это максимальный запас времени, на который можно отсрочить начало или увел-ть длит-ть работы без увеличения длит-ти критич-го пути. Работы на критич-ком пути не имеют полного резерва вр., для них R_п(i,j)=0.

• Частный резерв R₁(i,j) = R_п(i,j) - R(i) = t_п(j) – t_п(i) - t_ij. Это часть полного резерва, на которую можно увеличить продолж-ть работы, не изменив позднего срока ее начального события.

• Свободный резерв R_с(i,j)=R_п(i,j)-R(j)=t_p(j)–t_p(i)-t_ij. Это max запас вр., на кот. можно задержать начало работы или увеличит ее продолж-ть, не изменяя ранних сроков начала послед-щих работ.

• Независимый резерв R_н(i,j)=R_п(i,j)-R(i)–R(j)=t_p(j)–t_п(i)-t_ij. Запас вр., при кот. все предшествующие работы заканч-ся в поздние сроки, а все последующие – нач-ся в ранние сроки. Использование этого резерва не влияет на величину резервов вр. других работ.

6. Общая постановка злп. Формы записи злп.

Мат. программир-ие – область математики, разработ-ая теорию и числ. методы решения многомерных экстрем-х задач.

Ф-ия, экстрем. значение кот-ой необх-о найти, называют целевой.

Модель ЗЛП вкл-т: - совок-ть неизв-ых величин х=(х₁, х₂…)

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

ЗЛП – целевая функция и сис-а ограничений линейны.

Общая форма записи ЗЛП f(x)= c₁x₁+c₂x₂+…+c_nx_n→max (цел. ф-ия). система (осн. ограничения)

a₁₁x₁+a₁₂x₂+…+a_nx_n=b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n=b₂

………………………

a_m1x₁+a_m2x₂+…+a_mnx_n=b_m

x_j≥0 (прямые ограничения)

Введем обозначения: a₁₁ a₁₂ … a_1n

;;; A= a₂₁ a₂₂ … a_2n

x – вектор неизвестных (план) …………..

с – вектор целей a_m1 a_m2…a_mn

b – вектор ограничений

А – матрица условий

Тогда стандарт. форма записи ЗЛП в матричном виде

с'х→мах с'х→мin

Ах≤b Ах≥b

x≥0 x≥0

если сис-а ограничений представлена одними ур-ями, то ЗЛП выражена в канонической форме.

с'х→мах(мin) ; Ах=b ; x≥0

maxf(x)=-minf(x), т.к. люб. задачу на мах можно свести на min и наоборот, то мы будем рассм-ть только задачи максимизации.

от неравенства a_i1x₁+a_i2x₂+…+a_inx_n≤b_i можно перейти к ур-ю введя доп. переменную a_i1x₁+a_i2x₂+…+a_inx_n+x_n+1 =b_i.

если же мы имеем дело с равенством a_i1x₁+a_i2x₂+…+a_inx_n=b_i, то вводим 2 нер-тва a_i1x₁+a_i2x₂+…+a_inx_n≤b_{i ;} a_i1x₁+a_i2x₂+…+a_inx_n≥b_i

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