Векторная задача покрытия графа звездами и ее приложения

• Автор: Тебуева, Фариза Биляловна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Ставрополь
• Количество страниц: 153 с. : ил

СОДЕРЖАНИЕ стр

Введение
Глава 1. СОДЕРЖАТЕЛЬНОЕ ОПИСАНИЕ ЕСТЕСТВЕННОНАУЧНЫХ ПРОБЛЕМ, СВОДЯЩИХСЯ К ЗАДАЧАМ ПОКРЫТИЯ ГРАФА ЗВЕЗДАМИ.

1.1. Теоретикочрафовые модели инженерных и организационных задач.

1.2. К использованию теоретикографовых моделей в кластерном анализе

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

1.4. О теоретикографовых задачах землепользования.

1.5. К вопросу о получении численных значений исходных данных для задачи землепользования.

1.5.1. Общие положения.

1.5.2. Зависимость урожайности культуры от предшественников, внос и вынос ими питательных веществ

1.5.3. Влияние органического и минерального удобрения на урожай и плодородие почвы.

1.5.4. Экологическая оценка агромероприятий
1.5.5. Показатели экономической эффективности применения удобрений
1.6. Проблема многокритериальное и отсутствие безусловного оптимума в системе земледелия.
Глава 2. МАТЕМАТИЧЕСКИЕ ФОРМУЛИРОВКИ ЗАДАЧ ПОКРЫТИЯ ГРАФОВ И ГИПЕРГРАФОВ ЗВЕЗДАМИ. ОЦЕНКИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
2.1. Обшая постановка проблемы дискретной многокритериальной оптимизации.
2.2. Математическая постановка векторной задачи покрытия графа звездами.
2.3. Обоснование свойства полноты исследуемой задачи
2.4. Исследование вычислительной сложности векторной задачи покрытия графа звездами.
2.5. Основные термины и понятия, необходимые для формулировки задачи покрытия гиперграфа звездами
2.6. Математическая модель векторной задачи землепользования на гиперграфах.
Глава 3. НАХОЖДЕНИЕ И ОБОСНОВАНИЕ ПОЛИНОМИАЛЬНО РАЗРЕШИМЫХ ПОДКЛАССОВ ЗАДАЧ ПОКРЫТИЯ ГРАФА ЗВЕЗДАМИ.
3.1. Исследование условий существования допустимого покрытия графа звездами.
3.2. О методах решения линейных диофантовых уравнений .
3.3. Полиномиально разрешимый подкласс 1критериальных задач.
3.4. Полиномиально разрешимый подкласс 2критериальных задач
Глава 4. ИССЛЕДОВАНИЕ ПРОБЛЕМЫ РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ КРИТЕРИЕВ ИНТЕРВАЛЬНОЙ ЗАДАЧИ ПОКРЫТИЯ ГРАФА ЗВЕЗДАМИ
4.1. Формулировка интервальной экстремальной задачи
4.2. Сведение интервальной задачи покрытия графа звездами к векторной задаче.
4.3. Методы отыскания паретовских оптимумов с помощью алгоритмов линейной свертки критериев
4.4. Обоснование неразрешимости с помощью алгоритмов линейной свертки критериев интервальной задачи покрытия рафа звездами с критериями вида I .
Глава 5. ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ ДЛЯ ТРУДНОЙ ЗАДАЧИ ПОКРЫТИЯ ГРАФА ЗВЕЗДАМИ И ОЦЕНКИ ИХ ЭФФЕКТИВНОСТИ
5.1. Основные положения методологии приближенных алгоритмов.
5.2. Статистически эффективный и асимптотически
точный алгоритмы.
5.3. Обоснование статистически эффективного
алгоритма
5.4. Обоснование асимптотически точного алгоритма
5.5. Вероятностный анализ применения асимптотически точного алгоритма к конечным множествам
взвешенных графов.
Заключение
Литература


В терминах теории графов и гиперграфов подмножества из первых образуют центры звезды, а вторых висячие вершины ребер звезды. Задача кластерного анализа в теоретикографовой интерпретации состоит в том, чтобы в данном гиперграфс выделить множество непересекающихся звезд, которые образуют наилучшее покрытие его звездами. Задача о покрытии графа звездами заданного типа возникает при моделировании процесса формирования целевых групп исполнителей, т. В процессе математического моделирования агроэкологоэкономической задачи землепользования возникает задача покрытия гиперграфа звездами. Содержательная суть рассматриваемой задачи состоит в следующем. Землепользователь выращивает определенный перечень сельскохозяйственных культур на пахотных угодьях, разбитых на поля одинаковой площади. Для каждой пары конкретная культура конкретное поле является известным ожидаемый выход продукции в руб, изменение содержания гумуса в , ожидаемый выход кормов в кормопротеиновых ед Являются также известными потенциально возможные объемы агротехнических мероприятий и эффект от них изменение содержания гумуса и др В качестве решения требуется найти для каждого поля такое назначение культуры и агротехнического мероприятия на поле, чтобы максимизировать суммарный эффект по трем показателям выход продукции, объем кормов, процентное содержание гумуса в пахотном слое. Глава 2 посвящена математической постановке многокритериальной задачи покрытия графа звездами и построению математической модели многокритериальной задачи землепользования на гиперграфах. Считаются заданными вершинный граф , и множество допустимых типов звезд Я . Гс 1,2,. Допустимое покрытие графа звездами представляет собой такой его остовный подграф д v,, , у которого каждая компонента связности является звездой из заданного множества Я. Если граф является взвешенным, т. Я, 1, Я, 3
а также критерия количества звезд в покрытии а, т. ВЦФ 1 4 определяет на X паретовское множество ПМ 1с, состоящее из парстовских оптимумов ПО данной векторной многокритериальной задачи. Элемент хеХ называется ПО, если не существует такого допустимого решения х е X, что выполняются неравенства . V 1,ЛГ, среди которых хотя бы одно является строгим. Под искомым математическим решением дискретной многокритериальной задачи обычно подразумевается полное множество альтернатив ПМЛ Ли, которое определяется как подмножество Х X минимальной мощности Л такое, что гл г, рх х д е ХХ с X. При исследовании сложности векторных многокритериальных задач особый интерес представляет полнота задачи. Обозначим через IV х семейство всех множеств допустимых решений задачи покрытия фафа звездами. Х X X. ТЕОРЕМА 2. Векторная задача покрытия графа звездами является полной, если ее ВЦФ 1 содержит не менее двух весовых критериев вида 2. СЛЕДСТВИЕ 2. Векторная задача покрытия графа звездами является труднорешаемой, т. НМД растет экспоненциально с ростом размерности задачи, если ее ВЦФ 1 содержит хотя бы пару критериев весового вида 2. Т.к. ХРтрудной, то алгоритм нахождения оптимума предполагает целенаправленный перебор. Поэтому представляют интерес формулы вычисления максимальной мощности МДР А
Глава 3 посвящена исследованию необходимых и достаточных условий, при выполнении которых МДР X задачи покрытия графа звездами не является пустым и выделению полиномиально разрешимых подклассов Iкритсриальных и 2критериальных задач покрытия графа звездами. Определение 3. Для данного МТЗ II Лр. У ТВЕРЖДЕНИЕ 3. Для того, чтобы было непустым МДР Х,Н задачи покрытия полного п вершинного графа С звездами из какоголибо заданного МТЗ Н, необходимо и достаточно существование хотя бы одного решения диофантова уравнения 7. Для данного МТЗ Н ,,,7,,. Ит множество всех решений диофантова уравнения 7 обозначим через 2Н 2. Пусть при этом Н2 . Приводится алгоритм, снимающий вопрос о разрешимости уравнения 7. На выходе этот алгоритм приводит список всех решений заданного диофантова уравнения. Суть алгоритма заключается в следующем. Обозначим через а2,а3,. Приведем описание алгоритма а2 нахождения множества 2 2Н. И2 к1 , г, г.