Пример 6. Задан граф схемы электроснабжения (рисунок 9)

Задан граф схемы электроснабжения (рисунок 9). Необходимо найти оптимальную схему электрической сети.

Исходные данные:

P₁ = 5 MВт, P₂ = 3 MВт, P₃ = 2 MВт, P₄ = 4 M Вт, P₅ = 10 MВт;

a = 1 млн тг/км, b = 0,2 млн тг/(км× МВт).

Длины ребер (ветвей) и результаты расчета удельных затрат приведены в таблице 8.

ГПП

I

1 2

II III

4 P₁ 5 7 P₂ 8

IV 6 9 VI

V

P₃ P₄ P₅

Рисунок 9 – Исходный граф схемы электроснабжения

Таблица 8 – Длины ребер и удельные затраты

Номер ветви
Длины вет- вей Li, км	1,5		2,5	0,5	1,0		1,5		0,5
a× Li , млн тг	1,5		2,5	0,5	1,0		1,5		0,5
Сi = b× Li, млн тг/MВт	0,3	0,4	0,5	0,1	0,2	0,6	0,3	0,4	0,1

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

Для определения минимально возможных постоянных затрат необходимо построить кратчайшее дерево. С этой целью упорядочим ребра графа в порядке

возрастания составляющей a×L_i (табл. 9).

Таблица 9 – Таблица упорядоченных ребер графа

Номер ветви
a×Li	0,5	0,5		1,5	1,5			2,5

Начав с ребра номер 1, имеющего наименьшее значение a×L_i из всех ребер, выходящих из вершины I, выбираем на каждом последующем шаге ребро с наименьшим значением a×L_i при условии, что не образуется замкнутых контуров с выбранными ранее ребрами. При этом, если имеются ребра с одинаковыми значениями a×L_i, то выбирается любое из них.

Число ветвей в дереве должно быть на единицу меньше числа вершин. Кратчайшая связующая сеть имеет следующий вид:

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