Временной анализ (для детерминированной сети)

Временной анализ – определяются времена событий, времена начала, окончания работ, всего комплекса, резервов, критических работ. Критический путь (T_кр) – самый длинный полный путь; минимальное время, за которое может быть выполнен весь комплекс работ при исходных данных Работы, из которых состоит критический путь – критические (начальные и конечные события имеют нулевые резервы событий). Для событий определяются:

1. Ранние сроки наступления i-го события – срок, раньше которого не м наступить это событие. Номер исходного события - 1. T₁^р=0. Далее расчет ранних сроков свершения событий ведется от исходного к завершающему событию. , где максимум берется по всем работам , входящим в событие i. Т_n^р=Т_кр.

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

Для завершающего события . Для остальных , где минимум берется по всем работам , выходящим из события i.

 

3. . – резерв события - показывает максимальное время, на которое можно увеличить продолжительность отдельной работы или отсрочить ее начало, не меняя ранних сроков начала последующих работ. L=T_n^р→min; T_j^р- T_i^р>=t_ij

Параметры работ: определяются сроки окончания работ и резервы

1) - ранний срок начала работы;

2) - поздний срок начала работы

3) - ранний срок окончания работы

4) ; - поздний срок окончания работы

5) ; - полный резерв

6) . - свободный резерв; r_св<=r_п. сети PERT

55. Задачи СПУ: оптимизация.

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

Случай 1.

Исходные данные: Х - дополнительные средства. х_i – дополнительные средства, которые добавляются к ресурсам i – ой работы. T_пл – плановое время (срок выполнения работ).

Условия:

T_кр > T_пл

, где n – завершающее событие.

, у которых дуга ij входит в событие.

Если линейная, то задача ЛП.

Вкладывая средства добиваемся наименьшего срока выполнения.

Случай 2. минимизируем критический путь

Варианты распределения: - средства, которые мы можем переместить. - количество средств, которые добавляем на выполнение операции. - количество средств, которые снимаем с операции.

; ; ;

Случай 3. По стоимости:

; ; ; ; ; ;

56. Многокритериальные задачи: постановка, проблемы, основные понятия, методы.

Многокритериальность может быть обусловлена одной из трех причин:

1. Цель не может быть адекватно представлена (покрыта) одним критерием.

2. Принимающий решения ставит более 1 цели, которые связаны общими активными средствами.

3. Решения принимаются группой лиц с несовпадающими интересами.

В формальном представлении критерии (целевые функции), по которым оценивается решение Х, будет записываться в виде f_i (Х), . Критерий f_i называют также частными. Задача:

max{ f ₁(X)= y ₁}, max{ f ₂(X)= y ₂},....... max{ f_m (X)= y_m }, Х D, где D – множество допустимых решений. Иначе говоря, задача состоит в максимизации вектора критериев f (X)=Y по X D.

При многих критериях увеличение одних критериев приводит к уменьшению других, поэтому понятие оптимальности требует уточнений. Требуется дополнительная информация о предпочтениях ЛПР. Допустимое множество D строится в n -мерном пространстве переменных Числовое m -мерное пространство E ^m, координатами которого являются y_i=f_i (X), называется критериальным пространством. Каждому Х можно поставить в соответствие точку в критериальном пространстве. Если решение Х допустимо, то соответствующая точка в E ^m - достижимая. Множество таких точек в критериальном пространстве - множество достижимости (достижимых векторов). Векторная функция f (X) отображает допустимое множество D на множестве достижимости G: и задача состоит в выборе вектора из этого множества, наилучшего с точки зрения ЛПР.

Учитывая стремление ЛПР к увеличению значений всех частных критериев, можно формальными методами исключить из множества G (и D) заведомо не перспективные точки и тем самым облегчить решение задачи. Пример: с двумя критериями. Независимо от предпочтений ЛПР, вектор критериев, соответствующий точке 2, лучше, чем в точке 1. Аналогично, точка 3 лучше точки 2, а 4 лучше 3. Но точки 4 и 5 оказываются не сравнимыми, так как по первому критерию лучше точка 5, а по второму – точка 4. Как для точки 5, так и для 4 на множестве G можно найти лучшую точку, например 6. Для любой точки Y внутри G найдется точка, которая ее доминирует, т.е. лучше хотя бы по одному частному критерию и не хуже по всем другим. В то же время для точек 6 или 7 этого сделать нельзя. Более того, не найдется вектора из G, который доминировал бы точку, принадлежащую северо-восточной границе AB множества G. Векторы на АВ являются недоминируемыми (неулучшаемыми). Одновременно они являются несравнимыми между собой, поэтому отдать предпочтение одному из них без ЛПР невозможно. Такие точки называют эффективными или оптимальными по Парето. Их совокупность образует множество Парето (паретовское множество). Оптимальное решение следует искать только среди эффективных точек. Если эффективная точка одна (А на рис.), то она и является искомым оптимумом.

Если из двух объектов a и b ЛПР выбирает a, то говорят, что a предпочтительнее b. Все пары вида (a,b), где a,bÎА, для которых a предпочтительнее b, образуют множество, называемое отношением строгого предпочтения на А. Такое отношение обозначают символом ý (a ý b или a P b).

Объекты a и b неразличимы для ЛПР, если они одинаковы по предпочтительности; не выполняется ни отношение a ý b, ни b ý a. Множество всех неразличимых пар (a, b) называют отношением неразличимости или безразличия и обозначают символом ~ (a~b или a I b).

Для любой пары a,b A выполняется только одно из трех соотношений: a ý b, b ý a, a~b. Объединение P и I дает отношение нестрогого предпочтения, обозначаемого символом (a b или a R b). Отношение a b означает, что a не менее предпочтительно, чем b.

В соответствии с этими определениями решение Х * D (вектор Y * G) называют оптимальным по отношению ý на множестве D (G), если не существует другого решения Х D (вектора Y G), для которого справедливо соотношение ХýХ * (YýY*). Если для любых X D ( Y G) выполняется соотношение X * X (Y* Y), то X * D ( Y * G) называется оптимальным решением (вектором) по отношению.

Задачи, в которых все критерии независимы по предпочтению, а отношением строгого предпочтения R является отношение >= (не меньше) называются многокритериальными задачами максимизации (аналогично при отношении «не больше» – задачами минимизации).

Вектор (решение), оптимальный по отношению ≥ на множестве G (D), называется эффективным или парето-оптимальным. Вектор, оптимальный по отношению >, называют слабо эффективным, слабо оптимальным по Парето (слабым оптимумом Парето).

Числовая функция F (Y), определённая на множестве G, является возрастающей по отношению ³, если из выполнения неравенства Y³Y ^¢ всегда следует справедливость неравенства F (Y) >F (Y^¢). Аналогично, F (Y) – функция, возрастающая по отношению >, если из Y>Y ^¢ всегда следует F (Y )>F (Y^¢).

Пусть функция F (Y ) определена на множестве G. Для того чтобы точка Y^*Î G была эффективной (слабо эффективной), достаточно, чтобы она являлась точкой максимума на множестве G функции F (Y), возрастающей по отношению ³ (по отношению >).

F= , где .