ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2010, том 50, № 10, с. 1715-1726
УДК 519.626
ЧИСЛЕННОЕ РЕШЕНИЕ ЛИНЕЙНОЙ ДВУХУРОВНЕВОЙ ЗАДАЧИ
© 2010 г. Т. В. Груздева, Е. Г. Петрова
(664033 Иркутск, ул. Лермонтова, 134, ИДСТУСО РАН) e-mail: nekolyap@mail.ru, gruzdeva@icc.ru Поступила в редакцию 05.02.2010 г.
Переработанный вариант 13.05.2010 г.
Рассматривается линейная задача двухуровневого программирования в оптимистической постановке. Произведена редукция данной задачи к оптимизационной задаче с невыпуклым ограничением, представимым в виде разности двух выпуклых функций (d.c.-функции). Для полученной задачи разработаны методы локального и глобального поисков. Проведен вычислительный эксперимент на сериях специальным образом сгенерированных задач, в том числе на задачах высокой размерности, продемонстрировавший эффективность предложенного подхода. Библ. 31. Фиг. 1. Табл. 2.
Ключевые слова: линейная двухуровневая задача, оптимистическое решение, задача с ё.с.-не-равенством, локальный поиск, глобальный поиск, вычислительный эксперимент.
1. ВВЕДЕНИЕ
Как известно, задачи двухуровневого программирования представляют собой экстремальные задачи (см. [1], [2]) с иерархической структурой, в которые наряду со стандартными ограничениями типа равенств и неравенств входит ограничение, описываемое с помощью оптимизационной подзадачи. В настоящее время иерархические задачи, возникающие на практике при исследовании сложноорганизованных систем управления, являются весьма популярным объектом для математического исследования (см. [3]—[18]).
С одной стороны, это обусловлено широким полем приложений задач подобного сорта (см. [7]), с другой — трудностями их исследования, которые возникают вследствие иерархической структуры задач даже в простейшем линейном случае (см. [13]). В работе исследуется непрерывная двухуровневая задача с линейными функциями на верхнем и нижнем уровнях (см. [7], [13]). При этом предполагается, что из всех возможных решений на нижнем уровне выбирается то, которое благоприятствует достижению цели верхнего уровня. Такая постановка двухуровневой задачи носит название оптимистической (см. [13]). Будем рассматривать линейно-линейную двухуровневую задачу в следующей постановке:
f(x, У) := <с, x) + <d, y) i min,
x, У
x e X := {x e R™|^x ^ b}, (1.1)
y e Y*(x) = Argmin{<d1, y)\y e Y(x)};
y
здесь множество Y(x) определено системой неравенств
Y(x) = {y e R*|^x + By ^ b1}, (1.2)
m n p q
где c e R , d, d1 e R , b e R , b1 e R — заданные векторы, A, A1, B1 — матрицы размеров (p x m), (q x m), (q x n) соответственно.
Несмотря на внешнюю простоту, задача (1.1) оказывается весьма сложной для исследования. Тем не менее за три десятилетия интенсивного исследования непрерывных двухуровневых задач различных классов было предложено достаточно много методов их решения (см., например, обзоры [12], [13]). Однако сравнительно эффективными оказываются только специальные численные методы решения задач с линейными целевыми функциями на обоих уровнях. А в нелиней-
1715
ном случае авторы зачастую ограничиваются рассмотрением иллюстративных примеров небольшой размерности.
В линейно-линейном случае двухуровневая задача обладает тем свойством, что хотя бы одно ее глобальное решение достигается в крайней точке допустимого множества, поэтому широкий класс методов решения таких двухуровневых задач базируется на переборе вершин допустимого множества. Первые результаты в этом направлении были опубликованы в [11], а затем получили развитие в [17], [19] и др.
Еще одним интенсивно развивающимся направлением является разработка методов спуска, предназначенных для поиска стационарных точек и локальных минимумов в двухуровневых задачах (см. [16]).
Наиболее популярен при решении двухуровневых задач подход, основанный на замене задачи нижнего уровня ее условиями оптимальности (что возможно в случае выпуклой, в частности линейной, задачи оптимизации нижнего уровня по своей переменной). В результате вместо двухуровневой получаем эквивалентную ей одноуровневую задачу с невыпуклым ограничением-равенством. В этом случае мы имеем дело с задачей, принадлежащей классу задач с комплементарными ограничениями, специальная структура которых создает трудности ее эффективного численного решения (см. [20]). Тем не менее, учитывая комплементарность множителей Лагран-жа и ограничений задачи нижнего уровня, можно предложить различные варианты метода ветвей и границ (см. [6], [21]). Один из популярных подходов в этом случае — так называемые методы релаксации, в которых ограничение-равенство параметрически возмущается так, чтобы получаемая задача могла обладать свойствами регулярности ограничений (см. [20]).
Другой подход к решению двухуровневых задач — это решение последовательности вспомогательных задач линейной дополнительности (см., например, [15]), что, по сути, представляет собой симбиоз метода крайних точек и метода ветвей и границ.
Кроме того, при использовании подхода, основанного на сведении двухуровневой задачи к одноуровневой, для решения последней часто применяется метод штрафов (см. [9]), хотя, в силу невыпуклости оштрафованной целевой функции, такой подход обоснован только лишь для поиска локальных экстремумов (см. [10]). В то же время уже удалось успешно использовать данный метод для численного поиска глобального решения (см. [22]) в двухуровневых задачах с квадратичной целевой функцией на верхнем и линейной целевой функцией на нижнем уровне.
Насколько можно судить по доступной литературе, размерность, которую приводят авторы публикаций для тестирования предлагаемых алгоритмов, недостаточна для решения практических задач. Эффективно решаются только линейно-линейные задачи средней размерности. Так, в [6] приведены результаты решения таких задач с суммарным числом переменных до 130, а в [21] - до 200.
Целью данной работы является разработка эффективного метода решения линейных двухуровневых задач, позволяющего численно решать задачи высокой размерности. Для этого используется подход, основанный на редукции двухуровневой задачи в оптимистической постановке к задаче оптимизации с билинейным ограничением-равенством. Как известно, билинейная функция может быть представлена в виде разности двух выпуклых функций (см. [23], [24]), поэтому для решения получившейся задачи оптимизации применима теория глобального поиска для задач с ё.е.-ограничением (см. [25]-[28]).
Статья имеет следующую структуру. В разд. 2 обосновано сведение двухуровневой задачи к невыпуклой задаче оптимизации. Разд. 3 и 4 посвящены локальному поиску и его тестированию. В разд. 5 и 6 представлен алгоритм глобального поиска, особенности его реализации и результаты тестирования на достаточно широком поле специальным образом сгенерированных линейно-линейных двухуровневых задач различной сложности и размерности.
2. ПОСТАНОВКА ЗАДАЧИ
Сделаем следующие предположения относительно задачи двухуровневого программирования (1.1):
1) множество У*(х) = А§ш1п{ (с1, У) \у е У( х)} - непустой компакт для произвольного фик-
У
сированного х е X, где У(х) определено по формуле (1.2);
2) целевая функция верхнего уровня fx, y) ограничена снизу на непустом множестве
Z = {х е R™, y е П"\Лх ^ b, A1x + B1y ^ b1};
3) функция ( d1, y) ограничена снизу на множестве Y(x) для всех x е X, так что
infinf{ <d1, y) |y е 7(x), x е X} > -да.
x y
При выполнении этих предположений можно гарантировать существование оптимального решения исследуемой задачи (см. [7], [13]).
Напомним, каким образом двухуровневая задача (1.1) может быть сведена к невыпуклой задаче математического программирования (см. [7], [13]).
Для задачи нижнего уровня двухуровневой задачи (1.1), которая представляет собой задачу параметрического линейного программирования (ЛП)
(d1, y) I min, y е 7(x) = {y е R^x + B1y ^ b1}, (2.1)
y
запишем двойственную задачу (см. [2], [29]), считая x е X заданным параметром:
(A1x - b\ v) t max, v е V = { v е vB1 = -d\ v ^ 0}. (2.2)
v
Как известно, согласно теореме двойственности в ЛП (см. [2], [29]), для допустимых векторов x, y, v справедливо следующее неравенство:
(d1, y) - (Aix - b\ v) ^ 0. (2.3)
Кроме того, с учетом сделанных предположений 1)—3) взаимодвойственные задачи (2.1) и (2.2) при фиксированном x е X разрешимы, а значит, по теории двойственности (см. [29]), найдутся
векторы y е R и v е [ такие, что тройка (x, y, v) удовлетворяет системе ограничений
( d1, y) = (A1x - bv),
1 (2.4)
A1 x + B1 y ^ b1, vB1 = -d1, v ^ 0,
где y и v — решения прямой и двойственной задач нижнего уровня при фиксированном x соответственно. Поэтому, заменяя в задаче (1.1) задачу нижнего уровня эквивалентной ей системой (2.4), получаем следующую невыпуклую задачу математического программирования:
(c, x) + (d, y) I min, (x, y, v) е S,
x. y> v (2.5)
F(x, y, v) := (A^ - b\ v) - (d\ y) = 0,
где
S := {Ax ^ b, A1x + B 1y ^ b\ vB1 = -d\ v ^ 0}. (2.6)
Нетрудно видеть, что невыпуклость в задаче (2.5) порождается билинейным ограничением-равенством, более точно — наличием произведения (A1 x, v) в последнем равенстве. Кроме того, при переходе от задачи (1.1) к задаче (2.5) увеличивается размерность пространства: появляется
вектор двойственных переменных v е Взаимосвязь задач (2.5) и (1.1) устанавливается следующей теоремой.
Теорема 2.1 (см. [7], [13]). Для того чтобы пара (x*, y*) являлась решением двухуровневой задачи (1.1), необходимо и достаточно существования вектора v* такого, что тройка (x*, y*, v*) является глобальным решением задачи (2.5).
Таким образом, вместо двухуровневой задачи (1.1) можно решать задачу (2.5) с невыпуклым ограничением. Как уже упоминалось, одним из стандартных походов к решению задач такого класса является применение метода штрафов (см. [7], [18]). В этом случае невыпуклость задачи (билинейное ограничение-равенство) переходит в целевую функцию и возникает дополнительный штрафной параметр (см. также [22]).
В данной работе предлагается решать задачу (2.5) напрямую, применяя теорию глобального поиска для задач с ограничением, задаваемым d.c.-функцией (см. [25]—[28]),
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.