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

Рисунок 8-Построение модели задачи различными методами формализованного представления систем а) — аналитическими; б) — статистическими; в) — логическими; г) — лингвистическими; д) — нечеткими

1.4Мера сложности моделирования задачи

Измерение сложности задач можно сравнить с измерением количества информации. Известны фундаментальные результаты [54 — 65] по синтаксической, семантической и прагматической информации. На их основе В.И. Николаев [48] вводит для оценки сложности решения задачи показатель:

где P_p — вероятность правильного решения; C₀ = ln (k (l !- k +1) l!) ,

1. — число возможных схем решения, l — число операций (ЭВМ), которые нужно выполнить для решения задачи; a и b — коэффициенты учета условий получения и обработки информации; I ₀ , I₁ , I _p — информация, участвующая в решении задачи; I_{l +1} — информация, полученная в результате решения задачи.

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

Определяя меру количества информации, У.Эшби исходил из понятия «разнообразие» [16], употребляя его в двух смыслах: 1) количество различных элементов; 2) логарифм этого количества по основанию два.

Поскольку базисом для построения моделей «однородная задача» и «неоднородная задача» выбран естественный язык, то разнообразие и неоднородность были сведены к разнообразию и неоднородности двух фундаментальных понятий: переменной и отношения. Составлены ограниченные перечни классов переменных (табл. 1.3), которыми оперирует наука [4], и классов отношений, связывающих эти переменные. Разнообразие классов отношений показано на рисунке 9. На нем представлен ориентированный граф G = <VT, RT>, где вершины VT— классы переменных из таблицы 3, а дуги RT — классы отношений между переменными. Класс отношения будем определять по классам переменных, которые оно связывает, например: «ДП — ДП», «ДП — СП» или «СП — ДП». Отношения переменных одного класса будем называть однородными (представлены петлями на графе G), в противном случае — разнородными.

Разнообразие и неоднородность информации — фундаментальная причина сложности моделирования решения задач [15]. Вводимая ниже мера названа мерой сложности моделирования задачи и будет включать два показателя: 1) количество классов переменных в модели задачи; 2) количество классов разнородных отношений между ними.

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

Таблица 3- Классы переменных

Рисунок 9-Полный граф G классов переменных и классов отношений

Обозначим число классов переменных (таблица 3), используемых в модели задачи, как x X , а число классов разнородных отношений — y Y. И количество классов переменных, и количество классов разнородных отношений — положительные целые числа. Число классов переменных ограничим пятью, рассмотренными в таблице 3. Если разнородные (т.е. связывающие переменные разных классов) отношения отсутствуют в модели, число их классов равно нулю, т.е. X , Y {0}. Кроме того, верхняя и нижняя границы числа классов разнородных отношений y зависят от числа классов переменных x, используемых в модели. Пусть G’ = <VT’, RT’> — подграф графа G классов переменных и классов разнородных отношений, используемых в модели задачи, где вершины VT’ — классы переменных, используемые в модели, x = |VT’|, а дуги RT’ — классы разнородных отношений, y = |RT’|. Исследуем на графе G’ два случая.

Случай 1. Максимальное число дуг на графе G’ достигается, если каждая вершина связана дугой с каждой другой вершиной, т.е. граф — полный. Кроме того, в нем должны отсутствовать петли, так как они представляют однородные отношения (т.е. связывающие переменные одного класса). Число дуг такого графа |RT’|, т.е. максимально возможное число классов разнородных отношений y_max, определяется как размещение без повторений из x элементов по 2:

Случай 2. Минимальное число дуг достигается, если граф G’ — ори-ентированное корневое дерево. Любая вершина достижима из корня, либо корень достижим из любой вершины. В корень не заходит либо не выходит ни одна дуга. Число дуг такого графа |RT’|, т.е. минимально возможное число классов разнородных отношений y_min:

Если в модели задачи используется один класс переменных (x = 1), то согласно (1.8) значение y_max не определено. Очевидно, что в модели, где все переменные одного класса, не может быть разнородных отношений, т.е. y_max = y_min = 0.

Определим соответствие V как множество векторов (x, y), т.е. допустимых в модели задачи пар («число классов переменных», «число классов разнородных отношений»):

Вектор (1, 0) в (1.10) обозначает ситуацию, когда в модели задачи используется один класс переменных и y_max не определено. Вектор

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

Для сравнения задач по сложности моделирования введем метрику p множества V как евклидово расстояние. Тогда расстояние между векторами v₁ и v₂, представляющими две задачи, определяется:

Введение метрики позволяет рассмотреть классификацию задач по сложности моделирования. Для этого определим отображение H множества векторов V на множество классов задач Z = {«простые», «сложные»}. Модели простых задач однородны, то есть используют не более одного класса переменных. Модели сложных задач неоднородны и содержат не менее двух классов переменных. Классификация задач по сложности моделирования выглядит так:

Графически отображение H представлено на рисунке 10. Ось абсцисс— количество классов переменных, ось ординат — число классов разнородных отношений. Элементы множества V представлены точками. Верхняя и нижняя границы множества V показаны кривыми, интерполирующими значения функций y_max и y_min , соответственно. Отображение H представлено точками на плоскости (X, Y), а третье измерение Z — фигурными скобками под осью OX . Оно делит вертикальными линиями точки на плоскости (X, Y) на две области: простых и сложных задач. Область простых задач содержит только один вектор — начало координат, (1; 0), а область сложных задач — все векторы, представленные черными точками. Учитывая, что в таблице 3 было рассмотрено пять классов переменных, то область сложных задач ограничена прямой x=5.

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

Рисунок 10-Классификация задач от простого к сложному

Вывод:

1.Изложена суть задачи коммивояжера, область ее применения. Делается вывод, что традиционная постановка задачи не отражает многие практические случаи. 2. Рассмотрены характерные технологические задачи, решаемые с помо- щью задачи коммивояжера: оптимизация маневровых передвижений на сортировочной станции, нахождение оптимальных маршрутов передвиже- ния ремонтным бригадам. 3. Приведен подсчет общего количества туров в задаче коммивояжера. Подробно рассмотрены наиболее часто используемые методы ее решения: полный перебор, метод динамического программирования, метод ветвей и границ, эвристические подходы. Приведен необходимый анализ применения методов, их достоинства и недостатки. 4. Описаны возможные пути решения многокритериальной задачи ком- мивояжера. В свете решения задачи коммивояжера рассмотрены два подхода к решению многокритериальных задач. первый подход заключается в сведении многокритериальной постановки к однокритериальной. Второй подход: задача решается, оставаясь многокритериальной. Ставятся вопросы выбора критерия максимальной надежности функционирования системы и способа измерения расстояния между точками допустимой области в случае использования методологии второго подхода. 5. Описаны имеющиеся в литературе математические модели задач орга- низации движения транспортных средств. Перечислены недостатки этих подходов. 

2 Разработка модели нескольких коммивояжеров

2.1 Определение модели нескольких коммивояжеров с использованием теории графов

Рассмотрим следующую математическую модель, являющуюся обобще­нием классической задачи коммивояжера на случай нескольких коммивояже­ров. Предполагается, что есть некоторое максимально возможное количество коммивояжеров s, число п - количество городов для посещения, а также пол­ный ориентированный граф G(X,U), связывающий эти города и точки место­нахождения коммивояжеров. Множество X содержит n + 2s вершин, из них:

1. n вершин, где требуется побывать, занумерованных натуральными чис­лами от 1 до п, называемых небазовыми.

2. s базовых вершин, где коммивояжеры находятся на начальном этапе пути. Эти вершины нумеруются целыми числами от n+1 до n + 2s-\ с шагом 2.

3. s базовых вершин, где коммивояжеры будут находиться в конце путе­шествия. Вершины занумерованы числами от п+2 до n+2s с шагом 2.

i-й коммивояжёр начинает обход из точки a_h а закончить движение дол­жен в точке b_h. Дугам множества U графа приписаны неотрицательные числа-веса. Каждая дуга (w,v) имеет вес d(u,v). Необходимо:

1. Определить наилучшее в некотором смысле количество торговцев m (m<s) для посещения городов. Заметим, что число s может превосходить чис­ло городов п. Поскольку каждый коммивояжер должен посетить, по крайней мере, по одному пункту, количество их т должно быть выбрано не больше п.

2. Выбрать т конкретных агентов из s имеющихся.

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

Длиной маршрута будем называть сумму весов всех его ребер. Через G обозначим количество небазовых вершин в i-м маршруте. Если i-й ком­мивояжер не задействуется, G =0.