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

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

Рисунок 6- Преобразование задачи методологии рационализма и детерменизма

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

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

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

Таблица 2-Характеристика классической задачи коммивояжера

В [11] рассматривается одна из разновидностей задачи коммивояжера — задача коммивояжера с временными окнами — задача поиска маршрута автомобиля, развозящего заказы потребителям. Все заказы загружены в машину на складе — исходной точке маршрута — и для каждого потребителя задан интервал времени, в течение которого он должен быть посещен машиной, заданы матрицы расстояний и времени проезда между потребителями. Если машина прибывает к потребителю до начала интервала его обслуживания, то она ожидает его начала, после чего начинается разгрузка, а если после завершения временного интервала, маршрут либо считается недопустимым (задача с жесткими временными окнами), либо подвергается штрафу за опоздание (задача с мягкими временными окнами). Требуется найти маршрут посещения потребителей, обладающий, по возможности, наивысшим качеством.

Если сравнить этот вариант задачи коммивояжера с классической задачей коммивояжера, можно заметить, что добавились две детерминированные переменные: «время проезда между потребителями» и «интервал обслуживания потребителя», причем граф модели стал вершинно- и реберновзвешенным.

Могут быть и другие постановки задачи коммивояжера. При этом расширяется не только количество детерминированных переменных, что оставляет задачу в классе однородных задач, но и вводятся новые отношения и переменные из классов: стохастических, логических, нечетких и др. [4].

При выполнении подобных действий по детализации и уточнению условий задачи происходит следующее:

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

• формирование множества «задач-систем» из различных областей однородных подзадач, причем отношения возникают между задачами внутри области и задачами из разных областей; минимальное количество областей, комбинируемых в «задаче-системе», — две;

• должно быть учтено большее количество переменных и их зависимостей, чтобы «задача-система» могла считаться решенной по мере интеграции областей; при этом растет и сложность моделирования задачи. Графически этот процесс показан на рисунке 7.

Рисунок 7- Преобразование игровой задачи комбинированием областей подзадач с однородными переменными

На рисунке 7 изображен переход («справа — налево») от понятия «игровая задача» к понятию «сложная задача» методом комбинирования пяти областей подзадач с однородными переменными. Подзадачи показаны точками, а связи между ними внутри областей — линиями.

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

• количеством однородных областей, интегрируемых в задаче-системе;

• количеством подзадач в областях;

• различными отношениями между подзадачами в различных областях.

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

• понятию сложности моделирования приводит анализ свойств практических задач. К таким свойствам относят:

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

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

Третье — динамичность. Сложные задачи имеют нефиксированные предметную и проблемную области, изменяющиеся данные, а также состав подмножеств задач-элементов. Нельзя говорить о методе, навсегда разработанном и применяемом для решения сложной задачи.

Четвертое — неопределенность в ситуации решения задачи и необходимость анализа риска последствий. Неопределенность может быть вызвана неполнотой исходных данных и знаний экспертов, невозможностью учета реакции внешней среды, а также неточным пониманием своих целей ЛПР.

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

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

Анализ свойств сложных задач показывает, что для практики автоматизированного решения задач важно получить оценку сложности их моделирования (разработка и эксперименты с моделями). Чтобы отобразить сложность моделирования на реалии внешнего мира через «призму» разнообразия, в [4] были введены две модели: «однородная задача», «неоднородная задача». Однородные задачи — задачи, не имеющие структуры и не подлежащие редукции в ходе моделирования; содержат минимум разнообразия и специфицируются одним методом формализованного представления систем (термин предложен Ф.Е. Темниковым [13]). Неоднородные задачи — задачи-системы, состоящие из однородных подзадач, описанных различными МФПС, обладающие свойством эмерджентности, несводимости свойств неоднородной задачи к сумме свойств составляющих ее подзадач. В научных представлениях многообразия реального мира различают следующие МФПС [17]:

• аналитические — методы, в которых свойства многомерной системы S_x отображаются функционалом Ф(S_x) в точку многомерного пространства, совершающую движение (рисунок 8,а). К ним относятся методы классической математики, поиска экстремумов функций, вариационное исчисление, методы математического программирования и тому подобное. Применяются, если свойства системы представимы детерминированными величинами, а их взаимосвязи — аналитическими зависимостями;

• статистические — методы, в которых свойства многомерной системы S_x отображаются функционалом Ф(S_x) в «размытую» точку (область) многомерного пространства, совершающую движение в соответствии со случайной функцией (рисунок 8,б). К ним относятся теория вероятностей, математическая статистика, теория массового обслуживания и тому подобное Они расширяют возможности моделирования систем, так как не требуют выявлять все детерминированные связи между компонентами системы, заменяя их статистическими закономерностями. Применение этих методов ограничивается возможностью определения представительной выборки и проведения статистических исследованиях;

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

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

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

При классификации задач по сложности моделирования простыми задачами будем называть однородные задачи, а сложными — неоднородные задачи-системы, элементы-подзадачи которых описываются различными МФПС.