Лекция № 19 Методы сетевого планирования в УР

Минимаксный критерий.

Правило выбора решения в соответствии с минимаксным критерием (ММ-критерием) можно интерпретировать следующим образом:

матрица решений дополняется ещё одним столбцом из наименьших результатов e_ir каждой строки. Необходимо выбрать те варианты в строках которых стоят наибольшее значение e_ir этого столбца.

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

Применение ММ-критерия бывает оправдано, если ситуация, в которой принимается решение следующая:

1^o. О возможности появления внешних состояний F_j ничего не известно;

2^o. Приходится считаться с появлением различных внешних состояний F_j;

3^o. Решение реализуется только один раз;

4^o. Необходимо исключить какой бы то ни было риск.

Б) Критерий Байеса – Лапласа. В). Критерий Сэвиджа

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

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

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

2 4 7

1

3 5 8

В методе сетевого планирования выделяют три основных понятия:

- событие;

- работа;

- путь.

Событие – момент начала или окончания работы.

Работа – обычное понятие i j.

Работа фиктивная () – связь между событиями.

Путь – последовательность работ от начального события до конечного события.

Правила построения графиков:

1. событие не считается наступившим, пока не выполнены все работы ведущие к нему;

2. каждому событию присваивается свой номер, нумерация слева направо;

3. событие j должен иметь номер больше i;

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

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

Расчет графиков складывается из определения:

1. ранних сроков наступления событий;

2. поздних сроков наступления событий;

3. нормы резерва времени (полный резерв);

4. свободного резерва времени;

5. критического пути.

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

t_ij= (a+4m+b)/6 (19.1)

Определение ранних сроков наступления событий

T^p_j= max(T^p_i + t_ij)

Определение поздних сроков наступления событий

Tⁿ_j = min(Tⁿ_j – t_ij)

Расчет резервов времени выполняется стандартными способами.

Дата добавления: 2014-01-13