Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

Введение

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

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

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

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

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

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

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

В пятой главе рассматривается проблема отыскания «оптимального» решения для задачи с интервальными данными. В главе отмечены ряд фундаментальных особенностей таких задач. 1)Для задач оптимизации с нечеткими или интервальными данными отсутствует общепризнанное универсальное определение бинарного отношения порядка «меньше-больше», а также универсальное определение арифметических операций сложения, умножения и т.д. 2)Понятие «оптимум» оказывается неадекватным и в контексте алгоритмической проблемы формулируется открытый вопрос о нахождении множества альтернатив (МА); обычно искомое МА есть подмножество паретовского множества. 3)Алгоритмы классической оптимизации оказываются неадекватными для нахождения этих МА. В качестве конструктивных авторских результатов, относящихся к верхнему уровню, для одного класса экстремальных задач на графах с интервальными весами осуществлено обоснование достаточных условий, при которых предлагаемые полиномиальные алгоритмы являются асимптотически точными, статистически эффективными, точными.