Н.М. Новикова - Дискретные и непрерывные задачи оптимизации (1125224), страница 11
Текст из файла (страница 11)
Предпочтительность той или иной стратегии ветвления оценивается каждым вычислителем по-своему, исходя нз главной задачи метода ветвей и границ — быстрее получить лучший рекорд, чтобы отсечь больше ветвей. В рассматриваемой задаче есть хороший способ улучшения рекорда — локальная оптимизация (см. в 18). Ее имеет смысл проводить из текушей точки, в которой произошло обновление рекорда, например, делая несколько шагов градиентного метода. При этом расположение кубиков менять не надо, просто увеличивается шанс сокрашения перебора (отбрасывания ббльших кубиков). Отметим, что в худшем случае у = сопя! ЯТ< = 9) — не удается отбросить ни одной точки х — и. приходим к полному перебору; т.е. указанная в п.1 экспоненциальная оценка точна на классе всех липшицевых функций. 111.
Целочисленное линейное программирование (ЦЛП) Отличив задач ЦЛП и ЛП: существенная нелингйностпь ограничений тина Кглвчисленнвсти. Нгэффснтивнвсгль внругленил решения ЛП дв блихсайшегв иелого. Случай вполне унимодулврнвй матрицы ограничений. МВГ в ЦЛП. МВГ для булава линейного программирования (БЛП). 1. По-видимому, наиболее важным классом задач глобальной оптимизации являются задачи ПЛП. Эти задачи формулируются как задачи ЛП с дополнительным ограничением пелочисленности переменных. Последнее ограничение, какими бы способами от него ни избавляться, "портит" свойство выпуклости (и полиномиальности) задачи ЛП.
Например, выразив условие целочисленности в форме ограничений неравенств, рассмотренной в доказательстве утверждения 1 18, и сняв их методом штрафов, придем к задаче глобальной оптимизапии, имеюшей не меньше локальных экстремумов, чем вариантов для целочисленных переменных в исходной ПЛП. Поэтому 84 на практике удается решать задачи ЦЛП только небольшой размерности или с ограничениями целочисленности не на все, а лишь на несколько переменных. Существует частный класс задач ЦЛП, в которых ограниченые целочисленности оказывается несущественным.
Опгкдклкник 1. Матрица называется оволнс укамодуляриоп, если определитель любой ее невырожденной квадратной подматрицы равен по модулю 1. Утвкгждкиик 1. Если матрица ограничений разрешимой задачи ЛП с целыми коэффициентами вполне унимодулярна, то у «ее существует целочисленное решение. Поклзлткльство очевидно из принципа граничных решений (35) и правила Крамера (см. доказательство теоремы 1 35). Утвкгждкиик 2. Матрица А вполне унимодулярна тогда и только тогда, когда для любого целочисленного вектора 6 все вершины многогранника Ах < 6, х ) 0 являются целочисленными.
Поклзлткльство в одну сторону аналогично предыдущему, в другую сторону см. ссылку в [2, с. 333]. Таким образом, вполне унимодулярными 'матрицами ограничений в принципе ограничивается класс задач ЦЛП, эквивалентных ЛП и, следовательно, допускающих эффективное решение. Отметим, что укаэанный класс, хотя и чрезвычайно узок с формальной точки зрения (элементами матрицы А могут быть только О, 1 и -1, причем по большей части О), соответствует достаточно широкому классу практических задач оптимизации на графах и сетях (одно- и двух- продуктовые сети, двудольные графы и т.п.). Приведем без доказательства еще одно полезное утверждение, позволяющее в некоторых случаях получать приближенное решение ЦЛП путем решения ЛП.
Утвкгждкник 3. Если все элементы симплекс-таблицы ау, бы су— натуральные числа, то для любого решения хо задачи ЛП шах (с, х) л<ь, >з вектор 1хо1, составленный из компонент ~хо1, будет допустимым в данной задаче. При этом для решения х* соответствующей задачи 55 ЦЛП шах (с, в) Аг<Ь, гЕК"Ь очевидна оценка ](с, (хв]) — (с, х*)] < (с, 1). Условие положительности исходных данных выполняется для некоторых экономических задач.
Такой же результат можно получить для ряда многопродуктовых потоковых задач на сетях и других линейных задач максимизации с положительным с, в которых допустимое множество вместе с любой точкой в содержит и все в' с компонентами в) б (О, ху]. Однако поиск х' по ф'] может потребовать перебора 2" вариантов округления компонент хв. К сожалению, в общем случае и перебора всех возможных вари- . антов округления компонент решения непрерывной задачи ЛП оказывается недостаточно для получения решения ЦЛП (например, при и = 2, если для положительного с рассмотреть систему ограничений -9хь + 10хз < О, — 8хь + 10хг < — 1).
Таким образом, поиск решения ЦЛП может потребовать очень большого перебора целочисленных точек, и возникает та же, что и в з10, задача организации перебора с целью попытаться его сократить в случае не самой плохой задачи. Одним из достаточно употребительных методов перебора здесь является метод ветвей и границ, который для ЦЛП будет рассмотрен в п.2. Лругие методы см. в (2,6]. 2. Меньвд вепьвей н границ для ЦЛП. Рассматривается задача шах (с, г), зев": Ан<Ь решением которой является целочисленный вектор з'.
В корневой вершине метода вместо задачи (1) решается озЛП (2) шах (с, х), гец: Ав<Ь решением которой является вектор х~. Если ве оказался целочисленным, то з'.=хе — решение задачи (1) закончено. Иначе Звг ф Е и осуществляем ветвление по у-й компоненте следующим образом. Из вершины выходят две ветви, и на новом ярусе к ограничениям озЛП, решаемой в порождающей вершине, добавляется ограничение ву ( ~хе1 для 1-й ветви или х > (хз) для 2-й ветви. Значение максимума в исходной задаче ПЛП (1), очевидно, равно максимальному из значений подзадач ЦЛП на каждой ветви.
Но, как и ранее, вместо подзадачи ЦЛП рассматривается подзадача без ограничения целочисленности. Такая озЛП и решается в очередной порожденной вершине в случае ее раскрытия, обозначим решение через х . Если и — целочисленное, то вершина закрывается, а значение з (с,хь) функции цели сравнивается с рекордом для его обновления или, по первому разу, присваивается рекорду, и точка х — допустимзл точка в задаче (1) — запоминается. После получения рекорда может быть закрыта любая раскрытая вершина, для которой оптимальное значение целевой функции окажется меньше рекорда.
Лействительно, поскольку максимум по большему множеству не меньше максимума по меньшему, то значение озЛП дает оценку сверху (гравииу) значения соответствующей целочисленной подзадачи, и когда верхняя оценка не превышает рекорда, бессмысленно пытаться уве' личить рекорд на данной ветви. ,Пругим случаем закрытия вершины (отсечения ветви) является неразрешимость поставленной озЛП и, следовательно, той же подзадачи ЦЛП. Заметим, что для проверки неразрешимости не всегда надо решать задачу, несовместными могут сразу при формулировке оказаться, например, ограничения в.
> (х ~, оставшиеся с одного з-! из предыдущих ярусов, и х ( ~х~з~, добавленные снова. Если вь — нецелочисленное, то Зх~ 1е Е, и осуществляем ве' 'твление по 1-й компоненте описанным выше способом. Процедура заканчивается после закрытия всех вершин, тогда значение (1) равно текущему рекорду, либо рекорд остался неопределенным и задача (1) не имеет решения.
Выбор стратегии ветвления в ПЛП играет не меньшую роль, чем в глобаяьной оптимизации. Отсутствие рекорда приводит к лишнему перебору, но процедура ветвления "в глубину" может вместо рекорда дать несовместную систему ограничений. Кроме того, для нескольких нецелых компонент в» не понятно, по какой из них лучше осуществлять ветвление: по новой, которая не рассматривалась на предыдущих ярусах, или сначала перебрать все допустимые целые значения одной из компонент (по аналогии с БЛП вЂ” см. ниже).
Последняя стратегия имеет смысл при наличии двусторонних огра- ничений на переменные. 3. Метод ветвей а гракхи для БЛП. Частным случаем задачи (1) ПЛП является задача БЛП шах (с, х), *вв'. лв<в (3) 112. Метод динамического программирования (ДП) Теоретические основы ЛП. Обц1ая схема мгтаоди Метод ЛП длл БЛП с кготрипатгаъкыма коэффицыгнтами. Связь с МВГ.
1. Еще одной традиционно используемой схемой перебора является метод дккамкчгского врограммароваккя 1ДП). Один пример алгоритма ПП приводился в 14, где этод метод позволил построить псевдополиномиальный алгоритм решения задачи о рюкзаке. Вообще говоря, подобные алгоритмы и надеются получить путем применения схемы,ПП. Однако ЛП можно использовать не для произвольных оптимизационных задач. Класс подходящих задач опишем далее.
88 решение которой — вектор хв из булева куба. Из результатов 12 (утверждения 8) вытекает ХР-трудность БЛП и, следовательно, правомерность использования переборных схем для решения (3). В з12 будет показана схема динамического программирования для БЛП с неотрицательными коэффициентами, а для произвольных задач (3) применима схема предыдущего пункта, которая несколько упрощается за счет дополнительного ограничения О ( х; ( 1, превращающего ПЛП в БЛП. А именно, после замены Ив на Вк, при ветвлении в новые подзадачи добавляется вместо ограничений неравенств условие равенства О (для одной ветви) или 1 (для другой) той переменной, по которой осуществляется ветвление.
Таким образом указанная переменная становится булевой во всех нижних ярусах, т.е. по ней не придется вновь проводить ветвление, а значит, на и-м ярусе решение (3) будет закончено. Число раскрываемых вершин (нли решений подзадач ЛП) прн этом не превысит 2"+', что, конечно, тоже немало, но заметно меньше, чем для ПЛП (сравнимо со случаем, предусмотренным утверждением 3). ОпРВДеление 2. ФУнкциа У называетсЯ Разделлемоа на Уг и Уз, если она представима в виде (4) у(х,у) = уг(х, Яу)). ОпреДЕПЕНИЕ 3. Функция у называется разложамоа на уг и уз, если она разделяема на уг, уз и функция уг монотонно не убывает по последнему аргументу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
