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

На правах рукописи

/

г

г

Салпагарова Аминат Абдулла.човна

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ НА МНОГОЦВЕТНЫХ ГРАФАХ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Черкесск 1998

Работа выполнен;! и Карачаево-Черкесском технологическом институте-*.

Научные руководители доктор физико-математических наук.

профессор Перепелица В.А.

кандидат технических наук профессор

Мамсдов А А

Официальные оппоненты: доктор физико-математических наук

Семенчин Е. А.

кандидат физико-математических наук Кочкаров A.M.

Ведущая организация Таганрогский государственный

радиотехнический \ ниверситст

Защита диссертации состоится «5» декабря 1998г. в 10 часов на заседании регионального диссертационного совета K200.74.0l по физико-математическим наукам в НИИ ПМА КБНЦ РАН по адресу: 360000. г. Нальчик, у.т Шортанова. 89 «а»

С диссертацией можно ознакомиться в научной библиотеке НИИ ПМА КБНЦ РАИ

Автореферат разослан __>■_________1998;

Ученый секретарь РДГ К20П 74.0]: к.ф.-м.н. k ^ Шибзухов З.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В связи с резко возросшей сложностью агробиологического моделирования и создания экономико-математической модели землепользования и возникла настоятельная потребность разработки алгоритмов нахождения множеств альтернатив в условиях многокритериальности.

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

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

Таким образом, актуальной является проблема создания для указанного класса задач быстрых (малотрудоемких) алгоритмов, которые применительно к выделенным классам дискретных многокритериальных задач оптимизации оказываются эффективными в типичном случае как по точности, гак и по трудоемкости

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

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

подмножествами вершин различных цветов, при которых достигается максимум мощности МДР; доказательство свойства полноты задач о паросочетаниях на многоцветных графах в случае, когда векторная целевая функция (ВЦФ) включает весовые критерии вида М/МБЦМ и \1AXSUM. и. как следствие, получение заключения о труднорешаемости рассматриваемой задачи; выделение полиномиально разрешимых классов векторных задач и построение статистически эффективных алгоритмов для общего случая; исследование проблемы разрешимости с помошью алгоритмов линейной свертки критериев.

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

Методы исследования: В работе использованы методы теории графов, теории вероятностей, комбинаторики и математического программирования.

1 I

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

Анробаиня работы. Материалы диссертации докладывались и обсуждались на Общенаучном математическом семинаре, I научно-практической конференции преподавателей и аспирантов КЧТИ (г.Черкесск, 1995), IV научно-методической конференции (г.Черкесск, 1995г.), на международном научном симпозиуме «Экономика и право-стратегия 3000» (г.Кисловодск, 1996г.), V научно-методической конференции «Новые технологии обучения: теория, опыт, проблемы, перспективы» (г.Черкссск, 1996г.), на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 1997), На международной конференции (Нальчик, 1996) на Всероссийской молодежной научной конференции «Гагаркнские чтения» (Москва, 1997), на конференции «Математическое программирование и приложения» (Екатеринбург, 1997), на международном коллоквиуме 1КМ-97 (Веймер, 1997), в всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной н управленческой деятельности» (Таганрог, 1998).

В диссертацию вошли результаты, полученные мною как одной из исполнителей проекта № 792 от 26.05.95г. о конкурсе грантов Госкомитета РФ по фундаментальным исследованиям в области

I I

математики по теме «Исследование векторных задач на графах. Разрешимость, сложность, алгоритмы» 1995-1997гг.; проекта о

конкурсе грантов Госкомитета РФ по фундаментальным исследованиям в области математики по теме «Исследование векторных задач на графах. Разрешимость, сложность, алгоритмы» 1998-1999гт.

Публикации. Основные результаты диссертанта опубликованы в шестнадцати работах.

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающего 58 наименований. Работа изложена на 126 страницах.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая глава диссертации посвящена исследованию нижних оценок сложности задач на многоцветных графах.

В общем случае постановка векторной оптимизационной задачи состоит в следующем: (У,Е)- п-вершинный граф с множеством ребер Е; к=1, 2,..., т - номера цветов в которые раскрашены вершины V е V; - подмножество вершин V € V, окрашенных в цвет к; для всякой пары 1 ^ выполняется \/ = 0, 1еу, |У1.|=пк >1 для каждого

к=1,2,..., ш; £ Ик=п;

Рассмотрим m-цветный граф G=(VbV2,.--,Vm, Е), в котором множество вершин V мощности |V|=n, n-четное разбито на m

П!

непересекающихся подмножеств Vk, | V^r^ > 1, ^ nk=n, где состоит

t=i

из вершш окрашенных в цвет к.

Допустимым решением является совершенное паросочетанке x=(V,Ex), где Е^сЕ состоит из ребер, концы которых окрашены в разные цвета. Пусть Х={х} множество всех допустимых решении (МДР).

Граф G называется N-взвешеиным, если каждому ребру е еЕ приписаны веса wv(e)>0, v=l,2,...,N. Если для данного графа G для всех

его ребер определены эти веса \vv (е), v- \,N Ve еЕ то говорим о данном конкретном) N- взвешивании графа G.

На множестве X определена векторная целевая функция (ВЦФ) F(XMF,(x),...,Fn(X)}, (1)

состоящая из критериев весового вида

Fv(x)=2»i(e)->min, v-l,2,...,N. (2)

в£

ВЦФ F(x) определяет собой паретовское множество (ПМ). Искомым решением задачи является полное множество альтернатив (ПМА).

Подмножество X°cr X называется ПМА, если его мощность |Х°| минимальное и яри этом выполняется равенство F(X°)=F( X), где F(X*)={F(x): х€Х*} VX*CX.

В настоящей работе рассматривается проблема решения векторной задачи о сочетаниях, которая состоит в том, чтобы построить

достаточно эффективный метод нахождения НМЛ. для какого-либо N-взвешенного ш-цветного графа. Введем обозначения :

iR (п,ш)-множество всех n-вершинных rn-цветных графов;

(G,N,m) (/Л (G,N,m)) -максимальная мощность ПМА (ПМ)которая определяется по всевозможным N-взвешиваниям (1)-(2) графа G; Вычисление

максимальных мощностей ПМА pim (п) и ПМ //m(n) представляет большой интерес, так как их можно рассматривать

в качестве нижних оценок сложности задачи о совершенных паросочетаннях на m-цвегных графах.

Рассмотрим задачу о совершенных паросочетаннях на

конкретном графе G €

Пусть M(G) множество всех Ы-взвепшваний графа G. Задачу' о совершенных паросочетаннях называем полной на графе G, если M(G) содержит хотя бы одни граф такой, что на этом графе для рассматриваемой задачи выполняется равенство

у?- X ~х,

то говорим, что рассматриваемая многокритериальная задача является полной на графе G.

Рассмотрены задачи о совершенных паросочетаннях на 2,3,4-цветном графе.

Теорема 1.2. При N>2 для векторной задачи о совершеных паросочетаннях на 2-цветных графах G(VbV2,) е 9? (п,2) Р/*]=Пк>0, к=1,2; максимальные мощности ПМА и ПМ достигают значений а) /и (п!.п2)= U7 (н, ,Пг) =0, при П] л п2,

б) /и2 (л,,п2) = (/г,,п2) = (|)!, при щ=п2=п/'2;

причем максимальные .мощности и2 (п) — //2 (//) - !

Теорема 1.3. При N>2 о совершенных паросочеганиях на 3-цветных графах 0(УьУ2,У3,Е ) е 9?. (п,3) |Ук|=пкХ), к=1,2,3; максимальные мощности ПМА и ПМ достигают значений

а) //3(п1,п2,п3)= при лз>п1+п2,

б) з)я//з(^,Л2,я3) = (|)!, прип3=п1+п2;

, и \ ~ , ^ лг,! лг2! ! с) р з ((я, ,п2,п3)^/и3(п1, п2, /;3) = -г---^-, при

П3<П1+П2.

Теорема 1.5. При N>2 для векторной задачи о совершенных паросочетаниях на 4-цветных графах С=( V? ,\г2,Уз,Е)еЭг(п,4).

к= 1,2,3,4; п,< п, при ¿< 3, максимальные мощности ПМА и ПМ достигают следующих значений:

п

а)^4(п1,п2.пз,п4)= при П:>—;

б)//4(«1,я2,Яз,л4) = //4(й,>112,Из,//4)в(|) !, при»4=^;

. чр пЛпЛпЛ

с)м=]Г - -1- - -

^ с«, - /, )\{п2 ~ /2)!(«з -1,)\кх\клкг\;

ы

где 1±±

1 2 2 -2 3 2

причем > 0,к2 > > 0 приа,= ~

д) №|У2НУ3МУ4|=4 4

„X/ !>.)'(»/ 4 - ^)!(п /4 - /,)!]2

п п

0<1, <7, 1,+Ь+1у=-. 4 2

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

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

обоснования трудоемкости этих алгоритмов получены следующие оценки.

Теорема 2 1. В случае рациональных весов ребер графа проблема нахождения ПМА двукритериальной задачи о совершенных

паросочетаниях 2 ',2' разрешима с полиномиальной сложностью T(Z;:))<0(n3l).

Теорема 2.5. Если в ВЦФ (1) число ее критериев (2) ограничено сверху полиномом n (N < О (пс). с - независящая от п

/7

константа), то при выполнении условия RN + {<-,%=Oútp(rí))

hn+%'

алгоритм а2 является статически эффективным на множестве двудольных графов G е íí2(nJR,N). При этом для вычислительной сложности нахождения ПМА справедлива оценка т(а2)<0(п2 N + п3).

Теорема 2.6. Если параметры n, R.N удовлетворяют

соотношению/^+i<——— 4' =(Х<р(п]), то AJ1C А является ЗСЬш+Ч,2)' 3

статическим эффективным на множестве $H(n.R,N) 3-дольных N-взвешенных графов с равномощными долями и справедлива оценка т (А) <0(п3).

Проведена оптимизация вычислений и для обоснования полученных оценок выведены следующие теоремы

Теорема 2.7. Если параметры n,R.N удовлетворяют

соотношению —-—4i-CXa(n)), то для почти всех графов

Ьш+Ч^'

GeSR2(n,R.N) алгоритм сС находит ПМА с вычислительной сложностью т (аг) < О (nv: + n2N).

Теорема 2.8. Если параметры пДЫ удовлетворяют соотношению

- — - ^К =(ХсЫп)). то для почти всех графов Ое,Л3(п.К.Ы) • ЗОпя+Ч^)' 2

алгоритм А* находит ПМА с вычислительной сложностью т(А*) < (п5'2+п2Н).

В третья глава настоящей работе исследуются вопросы разрешимости с помощью АЛСК проблемы нахождения паретовского множества и полного множества альтернатив для задачи о паросочетаниях на многоцветных графах. Одной из центральных проблем векторной оптимизации является проблема сведения векторной задачи поиска оптимальных альтернатив к скалярной задаче с обобщенным критерием, являющимся некоторой сверткой частных критериев. Существуют дискретные многокритериальные задачи, для которых алгоритм линейной свертки критериев не обеспечивает получение всех эффективных решений. Это обстоятельство позволяет говорить о неразрешимости таких задач в классе алгоритмов линейной свертки критериев. В настоящей работе исследуются вопросы разрешимости с помощью алгоритмов линейной свертки критериев проблемы нахождения паретовского множества и полного множества альтернатив для задачи о паросочетаниях на многоцветных графах. Полученные в настоящей работе результаты соотносятся с результатами работ других авторов. Эти результаты базируются на том факте, что так называемые примитивные индивидуальные задачи являются неразрешимыми с помощью АЛСК. В силу того, что она содержит примитивные индивидуальные задачи. Строго говоря, вопрос о разрешимости с помощью АЛСК не примитивных задач о совершенных паросочетаниях остается открытым. Кроме того, этот же вопрос остается открытым и для случаев, когда задача о совершенных паросочетаниях формулируется на

т-цветных графах. Обоснованию ответов на вышеуказанные открытые вопросы и посвящена настоящая глава и выведены следующие теоремы.

В работе получены теоремы для случаев 2-7 - цветных графов и по аналогии с этими теоремами получены следующие

Теорема 3.5. Для каждого четного ш>8 и всякого N>2 задача о совершенных паросочетаниях с критериями вида МШЗЦМ на ш-цветных И-взвешенных п-вершмных графах неразрешима с помощью АЛС

Теорема 3.10. Для каждого четного т>8 и всякого N>2 задача о совершенных паросочетаниях с критериями вида МБЧМАХ на ш-цветных 1\[-взвешешшх п-вершиньгх графах неразрешима с помощью АЛС.

В предложенной диссертационной работе получены следующие математические результаты:

- Выведены точные формулы вычисления максимальной мощности множества допустимых решений (МДР) задачи о совершенных паросочетаниях на многоцветных графах для числа цветов к=2,3,4.

- Дан вывод и обоснование верхней и нижней оценки максимальной мощности задачи о совершенных паросочетаниях на многоцветных графах для числа цветов к=2,3,4.

- Определены соотношения между подмножествами вершин различных цветов при которых достигается максимум мощности МДР.

- Доказано свойство полноты задач о паросочетаниях на многоцветных графах в случае, когда векторно-целевая функция (ВЦФ) включает весовые категории вида МШБЦМ и МАХвЦМ; дан строгий

вывод заключения о том, что ори этих условиях исследуемая задача является трудно решаемой.

- Для случая когда ВЦФ содержит критерий вида MINMAX получено полиномиальная верхняя оценка искомого полного множества альтернатив.

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

- Для рассматриваемой задачи на многоцветных графах исследована проблема разрешимости с помощью алгоритма линейной свертки (AJ1C) и дано обоснование теорем о неразрешимости с помощью AJTC задач о совершенных паросочетаниях на т-цветных графах.

Публикации по теме диссертации.

1. Салпагарова A.A. Оценки сложности для задачи о паросочетаниях на многоцветных графах // Научн.-практ. конф. препод, и аспирантов К-ЧТИ: Тез. дохл,-Черкесск: К-ЧТИ, 1995г.

2. Салпагарова A.A., Темирбулатов П. И. Научно-исследовательские аспекты преподавания дискретного программирования студентам экономических специальностей // Научн.-метод, конф. К-ЧТИ: Тез. докл.- Черкесск: К-ЧТИ, 1995г.-с. 16-17.

3. Салпагарова A.A., Темирбулатов П.И. Научно-методические аспекты прикладных дисциплин для экономических специальностей // Научн,-мегод. конф. «Новые технологии обучениятеория, опыт, проблемы, перспективы» К-ЧТИ: Тез. докл.- Черкесск: К-ЧТИ, 1996г.-с.13-15.

4. Салпагарова A.A., Тамбисва Ж.А.. Темирбулатов П.И. Исследование задач о кликах //Тсч.докл Международной конф. «Нелокальные краевые задачи и родственные проблемы математики, биологии, информатики и физики».-Нальчик: ин-т ПМА РАН., 1996.-с.78-79

5. Салпагарова A.A. Аналитическое исследование математической модели задачи о паросочетаниях на 3-цветном графе./ЛГез. докл. На Всероссийском симпозиуме «Математическое моделирование и компьтсриыс технологии» Сб. науч. трудов.: - 24-26апреля 1997г.-С92-93.

6. Салпагарова A.A. О двух обобщениях задачи о назначениях. Математическое моделирование и компьютерные технологии на математическом международном научи. Симпозиуме «Экономика и право - стратегия 3000». Кисловодск.: 1996.-С.46-48

7. Перепелица В.А., Касаев А Д . Попова Е.В., Салпагарова A.A.. Темирбулатов ПИ. Исследование операций и принятие решений. Часть II, методическое пособие для экономических специальностей.-Черкесск: КЧТИ, 1996, Збс.

8. Салпагарова A.A.. Темирбулатов П.И. Оценки сложности многокритериальных задач о сочетаниях. //Тезисы докладов Международной конференции «Математическое программирование и приложения»,- Екатеринбург: Ин-т математики и механики УРО РАН,- 1997. - С.78-80

9. Салпагарова A.A., Темирбулатов П.И. Алгоритмы с оценками решения векторной задачи о покрытии графа кликами //Тезисы

докладов второй научно-практической конференции КЧ'ГИ. Черкесск: 1997. -С. 51-52.

10. Salpagarova A.A., Temirbulatov P.I. On One Systemic Development Of The Problem Of Allocation //Jnternationals Colloquium über Anwendungen der Informatik und Mathematik in Architektur und Bauwesen- IKM? Bauhaus- Universität Weimar? Http://www/uni-\veimar/dc/~ikm/Beitrag 140/1997.

11. Салпагарова A.A. Исследование векторной задачи о сочетаниях на 3-цветном гра(|>е./7 Тезисы докладов Международной конференции «XXIII Гагаринские чтения».-М: 1997,

12. Салпагарова A.A. Вероятностный ана.тт задачи и статистически эффективный алгоритм. Препринт №824,- Киев: НАЛ Украины. Ин-т электродинамики. 1998.-С. 1- 15.

13. Салпагарова A.A.. Перепелица В.А. Полиномиально разрешимый класс векторных задач на графах. Препринт №825,- Киев: HAH Украины Ин-т электродинамики.. 1998-С. 1-30.

14. Салпагарова A.A. Исследование векторной задачи о сочетаниях на многоцветных графах. Деп. ВИНИТИ РАН 27.03.97. Хо%4-г- Г .-22с.

15. Салпагарова A.A. Исследование разрешимости с помощью алгоритма линейной свертки задачи о совершенных паросочетаниях на многоцветных графах. Препринт №826,- Киев: HAH Украины. Инт электродинамики.. 1998.-С. 1-13.

16. Салпагарова A.A. О неразрешимости с помощью алгоритмов линейной свертки одной векторной агробиологической задачи о паросочетаниях. // Всероссийская международная конференция «Компьютерные технологии инженерной и управленческой деятельности», 6-8 октября, Таганрог. 1998.

Министерство общего и профессионального образования Карачаево-Черкесский технологический институт

На правах рукописи

Салпагарова Аминат Абдуллаховна

АЛГОРИТМЫ С ОЦЕНКАМИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ НА МНОГОЦВЕТНЫХ ГРАФАХ

05.13.16- применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Диссертация на соискание ученой степени кандидата физико-математических наук

Научные руководители: доктор физ.-мат. наук, профессор В.А. Перепелица, кандидат технических наук, профессор А.А.Мамедов

Черкесск-1998

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................................................3

Глава I. Оценки сложности векторных задач на многоцветных графах

§1.1. Постановка задачи..........................................................................................................18

§ 1.2.Обоснование свойства полноты.....................................................................................20

§1.3. Вычисление оценок сложности для задачи

о совершенных паросочетаниях на 2-цветных графах..................................................23

§1.4. Вычисление оценок сложности для задачи

о совершенных паросочетаниях на 3-цветных графах...................................................24

§1.5. Вычисление оценок сложности для задачи

о совершенных паросочетаниях на 4-цветных графах...................................................28

Глава 2. Вероятностный анализ векторной задачи о сочетаниях на многоцветных графах

§2.1. Общая постановка задачи...............................................................................................33

§ 2.2. К проблеме нахождения множества всех допустимых

решений комбинаторной задачи...................................................................................34

§ 2.3. К проблеме нахождения ПМ1и ПМА Xo....................................................................37

§ 2.4. Полиномиально разрешимые случаи нахождения ПМА

для двукритериальной задачи.........................................................................................39

§ 2.5. Вероятностный анализ задачи и обоснование статистически

эффективного алгоритма..............................................................................................48

§ 2.6. Вероятностный анализ задачи о паросочетаниях на

ш-дольных (т-цветных) N-взвешенных графах...........................................................53

§2.7. Алгоритм линейной свертки (АЛС). Вероятностный анализ АЛС ...........................62

§ 2.8. Оптимизация вычислений...............................................................................................67

Глава 3. Исследование разрешимости задачи о совершенных паросочетаниях на многоцветных графах

§ 3.1. Формулировка проблемы.................................................................................................71

§ 3.2. Необходимые обозначения и определения....................................................................73

§3.3. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINSUM на 2-цветных графах............................76

§ 3.4. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINSUM на 3-цветных графах...........................81

§ 3.5. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINSUM на 4-5-6-цветных графах...................86

§ 3.6. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINSUM на 7-цветных графах...........................91

§ 3.7. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINSUM на m-цветных графах.........................95

§3.8. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINMAX на 2-цветных графах.......................101

§3.9. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINMAX на 3-цветных графах.......................105

§3.10. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINMAX на 4-5-6-цветных графах................109

§ 3.11. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINMAX на 7-цветных графах.......................112

§3.12. Исследование разрешимости с помощью АЛС задачи о совершенных

паросочетаниях с критериями вида MINMAX на m-цветных графах....................115

ЗАКЛЮЧЕНИЕ............................................................................................................120

ЛИТЕРАТУРА..............................................................................................................121

ВВЕДЕНИЕ

Актуальность темы. В связи с резко возросшей сложностью агробиологического моделирования и создания экономико-математической модели землепользования и возникла настоятельная потребность разработки алгоритмов нахождения множеств альтернатив в условиях многокритериальное™.

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

точных методов, которые гарантировали бы нахождение искомого решения за реальное время в производственных условиях.

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

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

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

включает весовые критерии вида МГШЦМ и МАХЗИМ, и, как следствие, получения заключения о труднорешаемости рассматриваемой задачи; выделение полиномиально разрешимых классов векторных задач и построение статистически эффективных алгоритмов для общего случая; исследование проблемы разрешимости с помощью алгоритмов линейной свертки критериев.

Научная новизна: Впервые разработана агробиологическая математическая модель многокритериальной задачи о совершенных паросочетаниях. Доказано, что рассматриваемая задача обладает свойством полноты в случае, когда ВЦФ состоит из критериев вида МПЧБиМ; выведена точная формула вычисления максимальной мощности полного множества альтернатив, откуда вытекает утверждение о труднорешаемости исследуемой векторной задачи; построен и обоснован эффективный алгоритм решения 2-критериальной задачи о совершенных паросочетаниях на многоцветных графах; выделен класс труднорешаемых 2-критериальных задач о совершенных паросочетаниях, для которых предложенные автором алгоритмы являются статистически эффективными; построен алгоритм, гарантирующий нахождение ПМА 2-критериальной задачи о совершенных паросочетаниях; доказана неразрешимость с помощью АЛС векторной задачи о паросочетаниях на многоцветных графах.

Методы исследования: В работе использованы методы теории графов, теории вероятностей, комбинаторики и математического программирования.

Практическая ценность: практическая ценность работы состоит в том, что полученные в работе результаты могут быть использованы при разработке системы поддержки принятия решений в процессе агробиологического математического моделирования задачи землепользования в условиях многокритериальности. Идеи доказательства

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

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

Многоцветные графы можно использовать, когда исследуемый процесс моделируется с помощью графа, вершины которого разбиты на группы и запрещено соединение вершин, принадлежащих одной группе. Содержательно это условие может отражать, например, при агробиологическом моделировании в землепользовании [2,3,8]. Указанное условие отражает агрономическое требование засевать поле повторно одной культурой не чаще, чем через определенное количество лет.

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

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

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

В процессе реализации выше указанной идеи использованы подходы, представленные в работах [2,3,8]. Это становится возможным, если при построении модели использовать двухиндексные переменные ху, где содержательно Ху означает площадь, на которой засеивается культура! по предшественнику ^ 1<У<п, где п- число выращиваемых культур. Отсюда система всех переменных представляется в виде квадратной

матрицы х=

, где 1=1,2,...,п - нумерация выращиваемых культур,

которые одновременно выступают и в роли предшественников ]==1,2,...,.п. При этом система переменных х^, 1<у<п должна отвечать условию сохранения площади возделывания каждой из культур при их ротации (т.е. севообороте). Для каждой фиксированной культуры ^ это условие определяется соотношением

п п

(1)

У=1

¿=1

Принципиально важным является тот факт, что при выполнении равенств (1)

целочисленная пхп - матрица х =

определяет собой ротацию (севооборот) культур на полях. Проиллюстрируем этот факт конкретным примером 4x4- матрицы на рис.1, где предполагается, что угодия некоторого хозяйства разбиты

Рис.1.

1 2 3 4

1 0 0 1 0

2 1 0 2 0

3 0 2 0 1

4 0 1 0 0

на 8 полей одинаковой площади. Единицей измерения элемента х° ех

служит площадь одного поля. Например, равенство х°3=2 в х° означает,. Что культура 1=2 засевается по предшественнику ]=3 на площади двух полей.

Матрица х° представляет собой матрицу смежностей некоторого ориентированного мультиграфа [16], в данном примере - мультиграфа на рис.2. Поскольку в силу (1) этот мультиграф Рис.2,

является эйлеровым [16], его можно разложить на систему контуров [16]. На рис.3 представлен такой пример разложения, когда эта система состоит из одного (эйлерова [16]) контура. Каждую из этих систем можно рассматривать как систему севооборотов.

Если известна ценность с,, 1=1,2,...,п и прогнозируемый выход иу учитываемого биологического вещества для каждой культуры { по ее предшественникам ]'=1,2,...,п, то пхп - матрица определяет собой ожидаемое

п

суммарное накопление ф,.(х) = ^иуху по всем культурам 1=1,2,...,п и

Рис.3.

1 — -©к

——. -

у=1-

агроэкологическую ЦФ

и п п

оо = ИИс*ииху тах

¿=1

/=1 У=1

Построение математической модели завершает система соотношений, определяющих совместно с (1) множество допустимых решений Х={х}:

о

7=1 п

в) ^Х*.>Уп1 = \,2,...,п.

7=1

Здесь условие б) отражает агробиологические требования вида «площадь

п

1>, занимаемая культурой не должна превышать известную величину

7=1

81; в равенстве а) параметр 8 означает суммарную площадь пахотных земель.

Наряду с агробиологическим показателем необходимо учитывать и экономический критерий. Если известны цены с;, [=\,2,...,п и прогнозируемые урожайности Иу для каждой культуры г по ее предшественникам ]=1,2,...,п, то пхп - матрица х= х:] определяет собой

п

ожидаемый суммарный урожай срДх) = ^ицху культур 1=1,2,.,.,п и

7=1'

экономическую ЦФ

и V

(=1 ¡=1

Условие в) отражает обязательства перед государственным или коммерческими партнерами. Эта математическая модель представляет самостоятельный теоретический и прикладной интерес по сравнению с известными подходами вида [8]. Последние оперируют усредненными (по всем предшественникам) урожайностями и отражают лишь общую структуру посевных площадей. Заметим, что усредненные урожайности являются весьма грубыми параметрами. Из статистических данных по Карачаево-Черкесской республике: урожайность озимой пшеницы колеблется от 26 ц/га до 36 ц/га в зависимости от предшественника, т.е. отклонение от минимума 26 ц/га составляет 38%, а для подсолнечника на зерно колебания составляют от 4,9 ц/га до 12,1 ц/га, т.е. уклонение от минимума 4,9 ц/га составляет более 145%.

Одно из достоинств математической модели состоит в том, что на ее системе переменных Ху, 1<1,]<п можно строить агробиоэкономическую математическую модель при следующих условиях. На основе статистических и экспертных данных определяются (в баллах или других единицах) коэффициенты ку улучшения (при ку>1) или ухудшения (ку<1) состояния почвы после выращивания на ней культуры {, засеянной по предшественнику 1<:у<п. Тогда интегральный агробиологический показатель эффективности можно представить следующей целевой функцией:

п п

р2 (*) = X £ куХд -> тах.

/=1 ;=1

Т.о. на МДР X определена векторная целевая функция (ВЦФ) р(х)=(р1(х),р2(х)), состоящая из экономической ЦФ и экологической ЦФ. Эта векторно-целевая функция системно, т.е. с помощью единой системы соотношений, составляющих математическую модель, определяет паретовское множество [2], из которого выбирается «компромисно наилучший» варианта х° с помощью процедур теории выбора и принятия решений [2].

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

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