Кадура (Математическое моделирование процессов перевозки грузов железнодорожным транспортом на основе использования задачи коммивояжера), страница 2

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

Граф называют реберно-взвешенным (вершинно-взвешенным), если его ребра (вершины) имеют дополнительные характеристики. В задачах коммивояжера ребра взвешены одной характеристикой — длиной.

Последовательность смежных ребер или дуг, соединяющих две вершины x_i и x_j, называют маршрутом (i, j) (неориентированного графа — цепью, а ориентированного — путем). Маршрут открыт, если его концевые вершины различны, и замкнут, если они совпадают. Замкнутый маршрут неориентированного графа называют циклом, ориентированного — контуром, а цикл (контур) — гамильтоновым, если он замкнут и проходит через каждую вершину графа только по одному разу. Граф, содержащий гамильтонов цикл (контур), называется гамильтоновым.

Таким образом, в терминах теории графов задача коммивояжера формулируется следующим образом: найти гамильтонов цикл (контур) наименьшей длины на реберно-взвешенном графе G = <V, D>, вершины v_i| i = 1, …, N которого представляют города, а взвешенные ребра d_ij| i,j = 1, …, N, i  j – расстояния между ними.

В терминах теории графов сформулированы критерии существова-ния гамильтоновых циклов и возможности решения задачи коммивояжера. Необходимый и достаточный критерий существования гамильтонова цикла [1] имеет высокую вычислительную сложность, поэтому его использование не всегда оправданно. Другие достаточные критерии с меньшей вычислительной сложностью не являются необходимыми (и наоборот), поэтому нарушение данных условий не может гарантировать отсутствие (наличие) гамильтоновых циклов на графе. Тем не менее полезно проверить возможность существования гамильтонова цикла, прежде чем начинать его поиск: достаточные условия изложены в [2 — 4], а условия отсутствия гамильтоновых циклов представлены в работах [2], [3].

1.2Классификация задач коммивояжера

Задача коммивояжера возникает в обширном классе приложений, но в своей классической формулировке не учитывает многих аспектов задач, возникающих на практике. Введение ограничений на количество отображаемых объектов (только города и дороги), использование единственного отношения «находиться на расстоянии … от …» и только детерминированных переменных позволяет свести представление системы к реберно-взвешенному неориентированному графу, для которого может быть найден гамильтонов цикл наименьшей длины. Это облегчает моделирование предметной области, притом что задача обладает высокой комбинаторной сложностью, позволяя сконцентрироваться на создании эвристик для сокращения пространства поиска решений. В то же время, при этих упрощениях не учитываются многие аспекты практических задач, такие как динамичность, нечеткость, неточность, недоопределенность и другие [5]. Поиск оптимального решения задач коммивояжера без учета этих свойств реального мира ведет к решению, которое может стать неудовлетворительным даже при незначительных изменениях условий задачи.

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

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

Важный признак классификации задач коммивояжера — топологические особенности задачи — совокупность ограничений на отношения между объектами, например, в классической формулировке это ограничения (1), (2). На практике эти ограничения, особенно условие симметричности в (1), часто нарушаются, например, если пункты i и j соединяются двумя дорогами с односторонним движением разной длины. В этой связи различают два варианта КЗК: симметричную, когда условие симметричности в (1) выполнено, и асимметричную — в противном случае. Если d_ij — стоимость проезда из города i в город j, может нарушаться условие (2) (проезд из i в k напрямую стоит дороже, чем проезд транзитом через j). В этом случае различают метрическую задачу при выполнении (2) и неметрическую [6] — в обратном случае. Если не нужно возвращаться в исходный пункт, задача — незамкнутая (открытая) [7].

Часто к ограничениям (1), (2) добавляют новые ограничения, создавая методы решения частных случаев задачи. Такие методы работают лучше, чем методы решения КЗК, однако они узко специализированны и не могут быть перенесены на ЗК другого вида. Например, в [8] рассматривается задачи коммивояжера с ограничением следующего вида:

; (3)

Если задача коммивояжера удовлетворяет условию (3), то по алгоритму [8] она может быть решена за время O(n²), что гораздо эффективнее по сравнению с любым из точных алгоритмов решения КЗК.

Рисунок 1- Классификация формулировок задачи коммивояжера

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

Приведенная на рисунке 1 классификация демонстрирует множественность вариантов задач коммивояжера, что обуславливает ее практическую значимость и актуальность разработки методов решения.

1.3Понятия и особенности сложных задач коммивояжера

Раскроем понятие сложной задачи, в частности сложной задачи коммивояжера. Общепринятой классификации задач по сложности моделирования в настоящее время не существует [5]. Анализ литературных источников [9 — 11] показывает, что с задачей чаще всего соотносят две оценки: «трудность» и «сложность». Актуальность применения этих оценочных характеристик в деятельности человека связано с принятием решений как процессом сбора, анализа, хранения, обработки и выдачи информации.

• 1908 г. эмпирически был открыт закон Йеркса-Додсона [10] об оптимуме мотивации при принятии решений (рисунок 2).

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

Рисунок 2-Зависимость времени решения задачи от уровня мотивации

О.К.Тихомиров , Р.А.Гильманов, А.М.Сохор [11] рассматривали трудность задачи как психологическую характеристику, отражающую отношения между задачей и тем, кто ее решает. Уровень трудности зависит не только от задачи, но и от способностей ЛПР. Исследования ведутся в направлении количественной оценки трудности, полученной в ходе решения задачи [14].

В работе [15] В.М. Глушков, говоря о понятии «сложной задачи», связывал с каждой системой S_x величину Ф(S_x) сложности управления этой системой — количество элементарных операций, необходимых для выработки правильных решений по управлению системой за фиксированный промежуток времени. По мере развития системы S_x увеличивается сложность индивидуальных решений и процессов общения меж ду людьми. В результате сложность P(S_x) управления системой растет чем число людей N(S_x) в этой системе.

Рассмотрим рисунок 3, на котором видна зависимость между числом людей в замкнутой экономической системе и сложностью задачей управления этой системой.

Рисунок 3-Первый и второй информационные барьеры

Крива 3 показывает рост сложности задач управления системой по мере ее развития, прямая 1 отображает максимальное количество управленческих задач р, которые способен решить в единицу времени отдельный человек, прямая 2 (P = рN) — максимальное количество управленческих задач, которое способны решить все члены системы S_x без использования средств автоматизации. До прохождения 1-го информационного барьера система S_x может управляться одним человеком, а после перехода через 2-й информационный барьер любой неавтоматизированный механизм управления будет не эффективен.

Оценкам сложности задач посвящены работы [6 — 8]. Обобщая результаты этих работ, можно сделать следующие выводы:

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

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

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

• дальнейшем сконцентрируем внимание на «сложности», полагая, что «трудность» решения задач не составляет предмет настоящей книги.

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

Рисунок 4- Представление сложной задачи как системы

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

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

До появления квантовых и релятивистских теорий, неравновесной термодинамики и фрактальных представлений научные школы исследовали простые системы с детерминированным или (и) периодическим поведением. Как отмечает В.Б. Тарасов, методология классической науки основывалась на следующих положениях:

• предмет науки — общие (повторяющиеся), воспроизводимые и обратимые явления;

• наука позволяет преодолеть неопределенность и случайность;

• научное объяснение — это объяснение свойств целого из свойств частей;

• общенаучные положения должны выражаться как точное, непротиворечивое знание, описываясь строгими логико-математическими моделями.

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