ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 5, с. 45-51
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
УДК 519.8
ОБ ОДНОМ ТИПЕ УСТОЙЧИВОСТИ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
В СЛУЧАЕ МОНОТОННОЙ НОРМЫ*
© 2007 г. В. А. Емеличев, К. Г. Кузьмин
Белоруссия, Минск, БГУ Поступила в редакцию 02.10.06 г., после доработки 30.05.07 г.
Рассматривается многокритериальная задача целочисленного линейного программирования с конечным множеством допустимых решений, состоящая в поиске множества Парето. Получены нижняя и верхняя достижимые оценки радиуса сильной устойчивости задачи в случае, когда в пространстве решений задачи норма произвольна, а норма в критериальном пространстве монотонна. Используя неравенство Минковского-Малера, выведена формула для вычисления этого радиуса в случае, если множество Парето состоит из одного решения. Найдены также оценки радиуса в случае нормы Гёльдера в указанных пространствах. Выделен класс задач, для которых радиус сильной устойчивости бесконечен. В качестве следствий выводятся некоторые известные ранее результаты. Приведены также иллюстративные числовые примеры.
Введение. Многоцелевые дискретные модели принятия решений находят широкое применение в проектировании, управлении, экономике и многих других прикладных областях. Поэтому интерес математиков к многокритериальным (векторным) задачам дискретной оптимизации не ослабевает, что подтверждается частым появлением новых публикаций (см., например, библиографию в [1], содержащую 234 наименования). Одно из направлений в изучении таких задач - анализ устойчивости решений к возмущениям исходных данных (параметров задачи). Разнообразные постановки проблемы устойчивости порождают многочисленные направления исследований. Не задерживаясь на описании всего спектра вопросов, возникающих в этой области, отсылаем читателя к обширной библиографии [2], а также к монографиям [3-5].
Настоящая работа лежит в русле направления, связанного с исследованиями количественных характеристик устойчивости. Одна из таких характеристик, называемая обычно радиусом устойчивости, определяется как предельный уровень возмущений параметров задачи, сохраняющих некоторое наперед заданное свойство множества ее решений (или отдельного решения). В качестве возмущаемых параметров обычно выступают коэффициенты скалярного или векторного критерия. Под устойчивостью векторной задачи дискретной оптимизации понимают (см., например, [3, 4, 6, 7]) дискретный аналог свойства полунепрерывности сверху по Хаусдорфу оптимального отображе-
* Работа выполнена в рамках Межвузовской программы Республики Беларусь "Фундаментальные и прикладные исследования" (грант № 492/28).
ния, задающего паретовскую функцию выбора, т.е. существование такой окрестности в пространстве начальных параметров задачи, внутри которой невозможно появление новых оптиму-мов Парето. Иначе говоря, множество Парето внутри этой окрестности может лишь сузиться. Ослабление этого требования приводит к понятию сильной устойчивости, которое трактуется как наличие такой окрестности первоначальных данных в пространстве параметров задачи, внутри которой хотя и возможно появление новых опти-мумов Парето, однако для каждого возмущения должно существовать хотя бы одно эффективное решение исходной задачи (не обязательно одно и то же), сохраняющее оптимальность по Парето. Впервые этот тип устойчивости был исследован в [7] для однокритериальной (скалярной) линейной траекторной (булевой) задачи. Позднее в [8] были получены нижняя и верхняя оценки радиуса сильной устойчивости векторной линейной траекторной задачи, а в [9] (см. также [6, 10]) найдена нижняя оценка этого радиуса векторной задачи целочисленного линейного программирования (ЦЛП). Эти оценки соответствуют случаю, когда в пространстве параметров задачи задана чебы-шевская норма
В данной статье выделен класс задач ЦЛП с бесконечным радиусом сильной устойчивости. В случае конечности этого радиуса указаны нижняя и верхняя достижимые оценки, исходя из предположения, что в критериальном пространстве задана монотонная норма, а в пространстве решений норма произвольна.
1. Основные определения. Допустим, что т -число критериев, п - число переменных, С - мат-
рица размера п х т со столбцами С, = (с71, с72, ..., сп)Те Яп, / е Ыт = {1, 2, ..., т}. Пусть х = (х1, х2, ..., хп)Т е X с Zn, причем количество элементов множества X конечно и больше одного. На множестве (допустимых) решений X зададим векторный линейный критерий
СТх = ((Съ х), (Съ х), ...,(Ст, х))Т — шт.
х е X
Под т-критериальной задачей ЦЛП 2т(С), С е е я х т, будем понимать задачу поиска множества Парето (множества эффективных решений)
Рт( С) = { х е X : Xx(С) = 0 },
где
X,, (С) = { х' е X : СТх > СТх' & СТх Ф СТх'}.
В силу конечности Xмножество Рт(С) ф 0 при любой матрице С е Яп х т.
Пусть || • || - произвольная норма в пространстве решений Яп, в котором векторы суть матрицы размера п х 1, и || • ||* - норма в сопряженном пространстве. Тогда для любых векторов и, Vе Яп справедливо неравенство Минковского-Малера (см., например, [11, с. 46])
|(и, V) < ||и|| • ||VII*. (1.1)
Поэтому верна формула
У0 > 0 Vv е Яп Зи0 е Яп
и0, V)| = 0||VI* & I|и°|| = 0^. (1'2)
Исследуем сильную устойчивость задачи 2т(С) при возмущении элементов матрицы С е Яп х т, которое будем осуществлять путем прибавления к ней матриц С из Яп х т. Для этого в критериальном пространстве Ят зададим произвольную норму || • ||, вообще говоря, отличную от нормы, определенной в Яп. Под нормой ||С|| матрицы С е Яп х т со столбцами С1, С2, ..., Ст, т > 2, будем понимать норму числового т-вектора
||с|| = ||(||С,||,1 \С2\|, |СЛ)т||.
По аналогии с [7-10] радиусом сильной устойчивости задачи ЦЛП 2т(С), т > 1, назовем число
[ эирЩ С), если Е( С )ф 0, Р (С) = 1п
[ 0 в противном случае,
где
Е(С) = {е> 0 : VC е й(е) (Рт (С )п Рт (С + С') ф 0)},
А(е) = {С е Япхт : ||СЦ <е}
- множество возмущающих матриц. Тем самым радиус сильной устойчивости - это предельный уровень возмущений элементов матрицы, при которых в возмущенной задаче 2т(С + С') сохраняется эффективность хотя бы одного (не обязательно одного и того же) решения исходной задачи.
Замечание 1. Очевидно, что в случае, когда
множество Рт( С) : = XXРт(С пусто, пересечение
Рт(С п Рт(С + С") ф 0 при всякой матрице С е Яп х т. Поэтому естественно считать, что в этом случае радиус сильной устойчивости рт(С) = ^ при любых нормах в пространствах Ят и Яп.
В противном случае (Рт (С) ф 0) рассмотрим следующие два класса задач. Задачу 2т(С назовем вырожденной, если выполняется
Vx е Рт (С) Va е Яп Зх0 е Рт(С) ((а, х - х0)> 0). Если же верно отрицание этой формулы, т.е.
Зх0 е Рт (С) За0 е Яп Vx е Рт(С) ((а0, х0- х)< 0),
то задачу 2т(С будем называть невырожденной. Далее покажем, что в вырожденном случае задача имеет бесконечный радиус сильной устойчивости, а в случае невырожденной задачи укажем нижнюю и верхнюю достижимые оценки этого радиуса.
2. Леммы. Как обычно, норму || • ||, заданную в пространстве Ят, будем называть монотонной,
если для любых векторов у, у' е из неравенства у <у' следует ||у|| < ||у'||. Отметим, что условию монотонности удовлетворяет достаточно широкий класс норм. Например, все нормы Гёльдера 1р, 1 < р < го, являются монотонными.
Лемма 1. Если норма в критериальном пространстве Ят монотонна, а число ф и решения х и х' таковы, что выполняются неравенства
0 <ф|| х'-х|| * < ||( СТ( х'-х ))+||,
то для любой матрицы С е П(ф) справедливо соотношение х' £ Xx(C + С').
Здесь и далее г+ = (г)+ - проекция вектора г = = (г1,г2, ..., гт) е Ят на неотрицательный ортант, т.е.
= (.••> г+т), = шах{ 0, г }, 7 е Ыт .
Доказательство. Допустим, наоборот, что существует такая матрица С0 е П(ф), что х' е е Xx(C + С0). Тогда для всякого индекса 7 е Ыт вер-
Лемма 4. Если рт(С) < то справедливо
но (Сг- + С0 )(х' - х) < 0, где С0, г е Ыт, - столбцы
матрицы С0. Поэтому благодаря (1.1) справедливы неравенства
(С, х' - х)+ < || С01| ■ ||х' - х||*, г е Нт, которые в силу монотонности нормы в Ят дают
||( СТ (х'-х ))+|| = ||(( С1; х'-х)+,(С2, х'-х)+, ..., (сп, х'-х)+ )Т ||<||(|| С?|| |С2||, И) Т|| X х||х'-х|| * = ||с0|| |х'-х|| * <ф1|х'-х|| *,
что противоречит условию. Лемма 1 доказана.
Лемма 2. Если для некоторого решения х е е Рт(С) и матрицы С е Яп х т справедливо
Хх (С + С' )п Рт( С) = 0, (2.1)
то множество Рт(С) п Рт(С + С') непусто.
Доказательство. В случае, когда х е е Рт(С + С'), утверждение леммы очевидно. Пусть х й Рт(С + С'). Тогда в силу внешней устойчивости множества Парето Рт(С + С) (см., например, [12, с. 34]) существует такое решение х0 е Рт(С + С), что х0 е Хх(С + С'). Отсюда, принимая во внимание условие (2.1), заключаем, что х0 е Рт(С). Следовательно, Рт(С) п Рт(С + С') Ф 0. Лемма 2 доказана.
Лемма 3. Для всякой невырожденной векторной задачи ЦПЛ 2т(С) найдется такая ненулевая матрица С* е Яп х т, что множество Рт(С) п п Рт(С*) пусто.
Доказательство. Согласно определению невырожденной задачи 2т(С), справедлива формула (1.3), т.е. верны строгие неравенства
(а0, х0- х)< 0, Ух е Рт(С).
С* =
| а , если г = 1, 1.0(п), если г Ф 1.
Тогда, учитывая (2.2), получаем
С* х < С* х, С* х0 = С* х при гФ 1,
За0 е Яп Ух е Рт (С) Зх'(х) е Рт(С) ((а0, х'(х) - х)< 0).
(2.3)
Доказательство. Пусть, напротив, формула (2.3) не выполняется, т.е.
У а е Яп Зх0 е Рт (С)
Ух' е Рт(С) ((а, х'- х0)> 0).
Тогда для любых С е Яп х т, х' е Рт (С) и г е Ыт верно неравенство
(С + С, х'- х0)> 0.
Поэтому решение х' й Xхо (С + С'). Откуда, применяя лемму 2, убеждаемся, что
Рт( С )п Рт( С + С' )Ф 0
при любой матрице С е Яп х т. Следовательно, рт(С) = го. Полученное противоречие завершает доказательство леммы 4.
Лемма 5. Пусть решения х Ф х0 и вектор п с компонентами п¡, г е Ыт, связаны неравенствами
П |х - х0||* >(С, х - х0)+, ге
(2.4)
(2.2)
Очевидно, что а0 Ф 0(п) = (0, 0, ..., 0)Т е Кп. Пусть столбцы С* , г е Ыт, матрицы С* е Яп х т заданы по правилу
т.е. х0 е Хх(С*). Это значит, что х й Рт(С*), если х е Рт(С). Следовательно, Рт(С) п Рт(С*) = 0. Лемма 3 доказана.
среди которых х
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.