Eng | Rus | Ukr
Исследование операций
29.01.2005

<< prev | ^up^ | next >>

4.5. ПОСЛЕДОВАТЕЛЬНЫЕ АЛГОРИТМЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

Общая характеристика

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

разбиение множества вариантов решения задачи на несколько подмножеств, каждое из которых обладает специфическими свойствами;

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

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

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

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

Разработке и исследованию приближенных алгоритмов дискретной оптимизации посвящено значительное количество работ [43; 46].

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

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

В качестве основных показателей эффективности приближенных алгоритмов на практике часто используют абсолютную Δ1 и относительную Δ2 погрешности полученного приближенного решения, которые определяются из соотношений:

Δ1 = f (x*) - f (x1); Δ2 = ,

где f - целевая функция, определенная на дискретном множестве M; x1 - приближенное допустимое решение задачи; x* - оптимальное решение задачи (для определенности здесь имеется в виду поиск максимума f (x)).

Если Δ1 = 0 (в этом случае будем считать Δ2 = 0, даже если f (x*) = 0), то приближенное решение совпадает с точным решение.

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

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

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

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

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

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

Для структур, которые имеют форму дерева, были исследованы вопросы, связанные с порядком просмотра ветвей, и найдены способы минимизации числа массивов информации, необходимой для реализации процедур ПАВ.

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

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

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

Общая схема метода

Метод последовательного анализа вариантов (ПАВ) базируется на отсеве бесперспективных элементов как по ограничениям, так и по целевой функции. Его идеи рассмотрим на примере такой задачи дискретного программирования [9].

Пусть L(D(X)) - задача минимизации функции  на конечном множестве D(X), то есть задача нахождения

                                  (4.5.1)

где множество допустимых решений D(X) задается так:

gp(x) £ gp*(x),   ;                              (4.5.2)

gp(x) ³ gp*(x),  ;                           (4.5.3)

                                    (4.5.4)

Здесь

    (4.5.5)

f(x), gp(x) - произвольные функции дискретного аргумента. Будем называть решение (вариант) x Î X допустимым, если оно удовлетворяет (4.5.2),(4.5.3).

Основой метода ПАВ для задачи (4.5.1) - (4.5.5) является процедура W последовательного отсева значений переменных Î . Эта процедура состоит из двух процедур W1 и W2. Процедура W1, в свою очередь, состоит из Q элементарных процедур , , каждая из которых заключается в отсеве по p-му ограничению элементов ( - kj-тое значение переменной ), которые удовлетворяют неравенству

    (4.5.6)

где

         (4.5.7)

если , и

  (4.5.8)

где

 если .  (4.5.9)

Другими словами, вариант , который описывается соотношениями (4.5.7),(4.5.9), обеспечивает оптимум функции gp(x) по всем переменным, кроме , при фиксированном элементе  для множества .

Обозначим множество элементов = , которые остались после применения процедуры , через . Тогда, применив процедуру W1, получим сокращенное множество вариантов :

Очевидно, . Дале к множеству  снова применим процедуру W1 и получим и т.д. Ясно, что при последовательном применении процедуры W1 получим цепочку из вложенных множеств

X = É É ... É Ê .

Пусть при некотором l  = . Тогда - множество элементов, которые остались в множестве X после применения процедуры W1.

Итак, мы доказали такое утверждение.

Лемма. Условие = является условием окончания применения процедуры W1.

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

        Пусть ,

где

является множеством точек оптимума функций  для любого r, r - номер итерации.

Нетрудно увидеть, что условие = эквивалентно условию . Таким образом, если при двух последовательных применениях процедуры W1 множество оптимальных точек функций  для любого  не изменяется, то применение процедуры заканчивается.

Справедливое такое утверждение: число применений процедуры W1 к задаче (4.5.1) - (4.5.4) конечное. Его справедливость вытекает из конечности множества допустимых решений.

Сформулируем критерий отсева в виде теоремы.

Теорема 4.4. Элемент  (то есть отсеянный по процедуре W1) не может входить в допустимый вариант задачи L(D( .

Доказательство этой теоремы несложное и приводится в [33]. Из теоремы 4.4 вытекает, что множество допустимых решений в результате использования процедуры W1 не изменяется, то есть D( = D(. Итак, вследствие применения W1 к задаче L(D(X)) возможные три случая:

1) = Æ, это означает, что задача недопустимая;

2) ¹ Æ и множество  довольно малое, то есть применение процедуры W1 привело к значительному сокращению множества допустимых вариантов . В этом случае дальше решаем задачу на множестве  прямым перебором;

3) ¹Æ, а множество  довольно большое, что не дает возможности решить дальше задачу простым перебором. В этом случае к задаче L(D( )) применяем процедуру W2, которая состоит в замене исходной задачи последовательностью задач L(k)=L(k)(D( )), k=1,2, ..., которые имеют вид

минимизировать                                                                  (4.5.10)

при ограничении                             ,

где множество допустимых значений  определяется из соотношений:

                                   (4.5.11)

                                  (4.5.12)

Рассмотрим первую задачу . Положим

                (4.5.13)

К полученной таким образом задаче Λ(1) применим процедуру W1, которая состоит в отсеве элементов Î по ограничению f(x) £ f1*. Это ограничение аналогично (4.5.2), но для функций с правой частью, которая равняется f1*. Множество элементов, которые были отсеяны, обозначим через , а множество элементов, которые остались после отсева - через .

Далее, к множеству элементов  применим процедуру отсева W1 по ограничениям (4.5.2),(4.5.3). Полученное множество обозначим . Здесь возможные два случая.

Случай 1. Полученное множество  пустое. В этом случае среди элементов множества  нет допустимых вариантов, то есть исключается из рассмотрения. Кроме того, можно сделать вывод, что если существуют допустимые варианты  задачи (4.5.1) -(4.5.4), то для них . В самом деле, если для варианта

 , а , и ,

то применение процедуры W1 не может привести к его отсеву.

Сформулируем это утверждение в виде теоремы [33].

Теорема 4.5. Если  = Ø и , то .

Случай 2. Множество  - не пустое. В этом случае оно исследуется на существование в нем оптимального варианта.

Соответствующие признаки оптимальности можно сформулировать в виде следующих теорем.

Теорема 4.6. Критерий оптимальности I. Если

                             (4.5.14)

и                  ,  то , где .

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

Д о к а з а т е л ь с т в о. Пусть некоторое решение . Тогда по доказанному  выше , и поскольку

,

то  для любого  то есть в этом случае .

Если хотя бы один элемент , например , то есть , то , в соответствии с правилом отсева по ограничению (4.5.11), в то время как  поскольку по условиям теоремы 4.6.  Итак, и в этом случае x1 = x0.

Теорема 4.7. Критерий оптимальности II. Если

                        (4.5.15)

                         (4.5.16)

где  - множество элементов, которые остались после отсева по ограничению f (x) £ f (x/), то

 .                            (4.5.17)

Доказательство этой теоремы аналогично доказательству теоремы 4.6. Объясним содержание теоремы 4.7. Условие (4.5.15) означает, что для допустимого по ограничениям варианта x1  f(x1) > f1 * (поскольку ), и потому критерий оптимальности I для него не применим. Введенное множество  образованно из  добавлением элементов x, которые невозможно отсеять по ограничениям f(x) £ f(x1), но которые отсеиваются по ограничениям f(x) £ f1* (f1* < f(x1)), так как к ограничениям (4.5.2),(4.5.3) прибавляется ограничение f(x) £ f(x1).

Д о к а з а т е л ь с т в о. Поскольку D( ) = D( ), то есть множество допустимых вариантов не изменяется при применении процедуры W1, то

 .                   (4.5.18)

Докажем вторую часть теоремы 4.7. Условие (4.5.16) означает, что  - оптимальное решение на множестве элементов , которые не отсеялись по ограничению f(x) £ f(x/), где x/ - некоторое допустимое решение. Пусть xopt - оптимальное решение задачи . Предположим, что . Тогда f(xopt) ≥ f(x/). Это противоречит условию, что- оптимальное решение . Итак,

 .          (4.5.19)

Сравнивая условия (4.5.18) и (4.5.19) с (4.5.17), убеждаемся, что они совпадают. Итак, теорема 4.7 доказана.

Критерий оптимальности II означает, что если множество решений задачи :  f(x) £ f1* окажется пустым и известно некоторое допустимое решение , то целесообразно следующий отсев выполнить по условиям

f(x) £ f(x');   f(x) > f1*.

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

Процесс сужения поиска осуществляется таким образом. Если множество , которое получено в результате решения задачи L, довольно большое, то рассматривается новая задача со значением

 .

Процесс сужения множества  выполняется до тех пор, пока не будет получено =Ø. Если с самого начала получено =Ø, то осуществляется процесс расширения множества введением ограничения . При этом рассматривается следующая задача L(2):

найти

                          (4.5.20)

где  определяется ограничениями

f(x) > f1*;                                     (4.5.21)

f(x) £ f2*;                                     (4.5.22)

а также ограничениями (4.5.2),(4.5.3). Ограничение (4.5.2) можно использовать в двух направлениях: во-первых, для проверки допустимости отсева вида (4.5.6), (4.5.8) с целью отбрасывания элементов , которые наверно не удовлетворяют ограничению (4.5.2), а во-вторых, в случае получения приближенного решения задачи.

Если после сужения надо провести расширение множества вариантов, или наоборот после расширения - снова проводить сужение, то

 = ( + ),  s ≥ 2.

Здесь имеется в виду то, что одна из задач  или недопустима, тогда как вторая - наоборот допустима.

Изложенный метод решения задачи дискретного программирования (4.5.1),(4.5.2) может быть практически применен, если удастся реализовать эффективную процедуру проверки условий отсева (4.5.6), (4.5.8).

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

Однако для конкретных классов задач можно воспользоваться тем условием, что надо отыскать безусловный экстремум. Для этого желательно, чтобы, во-первых, функции f(x), gp(x) были такими, что для каждой переменной  величины  не зависели бы от значения этой переменной и, кроме того, чтобы оптимум функций f(x), gp(x),  определялся независимо для каждой переменной. Это будет в случае сепарабельных функций.

Дополнительные упрощения можно сделать в случае, если f(x)  является монотонной, не возрастающей функцией, а все gp(x) - монотонно неубывающие для любой переменной . Тогда нахождение безусловного оптимального варианта для любой из функций f(x) требует не более, чем  вычислений этой функции, не более чем  сравнений, а проверки условий отсева (4.5.6),(4.5.8) тоже сводятся не большее чем к  операциям.

В случае, если при сделанных выше предположениях функции gp(x),  являются выпуклыми кверху (то есть вогнутыми), а f(x) - выпуклой вниз, при больших значениях  можно построить эффективную процедуру проверки ограничений (4.5.6), (4.5.8), воспользовавшись известным неравенством для вогнутых функций

f(x¢) - f(x¢¢) £ f ¢(x¢¢)(x¢-x¢¢);   x¢,x¢¢ÎX.

Для выпуклых функций знак неравенства будет противоположный. Поскольку в (4.5.6) и (4.5.8) все переменные, кроме одной, зафиксированной, то будем рассматривать gp(x) как функцию одной переменной. Из последнего неравенства получим

 .

где , x* - неотсеиваемое по (4.5.8) значение x, g′p(x p) - производная функции gp в точке ; а также

 ,

где

 .

Понятно, что все значения x, для которых  и , отсеиваться не будут и проверять условия отсева (4.5.6),(4.5.8) для этих значений не надо.

Если для следующего за x* значения x  или , то значение x* уточняем так:

 находим из неравенства

или

и т.д., откуда получаем такое значение , что для следующего за ним значения x  или .

Алгоритм решения задачи дискретного сепарабельного программирования

Рассмотрим задачу дискретного программирования с так называемыми сепарабельными (аддитивными) функциями критериев и ограничений:

максимизировать                            (4.5.23)

при таких ограничениях:

 ,   ,              (4.5.24)

 ,  ,             (4.5.25)

где  - произвольные функции дискретного аргумента, которые заданные  таблично;  - заданные числа. Обозначим

      (4.5.26)

              (4.5.27)

На основании результатов предыдущего раздела сформулируем условия отсева по ограничениям (4.5.24), (4.5.25) для задачи (4.5.23) - (4.5.25) таким образом [9].

Пусть ΠCj,  , тогда если

                (4.5.28)

или

                          (4.5.29)

хотя бы для одного p = q+1,.,Q, то элемент  не может входить в допустимое решение задачи (4.5.23) - (4.5.25). Заметим, что в рассматриваемом случае, поскольку функции gp (x) - сепарабельны, то нахождение оптимального решения проводится независимо для каждой отдельной переменной и нуждается в  операциях сравнения.

Перейдем к описанию алгоритма отсева элементов возможных вариантов задачи (4.5.23) - (4.5.25).

Построим таблицу C, j -ой строкой которой являются элементы множества Cj:

 .

Укажем, что число элементов в j-ой строке равняется kj , причем в общем случае k1 ¹ k2 ¹...¹kn.

Излагаем процедуру отсева W по ограничениям вида gp(x)<g*p.

П е р в ы й  ш а г. Построим таблицу X(0), которая образована из таблицы X упорядочением ее элементов j-ой строки ( ) по возрастанию значений функции g1(xj), тогда элемент xjl ,будет расположен по левую сторону от xjk, если g1(xjl)< g1(xjk).

В т о р о й  ш а г. Проверим выполнение условия

 ,                               (4.5.30)

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

Т р е т и й  ш а г. Вычисляем значения функции  на всех элементах первого столбца, кроме элемента x11, то есть в соответствии с (4.5.27) вычисляем  и проверяем, выполняется ли неравенство

                      (4.5.31)

последовательно для каждого элемента , l1 = 2, 3, . . . , k1. Если , то порядок чередования элементов , произвольный и из всех этих элементов в таблицу X(0) можно включить лишь один.

Если kj имеет большое значение, целесообразно применять другие правила проверки условия (4.5.31). Например, делается проверка , а потом выбор следующих точек выполняется методом дихотомии или Фибоначчи (см. гл.5).

Первый элемент в строке, для которой неравенство (4.5.31) выполняется, и все следующие элементы отбрасываются в соответствии с правилом отсева.

Процесс третьего шага повторяем для всех строк таблицы X(0). Для j-й строки условие отсева (4.5.31) принимает вид

 .

В результате получаем сокращенную таблицу C1(0).

Далее переходим к первому шагу следующей итерации и применяем процедуру W1 к таблице C1(0) относительно ограничения , в результате получим таблицу C2(0).

Затем, используя третье ограничение , получим сокращенную таблицу C3(0) и так далее, пока не получим сокращенную таблицу Cq(0). На этом первый этап применения процедуры W1 заканчивается.

Следующий этап состоит в применении процедуры W1 к ограничениям вида

 ,   .

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

В т о р  о й  ш а г. Проверим выполнение условия

                             (4.5.32)

где  - первый столбец таблицы . Если оно не выполняется, то задача не имеет решения (по тем же причинам, что и в процедуре W1 на втором шаге первого этапа).

Т р е т и й  ш а г. Проверим выполнение условия

                      (4.5.33)

Если условие (4.5.33) выполняется, то перейдем к первому шагу и рассмотрим следующее ограничение: . Если условие (4.5.33) не выполняется, то переходим к следующему шагу.

Ч е т в е р т ы й  ш а г. Проверяем выполнение условия

           (4.5.34)

последовательно для всех элементов первой строки таблицы .

Первый элемент в строке 1, для кого неравенство (4.5.34) выполняется, и все дальнейшие элементы отбрасываются.

Пара шагов третий-четвертый выполняется для всех строк таблицы . Получаем сокращенную таблицу .

Далее процедура W1 последовательно применяется ко всем ограничениям , , при этом отсев проводится на основе соотношения (4.5.34).

В результате получим сокращенную таблицу CQ(0) = C(1), к которой снова применим процедуру W1 в соответствии с вышеизложенным. Этот процесс повторяем до тех пор, пока в конце концов не начнет выполняться условие C(k) = C(k+1) º , где верхний индекс  указывает на число применений процедуры итераций W1 к начальной таблице C(0).

В соответствии с вышедоказанным, число применений процедуры W1 конечное и в результате ее применения ни одно из допустимых решений начальной (исходной) задачи не будет отсеяно. Если D( = Æ, то исходная задача неразрешима.

В случае, если множество  довольно мало, находим оптимальное решение прямым перебором. В противном случае к таблице возможных решений  применим процедуру W2.

Рассмотрим процедуру W2.

П е р в ы й  ш а г. Приведем в порядок элементы в строках таблицы  по уменьшению функции .

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

 ,

применяя процедуру W1, но уже к функции f, и запоминая отсеянные элементы. Здесь fmax - значение функции f на элементах первого столбца таблицы , упорядоченной на первом шаге; fmin - значение f  на элементах, которые занимают крайние правые позиции в своих строках.

Т р е т и й  ш а г. Сокращенную таблицу , полученную на втором шаге, обозначим  и к ней применим процедуру W1. Если на некотором шаге ее применения не выполняются условия (4.5.30) второго шага процедуры W1 для  pÎ{1,2, ., Q}, то снова переходим на второй шаг, где выполняем отсев по распространенному ограничению:

 .

Этот процесс повторяем до тех пор, пока на k-м шаге не получим таблицу  (эта таблица получается из таблицы  вследствие применения процедуры W1).

В этом случае к ограничениям (4.5.24), (4.5.25) добавляем ограничение

                                    (4.5.35)

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

и т.д. В конце концов на s-м возвращении на второй шаг имеем . Этот процесс повторяем до тех пор, пока не получим таблицу .

Тогда к ограничениям (4.5.28) добавим ограничение  и перейдем на следующий шаг.

Ч е т в е р т ы й  ш а г. Итак, пусть на третьем шаге мы получили таблицу , а также таблицу , для которой .

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

В случае отсутствия допустимых решений в таблице  отмечаем ее элементы, а вместо нее исследуем таблицу  предыдущего шага на существование в ней допустимых решений.

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

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

Тогда поделив отрезок  пополам и выполнив отсев по ограничению

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

П  я т ы й  ш а г. На этом шаге анализируем полученное на предыдущих шагах допустимое решение задачи x¢ Î D( ). Если , то x¢ - оптимальный решение исходной задачи, в соответствии с критерием оптимальности II. Если же , то к ограничениям (4.5.24), (4.5.25), (4.5.35) прибавляется еще и ограничение f (x) ³ f (x¢). Затем переходим на четвертый шаг. Если же величина e = - f (x¢) довольно малая, то решение x¢ можно взять за приближенное к оптимальному.

Укажем некоторые важные свойства изложенного алгоритма.

1. Алгоритм ПАВ по сути является аддитивным, так как в нем используются лишь операции сложения и вычитания.

2. Начальные таблицы в процессе работы алгоритма не вычисляются, а лишь некоторые их элементы вычеркиваются (те, которые отсеяны).

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

4. Возрастание числа ограничений повышает эффективность алгоритма вследствие усиления отсева бесперспективных элементов.

5. На каждом шаге работы алгоритма отсеиваются явным образом неэффективные по соответствующей системе ограничений варианты. Вариант x¢ не может быть улучшен по системе ограничений

 ,

если не существует такого варианта x2, что

и хотя бы для одного p′ соответствующее неравенство строгое.

Алгоритм решения задачи линейного целочисленного программирования

В качестве примера частного случая задачи дискретного программирования (4.5.23) - (4.5.25) рассмотрим задачу ЛЦП:

максимизировать                       (4.5.36)

при ограничениях

 , ;                           (4.5.37)

                      (4.5.38)

где

 - целые числа, .              (4.5.39)

Заменим условия (4.5.38), (4.5.39) такими:

 .

Нетрудно заметить, что k-тая компонента вектора xi =  будет равняться , если > 0, или  - в противном случае.

Тогда правило отсева для ограничений формулируем таким образом: если  удовлетворяет неравенству

                  (4.5.40)

хотя бы для одного i = 1, ., Q, то j-тая компонента решения задачи (4.5.36)-(4.5.39) не может приобретать значение, которое равняется .

Таким образом, в процессе работы алгоритма будут отсеянные такие значения : , если > 0 или , если < 0. В результате множество  для данной задачи будет иметь вид

где                                           .

Правило отсева по целевой функции для задачи  имеет такой вид:

если

 ,                   (4.5.41)

где

то j-тая компонента допустимого решения задачи L1 не может приобретать значения . То есть, если cj > 0, то значения  такие, что  отсеиваются по ограничению на целевую функцию, а в противном случае отсеиваются значения  из интервала .

В процессе работы алгоритма для задачи L(s), s = 2, 3, . величины  вычисляются по таким формулам:

а)         (4.5.42)

если надо расширить множество ;

б)         (4.5.43)

для сужения множества ;

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

Для применения алгоритма необходимо задать ограничение вида (4.5.38). На практике эти границы  можно во многих случаях определить из физического содержания задачи. Если же границы изменения каждой переменной заранее не определены, то их всегда можно найти, решив 2m задач ЛП вида

                                              

;                             ;

                                      .

В некоторых случаях определение  особенно простое:

1) если для всех  и   aij ³ 0, то

 ,

где знак [x] означает целую часть x;

2) если среди ограничений (4.5.37) обнаружится хотя бы одно, например k-тое, для которого > 0 для всех , то

 .

Пример 4.6. Для иллюстрации работы метода ПАВ рассмотрим такую задачу:

 максимизировать

при ограничениях

£ 28,

£ 14,

≥ 10,

 £ 12,

   ³ 0;

 - целые числа.

Предварительный этап. Найдем начальные множества , .

 = = 4; = = 7.

Таким образом, = {0, 1, 2, 3, 4}; = {0, 1, 2, 3, 4, 5, 6, 7}.

Первая итерация. Процедура W1. Отсев по первому ограничению:

 > = 28, > 4 - нет отсева;

 > = 28, > 7 - нет отсева.

Второе ограничение:

 > = 14, < -14 - нет отсева;

 > = 18, > 9 - нет отсева.

Третье ограничение:

 < , < 0 - нет отсева;

 < , < 0 - нет отсева.

Четвертое ограничение:

 > = 33, >  - нет отсева;

 > = 12, < -4 - нет отсева.

Поэтому переходим к процедуре W2.

Процедура W2:

 = ( + ) = (0 + 15) = .

Правило отсева такое: f (x) = <  = .

Итак, <  - = -7 = ; <  - отсеивается = 0;

 <  - = -8 = - ; < 0 -нет отсева.

Процедура W1.

Отсев по первому ограничению:

 > = 28, > 4 - нет отсева;

 > = 28-7   = 21, >  - отсеивается = 6,7.

По второму ограничению отсева нет.

Третье ограничение:

 < ; < 0 - нет отсева;

 < ; < 0 - нет отсева.

Четвертое ограничение:

 > = 12 + 15 = 27, >  - нет отсева;

 > = 8, < 0 - нет отсева.

Вторая итерация. Поскольку отсев по процедуре W1 состоялся, то перейдем снова к процедуре W2.

 <  - = -5 = ; <  - отсеивается = 1;

 <  - = -8 = - ; < 0 - нет отсева.

Процедура W1:

 > = 28, > 4 - нет отсева;

 > = 14, >  - отсеивается = 4,5.

Снова повторяем процедуру W2 при одном и том же значении .

Процедура W2:

 <  - = -3 = ; <  - отсеивается = 2;

 <  - = -8 = - ; < 0 - нет отсева.

Процедура W1:

 > = 28, > 4 - нет отсева;

 > = 7, >  - отсеивается = 2,3.

Итак, имеем такие сокращенные подмножества:

 (2) = {3, 4}, (2) = {0, 1}.

Теперь можно найти xopt  непосредственным перебором:

 = [3; 0]; f ( ) = 6; = [3; 1]; f ( ) = 7; = [4; 0] и = [4; 1] не удовлетворяют первое или четвертое ограничения.

Поскольку f ( ) > f ( ), то оптимальный решение

 = [3; 1]; fmax = f ( ) = 7.

Алгоритм последовательного анализа вариантов
  для задачи с булевыми переменными

Рассмотрим задачу булевого программирования, которая является частным случаем задачи (4.5.36) - (4.5.39):

максимизировать  f (x) =                    (4.5.44)

при ограничениях

                           (4.5.45)

и условиях

 .                              (4.5.46)

Раньше был рассмотрен аддитивный алгоритм Балаша для этой задачи. Рассмотрим теперь применение метода последовательного анализа вариантов.

Метод ПАВ базируется на таком критерии отсева вариантов по ограничениям (процедура W1) [9]:

если

 ,              (4.5.47)

хотя бы для одного i = 1, ., Q, то j-тая компонента допустимого решения задачи (4.5.44) - (4.5.46) не может иметь значение , которое равняется .

Условие отсева для задачи  имеет такой вид:

 , . (4.5.48)

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

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

В целом же в идейном плане метод ПАВ для задачи (4.5.44) - (4.5.46) близкий к аддитивному алгоритму, так как оба они базируются на анализе системы ограничений задачи. Однако сам анализ выполняется разными путями. Правило отсева по целевой функции для задачи имеет вид: если , то j-тая компонента допустимого решения задачи  не может приобретать значения

 ,

где

 .                    (4.5.49)

Для задачи  величина  вычисляется по аналогичными к (4.5.41) формулам. Будем говорить, что: , если  = 0; , если = 1; , если . Тогда

а)          (4.5.50)

для расширения множества ;

б)          (4.5.51)

для сужения множества ;

в)                                                                  (4.5.52)

для сужения множества  после его расширения, и наоборот.

Пример 4.7. Решить методом ПАВ такую задачу булевого программирования:

минимизировать

при ограничениях:

≥ 7,

≥ 5,

= {0,1}.

Первая итерация. Процедура W1. Первое ограничение

а) < 7 - = 7-3-5   - 3 = -4,  < -2 - нет отсева;

б) - < 7 - = -6, > 6 - нет отсева;

в) < 7-2-5    - 3 = -3  < -1 - нет отсева;

г) < 7-2-3    - 3 = -1  < - - нет отсева;

д) < 7-2-3    - 5 = -3  < -1 - нет отсева.

Аналогично проверяем, что и по второму ограничению отсев не происходит. Например:

x1< 5 - = 5-1-3- 2-4  = -5,  < -5 - нет отсева.

Процедура W2.

 =  = (0 + 15) =  = 7.5.

а) > - = 7.5 - 0; > 7.5 - нет отсева;

б) = > - 0 = 7.5 - нет отсева;

в) > - 0 = 7.5 - нет отсева;

г) > - 0 = 7.5 - нет отсева;

д) > - 0 = 7.5 - нет отсева.

Поэтому переходим снова к процедуре W2, и сужаем множество вариантов:

 =  =  = 3.75.

а) > = 3.75; >  - отсев = 1;

б) > 3.75 - 0 = 3.75 - отсева нет;

в) > 3.75 - отсева нет;

г) > 3.75 - 0 = 3.75; >  > 1 - отсева нет;

д) > 3.75; >  - отсев = 1.

Процедура W1. Первое ограничение

а) < 7 - = 7-3-5   = -1 - нет отсева;

б) - < 7-3-5   = -1, > 1 - нет отсева;

в) < 7-5   = 2; <  - отсев = 0;

г) < 7-3   = 4  <  - отсев x4 = 0;

д) < 7-3-5     = -1 - нет отсева.

Второе ограничение

а) < 5-1-3 - 2 = -1 - нет отсева;

б) < 5-3-2 = 0 - нет отсева;

в) < 5-1-2 = 2; <  - нет отсева;

г) < 5-1-3 = 1; <  - нет отсева;

д) < 5-1-3 - 2 = -1 - нет отсева;

Итак, осталось лишь два варианта:

 = {0,0,1,1,0} и = {0,1,1,1,0}.

Проверим каждый из них. Оба решения удовлетворяют всем ограничениям, но поскольку f ( ) = 3 < f ( ) = 6, то оптимальное решение = {0,0,1,1,0}.

<< prev | ^up^ | next >>

  
     
  Copyright © 2002-2004