Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах

  • автор:
  • специальность ВАК РФ: 05.13.16
  • научная степень: Кандидатская
  • год, место защиты: 1998, Черкесск
  • количество страниц: 126 с. : ил.
  • бесплатно скачать автореферат
  • стоимость: 240,00 руб.
  • нашли дешевле: сделаем скидку
  • формат: PDF + TXT (текстовый слой)
pdftxt

действует скидка от количества
2 диссертации по 223 руб.
3, 4 диссертации по 216 руб.
5, 6 диссертаций по 204 руб.
7 и более диссертаций по 192 руб.
Титульный лист Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах
Оглавление Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах
Содержание Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления
Глава I. Оценки сложности векторных задач на многоцветных графах
§1.1. Постановка задачи
§ 1.2.Обоснование свойства полноты
§1.3. Вычисление оценок сложности для задачи
о совершенных паросочетаниях на 2-цветных графах
§1.4. Вычисление оценок сложности для задачи
о совершенных паросочетаниях на 3-цветных графах
§1.5. Вычисление оценок сложности для задачи
о совершенных паросочетаниях на 4-цветных графах
Глава 2. Вероятностный анализ векторной задачи о сочетаниях на многоцветных графах
§ 2.1. Общая постановка задачи
§ 2.2. К проблеме нахождения множества всех допустимых
решений комбинаторной задачи
§ 2.3. К проблеме нахождения ПМХ и ПМА Х°
§ 2.4. Полиномиально разрешимые случаи нахождения ПМА
для двукритериальной задачи
§ 2.5. Вероятностный анализ задачи и обоснование статистически
эффективного алгоритма
§ 2.6. Вероятностный анализ задачи о паросочетаниях на
т-дольных (т-цветных) 1М-взвешенных графах
§ 2.7. Алгоритм линейной свертки (АЛС). Вероятностный анализ АЛС
§ 2.8. Оптимизация вычислений
Глава 3. Исследование разрешимости задачи о совершенных паросочетаниях на многоцветных графах
§ 3.1. Формулировка проблемы
§ 3.2. Необходимые обозначения и определения
§3.3. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШБСГМ на 2-цветных графах
§ 3.4. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШБиМ на 3-цветных графах
§ 3.5. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШ811М на 4-5-6-цветных графах
§ 3.6. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШБЦМ на 7-цветных графах
§ 3.7. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШБЦМ на т-цветных графах
§3.8. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШМАХ на 2-цветных графах
§3.9. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШМАХ на 3-цветных графах
§3.10. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШМАХ на 4-5-6-цветных графах
§ 3.11. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШМАХ на 7-цветных графах
§3.12. Исследование разрешимости с помощью АЛС задачи о совершенных
паросочетаниях с критериями вида МШМАХ на т-цветных графах
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

Актуальность темы. В связи с резко возросшей сложностью агробиологического моделирования и создания экономикоматематической модели землепользования и возникла настоятельная потребность разработки алгоритмов нахождения множеств альтернатив в условиях многокритериальности.
Настоящее исследование обусловлено следующими обстоятельствами. Известные экономико-математические модели землепользования отражают лишь структуру посевных площадей. Причем, они используют в качестве основных исходных данных усредненные показатели урожайности. Эти данные и представляют параметры экономической целевой функции (ЦФ). Математические модели, которые содержали бы одновременно и экономические и экологические ЦФ в их системной взаимосвязи к настоящему времени, к сожалению, отсутствует. В настоящей работе восполняется этот пробел. Предлагаемый подход базируется на идее строить математические модели землепользования, используя более тонкие, более адекватные (по сравнению со средней урожайностью) величины: во первых, урожайность каждой культуры, дифференцированную по всевозможным предшественникам, и, во вторых, учитывать изменения (т.е. истощение или, наоборот, улучшение) биоэкологического состояния почвы после выращивания на ней конкретной культуры по конкретному предшественнику. При этом проблема выбора наиболее рациональных решений неизбежно приводит к необходимости учета многих противоречивых требований. В результате адекватные математические постановки задач оказываются многокритериальными задачами. Наряду с этим многие возникающие задачи являются многокритериальными задачами большой размерности на графах. Последнее обстоятельство исключает возможность разработки

точных методов, которые гарантировали бы нахождение искомого решения за реальное время в производственных условиях.
Таким образом, актуальной является проблема создания для указанного класса задач быстрых (малотрудоемких) алгоритмов, которые применительно к выделенным классам дискретных многокритериальных задач оптимизации оказываются эффективными в типичном случае как по точности, так и по трудоемкости. Следует отметить, что для лица, принимающего решение, существенно больший интерес представляет множество конкурирующих альтернатив (парето-оптимальных) решений по сравнению с одним решением, оптимальным по какому-либо критерию или свертке критериев. Иными словами, возникает проблема нахождения множеств альтернатив. Однако, к настоящему времени эта проблема исследована очень слабо. Приведенными выше обстоятельствами и обусловлен резко возросший теоретический и прикладной интерес к так называемым статистически эффективным методам решения многокритериальных задач на графах.
Разработке и обоснованию этих методов и посвящена диссертационная работа. Вместе с этим в работе осуществлено обоснование вычислительной сложности рассмотренных задач, а также установлена их неразрешимость с помощью алгоритмов линейной свертки критериев. Разработан также точный полиномиальный алгоритм для одного полиномиально разрешимого класса.
Цель работы. Основной целью настоящей работы является: вывод точных формул вычисления максимальной мощности множества допустимых решений (МДР) задачи о совершенных паросочетаниях на многоцветных графах; определение соотношений между подмножествами вершин различных цветов, при которых достигается максимум мощности МДР; доказательство свойства полноты задач о паросочетаниях на многоцветных графах в случае, когда векторная целевая функция (ВЦФ)

x=(V.,,Ex) - подграф графа G= (V,E), где Vx cV, Ex с E; cov(x)= cov (e)-
teEx
v-й вес подграфа x.
Если VX=V, то подграф x называется остовным. При четном n допустимым решением рассматриваемой в настоящей работе задачи является совершенное паросочетание [6,17] х=( Vx, Ех) в которых
I ill I ft
VX=V, и концы ребер ecEv окрашены в различные цвета, I Ех I =— I Vx
В векторных задачах на графах критерии (2.2) используемой ВЦФ
(2.1) в терминах введенных обозначений чаще всего представляются целевыми функциями следующего вида:
Fv(x)= £ cov(e) -> min, 0<v<Nb (2.3)
eeEx
Fv(x)= max со v (e) —> min, N i +1 <v<N, (2.4)
e&Ex
где (2.3) - критерии весового вида, (2.4) - критерий “ узкого места ” или в другой терминологии, критерий оценки качества по наихудшему элементу [27,30].
Условимся употреблять символ Zq для обозначения какой-либо многокритериальной (массовой [19,26] задачи, где q—1,2
(2.2) в дальнейшем используем следующие обозначения:
Zi- задача о совершенных паросочетаниях на взвешенном графе G с четным числом вершин п=21;
x=(V,Ex)- совершенное паросочетание на граф G [6,17]; Zo- задача об остовных деревьях;
х- остовное дерево [32]; Z3- задача о цепях между парой вершин графа G;
Вы всегда можете написать нам и мы предоставим оригиналы страниц диссертации для ознакомления

Рекомендуемые диссертации данного раздела