Исследование сложности и разрешимости некоторых дискретных многокритериальных задач

• Автор: Темирбулатов, Пилял Исхакович
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Черкесск
• Количество страниц: 103 с.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ
Глава I. ОЦЕНКИ МАКСИМАЛЬНОЙ МОЩНОСТИ МНОЖЕСТВА
ДОПУСТИМЫХ РЕШЕНИЙ ЗАДАЧИ О ТРИСОЧЕТАНИЯХ НА МНОГОЦВЕТНЫХ ГРАФАХ §1.1. Формулировка проблемы. Максимальная мощность МДР задачи о
трисочетаниях на 3-цветных графах
§ 1.2. Максимальная мощность МДР задачи о трисочетаниях на 4-цветных графах
Глава II. ОЦЕНКИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ВЕКТОРНОЙ ЗАДАЧИ О 3-СОЧЕТАНИЯХ НА т-ЦВЕТНЫХ ГРАФАХ И СТАТИСТИЧЕСКИ ЭФФЕКТИВНЫЙ АЛГОРИТМ
§ 2.1. Содержательное описание и математическая постановка задачи
§ 2.2. Полнота задачи
§2.3. Мощность ПМА
§ 2.4. Алгоритм
§ 2.5. Вероятный анализ многокритериальной задачи о 3-сочетаних и алгоритмам, 34 § 2.6. Оптимизация вычислений
Глава III. ИССЛЕДОВАНИЕ РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМА ЛИНЕЙНОЙ СВЕРТКИ ЗАДАЧИ О ТРИСОЧЕТАНИЯХ НА МНОГОЦВЕТНЫХ ГРАФАХ
§3.1. Формулировка проблемы
§ 3.2. Необходимые обозначения и определения
§ 3.3. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МШБЦМ на 3-цветных графах
§ 3.4. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МПЧЬЦМ на 4-цветных графах
§ 3.5. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МЕЧЬСМ на 5-цветных графах
§ 3.6. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МПЧЬиМ на ш-цветных графах (т > 6)
§ 3.7. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МІ1ЧМАХ на 3-цветных графах
§ 3.8. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МШМАХ на 4-,5-цветных графах
§ 3.9. Исследование разрешимости с помощью АЛС задачи о трисочетаниях с
критериями вида МШМАХ на т-цветных графах (т > 6)
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ
ЛИТЕРАТУРА

ВВЕДЕНИЕ
На пороге третьего тысячелетия человечество, осознав возможности использования вычислительной техники и математики в решении как локальных, так и глобальных проблем во всех сферах жизнедеятельности, все больше и больше обращается к математическому исследованию и математическому моделированию различных процессов. Общепризнанно, что моделирование - один из наиболее эффективных методов познания. И справедливо утверждение, что "... развитие любой науки можно трактовать - в весьма общем, но вполне разумном смысле, - как "теоретическое моделирование"" [4].
Исследуемые в настоящей работе задачи обусловлены глобальной проблемой удовлетворения потребностей населения в продуктах питания при условии, что потенциал похотных угодий должен быть сохранен или, что более актуально, иметь тенденцию его повышения. Заметим, что в настоящем тезисе уже заложена необходимость разрабатывать и рассматривать соответствующие математические модели в условиях многокритериальности. Концепция многокритериальное™ учитывается в полной мере в математических моделях, предлагаемых в настоящей работе.
С точки зрения конкретного содержания рассматриваемые ниже математические модели отражают такие аспекты агробиологических процессов, как изменение плодородия почвы в зависимости от порядка чередования культур на полях, а также ожидаемая урожайность или выход биомассы данной культуры в зависимости от ее предшественника. Причем, в контексте этих показателей прелагаемые модели являются открытыми для рассмотрения и учета других критериев, например, экономических, экологических и т.д.
Рассматриваемые математические модели базируются на математическом аппарате теории графов. Это обусловлено тем, что специфика теории графов в наибольшей степени приспособлена для абстрактного представления циклических процессов чередования. При этом мы ограничиваемся, в
основном, задачей о трисочетаниях, которую можно назвать задачей о коротких циклах. Последнее в содержательном смысле соответствует системе так называемых коротких севооборотов, т.е. такой ротации культур на полях, когда перечень этих культур является весьма ограниченным. Это обстоятельство обусловлено тем, что в последние годы обострились проблемы устойчивого развития и управления ресурсным потенциалом пахотных угодий в связи с тенденцией перехода хозяйств на производство весьма ограниченного перечня культур.
Изложению конкретных результатов, полученных в настоящей работе, предпошлем следующее замечание общеметодологического характера. Главная проблема, которую приходится решать при моделировании и анализе всякой сложной системы, - это выбор существенных переменных. В настоящей работе основное внимание сконцентрировано на связке "рассматриваемая культура г -ее предшественник (на данном поле) у". В процессе моделирования для всякой пары (г,у) указанного вида отражается скорее не фактическое плодородие почвы, а его динамика, т.е. его изменения в случае, когда рассматриваемая культура засевается на поле, для которого известна культура - предшественник, которая была засеяна на этом поле в предшествующий сезон. В рассматриваемых математических моделях в конкретный момент времени подразумеваются фиксированными такие факторы как тип почвы, его увлажнение. Вместе с тем, конкретная пара (г,у) определяет собой такие компоненты плодородия, как количество гумуса, азота, фосфора и тому подобное [33]. Важно подчеркнуть, что указанные факторы отражаются в рассматриваемых ниже моделях в виде общего агрегированного показателя, например, в таких относительных (безразмерных) единицах как баллы, проценты и т.д.
Сказанное выше относительно, используемого агрегированного показателя означает, что он может быть получен на базе моделей другого уровня, которые можно найти в публикациях [45,28]. В свою очередь

дает. Для М5-трудных или труднорешаемых комбинаторных задач получаемых по этому принципу экспоненциальные оценки вычислительной сложности имеют ограниченное значение для практических целей. В таких случаях средняя вычислительная сложность или, например, вычислительная сложность в типичном (наиболее часто встречающемся) случае представляется более информативной.
Поиск точных методов для ТУР-трудных оптимизационных задач и, тем более, для векторных труднорешаемых задач не имеют практического смысла. В этой ситуации мы вынуждены либо переходить к изучению более частных задач и строить для них малотрудоемкие алгоритмы, либо строить приближенные алгоритмы. Отсюда возникает подход к алгоритмическим проблемам, который получил название «алгоритмы с оценками» [11]. Речь идет о векторной оценке качества алгоритмов. Критериями, т.е. компонентами этой векторной функции (т.е. оценки) являются вычислительная сложность, точность, объем памяти, размер области, в пределах которой почти всегда на выходе алгоритма получается искомое решение в виде определенного множества альтернатив (МА) и т.д.
Для формулировки и обоснования дальнейших результатов настоящей работы приведем дополнительные содержательные пояснения и некоторые строгие определения.
Обосновать какой-либо результат для той или иной задачи Ъ в самом общем виде, как правило, затруднительно. Желаемое обоснование удается получить обычно в предположении, что выполняются те или иные ограничения, условия. Например, задачу о коммивояжере [23] можем рассматривать только на полных графах или в предположении, что веса ребер ограничены не зависящей от размерности п константой, и т.д. Иными словами, рассматривая задачу Ъ при тех или иных ограничениях (условиях) мы рассматриваем тот или иной класс К индивидуальных задач. Не опасаясь возможных недоразумений, в дальнейшем вместо выражения «класс индивидуальных задач К» будем