Задача о ранце.

Турист готовится к длительному переходу. Он может нести груз весом b, который может включать n типов предметов. Каждый отдельный предмет типа j весит a [j] (j=1,n), а полезность его использования в переходе оценивается числом c [j]. Необходимо определить, сколько предметов каждого типа турист должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной. Формальная запись задачи имеет следующий вид:

,. (3.3)

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

Метод лексикографического неявного перебора (МЛНП)

Этот метод основан на процедуре перебора отдельных точек области возможных решений, аналогичной упорядочению слов в словаре и называемой поэтому лексикографической. Все переменные исходной задачи упорядочиваются по быстроте изменения. Если никаких дополнительных соображений при этом не использовать, то этот порядок будет соответствовать естественному порядку нумерации переменных исходной формализованной записи оптимизационной задачи: самой медленноменяющейся переменной будет x [1], а самой быстроменяющейся - x [n]. B процессе перебора каждая переменная принимает последовательно целочисленные значения, начиная с (как правило, ) и кончая . Но прежде чем увеличить значение переменной x [j] на единицу, необходимо перебрать все возможные комбинации переменных x [j+1],.,x [n]. Для этого каждая из них должна пробежать все свои значения от наименьшего до наибольшего возможного. Рассмотрим эту процедуру на примере. Пусть n= 3, а переменные x [j] могут принимать последовательно следующие значения:

x [1] =A, B; x [2] =1, 2; x [3] =, , .

Тогда при естественном упорядочении переменных по быстроте изменения последовательность рассматриваемых точек будет следующей:

1) A 1 ,4) A 2 ,7) B 1 ,10) B 2 ,

2) A 1 ,5) A 2 ,8) B 1 ,11) B 2 ,

3) A 1 ,6) A 2 ,9) B 1 ,12) B 2 .

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

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

. (3.30)

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

. (3.31)

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

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

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

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

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

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

Алгоритм МЛНП

Шаг 1. Выбор очередной рассматриваемой точки х в соответствии с лексикографическим порядком и с учетом упорядочения компонент x [j] по быстроте изменения.

Шаг 2. Если фильтрующее ограничение сформировано, то - проверка выполнения его в точке х: если оно не выполняется, то - переход на шаг 7.

Шаг 3. Проверка выполнения в точке х очередного ограничения оптимизационной задачи (в порядке их ранжирования по степени активности): если оно не выполняется, то - переход на шаг 7.

Шаг 4. Если рассмотрены не все ограничения, то - на шаг 3.

Шаг 5. Вычисление целевой функции в очередной найденной допустимой точке: z (x).

Шаг 6. Если фильтрующее ограничение еще не введено, то ввести его с правой частью =z (x), зафиксировать =x. Если фильтрующее ограничение уже сформировано и выполняется условие z (x) <, то переопределить его правую часть (=z (x)) и зафиксировать =x.

Шаг 7. Если еще не все точки рассмотрены, то - на шаг 1.

Шаг 8. Если (,) определено, то это - оптимальное решение, иначе D=.

5. Определение данных