БИЛЕТ 6 ВОПРОС 1 Алгоритм нумераций событий структурного плана

Упорядоченную нумерацию событий проводят по алгоритму:

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

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

БИЛЕТ 6 ВОПРОС 2 Метод ветвей и границ.

Для определения истинного значения целочисленных переменных применяется метод отсечений и метод ветвей и границ.

Первый базируется на идее деформации ОДР задачи ЛП таким образом, чтобы от нее было отсечено оптимальное нецелочисленное решение, но сохранены все допустимые целочисленные решения.

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

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

Второй метод основан на идее проверочной подстановки всех допустимых целочисленных значений в целевую функцию и сравнении полученного результата. Естественно что удобной для использования это идея становится лишь тогда, когда полный перебор может быть сокращен дополнительными рассуждениями, основанными на принципе разветвления комбинаторского прог - ия.

БИЛЕТ 7 ВОПРОС 1 Расчет временных параметров событий структурного плана: организационный смысл параметров и методика определения значений

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

Расчет начинается с ранних сроков наступления событий, определяемых по формуле 10.1.

(10.1),

где Тран(j) - ранний срок свершения события j;

Ui - множество событий, непосредственно предшествующих событию j;

Тран(i) - ранний срок свершения события i;

tij - продолжительность работы (i, j).

Определение Тран(j) - ведут строго по порядку номеров, начиная с первого события, приняв ранний срок свершения исходного события равным нулю Тран(0)=0.

Вычисления продолжают вплоть до завершающего n -го события.

С организационной точки зрения ранний срок свершения события - это минимально необходимое время для выполнения всех предшествующих работ. Отсюда ранний срок свершения конечного события представляет - собой минимальное время, необходимое для выполнения комплекса работ. Это время необходимо для реализации самого длинного, "критического" пути, соединяющего начало и конец сети. В дальнейшем это время будет обозначаться S и определятся как

S = Тран(n) (10.2).

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

Тпоз(n) = Тран(n) = S (10.3).

Вычисления выполняют, начиная с последнего события, в порядке строгого убывания номеров по формуле

(10.4),

где Тпоз(i) - поздний срок свершения события i;