Розглянуто задачу визначення пропускних можливостей ребер мережі з мінімальною загальною вартістю за умови, що після вилучення з неї принаймні одного ребра повинні існувати шляхи проходження одиничного потоку з джерела в стік на отриманій мережі.

Доведено, що задачі мінімізації загальної субоптимальної функції є задачами знаходження мінімального розрізу в мережі, якщо двоїста функція для довільної множини визначається як сума її значень на підмножинах з двома елементами. Цей результат використано для синтезу мережі за допомогою розрізної субмодулярної функції.

Розглянуто задачі синтезу мереж мінімальної вартості за умови, що після вилучення всіх ребер деякого підграфу, ізоморфного заданому графу, в мережі існує принаймні один шлях, який зв'язує довільну пару вузлів. Досліджено існування розв'язку задач синтезу мереж для різноманітних ізоморфних підграфів.

Показано, що за умов використання древоподібних структур для представлення даних покращується час розв'язання мережевих задач за допомогою спеціалізованого сімплекс-алгоритму.

Індекс рубрикатора НБУВ: В173.112 + З813.1

Рубрики:

Дискретне програмування

Моделювання систем

Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ 

Зазначено, що у відомих алгоритмах розв'язування задачі про призначення в явному вигляді чи опосередковано використовуються відомі класичні умови існування перфектного паросполучення в дводольному графі. Показано, що кожному дводольному графу можна співставити деякий вектор і розширений поліматроїд таким чином, що даний вектор є базою цього розширеного поліматроїда тоді та тільки тоді, коли даний граф містить перфектие паросполучення.

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

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

Індекс рубрикатора НБУВ: В195 + В161.41

Рубрики:

Прикладна математика

Теорія множин

Шифр НБУВ: Ж22412/а Пошук видання у каталогах НБУВ 

We consider the minimum cost design network problem under condition that if an edge is deleted from the network, then there exists at least one path connecting any pair of nodes. We investigate a structure of faces of the polytope associated with this problem and use these faces for decreasing the dual gap.

Рассмотрены проблемы синтеза сетей, возникающие при проектировании и эксплуатации телекоммуникационных и транспортных сетей. Предложена формализация задач синтеза сетей на графах, в которых заданы ограничения на пропускные способности разрезов и учитываются возможности выхода из строя некоторых компонентов сети. Описаны подходы к решению и анализу трудоемкости рассмотренных задач.

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

Рассмотрена задача нахождения максимального разреза на графaх. Приводится новая модель задачи в терминах базы полиматроида. Показано, что решение задачи можно найти гриди алгоритмом после определения оптимального линейного упорядочения вершин.

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

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

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