Пример 6.
Задан граф схемы электроснабжения (рисунок 9). Необходимо найти оптимальную схему электрической сети.
Исходные данные:
P1 = 5 MВт, P2 = 3 MВт, P3 = 2 MВт, P4 = 4 M Вт, P5 = 10 MВт;
a= 1 млн тг/км, b =0,2 млн тг/(км× МВт).
Длины ребер (ветвей) и результаты расчета удельных затрат приведены в таблице 8.
ГПП
|
1 2
II III
4 P1 5 7 P28
IV 6 9 VI
V
P3 P4 P5
Рисунок 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×Li (табл. 9).
Таблица 9 – Таблица упорядоченных ребер графа
| Номер ветви | |||||||||
| a×Li | 0,5 | 0,5 | 1,5 | 1,5 | 2,5 |
Начав с ребра номер 1, имеющего наименьшее значение a×Li из всех ребер, выходящих из вершины I,выбираем на каждом последующем шаге ребро с наименьшим значением a×Li при условии, что не образуется замкнутых контуров с выбранными ранее ребрами. При этом, если имеются ребра с одинаковыми значениями a×Li , то выбирается любое из них.
Число ветвей в дереве должно быть на единицу меньше числа вершин. Кратчайшая связующая сеть имеет следующий вид:
