6.19. Объединение электростанций в энергосистему

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

Задача объединения электростанций состоит в том, чтобы спроектировать систему связей, имеющую минимальную общую стоимость и удовлетворяющую требованиям по для всех станций. Очевидно, она эквивалентна следующей задаче теории графов. Дан полный граф с вершинами и весами приписанными каждому ребру соединяющему Требуется найти подграф, имеющий минимальную взвешенную сумму ребер, степень вершины у, которого, по крайней мере, Можно также искать подграф, имеющий максимальную взвешенную сумму ребер, каждая вершина которого имеет степень не больше а затем взять дополнительный граф. Видно, что при таком подходе исходная задача требует использования обоих обобщений задачи о максимальном паросочетании, рассмотренных в конце раздела 6.14.

В частном случае, когда вершины раделены на два класса так, что каждое ребро, соединяющее пару вершин одного и того же класса, имеет вес, равный нулю, задача объединения станций сводится к транспортной задаче. В общем случае, теория решения этой задачи значительно сложнее, чем транспортной. Хороший алгоритм ее

решения был найден Эдмондсом (но этот результат покд не опубликован).

Задача объединения электростанций или общая определения оптимального подграфа с ограниченными степенями вершин по существу связана с большинством экстремальных комбинаторных задач, для которых известны хорошие алгоритмы решения. Эти алгоритмы хороши в том смысле, что объемы вычислений при их применении растут как степенные функции при увеличении размерности задачи. В случае, когда все мы получаем задачу, очень близкую к задаче коммивояжера. Действительно, небольшая модификация алгоритма объединения станций дает минимальный взвешенный подграф со степенями вершин, равными 2. Если этот подграф связен, то мы получим минимальный маршрут коммивояжера при длинах ребер К сожалению, задача, получаемая после добавления к задаче объединения электростанций дополнительного ограничения связности подграфа, пока не решена.