- •Математические методы исследования операций и теории иГр
- •Введение
- •Глава 1. Задачи линейного программирования
- •1. Постановка задачи линейного программирования (злп)
- •2. Графический метод решения злп
- •3. Симплекс – метод решения злп
- •Метод искусственного базиса
- •Двойственные злп
- •Двойственный симплекс-метод
- •Алгоритм двойственного симплекс-метода.
- •Метод ветвей и границ решения задачи цлп
- •Алгоритм метода ветвей и границ
- •Оптимальность по Парето
- •Множество Парето
- •Постановка задачи
- •Метод идеальной точки
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 2. Теория игр
- •1. Основные понятия теории игр
- •Принцип доминирования
- •2. Задачи теории игр и линейное программирование
- •3. Игры с природой
- •Применение матричных игр в прикладных задачах
- •Переговоры о заключении контракта между профсоюзом и администрацией
- •Локальный конфликт
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Имитационное моделирование
- •Основные понятия
- •Типы имитационных моделей.
- •Принципы построения дискретных имитационных моделей
- •Метод Монте-Карло (метод статистических испытаний)
- •Применение имитационных моделей в системах массового обслуживания
- •Вопросы для повторения.
- •Глава 4. Сетевое планирование
- •1. Сетевой график
- •Оптимизация пути на сети
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Заключение
- •Библиографический список
- •Оглавление
- •3 94026 Воронеж, Московский просп., 14
Глава 4. Сетевое планирование
1. Сетевой график
Если выполняется сложный комплекс работ (строительство дома, проведение избирательной компании), требуется согласовывать отдельные работы, с тем, чтобы завершить их в наиболее короткие сроки, или распределить финансы, оборудование, материалы, прочие ресурсы, чтобы вся работа обошлась дешевле. Ответы на поставленные вопросы можно получить методами сетевого планирования.
Намеченный комплекс работ, необходимый для достижения некоторой цели, называется проектом. Примеры: проект строительства здания, сервировки стола, написания контрольной и т.д.
Каждая отдельная работа, входящая в проект, требует затраты определённого времени. Некоторые работы можно выполнить только в определённом порядке (сначала купить гуся, потом зажарить), другие – одновременно (приготовление стола и жарка гуся).
Если каждому отдельному событию, входящему в проект, поставить в соответствие некоторую точку (вершину), а каждой работе – отрезок с учётом его направления (ориентированное ребро), то получится орграф, отражающий последовательность выполнения отдельных работ в общем проекте.
Рис. 19.
Схема выполнения работ при начале строительства здания.
0 - начало
1 - котлован готов
2 - фундамент подведён
3 - металлоконструкции завезены
4 - смонтирован кран
Если над рёбрами поставить время, необходимое для завершения соответствующей работы, то получится сеть, то есть орграф, рассматриваемый вместе с функцией, приписывающей каждому ребру некоторое положительное действительное число. Изображение сети называется сетевым графиком (сетевым графом). Если для начала какой - то работы требуется завершение нескольких работ, для отражения очерёдности их выполнения используются штриховые стрелки.
Рис. 20. Пример сетевого графика.
Сетевой график является графической моделью всего проекта. Он отражает взаимосвязь всех работ.
Любая стрелка на сетевом графике соединяет только две вершины и отражает переход от одного события к другому. Стрелки используются для отображения:
действительной работы (любой трудовой процесс, требующий затрат труда, времени и материальных ресурсов);
б) ожидания (пассивный процесс, требующий временных
затрат - «что-то сохнет …»);
в) фиктивной работы (чисто условная зависимость между
событиями, не связанная с какими - либо затратами, и
вводимая для удобства изображения сети).
При этом для отображения действительной работы и ожидания используют сплошные стрелки, а фиктивная работа отображается штриховыми стрелками.
Рис. 21. Пример сетевого графика.
До события 3 надо произвести работы 1, 2, 4 - 6.
Событие 0 - исходное.
Событие 7- завершающее.
Остальные - промежуточные.
При построении сетевых графиков следят, чтобы:
из всех вершин, кроме “завершающей”, выходили стрелки;
во все вершины, кроме исходной, входили стрелки;
если одно событие служит началом для двух или более работ, после завершения которых начинается выполнение следующей работы, то вводится штриховая стрелка и дополнительное событие со своим номером.
Рис. 22. Пример сетевых графиков.
Вообще, на сетевом графике надо чётко отражать последовательность выполнения отдельных работ и их взаимосвязи.
Не допускаются циклы, то есть пути, у которых совпадают начальные и конечные вершины.
Рис. 23. Примеры циклов.
Рис. 24. Пример сетевого графика, содержащего ошибки.
Ошибки:
у вершины 2 нет входа;
у вершины 8 нет входа;
имеется цикл