автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Условия устойчивости множества крайних точек полиэдра и их применение для исследования многопродуктовых сетевых моделей

РГБ Ой

2 2 № ВО'о

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

ДАВИДСОН Михаил Рувимович

УДК 519.85

УСЛОВИЯ УСТОЙЧИВОСТИ МНОЖЕСТВА КРАЙНИХ ТОЧЕК ПОЛИЭДРА И ИХ ПРИМЕНЕНИЕ ДЛЯ ИССЛЕДОВАНИЯ МНОГОПРОДУКТОВЫХ СЕТЕВЫХ МОДЕЛЕЙ

( 05.13.18 - теоретические основы математического моделирования, численные методы и комплексы программ)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1995

Работа выполнена на факультете вычислительной математики и кибернетики Московского государственного университета им. М.В.Ломоносова

Научный руководитель:

академик РАН П.С.Краснощекое

Официальные оппоненты:

доктор физико-математических наук, доцент С.К.Завриев

кандидат физико-математических наук, старший научный сотрудник М.Г.Клепикова

Ведущая организация:

Институт высокопроизводительных вычислительных систем РАН.

Защита диссертации состоится "(.И?. 1995 г. в .(?'... ч. на заседании диссертационного совета Д002.32.05 Вычислительного Центра РАН по адресу:

117967, Москва ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке МИ РАН. Автореферат разослан "/С.". .. 1995 г.

Ученый секретарь совета кандидат физико-математических наук

В.А.Бушенков

и

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Цели диссертационной работы.

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

Результаты, выносимые на защиту.

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

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

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

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

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

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

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

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

Практическая ценность работы. Полученные в диссертации результаты с одной стороны подтверждают адекватность рассматриваемых сетевых моделей для анализа предельных функциональных возможностей МП-сетей. С другой стороны они могут служить обоснованием корректности правил распределения многопродуктового потока в сети, получаемых в результате решения соответствующих экстремальных задач. Для решения задач о допустимости и лексикографического максиминного анализа МП-сети применимы алгоритмы, описываемые в работе. Ряд результатов диссертации включен в научные отчеты ВЦ РАН по темам НИР "ТРАКТ-ВЦ", 1992-93

гг. и "ДОВЕРИЕ-РАН", 1994 г., а также используется в работе по проекту РФФИ М.95-01-00232а.

Апробация работы. Основные результаты диссертации докладывались на научно-исследовательских семинарах ИПУ и ВЦ РАН, факультета ВМиК МГУ.

Публикации. По материалам диссертационной работы опубликовано 5 печатных работ.

Структура и объем работы. Диссертация состоит из введения, двух глав (в 1-й - 8, а во 2-й - 6 параграфов), приложений А и Б и списка литературы. Содержит 96 страниц текста, включая приложения и список литературы из5"4*наименований.

СОДЕРЖАНИЕ РАБОТЫ

В §1.1 дается постановка задачи и вводятся основные определения.

Пусть Т — многозначное отображение, действующее из V С П.* в множество всех подмножеств и". Обозначим вг{г) = {у\р(у, г) < г}, р(-, •) - евклидова метрика, || • |) - евклидова норма.

ОПРЕДЕЛЕНИЕ 1.1.1 (2). Многозначное отображение Т называется полунепрерывным сверху (снизу) на V в точке р £ V , если для любого е > 0 существует 6 > О такое, что Ур' £ Вг(р) ПТ:

ПР')^МНР)) (?(Р)Я *.№')))■

Определение 1.1.3 (4). Отображение Т Липшиц-полунепрерывно сверху (снизу) на V в точке р £ V, если существует 6 > 0 и такая константа Ь, что Ур' £ Д;(р) П V

Р(Х\?(Р))<ЧР-Р'\\ Чх'еНр')

(р(*,^(р'))<ь||р-р'|| VI е Т{р)).

Определение 1.1.5. Многозначное отображение Т называется непрерывным (Липшиц-непрерывным) на V в точке р £ V если Т полунепрерывно (Липшиц-полунепрерывно) сверху и снизу на V в точке р.

Рассмотрим множество X — Х(А,Ь) С й-", заданное системой линейных равенств и неравенств

Х(А,Ь)=Г {х £ < Ь}.

Обозначим Е(Х(А, Ь)) множество крайних точек полиэдра Х{А, 6).

Предположим, что А и Ь, задающие множество Х(Л,6), могут подвергаться возмущениям. Определим многозначное отображение М. по формуле

М : (Л,6) ■-» Е(Х(А,Ь)).

В первой главе проводится исследование свойств устойчивости множества Е(Х(А,Ь)), или иначе, непрерывности отображения М.

В работе рассматриваются различные классы возмущений V. В §§1.2-7 изучаются свойства отображения М на классе

Р =Г {(А', У) е Нтп х Кт|Х(Л',6') ф 0},

т.е. множество допустимых возмущений таково, что возмущаемое множество остается непустым.

Характеризация Липшиц-непрерывности отображения М дается в § 1.7, где доказывается следующая

Теорема 1.7.1 Отображение М Липшиц-полунепрерывно сверху (снизу) на V в точке (Л, 6) тогда и только тогда, когда оно полунепрерывно сверху (снизу) на V в точке (А,Ь).

§§1.3-6 посвящены исследованию непрерывности М. на V.

В отличие от случая, когда возмущениям подвергается лишь правая часть, наложенное на класс V условие непустоты возмущенных множеств оказывается существенным для непрерывности многозначного отображения Л4 только, если Х(Л, 6) состоит из единственной точки. Теорема 1.3.1 утверждает для одноточечных множеств Х(А, 6) непрерывность отображения М на V без дополнительных условий на систему Ах < Ь.

Теорема 1.4.1. Если множество Х(Л, Ь) содержит более одной точки, то отображение М. полунепрерывно снизу на V в точке (Л, Ь) тогда и только тогда, когда для ограничений Ах < Ь выполнено хотя бы одно из условий регулярности: Робинсона, Мангасаряь'а-Фромовица (МР) или линейной независимости (Ы).

Указанные условия эквивалентны, и в линейном случае при выполнении хотя бы для одного х & X справедливы для произвольного х 6 X. Условие МГ является условием общего положения. Отсюда следует, что при X ф {ж} любая точка (А,Ь) £ V, в которой М. полунепрерывно снизу, принадлежит внутренности множества V, и поэтому условие непустоты для возмущенных множеств выполняется автоматически. Таким образом, класс 7> в теореме 1.4.1 можно заменить на 11пт+т.

Условия регулярности, гарантирующие непрерывность отображения (А, 6) н-> Х(А,Ь) и полунепрерывность снизу М : {А, Ь) и-> Е(Х(А, 6)), не обеспечивают полунепрерывности М. сверху. Полунепрерывность сверху отображения М на V исследуется в §5.

Обозначим Л(Х, ж) - множество активных ограничений в точке х £ X. Определим множество вырождения для X по формуле

У(Х) =г {х £ > п, V/ С Я{Х, х), |/| = п => = 0},

здесь и далее через А/ обозначается подматрица А, составленная из строк с номерами г£ /.

Теорема 1.5.3 утверждает, что для полунепрерывности сверху отображения Л4 на V необходимо и достаточно, чтобы выполнялись

Условие С: = 0 и Условие ЯС: У{ЯС(Х)) = 0,

где ЯС(Х) - рецессивный конус множества X.

Отметим, что, если множество X ограничено, то условие НС вы- . полнено тривиально. Условие С иначе можно сформулировать как

х, у е Е( X), хфу^ | ЩХ, (х + у)/2)| < п.

В ТЕОРЕМЕ 1.5.5 дается эквивалентная формулировка необходимых и достаточных условий полунепрерывности сверху отображения Л4 на "Р, при этом удается несколько более тонко охарактеризовать класс систем Ах < Ь, удовлетворяющих данным условиям.

В §1.4,5 свойства полунепрерывности сверху и снизу отображения М. рассматривались по отдельности. Условия непрерывности могут быть получены объединением условий для полунепрерывности сверху и снизу. Однако, в §1.6 доказано, что, фактически, условия С

достаточно для непрерывности отображения М на т.е. полунепрерывность снизу есть следствие полу непрерывности сверху.

Теорема 1.6.1. Если X состоит более, чем из одной, точки, то для того, чтобы отображение М было непрерывным на V в точке (А,Ь) необходимо и достаточно, чтобы выполнялись условия С и Ж.

Условие С, таким образом, играет ключевую роль при исследовании непрерывности. В §1.6 проводится более подробный анализ этого условия. В частности, условие С сопоставляется с условием регулярности, известным в оптимизации как условие строгой дополняющей нежесткости, точнее, следующим обобщением этого условия. Рассмотрим задачу максимизации (с, х) на X и потребуем, чтобы для всех с таких, что эта задача разрешима, было выполнено

х Е Х0р(, А £ Л0р{, г £ Е(Х, х) => А,- > 0, (1)

где Хор1, Лор( - множества решений прямой и двойственной задачи, соответственно. В этом случае для всех 2 из Е(Х) |Я(Х, ж)| = га.

Таким образом, из (1) следует С. В то же время, из С не следует (1) - условие равенства числа активных ограничений в каждой крайней точке размерности пространства оказывается слишком жестким.

В §1.6 рассмотрено более слабое условие (81), которое требует, чтобы для всякой крайней точки любая квадратная подматрица, составленная из градиентов активных ограничений в этой точке, была не вырождена. Показано, что условие Б1 является достаточным для выполнения условия С (Замечание 1.6.1), но не является необходимым, что видно из следующего примера.

Пример. Пусть X задано ограничениями:

XI + х-1 < 0,

Х2 + Х3 < 0,

+ 3=2 < 0,

Х-2 - Ез < 0,

аг4 = 0,

> -1

Градиенты первых четырех ограничений составляют вырожденную квадратную матрицу, и эти ограничения активны в крайней точке

х = 0. Поэтому условие SI не выполнено. В то же время выполнено условие С.

лемма 1.6.1 утверждает, что, если Е(Х) ф 0 и X содержит более одной точки, то С эквивалентно следующему условию S2

г g Е{Х) => rankA4XiX) = |R(X,®)|.

Это требование, в свою очередь, является достаточным для выполнения условия LI. (Отсюда, пользуясь теоремами 1.4.1 и 1.5.3, получаем утверждение теоремы 1.6.1.) Из S2 также следует, что, если х £ Е(Х), то среди ограничений из Л(Х, г) отсутствуют избыточные, т.е.

(2)

.•ея(л»\Ш

где компоненты А, соответствующие ограничениям-неравенствам, -неотрицательны. Вместе с тем, Б2 не сводится к Ы и (2). Чтобы показать это, модифицируем предыдущий пример, заменяя равенство «4 = 0 парой неравенств — 1 < Х4 < 0. Легко проверить, что условия Ы и (2) выполнены. Рассмотрим возмущенное множество Х(А6 ,Ье), определяемое ограничениями

xi +

-xi -f

®2

«2 ®2

+ Х3

- Хз

+ 26x4 < <

< < < >

х4 х4

-6, О, 0, 0, 0, -1.

Точка = (0, 0,0, —1/2) есть крайняя точка множества Х(А1 ,Ь1), т.е. Б2 не выполнено.

Заметим, что оба рассмотренных примера возможны лишь при п > 3. При п < 3 условия Ы, (2) эквивалентны Б1.

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

В п. 1.5.2 условие С проинтерпретировано для транспортной задачи:

mJ2cHxi} (3)

min rex Ч

X = {xij > 0| гUj = <Ti, i = 2,..., n - 1,

£"=1*4=^ i =!,•••."»},

где ^ > 0 задает мощность г-го источника, г = 1,..., га, 6j > 0 -потребность j-го стока, j = 1,..., m,

' i

Xij - величина потока между г-м источником и j-м стоком, c,j -стоимость транспортировки. В этой записи опущено ограничение

^—-«in „ w

2^J=1 Xij = cri, что делает строки ограничении-равенств линеино независимыми.

Пусть сг,- и 5,- удовлетворяют дополнительному требованию

¡ВТи Т2: 7\ С{1,Т3с{1,...,т}, | + |Т2| < п + ш, ¡ет, ;'ет2

Условие (5) означает, что задача не сводится к нескольким задачам того же типа, но меньшей размерности. Наряду с (5) рассмотрим более сильное требование

ш,п>3, ДЪ, Т2: Ъ С {1,..., п}, Т2 С {1,...,т},

2<|Т1|<п-1, 2<|Т2|<т-1, (6)

Х> = £ ^

>6Т1 ¿ет3

Утверждения 1.5.1,2 показывают, что с одной стороны из (5) следует условие С для задачи (3),(4), а с другой стороны из С следует

(6). Данный пример также содержательно поясняет, насколько требование устойчивости множества крайних точек сильнее условия регулярности МГ, - для задачи, записанной в форме (3),(4), условие МГ очевидно выполнено.

В §1.8 рассматриваются произвольные классы возмущений V' и даются достаточные условия Липшиц-непрерывности отображения М на таких классах (ТЕОРЕМА 1.8.2).

Глава 2 посвящена исследованию устойчивости решений экстремальных задач на МП-сетях. МП-сеть как математическая модель, используемая для представления объектов с сетевой структурой, задается парой (0,0), где 0 = {V, Е) - граф на вершинах V — {их,. ..,«„}, Е = {г1,...,гв} - множество ребер, О. = {(8ь^г)| • ■ ■, («м|'м)} С V х V - множество, состоящее из М упорядоченных пар вершин в,- и являющихся источником и стоком некоторого продукта вида ¿. Ребрам графа 0 ставятся в соответствие положительные числа ¿г, имеющие смысл пропускной способности ребер гб£. При передаче продукта по сети от его источника к стоку говорят о потоке продукта данного вида, суммарные величины потоков ограничены пропускной способностью ребер. Предполагается, что все потоки проходят по сети одновременно и они не взаимозаменяемы. В дальнейшем предполагается, что граф @ неориентированный, поэтому каждое ребро моделируется парой противоположно-направленных дуг, имеющих общую пропускную способность.

Обозначим через у|+, у)Г величины потоков продукта i, передаваемых по ребру г в противоположных направлениях, и пусть у1+, у'~ 6 IIе - соответствующие векторы, задающие распределение потоков продукта I по всем ребрам графа 0', обозначим через > О величину потока продукта вида г между источником в,- и стоком £,-. Тогда равенства

с(г/+-г/-)-г.-б'' = о, (7)

задают баланс потоков г—го продукта в каждой вершине г = 1,2,..., М. Здесь С - матрица инцидентности <Э\ Ьхч = 1, если и — 5,-, = —1, если и = и, = 0, если и ф и ф

Для потоков продуктов по ребрам сети должны также выполняться условия неотрицательности и ограничения по пропускной способ-

ности

Af

Х^ + уГ) < dr4r£E, (8)

¿=1

у<+,у<- > 0 Vi =1,2,..., Л/. (9)

Обозначим Уо(^) = {(у, -г)| выполнены условия (7) — (9)}.

Предположим, что каждому виду продукта i 6 {1, 2,..., М} приписано число /; > 0, обозначающее величину потока этого продукта, которую требуется передать по сети между соответствующей парой вершин. Отсюда возникает задача о допустимости заданного вектора требований / для данной МП-сети, т.е. существует ли распределение потоков (у, z) £ }\)(d)> такое, что г,- > /; Vi = 1,2,М.

Обобщением указанной задачи на случай недопустимости вектора требований является задача поиска приемлемого распределения потоков в заданной МП-сети. В качестве ее решения разными авторами рекомендуется выбирать "справедливое" (максиминное) распределение, реализующее

Z'

77i = шах min (10) (у,г)£Уо(Л) «£{1,2.....Л/} Ji

Задача (10) сводится к следующей задаче ЛП

max 0, (11)

(y,*,«)ev

где через У обозначено множество всех (у, z, в) таких, что (у, z) £ y0{d), -Zi + Ofi <0, i= 1,...,М.

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

§2.1 носит технический характер. В нем указан ряд свойств задачи ЛП, которые на основании полученных в главе 1 условий, достаточны для ее устойчивости. В частности, в дальнейшем используется

Условие 2: 35 > 0, 3R > 0 : Ч(А',Ь') £ Bs((A,b)) П V, Vx' £ Е(Х'), V/ С R(X',x') : deM'7 ф 0 =»

3i : < R, detf^i 1,-6/j = c(I, i) ф 0,

где матрица [А'/^бу] состоит из столбцов с номерами из индексного множества 1 с заменой столбца I на с(/, г) - константа, не зависящая от конкретного возмущения.

В §2.2 получен ряд свойств, относящихся к устойчивости крайних точек множеств Е(У), Е(А), а также множеств Еорх(У), Еор1{А^й) при различных возмущениях, где Л - допустимое множество задачи, двойственной к (11), Еор1{-) - множество оптимальных крайних точек.

Предположим вначале, что возмущениям подвергается только вектор требований /, т.е. класс возмущений задается следующим образом

■Р/ = {/' е Г1М|(]])' разрешима}.

(Здесь и далее штрих у номера формулы означает, что в нее подставлены возмущенные значения параметров в соответствии с рассматриваемым классом V.)

Теорема 2.2.1 Пусть в задаче (11) в качестве допустимого множества взято к о Ь, где Ь произвольное полиэдральное множество такое, что из (у, г,0) € Ь следует, что в > а > 0. Тогда отображение /' н-> Е(У Г\Ь) Липшиц-непрерывно на V/ в точке /.

Когда правая часть также может подвергаться возмущениям, класс возмущений определяется как

V = {(/', е Им х И61( 11)' разрешима}.

теорема 2.2.2. Многозначное отображение (/\с1') н-> Е(А') Липшиц-непрерывно на V в точке (/, в).

Следствие 2.2.2 Многозначное отображение (/', й') н-> Еор1(А', в! Липшиц-полунепрерывно сверху паТ в точке (/, с/).

Следующее свойство вытекает из теоремы 2.2.2 и вспомогательного утвеждения из §2.1.3 (Лемма 2.1.3).

Следствие 2.2.3 Многозначное отображение (/',в,') i—» Еор1{У) Липшиц-полунепрерывно сверху на V в точке (/,6,).

Недостатком постановки (10) является возможное недоиспользование пропускной способности ребер сети. От указанного недостатка свободно правило управления потоками, предложенное Ю.Е.Малашенко, которое приводит к следующей задаче.

Найдем значение (10) и определим множество Qi индексов i продуктов, для которых

•г.- = mfi V(y, z) G =f Arg шах < min Ц- S .

(у,*)£Уа(d) L 1 fi J

Если Qi ф {1,2,..., M}, то поставим задачу поиска

Z'

m'= max min (12)

itS. fi

02 = 1 i £ Qi\zi = mfi V(y, z) e y2 d= Arg max i min Sl. L (у,г)€У1 L'iQi fi ) )

Аналогично, V/ = 2,3,..., если Qi U ... U Qj ф {1,2,..., А/}, будем

продолжать решение соответствующих максиминных задач поиска

*

77/4-1 = max min — (13)

<eö>u...uSi fi

до тех пор, пока не исчерпается все множество продуктов: Q\ U ...U Ql — {1,2,..., М). Тогда произвольный элемент из Ус можно выбрать в качестве решения (у*, г*) задачи (10) - (13). Указанное решение является одновременно "справедливым" и эффективным - парето-оптимальным в задаче максимизации вектора критериев {г,-}, а также максимально использующим пропускную способность ребер МП-сети. При этом каждому продукту г = 1,2,..., М сопоставляется число T](i), которое назовем максиминным уровнем обеспеченности требования на величину потока г-ro продукта,

ч(0 = Гц & ie Qj.

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

В §2.3 проводится исследование устойчивости задачи (10) - (13) к возмущениям вектора требований / и вектора пропускных способностей d, т.е. в качестве класса возмущений рассматривается V.

ОПРЕДЕЛЕНИЕ 2.3.1. Лексикографическая задача (10)—(13) устойчива по критериям, если величины т/(г) максиминных уровней обеспеченности требований, как функции от возмущений, Липшиц-непрерывны на V в точке (/, <1).

Определение 2.3.1. Лексикографическая задача (10)~(13) устойчива по решению, если многозначное отображение (/', ¿') н-> Е(У Липшиц-полунепрерывно сверху на V в точке (/,

(Здесь »/(г), Е(У'Ь,) определяются по аналогии с т](г), Е(Уь) с учетом зависимости от параметров (/',<!').)

Теорема 2.3.1. Задача (10)~(13) устойчива по критериям.

ТЕОРЕМА 2.3.2. Задача (10)-(13) устойчива по решению.

В п. 2.3.3 задача (10)—(13) сводится к последовательности задач линейного программирования: указывается- конкретный способ построения множеств Qj и получения соответствующих решений.

В §2.4 рассматривается устойчивость лексикографической макси-минной задачи (10)—(13) по отношению к погрешностям вычислений.

Наличие в МП-сетях нескольких невзаимозаменяемых видов продуктов, конкурирующих за общий ресурс - пропускную способность, естественным образом приводит к рассмотрению многокритериальных задач на МП-сетях. В частности, более подробный анализ функциональных возможностей МП-сети приводит к задаче многокритериальной оптимизации вектора критериев {г\,...,2м} (величин потоков) при заданном векторе пропускных способностей:

Мах(!/,*)еУо(<о{г1. • • ■ > 2М }, (14)

где Уо(с1) определено в §2.2. Эта задача обобщает рассмотренную в §2.3 лексикографическую задачу (10) - (13) анализа МП-сети -множество решений (10) - (13) является подмножеством Парето-оптимумов (14).

Другой класс задач связан с оптимальным развитием МП-сети, т.е. увеличением пропускной способности ребер сети с тем, чтобы заданный вектор требований был допустим. Оптимальность понимается, например, в смысле неизбыточности добавляемой пропускной способности, что приводит к следующей задаче многокритериальной оптимизации

Мт(г/|г1д)ез;{Д1,...,Де},

где У = {((у, г) £ У0{<1 + А), Д)| > /,■}, А = (Дь ..., Де), Д4 > 0.

Указанная задача обобщается на случай, когда учитывается возможность выхода из строя произвольного ребра, после чего МП-поток перераспределяется с тем, чтобы обеспечить выполнение неравенств 2{ > /,• Уг. Такая задача известна как задача развития с гарантией живучести.

Задача оптимального развития МП-сети может также быть поставлена с критерием минимизации стоимости наращивания пропускной способности. При стремлении к экономии средств может оказаться целесообразным отыскание некоторого баланса между затратами на увеличение пропускной способности и качеством функционирования МП-сети. Это можно выразить в виде следующей двух-критериальной задачи

где У = {((у, г) € + Д),Д,0)| (с, Л) = р, А > 0, г > 0/}, с-вектор удельных затрат на добавление пропускной способности.

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

Теорема 2.5.3. Если М. Липшиц-полунепрерывно сверху на классе V, то отображение Б: (Л, 6) 8Ь(Х{А, Ь)) П Е{Х(А,Ь)) Липшиц-полунепрерывно сверху паТ>. Если М Липшиц-полунепрерывно снизу на V, то отображение Р : (Л, Ь) н-> РО(Х(А, Ь)) П Е(Х(А, ¿)) Липшиц-полунепрерывно снизу на V. (Здесь БЬ и РО обозначают множество Слейтер-оптимальных и Парето-оптимальных точек.)

Затем в §2.6 обосновывается устойчивость перечисленных выше моделей векторной оптимизации на базе МП-сетей (Теорема 2.6.1).

В приложении А предложен итеративный метод для решения задачи о допустимости МП-сети; доказана сходимость метода и получена оценка скорости сходимости; приведены результаты численных экспериментов. В приложении Б даны результаты расчетов для лексикографической максиминной задачи анализа МП-сети.

Основные результаты диссертации опубликованы в работах:

1. Давидсон М.Р. Субградиентный метод решения задачи развития многопродуктовых сетей с гарантией живучести // Журнал вычислительной математики и математической физики, 1993, т.33, N4, с.503-521.

2. Давидсон М.Р. Об условной устойчивости крайних точек многогранного множества // Журнал вычислительной математики и математической физики, 1994, т.34, N1, с.29-43.

3. Davidson M.R., Stability of lexicographical multicommodity flow problem // 15th International Symposium on Mathematical Programming, Program and Abstracts, The University of Michigan, Ann Arbor, Michigan, USA, 1994, p.62.

4. Давидсон М.Р. Устойчивость лексикографической максимин-ной задачи распределения потоков в многопродуктовых сетях // Журнал вычислительной математики и математической физики, 1995, т.35, N3, с.334-351.

5. Давидсон М.Р., Малашенко Ю.Е., Новикова Н.М., Смирнов М.М., Строгая Г.В. Математические постановки задачи восстановления и обеспечения живучести для многопродуктовых сетей. М.: ВЦ РАН, 1993.

М.Р.Давидсон

Условия устойчивости множества крайних точек полиэдра и их применение для исследования многопродуктовых сетевых моделей

Подписано в печать 19.04.95 Формат бумаги 60x84 1/16 Тираж 100 экз. ЗаказЗ!. Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117967, Москва, ул. Вавилова, 40