мальный вариант находится «обратным ходом» сверху вниз. Сначала находим вершину-кружок, смежную с начальной вершиной сети и имеющую минимальный индекс среди всех вершин, смежных с начальной. Из этой вершиныкружка исходят две дуги к вершинам-квадратам нижележащего уровня. Для каждой вершины-квадрата находим вершину-кружок, имеющую минимальный индекс среди всех вершин, смежных с соответствующей вершиной-квадратом и т.д. В результате будет выделен подграф, определяющий оптимальный вариант программы. Рассмотрим работу алгоритма на примере сети напряженных вариантов рис. 2 .2 .8 . Пр/тер 2.2.1. Пусть матрица затрат (ву) имеет вид, представленный в табл. 2 .2 .2 . Таблица 2.2.2 76 1 2 3 4 и ] 2 7 2 0 60 Б 3 1 0 35 50 Э 1 8 50 1 0 0 Индексы вершин сети, полученные на основе описанного алгоритма, указаны на рис. 2.2.8 в верхней половине соответствующих вершин. Оптимальный вариант выделен толстыми линиями. Это вариант (2; 2; 2) с затратами э0 = 25, соответствующий сбалансированному развитию по всем направлениям. К сожалению, в весьма редких случаях предположение о независимости отдельных подпрограмм по направлениям выполняется. Как правило, подпрограммы зависимы, т.е. выполнение мероприятий по одной подпрограмме влияет на критерии других подпрограмм. Особенно это касается подпрограммы повышения уровня транспортно-эксплуатационного состояния дорог, которая влияет и на состояние инженерного оборудования и обустройства и на показатель эксплуатационного содержания. Пусть для каждой оценки уровня экономической эффективности заданы затраты (вщ) и (вбД требуемые для достижения оценки], соответственно по критериям Б и И. В этом случае, метод определения программы минимальной |
различным критериям независимы, то есть мероприятия -ой подпрограммы не влияют на другие направления (цели). В этом случае существует эффективный алгоритм определения программы минимальной стоимости. В его основе также лежит метод индексации вершин сети напряженных вариантов снизу вверх. 1 шаг. Помечаем нижние вершины сети индексами . Общий шаг. Вершины следующего (более высокого) уровня сети напряженных вариантов помечаются только после того, как помечены все смежные вершины нижележащего уровня. При этом индекс вершины-квадрата (в таких вершинах записывается одно число – оценка соответствующего агрегированного критерия) равен минимальному из индексов смежных вершин-кружков нижележащего уровня, а индекс вершины-кружка (в кружке записаны два числа – это пара оценок критериев нижнего уровня, агрегирование которых дает соответствующую оценку критерия верхнего уровня) равен сумме индексов смежных вершин-квадратов нижележащего уровня. При описанной процедуре индекс начальной вершины-квадрата равен минимальным затратам на реализацию соответствующей программы. Оптимальный вариант находится «обратным ходом» – сверху вниз. Сначала находим вершину-кружок, смежную с начальной вершиной сети и имеющую минимальный индекс среди всех вершин, смежных с начальной. Из этой вершины-кружка исходят две дуги к вершинамквадратам нижележащего уровня. Для каждой вершины-квадрата находим вершину-кружок, имеющую минимальный индекс среди всех вершин, смежных с соответствующей вершиной-квадратом и т.д. В результате будет выделен подграф, определяющий оптимальный вариант программы. Рассмотрим работу алгоритма на примере {Нумерация примеров независимая внутри глав и включает их номер.} сети напряженных вариантов рис. 2.6. Пример 2.1. Пусть матрица затрат ( ) имеет следующий вид, показанный в табл. 2.1. Таблица 2. 1 МАТРИЦА ЗАТРАТ i j 1 2 3 4 Ж 2 7 20 60 Б 3 10 35 50 Э 1 8 50 100 Индексы вершин сети, полученные на основе описанного алгоритма, указаны на рис. 2.7 в верхней половине соответствующих вершин. Оптимальный вариант выделен толстыми линиями. Это вариант (2; 2; 2) с затратами соответствующий сбалансированному развитию по всем направлениям. 2.2. Методы оптимизации комплексной программы развития с учетом риска Рассмотренный выше подход к построению оптимальной по стоимости программы развития региона имеет один недостаток. Он связан с тем, что напряженные варианты развития обладают низкой надежностью реализации. Действительно, достаточно срыва программы по одному направлению, и поставленная цель не достигается. Для повышения надежности вариантов программы введем понятия критической оценки и резерва направления. Пусть задан некоторый вариант развития , имеющий комплексную оценку . Будем уменьшать оценку направления . Обозначим – минимальное значение этой оценки, такое что дальнейшее уменьшение оценки приводит к уменьшению комплексной оценки. Оценку будем называть критической оценкой для -го направления варианта . |