Свойства и сложность задач двухуровневого программирования
It is proved that a solution of linear bilevel programming problem is achieved at an extreme point of its constraint region. Based on this property, the algorithm for search a problem solution is suggested. It is demonstrated the mapping of follower’s responses is a polyhedral one. It is showed that...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84961 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Свойства и сложность задач двухуровневого программирования / В.М. Горбачук, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 106-115. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84961 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-849612025-02-09T14:58:12Z Свойства и сложность задач двухуровневого программирования The properties and complexity of bilevel programming problem Горбачук, В.М. Шулинок, Г.А. It is proved that a solution of linear bilevel programming problem is achieved at an extreme point of its constraint region. Based on this property, the algorithm for search a problem solution is suggested. It is demonstrated the mapping of follower’s responses is a polyhedral one. It is showed that in general case a set of problem solutions may not be connected. The NP-completeness of problem is proved. 2006 Article Свойства и сложность задач двухуровневого программирования / В.М. Горбачук, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 106-115. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84961 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
It is proved that a solution of linear bilevel programming problem is achieved at an extreme point of its constraint region. Based on this property, the algorithm for search a problem solution is suggested. It is demonstrated the mapping of follower’s responses is a polyhedral one. It is showed that in general case a set of problem solutions may not be connected. The NP-completeness of problem is proved. |
| format |
Article |
| author |
Горбачук, В.М. Шулинок, Г.А. |
| spellingShingle |
Горбачук, В.М. Шулинок, Г.А. Свойства и сложность задач двухуровневого программирования Теорія оптимальних рішень |
| author_facet |
Горбачук, В.М. Шулинок, Г.А. |
| author_sort |
Горбачук, В.М. |
| title |
Свойства и сложность задач двухуровневого программирования |
| title_short |
Свойства и сложность задач двухуровневого программирования |
| title_full |
Свойства и сложность задач двухуровневого программирования |
| title_fullStr |
Свойства и сложность задач двухуровневого программирования |
| title_full_unstemmed |
Свойства и сложность задач двухуровневого программирования |
| title_sort |
свойства и сложность задач двухуровневого программирования |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2006 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84961 |
| citation_txt |
Свойства и сложность задач двухуровневого программирования / В.М. Горбачук, Г.А. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 106-115. — Бібліогр.: 5 назв. — рос. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT gorbačukvm svojstvaisložnostʹzadačdvuhurovnevogoprogrammirovaniâ AT šulinokga svojstvaisložnostʹzadačdvuhurovnevogoprogrammirovaniâ AT gorbačukvm thepropertiesandcomplexityofbilevelprogrammingproblem AT šulinokga thepropertiesandcomplexityofbilevelprogrammingproblem |
| first_indexed |
2025-11-27T02:58:21Z |
| last_indexed |
2025-11-27T02:58:21Z |
| _version_ |
1849910688300924928 |
| fulltext |
Теорія оптимальних рішень. 2006, № 5 106
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Доказано, что в общем случае ре-
шение задачи линейного двухуров-
невого программирования достига-
ется в крайней точке ее области
ограничений. На основе этого фун-
даментального свойства пред-
ложен алгоритм поиска решения.
Показана полиэдральность много-
значного отображения откликов
последователя. Показано, что в
общем случае множество решений
задачи может не быть связным.
Доказана NP-полнота задачи.
В.М. Горбачук, Г.А. Шулинок
2006
ÓÄÊ 519.8
Â.Ì. ÃÎÐÁÀ×ÓÊ, Ã.À. ØÓËÈÍÎÊ
ÑÂÎÉÑÒÂÀ È ÑËÎÆÍÎÑÒÜ ÇÀÄÀ×
ÄÂÓÕÓÐÎÂÍÅÂÎÃÎ
ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß
Введение. Многие задачи иерархической
оптимизации, включающие более одного
лица, принимающего решения (ЛПР), можно
моделировать как задачу многоуровневого
математического программирования. Двух-
уровневая структура известна как игра Шта-
кельберга, где лидер и последователь пыта-
ются минимизировать свои отдельные целе-
вые функции затрат ),( yxF и ),( yxf со-
ответственно (максимизировать ),( yxF− и
),( yxf− ). Эту игру считают последова-
тельной и некооперативной. Лидер осущест-
вляет ход первым и через свой выбор
mRy ∈ (на верхнем уровне) способен вли-
ять на действия последователя, но не кон-
тролировать их. Это достигается сужением
множества допустимых выборов, имеющих-
ся в наличии для последователя. Затем по-
следователь реагирует на решение лидера,
выбирая n
Rx ∈ (на нижнем уровне) и ми-
нимизируя свои затраты, не обращая внима-
ния на интересы лидера. Тем самым после-
дователь опосредованно влияет на про-
странство решений лидера и результат.
В основе известной традиционной игры
Штакельберга, как правило, лежат два базо-
вых предположения: все игроки имеют пол-
ную информацию; кооперация между игро-
ками запрещена. Это предотвращает исполь-
зование коррелированных стратегий и так
называемых побочных платежей. Задачу по-
следовательной оптимизации, в которой не-
сколько независимых ЛПР действуют не-
кооперативным образом, чтобы
СВОЙСТВА И СЛОЖНОСТЬ ЗАДАЧ ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2006, № 5 107
минимизировать свои отдельные затраты, относят к игре Штакельберга. Линей-
ный случай игры, когда все функции считаются аффинными, известен как задача
линейного двухуровневого программирования (ЗЛДУП), которая является ста-
тическим вариантом с открытым витком (open loop), где лидер контролирует
переменные решения y , а последователь – переменные решения )(yx [1, 2].
Пример 1. Рассмотрим задачу верхнего уровня (ЗВУ)
yxyxF
y
+= 3),(min (1)
при ограничении
61 ≤≤ y , (2)
где x – решение задачи нижнего уровня (ЗНУ)
xyxf
x
−=),(min (3)
при ограничениях
8≤+ yx , (4)
84 ≥+ yx , (5)
132 ≤+ yx . (6)
Минимизация функции xyxf −=),( по x равносильна максимизации x :
из ограничений (2), (4) получаем
7188 =−≤−≤ yx ;
из ограничений (2), (5) получаем
75.1125.0225.02 =×−=−≥ yx ;
из ограничений (2), (6) имеем
615.05.65.05.6 =×−=−≤ yx .
Отсюда
}5.05.6;8min{25.02 yyxy −−≤≤− ,
если
}5.05.6;8min{25.02 yyy −−≤− .
Последнее неравенство выполняется, если
yyy 5.05.6825.02 −≤−≤− ; 62875.0 =−≤y ; 83/46 =×≤y ;
yyy 5.05.05.685.1 =−≤−= ; y≤3 ,
либо
yyy −≤−≤− 85.05.625.02 ; 5.425.625.0 =−≤y ; 18≤y ; 3≥y .
Таким образом, учитывая (2), при ]6,3[∈y оптимальное решение ЗНУ –
yyx −= 8)( , а при ]3,1[∈y – yyx 5.05.6)( −= :
∈−
∈−
=
].6,3[,8
];3,1[,5.05.6
)(
yy
yy
yx
Тогда
В.М. ГОРБАЧУК, Г.А. ШУЛИНОК
Теорія оптимальних рішень. 2006, № 5 108
∈−=+−=+
∈−=+−=+
=
];6,3[,224)8(33
],3,1[,5.05.19)5.05.6(33
)),((
yyyyyx
yyyyyx
yyxF
1835.05.19)),(( =×−≥yyxF ; 126224)),(( =×−≥yyxF .
Итак, глобальное минимальное значение ЗВУ равно 12 при 6=y ,
268)( =−=yx ( 2)6( =x – решение ЗНУ).
Пусть ЗНУ выглядит так:
dycxyxf
x
+=),(max (7)
при ограничениях
ByaAx −≤ , (8)
0≥x ; (9)
пусть ЗВУ имеет вид
hygxyxF
y
+=),(max , (10)
0≥y , (11)
где p
Ra ∈ , а матрицы A , B и векторы c , d , g , h имеют соответствующие
размерности. ЗЛДУП (7)–(11) называют двухуровневой задачей управления ре-
сурсами.
Областью ограничений ЗЛДУП называют
};0;0:),{( aByAxyxyxS ≤+≥≥= .
Допустимым множеством для последователя при каждом данном 0≥y на-
зывают };0:{)( aByAxxxyS ≤+≥= .
Проекцией S на пространство решений лидера }0:{ ≥= yyY называется
0:0{)( ≥∃≥= xyYS такой, что }aByAx ≤+ .
Множеством рациональных реакций (откликов) последователя при
)(YSy ∈ называют )},(max:0{)(
)(
yxfArgxxyP
ySx∈
∈≥= .
Индуцированной областью (inducible region) называется
)}(;),(:),{( yPxSyxyxIR ∈∈= .
Так как на множестве IR лидер может оптимизировать, то ЗЛДУП можно
записать как стандартную задачу математического программирования
),(max
),(
yxF
IRyx ∈
.
Теорема 1. Предположим, область S непуста и ограничена. Рассмотрим
произвольную выпуклую комбинацию
∑
=
==
r
t
tt zzyx
1
),( λ , 0,...,1 ≥rλλ , ∑
=
=
r
t
t
1
1λ ,
СВОЙСТВА И СЛОЖНОСТЬ ЗАДАЧ ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2006, № 5 109
точек Szz r ∈,...,1 , принадлежащую множеству )}(;0:),{( yPxyyxP ∈≥= .
Тогда если 0>iλ (точка iz строго входит в данную выпуклую комбинацию),
},...,1{ ri ∈ , то Pzi ∈ (множество P обладает слабым свойством выпуклости
относительно S ).
Доказательство проведем методом от противного. Пусть 01 >λ , но
Pyxz ∉= ),( 111 . Тогда существует такая точка Pyxz ∈= ),~(~
111 , что
1111
~ dycxdyxc +>+ .
Поскольку Sz ∈1
~ и область S ограничений выпукла, то выпуклая комби-
нация точек Szzz r ∈,...,,~
21 также принадлежит S :
∑
=
∈+==
r
t
tt Szzyxz
2
11
~)~,~(~ λλ .
Если yy =~ , то
∑ ∑
= =
=+<+=
r
t
r
t
tttt xcxcxcxcxccx
2 2
11111
~~ λλλλ .
Итак, Sz ∈~ , yy =~ , 1
~xccx < , что противоречит Pyxz ∈= ),( . Поэтому
Pyxz ∈= ),( 111 . Доказательство проводится аналогично для любого ri ,...,2= .
Следствие 1. Если z – крайняя точка P , то z – крайняя точка S .
Доказательство проведем от противного. Предположим, z не является
крайней точкой S . Тогда z можно представить такой выпуклой комбинацией
крайних точек Szz r ∈,...,1 :
∑
=
=
r
t
tt zz
1
λ , 0,...,1 >rλλ , ∑
=
=
r
t
t
1
1λ .
Но по теореме 1 Pzz r ∈,...,1 , откуда Pz ∉ , получая противоречие.
Следствие 2. ЗЛДУП (7)–(11) достигает своего оптимального решения в
крайней точке S .
Заметим, что задачу (7)–(11) можно записать следующим образом:
hygxyxFzF
Pz
+==
∈
),()(max .
Поскольку )(zF – линейная функция, то решение последней задачи (если
оно существует) достигается в крайней точке P (могут существовать другие
оптимумы в точках, не являющихся крайними). Тогда в силу следствия 1 такая
точка также является крайней точкой области S .
Пользуясь следствием 2, можно предложить алгоритмы решения ЗЛДУП на
основе процедур поиска крайних точек. Рассмотрим задачу линейного програм-
мирования
В.М. ГОРБАЧУК, Г.А. ШУЛИНОК
Теорія оптимальних рішень. 2006, № 5 110
hygxyxFzF
Sz
+==
∈
),()(max (12)
и ее базисные допустимые решения Mzz €,...,€
1 , упорядоченные так, что
)€()€( 1+
≥ ii zFzF 1,...,1 −=∀ Mi .
Тогда индексу }€:,...,1min{ PzMK i ∈= соответствует глобальное опти-
мальное решение Kz€ ЗЛДУП. Поэтому достаточно найти K -е наилучшее реше-
ние задачи (12) в крайней точке, являющейся смежной с 1-й, 2-й,..., или )1( −K -
й крайней точкой. Следующий алгоритм направлен на минимальное хранение
индексов столбцов базисов, соответствующих первым )1( −K наилучшим точ-
кам, и на вычисление точки, которая является смежной с первыми )1( −K наи-
лучшими точками и дает максимальное значение целевой функции верхнего
уровня.
Шаг 1. Полагаем 1=j . Получаем оптимальное решение )€,€(€
jjj yxz = за-
дачи (12) (симплекс-методом). Полагаем =W Ø jz€∪ , =T Ø, переходим на шаг
2.
Шаг 2. Получаем оптимальное решение )~,~(~ yxz = задачи линейного про-
граммирования
}€:),({:)({max j
z
xxyxzSzzf ==∩∈
(ограниченным симплекс-методом). Если jzz €~ = , то jz€ – глобальное решение,
jK = и останов алгоритма; иначе переходим на шаг 3.
Шаг 3. Пусть {=jW все крайние точки, смежные с }€jz (из jWz ∈ вытека-
ет )€()( jzfzf ≤ ). Полагаем jzTT €∪= ,
c
j TWWW ∩∪= )( и переходим на
шаг 4.
Шаг 4. Полагаем 1+= jj , получаем решение задачи )(max zF
Wz∈
и перехо-
дим на шаг 2.
Вычислительную эффективность данного алгоритма можно улучшать, со-
храняя все обновленные небазисные столбцы или все обратные базисы. Тогда в
случае большой размерности приближенное решение можно оценивать верхней
и нижней границами оптимального решения.
Если лидер выбирает y , то это значение становится фиксированным пара-
метром целевой функции последователя. Поэтому всегда возможно удалять
компоненты решения y , линейно входящие в ),( yxf . Обозначим множество
оптимальных решений задачи нижнего (lower) уровня
}0;:{min)( ≥−≤=Ψ xByaAxcxArgy
x
L .
СВОЙСТВА И СЛОЖНОСТЬ ЗАДАЧ ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2006, № 5 111
Точечно-множественное отображение Γ называют полиэдральным, если
его график является объединением конечного числа выпуклых полиэдральных
множеств. Выпуклое полиэдральное множество – это пересечение конечного
числа полупространств [3].
Теорема 2. Точечно-множественное отображение )(yLΨ – полиэдральное.
Тогда ЗЛДУП можно решать, минимизируя линейную целевую функцию
ЗВУ по каждой компоненте графика отображения )(yLΨ при ограничениях
ЗВУ. Каждая из этих задач – задача линейного программирования.
Следствие 3. Если оптимальное решение ЗНУ однозначно определяется для
каждого значения параметра y , то существует оптимальное решение линейной
ЗВУ, являющееся вершиной множества ее ограничений.
Следствие 4. Теорему 1 можно обобщить на ЗНУ с линейными ограниче-
ниями и квазивыпуклой дробной целевой функцией ЗВУ.
Лемма 1. Если ограничения ЗВУ зависят от оптимального решения ЗНУ, то
допустимое множество ЗЛДУП может не быть связным.
Пример 2 (модифицированный пример 1). Рассмотрим ЗВУ
)3(min yx
y
+
при ограничениях
80 ≤≤ y , (13)
5≤x , (14)
}072;132;84;8:{min ≤−≤+≥+≤+−∈ yxyxyxyxxArgx
x
.
Решение ЗНУ эквивалентно максимизации функции xyxf =),( , причем
yx −≤ 8 ; yx 5.05.6 −≤ ; yx 5.3≤ ,
}5.3;5.05.6;8min{25.02 yyyxy −−≤≤− .
Для решения ЗНУ применим подход ветвей и границ, состоящий из сле-
дующих шагов.
1. Учитывая ограничение (13) для y , упорядочим ограничения сверху для
x при наименьшем возможном значении 0=y :
yyy −<−<= 85.05.605.3 .
2. Тогда вместо последнего соотношения рассматриваем
yy 5.325.02 ≤− ,
откуда
4/1575.325.05.32 yyyy ==+≤ ; y≤15/8 .
3. Упорядочим ограничения сверху для x при 15/8=y :
)15/8(5.35)15/8(5.05.6715/88 >>−>>− .
4. Тогда рассматриваем
yy 5.05.65.3 −≤ ,
В.М. ГОРБАЧУК, Г.А. ШУЛИНОК
Теорія оптимальних рішень. 2006, № 5 112
откуда
2/135.64 =≤y ; 8/13≤y .
5. Пользуясь линейностью всех ограничений, упорядочим остальные огра-
ничения сверху для x при 8/13=y :
)8/13(5.05.616/135.668/138 −=−>>− .
6. Рассматриваем
yy 5.05.625.02 −≤− ,
откуда
2/95.425.625.05.025.04/ ==−≤−== yyyy ; 18≤y .
7. Упорядочим по y два последние ограничения сверху для x :
yy −≤− 85.05.6 ,
откуда
2/35.15.6825.05.02/ ==−≤−= yyy ; 3≤y .
Таким образом, учитывая ограничения (13),
≤≤−
≤≤−
≤≤
=
.83,8
;38/13,5.05.6
;8/1315/8,5.3
)(
yy
yy
yy
yx
Проверим, удовлетворяет ли полученное )(yx ограничению (14):
55.32/7 ≤= yy ; 7/10≤y ; 2/5.055.65.12/3 yy =≤−== ;
y≤3 ; (15)
58 ≤− y ,
y≤−= 583 . (16)
Итак, учитывая (15)–(16), получаем
≤≤−
≤≤
=
.83,8
;7/1015/8,5.3
)(
yy
yy
yx
Если ограничение (14) перенести из ЗВУ в ЗНУ, то допустимое множество
ЗВУ является связным и состоит из всех точек )),(( yyx , где
≤≤−
≤≤
≤≤
=
.83,8
;37/10,5
;7/115/8,5.3
)(
yy
y
yy
yx
Следует отметить, что расстановка ограничений не является произвольной с
практической точки зрения: каждое ограничение ЗНУ сужает допустимые реше-
ния последователя. Когда такое же ограничение расположено в ЗВУ, то сужает
решение лидера в том смысле, что допустимость выбора лидером рассматрива-
ется после выбора последователем: ограничение ЗВУ неявно сужает задание ли-
дера. Эта проблема усугубляется, когда выбор последователем определяется не-
СВОЙСТВА И СЛОЖНОСТЬ ЗАДАЧ ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2006, № 5 113
однозначно для некоторого значения y~ параметра, потому что тогда какие-то
решения последователя )~(yx LΨ∈ могут означать, что выбор лидера y~ допус-
тимый, но другие решения последователя отбрасывают y~ .
Лемма 2. Ограничение ЗВУ, включающее отклик последователя, можно пе-
ремещать в ЗНУ, если существует по крайней мере одно оптимальное решение
ЗНУ, не зависящее от этого перемещения при каждом значении параметра.
Теорема 3. Пусть ),( ** yx – решение ЗЛДУП. Для любого 1>ε поиск та-
кого решения, что ),(),( ** yxyx ε
εε
≤ , является NP -трудной задачей.
Пусть nXXX ,...,, 21 являются n булевыми переменными. Рассмотрим k
предложений дизъюнкций максимального дерева булевых переменных и их от-
рицаний. Существует ли такое установление значений n булевых переменных,
что все k предложений являются истинными одновременно?
Преобразуем такой произвольный пример в специальный пример ЗЛДУП.
Пусть каждой булевой переменной iX отвечают две вещественные переменные
верхнего уровня iy и iy , причем 1=+ ii yy , ni ,...,1= . Тогда для каждого
предложения построим неравенство zsss kji ≥++ , где переменная ts – одна
из переменных ty или ty , если соответственно tX или tX¬ появляется в пред-
ложении, а z – дополнительная переменная верхнего уровня. Складывая n пе-
ременных нижнего уровня ix и n ограничений нижнего уровня ii yx ≤≤0 ,
ii yx ≤≤0 , получаем булевую ЗНУ (БЗНУ):
∑
=
n
i
i
x
x
1
min
при ограничениях
ii yx ≤≤0 , ni ,...,1= ,
ii yx ≤≤0 , ni ,...,1= .
Очевидно, эта ЗНУ при данном y имеет оптимальное решение
};min{ iii yyx = i∀ . Рассмотрим булеву ЗВУ (БЗВУ):
−∑
=
n
i
i
y
zx
1
min
при ограничениях
zsss kji ≥++ для каждого предложения,
01 ≥≥ z , 01 ≥≥ iy , ni ,...,1= ,
01 ≥≥ iy , 1=+ ii yy , ni ,...,1= ,
x – решение БЗНУ,
В.М. ГОРБАЧУК, Г.А. ШУЛИНОК
Теорія оптимальних рішень. 2006, № 5 114
где переменные is – искусственные для iy и iy , как вышеуказано. В варианте
ЗЛДУП ищется допустимое решение БЗВУ, исходя из некоторого наперед за-
данного значения целевой функции. Очевидно, пример исходной булевой задачи
имеет решение тогда и только тогда, когда оптимальная величина целевой
функции БЗВУ равна 1− . Это свидетельствует, что исходная булевая задача яв-
ляется подзадачей ЗЛДУП. Поскольку исходная булевая задача – NP -полная
[4], то ЗЛДУП – NP -трудная.
Теперь покажем, что вычисление приближенного решения ЗЛДУП имеет
такую же сложность, как вычисление оптимального решения. Это проверяется
преобразованием приближенного решения в допустимое решение со значением
целевой функции верхнего уровня, не худшим оптимального. Пусть
),,,( **** zyyx – ε -оптимальное решение, т.е.
∑
=
≤−
n
i
i fzx
1
***
ε ,
где величина *f – оптимальное значение целевой функции, 10 << ε . Когда
)2/1,0(*
∈iy , то на нижнем уровне **
ii yx = , полагаем 0=iy , 1=iy , 0=ix ,
причем полагаем значение z равным величине между
*z и )( **
ixz − , что необ-
ходимо для сохранения допустимости (действительно, z убывает до уровня, где
следующее ограничение-неравенство удовлетворяется как равенство). Тогда
значение целевой функции верхнего уровня не может возрастать. Это можно
осуществлять по очереди, уменьшая таким образом количество неинтегральных
переменных, но не увеличивая величину целевой функции [5].
Аналогично можно рассматривать случай, когда )1,2/1[*
∈iy : 1=iy ,
0=iy , 0=ix . Итак, все переменные ix получают интегральные значения.
Значение z достигнет 0 или 1, а величина целевой функции уменьшится до
}.1,0{*
∈f Эта процедура полиномиальна. Это показывает, что вычисление ε -
оптимального решения настолько же сложное, как вычисление оптимального
решения.
Из доказательства теоремы 2 видно, что ЗНУ имеет единственное оптималь-
ное решение при всех значениях параметров. Кроме того, маловероятно найти
полиномиальный алгоритм глобального решения ЗЛДУП.
Поскольку исходная булевая задача не является численной, то теорема 2 по-
казывает, что ЗЛДУП – NP -трудная в сильном смысле. Полностью полиноми-
альная схема аппроксимации является алгоритмом решения, параметризован-
ным по точности вычисленного решения, которая при данной точности ε дает
ε -оптимальное решение за время, полиномиальный по длине задачи и ε/1 . До-
казательство теоремы 2 показывает, что эти подзадачи, эквивалентные исходной
булевой, имеют неотрицательные целые оптимальные значения целевой функ-
СВОЙСТВА И СЛОЖНОСТЬ ЗАДАЧ ДВУХУРОВНЕВОГО ПРОГРАММИРОВАНИЯ
Теорія оптимальних рішень. 2006, № 5 115
ции (0 или 1) для всех примеров. Это означает, что не может быть полностью
полиномиальной схемы аппроксимации ЗЛДУП (при NPP ≠ ).
В.М. Горбачук, Г.О. Шулінок
ВЛАСТИВОСТІ ТА СКЛАДНІСТЬ ЗАДАЧ ДВОРІВНЕВОГО ПРОГРАМУВАННЯ
Доведено, що розв’язок задачі лінійного дворівневого програмування досягається в крайній точці
її області обмежень. На основі цієї властивості запропоновано алгоритм пошуку розв’язку задачі.
Показана поліедральність відображення відгуків послідовника. Показано, що в загальному випад-
ку множина розв’язків задачі може не бути зв’язною. Доведено NP-повноту задачі.
W.M. Gorbachuk, G.A.Shulinok
THE PROPERTIES AND COMPLEXITY OF BILEVEL PROGRAMMING PROBLEM
It is proved that a solution of linear bilevel programming problem is achieved at an extreme point of
its constraint region. Based on this property, the algorithm for search a problem solution is
suggested. It is demonstrated the mapping of follower’s responses is a polyhedral one. It is showed
that in general case a set of problem solutions may not be connected. The NP-completeness of
problem is proved.
1. Simaan M., Cruz J.B. On the Stackelberg strategy in nonzero-sum games // J. of optimiza-
tion theory and applications. – 1973. – 11. – P. 533–555 .
2. Горбачук В.М. Решение задачи двухуровневого программирования для билинейных
разрывных функций // Компьютерная математика. – 2005. – № 2. – С. 44–51.
3. Рокафеллар Т. Выпуклый анализ. – М.: Мир, 1973. – 469 с.
4. Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи. – М.:
Мир, 1982. – 416 с.
5. Сергиенко И.В. Математические модели и методы решения задач дискретной опти-
мизации. – Киев: Наук. думка, 1985. – 384 с.
Получено 27.06.2006
|