- •Математические методы исследования операций в экономике
- •Математические методы исследования операций в экономике
- •Введение
- •Глава 1. Задачи линейного программирования
- •1. Постановка задачи линейного программирования (злп)
- •2. Графический метод решения злп
- •3. Симплекс – метод решения злп
- •4. Двойственные злп
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 2. Теория игр
- •1. Основные понятия теории игр
- •Принцип доминирования
- •2. Задачи теории игр и линейное программирование
- •3. Игры с природой
- •Применение матричных игр в прикладных задачах
- •Переговоры о заключении контракта между профсоюзом и администрацией
- •Локальный конфликт
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Теория массового обслуживания
- •Основные понятия
- •Смо с отказами
- •Смо с неограниченным ожиданием
- •Смо с ожиданием и с ограниченной длиной очереди
- •5. Расчёт характеристик замкнутой смо с ожиданием.
- •Вероятность того, что занято обслуживающих каналов при условии, что число требований, находящихся в системе, не превосходит числа обслуживающих каналов системы:
- •Вопросы для повторения.
- •Глава 4. Сетевое планирование
- •1. Сетевой график
- •Оптимизация пути на сети
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Оптимизация пути на сети
Пусть сетевой график построен. За какое время его можно осуществить?
Путём в сети называется последовательность рёбер, такая, что конец каждого ребра совпадает с началом следующего и ни одно ребро не встречается больше одного раза.
Продолжительностью пути называется время, необходимое для выполнения всех работ, лежащих на нём.
Рассмотрим все пути, ведущие от исходного события к завершающему. Как правило, их несколько. Путь с наибольшей продолжительностью называется критическим путём, а работы, на нём лежащие - критическими.
Оказывается, минимальное время осуществления всего проекта равно продолжительности критического пути. Действительно, все работы, в том числе критические, необходимо выполнять в порядке, который определяет сетевой график, то есть движение по критическому пути неизбежно. Кстати, в сети может быть несколько критических путей.
Понятно, что сокращение или увеличение сроков выполнения критических работ соответственно сокращает или увеличивает общее время выполнения проекта.
На сетевом графике критический путь выделяют более жирными стрелками.
Что касается работ, не лежащих на критическом пути, то они, вообще говоря, допускают некоторое запаздывание в их выполнении, которое не задержит сроков реализации всего проекта.
Для отыскания критического пути на сети и его продолжительности применяется алгоритм пошаговоё оптимизации. Он основан на принципе оптимальности Р. Беллмана: критический путь обладает тем свойством, что каков бы ни был его отрезок от исходной до некоторой вершины сети, оставшаяся часть критического пути между этой и завершающей вершинами должна быть наиболее продолжительной.
Рассмотрим использование этого алгоритма на примере конкретного сетевого графика (цифры в нижних половинках кружков являются номерами этих вершин).
Обозначим через продолжительность наиболее «долгого пути», ведущего от вершины 0 к вершине . Тогда В соответствии с принципом оптимальности Р.Беллмана получаем:
(*)
где - множество вершин сети, непосредственно предшествующих - ой вершине (при =5, например, ), - продолжительность работы между -ой и -ой вершинами ( ).
В нашем случае:
Заметим, что в рассмотренном примере вершина 3 при вычислениях предшествовала вершине 2, а вершина 6 - вершине 5.
Итак, время (наименьшее) выполнения всего проекта равно 48 единицам. Соответствующий этому времени путь несложно восстановить, двигаясь назад от завершающей вершины 9 к исходной 0. В вершину 9 можно попасть лишь из вершины 8 (48 = 42+6), в 8 - из 6 (42 = 29+13), в 6 - из 2 (29 = 20+9), в 2 - из 3 (20 = 13+7) и, наконец, в 0 - из 3 (13 = 13+0).
Таким образом, критический путь
Аналогичным образом можно определить кратчайший путь на сети. Для этого в формуле (*) достаточно заменить на В нашем случае этот путь, точнее пути и имеют продолжительность 22 единицы.
Действительно,
В заключение отметим, что все вычисления можно выполнять непосредственно на сети. При этом полезно вычёркивать рёбра, «прошедшие «обработку», и последовательно приписывать каждой рассмотренной вершине наиболее продолжительное время её достижения из 0, как это сделано на последнем рисунке.