Лекция №1 (стр. 4 )

Работы а1, а4, а6, а7, а9 из длительностей которых составлено время Т, называются критическими работами, а направление стрелок на графике - критическим путем. Критический путь показан двойными стрелками.

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

Некритической дугой назовем совокупность некритических работ и узлов, начинающегося и кончающегося на критическом пути. Некритические дуги : A0 - a2 - A2 - A1

A0 - a3 - A3 - a5 - A5 - A6

A0 - a2 - A2 - A3 - a5 - A3 - A6

A6 - a6 - A8 - a10 - A10 - A9

Каждой некритической дуге соответствует временной резерв, который произвольным образом распределен между некритическими работами, лежащими на данной дуге. Этот резерв равен разности между суммой времени критических работ.

Методы минимизации нулевого порядка. Поиск по деформируемому многограннику

Нелдер и Мид предложили метод поиска, несколько более сложный по сравнению с прямым поиском, но оказавшимся весьма эффективным и легко осуществляемым на ЭВМ.

В основе метода лежит стратегия симплексного поиска. Симплексами в пространстве Е называются регулярные многогранники. Например, для 2-х переменных (на плоскости) регулярный симплекс представляет собой равносторонний треугольник (три точки); в случае трех переменных (XYOZ) регулярный симплекс представляет собой тетраэдр (4 точки) и т. д.

Идея метода поиска заключается в следующем : Целевая функция может быть вычислена в каждой из вершин симплекса. Из вершины, где целевая функция максимальна (т. А) проводится проектирующая прямая через центр тяжести симплекса. Например 3 B

1 A(max f) 2 3. Затем точка А исключается и строится новый симплекс, называемый отражаемым , из оставшихся прежних точек и одной новой точки В, расположенной на проектирующей прямой на определенном расстоянии от центра тяжести. 4. Процесс итераций продолжают. Каждый раз вычеркивая вершины, где целевая функция max и используется правило уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума.

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

В методе Нелдера-Мида минимизируется функция n независимых переменных с использованием (n+1) вершин деформируемого многогранника в Е. Каждая вершина может быть идентифицирована вектором = (x1, x2, ..., xn).

Пусть i = является i-ой вершиной (точкой) в Е на k-ом этапе поиска, k = 0, 1, 2, ...

Пусть значения целевой функции в т. равно f().

Определим те векторы многогранника, которые дают min и max значения f().

Пусть f() = max {f(), ..., f()} и f() = min {f(), ..., f()} Поскольку многогранник в Е состоит из (n+1) вершин x1, ..., xn+1 пусть xn+2 будет центром тяжести всех вершин, исключая xh. Тогда координаты этого центра определяются , j = 1, ..., n (1) где индекс j обозначает координатное направление. Начальный многогранник обычно выбирается в виде регулярного симплекса с точкой 1 в качестве начала координат (можно начало координат поместить в центре тяжести).

Процедура отсекания вершины в Е, в которой f() имеет лучшее значение, состоит в следующих операций : 1. Отражение - проектирование через центр тяжести в соответствии с соотношением : = (2) где a>0 коэф-т отражения; - центр тяжести, вычисляется по формуле (1) - вершина в которой f() принимает наибольшее из n+1 ее значений на k-ом этапе. 2. Растяжение Если f() £ f(), то вектор (-) растягивается в соответствии с соотношением : = + ¡(-) где ¡ > 1 представляет коэф-т растяжения. Если f() < f(), то заменяются на и процедуры повторяются с операции 1 при k=k+1. В противном случае заменяется на и также осуществляется переход к процедуре 1 при k=k+1. 3. Сжатие. Если f() > f() для всех i¹h, то вектор сжимается в соответствии с формулой = + b( - ) где 0<b<1 - коэф-т сжатия. Затем заменяется на и возвращаемся к операции 1. 4. Редукция. Если f() > f() , то все вектора ( - ) i = 1,...,n + 1 уменьшают в 2 раза с отчетом от хl в соответствии с формулой = + 0,5 ( - ) i = 1, ..., n + 1