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

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

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

МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

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

1. Структура метода достаточно универсальна и может быть использована для решения широкого класса задач.

2. Метод обладает потенциальными возможностями для существенного сокращения перебора.

3. Внешнее управление параметрами метода позволяет формировать различные приближенные алгоритмы.

Рассмотрим задачу дискретной оптимизации вида

(2.1)

где — некоторое конечное множество из .

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

1) построение дерева допустимых вариантов;

2) составление оценочных задач;

3) определение правила обхода дерева вариантов;

4) отбрасывание «неперспективных» множеств вариантов;

5) проверка на останов.

Рассмотрим подробно каждый из указанных модулей.

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

2. Оценкойфункции задачи (1) на множестве называется такое число , что . Для получения оценок составляется оценочная задача, решение которой используется для вычисления соответствующей оценки. К оценочным задачам предъявляются следующие требования: с одной стороны, их решение не должно занимать много времени. Но вместе с тем оценки, полученные с их помощью, должны быть как можно точнее (т.е. разность ( ) не должна быть слишком большой). Такие требования объясняются тем, что именно оценки используются при отбрасывании неперспективных множеств (при сокращении перебора). При составлении оценочных задач можно воспользоваться универсальным правилом: отбросить в исходной задаче наиболее «тяжелые» (трудновыполнимые) ограничения (например, требование целочисленности). Получаемые оценки должны удовлетворять требованию монотонностив том смысле, что оценки подмножеств не должны быть меньше оценки соответствующего разветвленного множества (то есть если , то должно быть выполнено условие ).

3. Правило обхода дерева вариантов в процессе работы алгоритма называют стратегиейобхода дерева. Существует множество различных стратегий. Наиболее распространенными являются три из них.

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

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

c. Смешанная стратегия. В этом случае для продвижения «вниз по дереву» используется односторонний обход дерева вариантов, а при «подъеме вверх» ищется множество с минимальной оценкой.

4. Будем называть множество неперспективным, если относительно него принимается решение о выбрасывании его из дальнейшего рассмотрения. Отбрасывание множеств в ходе решения обеспечивает сокращение перебора. Исключение множеств вариантов из дальнейшего рассмотрения производится с помощью оценок этих множеств и рекорда. Рекордом (или рекордным значением)называют значение целевой функции в «лучшей» (доставляющей наименьшее значение) из полученных допустимых точек. Для определения начального рекорда рекомендуется воспользоваться каким-либо приближенным алгоритмом или другой априорной информацией, если она имеется. По ходу решения задачи рекорд обновляется. Справедливо следующее утверждение.