§ 55. Нахождение хорошего решения эвристическим методом

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

В качестве примера мы рассмотрим эвристический метод для задачи о перевозках, предложенный Флетчером и Кларком (Fletcher, Clarke), Management and Mathematics. Business, Publ. Ltd. London, 1964.

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

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

Пусть задача о перевозках задана таблицей

Граф на рис. 351 представляет одно из возможных решений (направления всех стрелок можно изменить на обратные).

Значения для составляющих его контуров:

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

Изложим теперь метод Флетчера и Кларка.

A) Для каждой пары вершин вычислим величины

записывая их в таблицу.

Б) Для решения 5 вычисляем

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

Если вершины принадлежат различным классам то можем объединить их в класс при условии, что

B) Начинаем с тривиального решения

Г) Среди выбираем наибольшее, не выбиравшееся ранее (если таковых несколько, то берем любое из них). Если условия (55.5) и (55.6) выполняются, то объединяем классы, содержащие в один и отмечаем полужирным шрифтом выбранное Если же одно из этих условий не выполняется, то в клетку с этим ставим крестик и ищем новое как указано в начале этого пункта.

Рис. 351.

Д) Выписываем соответствующие

Е) Возвращаемся к Г).

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

Пример 1. По формуле (55.3), исходя из таблицы (55.1), вычисляем и составляем матрицу на рис. 352. Начинаем с

тривиального решения, представленного на рис. 353. В матрице находим

Имеем

Объединяем классы в и выделяем на рис. 352 полужирным шрифтом.

Рис. 352 Матрица —

Рис. 353

Таблица для не меняется. Новое решение даег рис. 354. Затем находим

Клетку (10, 9) помечаем крестиком. Далее

Берем Имеем и

Клетку помечаем крестиком. Затем берем

Имеем

Рис. 354.

Клетку помечаем крестиком. Далее

и

Классы объединяем в (рис. 355). Берем

Имеем

Классы объединяем в Новое решение представлено на рис. 356. Затем берем

Тогда

Клетку помечаем крестиком. Далее

Помечаем крестиком клетку Аналогично поступаем дальше:

Рис. 355

Рис. 356.

Классы объединяются в таблица для меняется: получаем новое решение, представленное на рис. 357.

Далее

Помечаем крестиком клетку

Рис. 357.

Выбрав и пометив крестиком соответствующую клетку, переходим к

Классы объединяем в таблица для меняется: получаем новое решение, представленное на рис. 358.

Имеем

Классы и объединяем в таблица для меняется: получаем новое решение, изображенное на рис. 359.

Имеем

Приходим к уже встретившемуся классу

Имеем поэтому помечаем крестиком клетку

Имеем поэтому помечаем крестиком клетку

Рис. 358.

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

Общая стоимость

Пример 2. Так как больше то в требуется специальная поездка. Результаты вычислений приведены на рис. 360 и 361, а решение — на рис. 362.

Общая стоимость

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

(кликните для просмотра скана)

Согласно изложенному методу имеем (рис. 363—366)

Общая стоимость

Рис. 363

Рис. 364.

Решение на рис. 366 дает

Общая стоимость

Рис. 365.

Рис. 366

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

Рассмотрим «задачу о музыкантах».

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

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

где

При простом переборе нужно вычислить значений Это, очевидно, возможно сделать при не слишком большом

Пример. Рассмотрим матрицу

(см. скан)

Требуется выбрать произведения с наименьшим числом исполнителей. Это достигается, как видно из таблицы (55.51), выбором произведений

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

Воспроизводим на рис. 367 таблицу (55.50), добавив к ней снизу строку, а справа столбец.

Рис. 367.

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

Рис. 368.

Пусть множество решений. Рассмотрим свойство -подмножество содержит произведение Найдем границу снизу для

Располагая числа, набранные курсивом в последнем столбце, в порядке возрастания: 2, 5, 11, 13, 14, заключаем, что граница для есть (см. рис. 373). Выбираем свойство соответствующее минимальному из чисел, набранных курсивом

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

Располагая числа, набранные курсивом в последнем столбце, в порядке 1, 4, 5, 9, заключаем, что граница для есть (см. рис. 373). Найдем границу для

Рис. 369.

Вычитая строку С из всех строк (последний столбец матрицы на рис. 367 не учитывается) и полагая

получаем (рис. 369). (Числа последнего столбца — суммы соответствующих элементов строки.) Так как должны быть исполнены С и еще два произведения, то нужно прибавить к 19, во-первых, 6, а во-вторых, 11 (так как курсивные числа в последнем столбце — это 11, 5, 11, 14).

Рис. 370.

Итак, нижняя граница для есть Теперь нам следует применить свойство Используя в, строим Для этого вычеркиваем строку В в матрице на рис. 369 и, действуя, как раньше, получаем (рис. 370).

Так как должны быть исполнены С и еще два произведения, то нужно прибавить к 19, во-первых, 17, а во-вторых, 3 (так как курсивные числа в последнем столбце — это 1, 3, 10). Итак, нижняя граница для есть Используя строим . Вычитая строку В из всех

строк (последний столбец не учитывается) матрицы на рис. 369 и полагая

получаем (рис. 371). (Числа последнего столбца — суммы соответствующих элементов строки.)

Рис. 371

Так как должны быть исполнены, то к нужно прибавить, во-первых, 1, а во-вторых, 11 (так как курсивные числа в последнем столбце — это 11, 11, 13). Итак, нижняя граница для есть

Рис. 372.

Теперь нам следует применить свойство и, исходя из , построить . Граница для :

Вычитая строку А из всех строк матрицы на рис. 370 (последний столбец не учитывается) и полагая получаем (рис. 372). (Числа последнего столбца — суммы соответствующих элементов строки.) Так как должны быть исполнены и еще одно произведение, то к нужно прибавить, во-первых, 2, а во-вторых, 3, т. е. есть нижняя граница . Далее, применяя строим

Граница для первого

а для второго

Рис. 373.

Следовательно, искомое оптимальное решение есть со значением 40 (рис. 373).