Математические модели агро-эколого-экономических задач на графах и гиперграфах в условиях многокритериальности

• Автор: Салпагаров, Солтан Исмаилович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Черкесск
• Количество страниц: 167 с. : ил

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

Введение.

Глава 1. ИССЛЕДУЕМЫЕ АГРОЭКОЛОГОЭКОНОМИЧЕСКИЕ ПРОБЛЕМЫ ЗЕМЛЕПОЛЬЗОВАНИЯ

1.1. Г Гредмет исследования.

1.2. Ключевые слова предмета и темы исследования, основные понятия, термины и их содержание.

1.3. Исходные данные и условия задачи.

Глава 2. ИССЛЕДОВАНИЕ ЗАДАЧ ЗЕМЛЕПОЛЬЗОВАНИЯ НА ГИПЕРГРАФАХ

2.1. Гиперграфы. Некоторые определения и свойства

2.2. Ориентированные гиперграфы.

2.3. Алгоритм выделения гамильтоновой цепи на гиперграфе

2.4. Оценки сложности для однородных гиперграфов

2.5. Формулировка и обоснование свойства полноты векторных задач на однородных гиперграфах
2.6. Об одной агроэкологоэкономической модели на гиперграфах
2.7. Построение и исследование агроэкологоэкономической модели на ориентированном гиперграфе
Глава 3. ИССЛЕДОВАНИЕ ИНТЕРВАЛЬНЫХ ЗАДАЧ ПОКРЫТИЯ ГРАФА ЦЕПЯМИ
3.1. Общая формулировка векторной задачи покрытия графа цепями
3.2. Задачи с интервальными данными
3.3. Сведение интервальной задачи о цепях к 2критериальной задаче.
3.4. Оценки сложности интервальной задачи о покрытии графа цепями.
Глава 4. ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ И ТРУДНЫЕ ПОДКЛАССЫ ЗАДАЧ ПОКРЫТИЯ ГРАФА ЦЕПЯМИ И ПРОБЛЕМА ПЕРЕБОРА РЕШЕНИЙ ДИОФАНТОВА У РОВ НЕНИЯ
4.1. Математическая постановка задачи .
4.2. АРтрудный подкласс 2критериальных задач покрытия графа цепями
4.2.1. Критерий количества цепей и проблема поиска решений линейного диофантова. уравнения
4.2.2. Алгоритм решения линейного диофантова уравнения
4.3. Полиномиально разрешимый подкласс экстремальных задач покрытия Идольного орграфа сквозными путями
4.4. Полиномиально разрешимый подкласс 2критериальных задач покрытия орграфа путями
Глава 5. АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ ЗАДАЧ ПОКРЫТИЯ ГРАФА ЦЕПЯМИ
5.1. Основные положения методологии приближенных алгоритмов.
5.2. Исследование векторной задачи покрытия графа цепями двух типов
5.2.1. Задача о покрытии графа И,к1 цепями.
5.2.2. Описание алгоритма
5.2.3. Вероятностный анализ алгоритма, применяемого к
1взвешенному графу
5.3. Асимптотически точный алгоритм для задачи о покрытии графа множеством цепей произвольного типа
5.3.1. Формулировка промежуточной задачи и
обозначения
5.3.2. Описание алгоритма
5.3.3. Обоснование вероятностных условий асимптотической точности .
5.3.4. Обоснование теоретикомножественных достаточных условий асимптотической точности алгоритма
5.4. Условия асимптотической точности в случае
произвольной структуры искомого покрытия.
Глава 6. ИССЛЕДОВАНИЕ РАЗРЕШИМОСТИ С ПОМОЩЬЮ АЛГОРИТМОВ ЛИНЕЙНОЙ СВЕРТКИ ИНТЕРВАЛЬНОЙ ЗАДАЧИ ПОКРЫТИЯ ГРАФА ЦЕПЯМИ
6.1. Определение понятий и терминов.
6.2. Обоснование неразрешимости с помощью алгоритмов линейной свертки интервальной задачи покрытия графа цепями с критериями вида.
Заключение
Литература


Е каждая пара вершин Уе принадлежит различным долям. Если каждое ребро ееЕ гиперграфа 0 Г, содержит в точности вершин, то 7 называется однородным гипсрграфом. В п. Теорема 2. Относительно нижней оценки максимального числа гамильтоновых цепей установлено, что в гамильтоновых пвершинных однородных гиперграфах нижняя оценка максимального числа гамильтоновых цепей растт экспоненциально с ростом размерности гиперграфа ул, 2к я,, где , 1. В условиях многокритериальности возникает необходимость вместо оптимума искать множество альтернатив. Качество допустимых решений хе X оценивается векторной целевой функцией ВЦФ x xi2x. V 1, У,, , Аг, а остальные критериев имеют
вид X оценка по наихудшему v ivе x, 9 . В определении этих критериев используются веса v, и 1,2 приписанные ребрам ееЕ. ВЦФ x определяет собой в МДР X паретовское множество XX. В качестве искомого решения принимается полное множество альтернатив ПМА, обозначаемое через Х. X x х X VX X. Принято говорить, что задача с ВЦФ x обладает свойством полноты, если для всякого ее МДР найдутся такие параметры ВЦФ, при которых выполняются равенства X X X. Для каждой культуры определено количество отводимых под нее полей, причем для каждого поля известна культурапредшественник, которая выращивалась в предыдущем сезоне. Для каждой пары конкретная культура конкретное моле являются прогнозируемыми следующие исходные данные задачи ожидаемый выход продукции в руб. Являются также известными потенциально возможные объемы агротехнических мероприятий и эффект от них. Теорема 2. Проблема нахождения ПМЛ для критериальной, 2 задачи о совершенных паросочетаниях на 3дольном 3однородном вершинном гиперграфе с критериями вида МАХЗим или МАХМ1Ы является труднорешаемой. В заключительной части главы 2 задачи, аналогичные представленным выше, рассматриваются на ориентированном гинерграфе. Полученные результаты также являются аналогичными и касаются, соответственно, свойства полноты, оценок максимальной мощности МДР и обоснования труднорешаемости проблемы нахождения ПМА для векторных задач на ор гиперграфах. Глава 3 посвящена исследованию в некотором смысле крайнему случаю неопределенности численных значений параметров рассматриваемых экстремальных задач на графах. Указанная неопределенность выражается в том, что в данном графе гиперграфе 0У,Е вес всякого ребра ееЕ представляется интервалом, т. В этом случае целевая функция задачи имеет интервальный вид нх не шш, где согласно определению сложения интервалов
получаем интервальную целевую функцию ИЦФ фг Кх,2х. Теорема 3. Паретовское множество задач с ИЦФ мх и ВЦФ л Р1дс,Рл, рх X 1,2 совпадает. На интервальные задачи не распространяются автоматически свойства многокритериальных задач, поскольку в классе последних интервальные задачи представляют весьма узкий подкласс. Вопрос о полноте интервальных задач снимает следующая Теорема 3. Интервальные задачи покрытия графа цепями одинаковой длины являются полными. В главе 4 осуществлены исследования, обусловленные тем обстоятельством, что в общем случае задача покрытия п вершинного графа цепями, типы которых выбираются из данного множества ,, г 1,7, требует обоснования не пустоты МДР X X, х. В свою очередь, для обоснования неравенства X,0 необходимо найти решения
диофантова уравнения л. V i критерий 7ЛЧ1 х х i означает количество цепей в покрытии. Т является не зависящей от п константой. В главе 4 исследована 2критериальная задача покрытия графа цепями, которая в контексте произвольных множеств Н является ЫР трудной. В классе этих трудных задач найден полиномиально разрешимый подкласс задач покрытия Лдольного графа сквозными вершинными цепями. По отношению к этой задаче развивается подход, известный под названием алгоритмы с оценками. Суть этого подхода состоит в том, чтобы для конкретного множества типов цепей Н И, построить малотрудоемкий алгоритм, максимально использующий специфику множества И и при этом достичь приемлемых значений критериев Xх, v 1, 1, составляющих ВЦФ x. Е приписаны веса е 1,2,. Е 0п2. Теорема 5.