УДК 681.3.07

Паник Л.А.

Днепропетровский национальный университет железнодорожного транспорта им. акад. В. Лазаряна

АНАЛИЗ И ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ ПОТОКОВ В ТРАНСПОРТНЫХ СЕТЯХ С УЧЕТОМ

ИНТЕРВАЛЬНЫХ НЕОПРЕДЕЛЕННОСТЕЙ

В представленной работе разработан метод и выполнен многокритериальный анализ потоков в сетевых моделях в условиях четких и нечетких (интервальных) исходных данных.

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

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

В докладе исследуется четкая потоковая сеть с весами, заданными в виде интервальных неопределенностей. В потоковой сети каждому ребру сопоставлена пропускная способность  , представленная в виде интервала , где - нижнее значение пропускной способности дуги , - соответствующее верхнее значение. Свойства носителей потока представляются интервалами, в этом случае поток в сети, определенный на дугах, также будет представлен интервальной величиной . Тогда условие сохранения потока и ограничения на пропускные способности дуг имеют вид:

Здесь -является источником, а -стоком, -множество ребер графа сети.

Исследуемая в задаче интервальная величина потока в сети, обозначенная через , определяется выражением:

В докладе рассматривается и новая задача - компромиссных вариантов выбора на множествах траекторий носителей потока с индивидуальными свойствами "право собственности". В задаче есть собственников, которым принадлежат заданные количества единиц потока: . Рассчитывается максиминная оценка эффективности потока с собственными свойствами носителей в следующем виде (принцип гарантированного результата):

,

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

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

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

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

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

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