Аннотация:
Рынки природного газа, нефти и электроэнергии играют важную роль в экономике многих страх. Задача оптимизации транспортной системы представляет практический интерес. Рассматривается проблема оптимизации общественного благосостояния с учётом производственных затрат, полезности потребления и затрат на увеличение пропускных способностей. Сложность проблемы определяется наличием существенных фиксированных расходов, связанных с расширением линий передачи. В целом задача - NP-трудная (см. Guisewite, Pardalos, 1990). В нашей работе (Васин, Григорьева, Цыганов, 2017) вводятся понятия дополнительных и конкурентных транспортных линий. Для рынков с древовидной структурой указываются легко проверяемые необходимые и достаточные условия инвариантности структуры потоков, при выполнении которых любая пара линий с одинаковой ориентацией потоков является дополнительной, а с противоположной ориентацией - конкурентной. Указанные свойства позволяют разработать эффективные алгоритмы как для решения дискретной задачи поиска оптимального множества расширяемых линий, так и для вспомогательной задачи оптимизации благосостояния при заданном множестве расширяемых линий.
