Дискретно-непрерывная математика (стр. 45 )

Выбор функции-критерия является важным звеном в формализации задачи. Вид (способ вычисления значений) функции-критерия должен соответствовать требованиям, предъявляемым к варианту, который может быть признанный «наилучшим». Различные функции-критерии считаются эквивалентными, если приводят к одному и тому же решение (в этом случае говорят также, что задачи — постановки — эквивалентны) .

То, что выбор функции-критерия - далеко не очевидная вещь - показывает следующая задача.

4. Задача о назначениях, или как рассадить группу за столами. Эта задача больше известная как задача о женихах и невестах. На некотором одиноком острове живут п женихов и п невест. Вопрос заключается в том, как лучшим образом всех их переженить. Решение становится невозможным, если принять во внимание, которое

«Оля любит Сашу,

И Зоя любит Сашу,

А Саша любит Лилю,

Лиля же любит Андрея,

Но Андрей никого не любит,

Но зато вот Сергей

По-прежнему любит Олю...».

Отношения между «женихами и невестами», соответствующие приведенному утверждению, схематично отображены на графе рис. 5.17.

Рис. 5.17. Граф взаимоотношений в одном коллективе, стрелка соответствует отношению «любит» (тот, от кого стрелка направлена, того, на кого направлена).

Жители острова уважают чувство молодых людей, но и проявляют заботу об интересах острова в целом. Противоречивый узел отношений молодых людей ими разрубается следующим образом. Считается, что не исключена возможность заключення любого брака, но одни браки предпочтительнее других. Эта предпочтительность выражена численно: для брака между i-м женихом и k-й невестой она получает значение аik. Это означает, что в общую суммарную «пользу» (для островного государства) каждая свадьба вносит свое слагаемое, равное аik. В общей постановке задачи о назначении требуется п претендентов назначить на п должностей — на каждую должность по одному. Общая польза рассматривается как выгода, суммируемая по всем назначениям, а выгода от назначения i-го претендента на k-ю должность оценивается в аik, независимо от других назначений. Как уже говорилось, всякая перестановка σn представляет возможное решение задачи о назначениях. Требуется найти такую перестановку σn , которая максимизирует F(σn):

(5.51)

Определять выгоду аik от назначения i-гo претендента на k-ю должность принято с помощью так называемых экспертных оценок, для чего собирают некоторый представительный консилиум специалистов-экспертов, и они выставляют свои оценки — например, в шестибальной системе — выгодности каждого возможного назначения (аналогично тому, как выставляют оценки за выполнение программы в фигурном катании на коньках). Крайние оценки (наименьшая и наибольшая), как правило, отбрасываются, оставшиеся усередняються (суммируются и делятся на их число), эта усредненная оценка и принимается за значение аik. Повторяем, такая оценка должна быть заранее поставлена любому возможному назначению - любой паре (i, k). Явная нежелательность какого-то назначения фиксируется в наиболее низкой оценке для этого назначения.

5.15. Метод перебора и схема конструирования вариантов

1. Метод перебора. Объект, на котором функция-критерий принимает экстремальное — минимальное или максимальное значения, — называют экстремальным элементом или оптимальным решением. Множество элементов (объектов), среди которых ищется экстремальный, называют множеством возможных решений, допустимых вариантов. Если это множество конечно, т. е. состоит из конечного числа вариантов и этих вариантов относительно немного, то можно последовательно рассмотреть все возможные решения, на каждом допустимом варианте вычислить значение функции-критерия и, сравнивая эти значения, выбрать оптимальное решение. Собственно, в этом состоит метод перебора (в современной математической терминологии - «метод проб и ошибок»), применимый, повторяем, в случае конечного множества допустимых решений и притом сравнительно немногочисленного, чтобы можно было провести все вычисления и сравнение в приемлемое время (или, как еще говорят, в реальном масштабе времени). Табл. 5.3 демонстрирует применение метода перебора в решении задачи, которая задана упражнением 5 (см. «Типовые тестовые задачи» данного микромодуля).

Таблица 5.3

Здесь нетрудно выписать все возможные решения (первый столбец табл. 5.3), потом вычислить значения функции-критерия для каждого варианта по формуле 5.51 (второй столбец табл. 5.3), указать (после просмотра этого столбца) наилучшее значение (2, 3, 1).

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

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

Пример. Рассмотрим задачу определения экстремума функции

F(x) = 3х4 + 4х3—12х2, заданной на отрезке [—2, 2]. Экстремум такой функции достигается или в крайних точках отрезка, или внутри отрезка в точках, где производная функции обращается в нуль. Таким образом, вместо бесконечного множества точек отрезка [-2, 2] экстремум функции следует искать среди значений f(x) для точек —2, 0, 1, 2, (—2, 0, 1 — корни уравнения f '(х) = 0, производная же нашей функции есть f '(х) =12х3+12х2 — 24 х = 12х(х2 + х — 2)). Максимум f(x) достигается, как это нетрудно проверить теперь методом перебора, в точке х = 2, f(x) = 32, минимум достигается в точке х = —2, f(x) = —32.

Вообще говоря, установив некоторые свойства оптимального варианта, можно значительно сузить множество допустимых решений, вплоть до получения конечного множества, где часто оказывается возможным применить метод перебора. Неоценимое значение метода перебора заключается в том, что он принципиально всегда «под рукой». Для конечных множеств допустимых решений это означает, следовательно, что существует конечный алгоритм решения задачи, т. е. задача будет разрешима за конечное время. Плохо то, что для метода перебора это «конечное» время оказывается неприемлемо большим уже даже в простых случаях. Так представим себе, что в задаче поиску экстремальной перестановки, в случае всего 10 элементов, на построение одной перестановки и вычисление значения функции-критерия мы затрачиваем один минуту. Тогда нетрудно подсчитать: при восьмичасовом рабочему дне методом перебора такую задачу пришлось бы решать... больше двух лет. В случае же 20 элементов даже с помощью ЭВМ такая задача методом перебора решалась бы дестилетиями! Значит, чтобы построить метод точного решения такого рода задач, надо изобрести что-то лучшее, чем примитивный перебор всех возможных вариантов.

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

2. Алгоритмы построения п-перестановок. Однако, чтобы «улучшать» метод перебора, нужно, прежде всего, уметь им пользоваться - для задач поиску экстремальных перестановок это означает уметь строить все возможные п-перестановки, иначе говоря, надо знать алгоритм построения всех п-перестановок.

Нетрудно после некоторых попыток «нащупать» элементарный регулярный прием получения последовательности всех п-перестановок (чем мы уже неявно воспользовались при формировании табл. 5.3 из предыдущего пункта), начиная с начального упорядочения чисел 1, 2, .., п по возрастанию (пусть п = 5):

1, 2, 3, 4, 5

1, 2, 3, 5, 4

1, 2, 4, 3, 5

1, 2, 4, 5, 3

1, 2, 5, 3, 4

1, 2, 5, 4, 3

1, 3, 2, 4, 5

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

Рассмотрим некоторую перестановку σп. Найдем первую с конца перестановки упорядоченную пару. Так в перестановке σп=(1,3, 5, 4, 2) первая с конца упорядоченная пара есть пара (3, 5). Первое число такой пары назовем обрывающим. Перестановочный хвост в σп образует последовательность чисел, начиная с обрывающего.

Реупорядочить перестановочний хвост означает:

1) заменить обрыивающее число на наименьшее из перестановочного хвоста число, которое превосходит обрывающее;

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

Так в нашей перестановке σп = (1, 3, 5, 4, 2) обрывающее число есть 3, перестановочный хвост есть последовательность (3, 5, 4, 2).

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

Введение понятий «обрывающего числа», «перестановочного хвоста», «реупорядочения» позволяет упростить описание алгоритма построения всех п-перестановок. Этот алгоритм — назовем его Алгоритмом-1 - представлен блок-схемой на рис. 5.18.