Многокритериальная задача

1.Введение

2.Тип задачи

3. Алгоритм решения

4.Многокритериальная задача

5.Роль ЛПР

1. введение

В 1859 г. Сэр Вильям Гамильтон, знаменитый математик, давший миру теорию комплексного числа, предложил детскую головоломку, в которой предлагалось совершить «кругосветное путешествие» по 20 городам, расположенных в различных частях земного шара. Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b, … t. Обязательным условием являлось требование: каждый город за исключением первого можно посетить один раз.

Гамильтонова задача о путешественнике нередко преобразуется в задачу о коммивояжере. Коммивояжер – не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Гамильтонова задача может стать задачей о коммивояжере, если каждое из ребер снабдить числовой характеристикой. Это может быть километраж, время на дорогу, стоимость билета, расход горючего и т.д. Таким образом, условные характеристики дадут числовой ряд, элементы которого могут быть распределены между ребрами как угодно.

2.тип задачи

Рассмотрим задачу о коммивояжере.

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

Очевидно, что задача коммивояжера – это задача отыскания кратчайшего гамильтонова цикла в полном графе.

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

Решить задачу коммивояжера также можно с помощью алгоритма Крускала и «деревянного» алгоритма. Эти методы ускоряют разработку алгоритма по сравнению с методом полного перебора, однако не всегда  дают оптимальное решение.

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

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

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

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

3.алгоритм

Метод ветвей и границ.

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами Xi и Xj нет дуги, то ставится символ «∞».

Алгоритм Литтла для решения задачи коммивояжера можно сформулировать в виде следующих правил:

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

.

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

,

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

3. Суммируем элементы и , получим константу приведения

,

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

.

4. Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

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

.

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

7. Приводим матрицу гамильтоновых контуров . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:

.

8. Находим множество гамильтоновых контуров , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞.

9. Делаем приведение матрицы гамильтоновых контуров . Пусть - константа ее приведения. Нижняя граница множества определится так:

.

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

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

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

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

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

    (1)

Условия (2) – (4) в совокупности обеспечивают, что каждая переменная равна или нулю, или единице. При этом ограничения (2), (3) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (2)), и один раз из него выехав (ограничение (3)).

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

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

, где , и .

Обратный метод Беллмана.

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

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

Пусть i – произвольный город (i  N), а V – любое подмножество городов, не содержащее города 1 и города i. Через М(i, V) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V) обозначим длину кратчайшего пути множества М(i, V). Для решаемой задачи В(i, V) – функция Беллмана. Как очевидно, В(1, {2, 3, …, n}) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.

Если V – одноэлементное множество, V ={j}, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути µ = (i, j, 1). Поэтому

i N, j  {2, 3,…, n}, j ≠ i.(1.1)

Предположим, что значения функции В(i, V) для всех i N \ {1} и всех возможных k-элементных (k < n – 1) множеств V уже вычислены. Тогда значение В(i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле

(1.2)

Уравнения (1.1)–(1.12) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана. Вычислительная сложность задачи равна ,где С – произвольная константа (С > 0), n – число городов.

Пример. Решить задачу коммивояжера, определяемую матрицей:

Сначала, пользуясь формулой (1.1), определяем значения В(i, {j}):

В(2, {3}) = 5 + 6 = 11; В(3, {2}) = 2 + 2 = 4; В(4, {2}) = 5 + 2 = 7;

В(2, {4}) = 2 + 1 = 3; В(3, {4}) = 1 + 1 = 2; В(4, {3}) = 4 + 6 = 10.

Далее по формуле (1.2) последовательно получаем (в левой части каждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуется указанный в правой части (1.2) минимум):

В(2, {3, 4}) = min [s23 + B(3,{4}); s24 + B(4,{3})] = min(5 + 2; 2 + 10)=7;

В(3, {2, 4}) = min [s32 +B(2,{ 4}); s34 + B(4,{ 2})] = min(2 + 3; 1 + 7 )=5;

В(4, {2, 3}) = min [s42 + B(2,{ 3}); s43 + B(3,{ 2})] = min(5 + 11; 4 +4)=8;

В(1, {2, 3, 4}) = min [s12 + B(2,{3,4}) s13 + B(3,{ 2,4}) s14 + B(4,{2,3 })]=

= min (4 +7; 3 +5; 4 + 8 ) = 8.

Итак, оптимальное значение критерия в рассматриваемом примере равно 8.

Выполненные выделения позволяют определить оптимальный маршрут. Он следующий:

1 ® 3 ® 2 ® 4 ® 1.

4. Бикритериальная задача коммивояжера.

Бикритериальная задача коммивояжера (БКЗК) определяется полным взвешенным ориентированным графом без петель G с множеством вершин   N = {1, 2, …, n}; вес каждой дуги – двумерный вектор (первая координата – вес по первому показателю, вторая координата – вес по второму показателю). Допустимые решения задачи – гамильтоновы циклы графа G. Каждый гамильтонов цикл оценивается двумя критериями – весами по имеющимся показателям (вес цикла по показателю i определяется как сумма весов составляющих данный цикл дуг по этому показателю). Оба критерия считаются минимизируемыми.

Исходную информацию по БКЗК считаем представленной парой (nn)-матриц S = {sij}, и T = {tij}, где sij и tij – веса дуги (i, j) графа G по первому и второму показателям соответственно, i = , j = , i  j; все элементы главных диагоналей матриц S и Т считаются нулевыми. В типовой интерпретации вершины графа G – это города, которые коммивояжеру необходимо обойти по замкнутому маршруту, побывав в каждом городе ровно по одному разу; для определенности считаем, что маршрут коммивояжера начинается и заканчивается в первом городе. Веса дуг sij (по первому показателю) и tij (по второму показателю) трактуются как стоимости и продолжительности соответствующих переходов; требование симметричности на матрицы не налагается, не считается обязательным и выполнение неравенства треугольника.

Рассматриваемую БКЗК обозначим символом Z. Полную совокупность эффективных в Z оценок Е(Z) будем строить методом динамического программирования.

Пусть i – произвольный город (i  N ), а V – любое подмножество городов, не содержащее городов 1 и i. Через М (i, V ) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Каждый путь из М(i, V) оцениваем весами по первому и второму показателям, т.е. стоимостью и временем реализации; оба показателя считаем минимизируемыми критериями. Получаемую бикритериальную задачу будем обозначать Z(i, V ). Множество эффективных в Z(i, V ) оценок обозначим Е(i, V ). Как очевидно, задача Z(1, {2, 3, ..., n}) совпадает с задачей Z; поэтому Е(1, {2, 3, ..., n}) = Е(Z).

Если V – одноэлементное множество, V = {j}, где j  1 и j  i, то совокупность М(i, V ) состоит из единственного пути  =  (i, j, 1). Поэтому

              Е(i, {j}) = (sij + sj1, tij + tj1),    i  N, j Î {2, 3,…, n}, j  i.              (4.65)

Предположим, что множества оценок Е(i, V) для всех i  N и всех возможных k-элементных (k < n – 1) множеств V уже вычислены. Тогда значение В(i, V' ), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле

Е(i, V' ) =

=              (4.66)

Уравнения (4.65)–(4.66) – рекуррентные соотношения динамического программирования для решения бикритериальной задачи коммивояжера. Вычислительная сложность задачи зависит от количества эффективных оценок,  вычисленных на промежуточных этапах решения задачи, которое очень сложно оценить заранее. Введем  некоторую константу k  и положим, что число эффективных оценок на каждом этапе не будет превышать значения этой константы. Тогда вычислительная сложность задачи равна ,где С* = , (С – произвольная константа > 0), n – число городов.