Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Салпагарова, Аминат Абдуллаховна

• Салпагарова, Аминат Абдуллаховна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Салпагарова, Аминат Абдуллаховна

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Введение диссертации (часть автореферата) на тему «Алгоритмы с оценками для некоторых задач векторной оптимизации на многоцветных графах»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

Научная новизна: Впервые разработана агробиологическая математическая модель многокритериальной задачи о совершенных паросочетаниях. Доказано, что рассматриваемая задача обладает свойством полноты в случае, когда ВЦФ состоит из критериев вида МПЧБиМ; выведена точная формула вычисления максимальной мощности полного множества альтернатив, откуда вытекает утверждение о труднорешаемости исследуемой векторной задачи; построен и обоснован эффективный алгоритм решения 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].

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

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

и

векторных задач на многоцветных графах, т. е. задачи оказываются труднорешаемыми [37].

Для подкласса труднорешаемых задач дано обоснование статистической эффективности полиномиально приближенного алгоритма. Для рассматриваемой задачи на многоцветных графах исследована проблема разрешимости с помощью алгоритма линейной свертки (АЛС) [27,45]. Получено обоснование теорем о неразрешимости с помощью АЛС задач о совершенных паросочетаниях на т-цветных графах, когда ВЦФ содержит критерий одного вида МЕЧМАХ или МЕЧБЦМ.

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

ПЕРВАЯ ГЛАВА диссертации посвящена исследованию нижних оценок сложности задач на многоцветных графах.

В общем случае постановка векторной оптимизационной задачи состоит в следующем: С= (У,Е)- п-вершинный граф с множеством ребер Е; к=1, 2,..., т - номера цветов в которые раскрашены вершины уеУ; Ук -подмножество вершин УеУ, окрашенных в цвет к [40]; для всякой пары

1ф] выполняется \^пу,-=0, \ еу, |Ук|=пк >1 для каждого к=1,2,..., ш;

т

X пк=п;

к=1

Рассмотрим ш-цветный граф 0=(УьУ2)...,Ут, Е), в котором множество вершин V мощности |У|=п, п-четное разбито на т

т

непересекающихся подмножеств Ук, |Ук|=пк>1, ^ пк=п, где состоит из

к = 1

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

Допустимым решением является совершенное паросочетание х=(У,Ех) [9,19], где ЕхсЕ состоит из ребер, концы которых окрашены в разные цвета [40]. Пусть Х={х} множество всех допустимых решений (МДР).

Граф О называется 1М-взвешенным, если каждому ребру е еЕ приписаны веса \¥у(е)>0, у=1,2,...,1чГ. Если для данного графа О для всех его ребер определены эти веса \уу (е), Уе еЕ то говорим о данном

(конкретном) 1М- взвешивании графа О.

На множестве X определена векторная целевая функция (ВЦФ) Р(х)={Р1(х),...,Рк(х)}, (1.1)

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

Ру(х)=5>Дг)-> гпш, у=1,2,...Л. (1.2)

ееЕ

ВЦФ Р(х) определяет собой паретовское множество (ПМ) [10,36]. Искомым решением задачи является полное множество альтернатив (ПМА). Подмножество Х°с X называется ПМА, если его мощность |Х°| минимальное и при этом выполняется равенство Р(Х° )=Р(Х), где Р(Х*)={Р(х): хеХ*} УХ*сХ.

В настоящей работе рассматривается проблема решения векторной задачи о сочетаниях, которая состоит в том, чтобы построить достаточно эффективный метод нахождения ПМА, для какого-либо 14- взвешенного т-цветного графа [42].

Введем обозначения : (п,ш)-множество всех п-вершинных ш-цветных графов; М- (в,N,111) ( ц (в,N,111)) -максимальная мощность ПМА (ПМ)которая определяется по всевозможным ^взвешиваниям (1.1)-(1.2) графа О;

Вычисление максимальных мощностей ПМА ¡хт (п) и ПМ ци(п)

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

Рассмотрим задачу о совершенных паросочетаниях на конкретном графе в еЩп,т).

Пусть М(О) множество всех ^взвешиваний графа в. Задачу о совершенных паросочетаниях называем полной на графе О [38], если М(в) содержит хотя бы один граф такой, что на этом графе для рассматриваемой задачи выполняется равенство

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

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

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

а) ц2 (пьп2)= ^2(пг,п2)=0, при П]фП2;

б) ц2(и1,и2)=р;2(и1,й2)=(|)!, При пх=п2=п]2\

Теорема 1.3. При N>2 о совершенных паросочетаниях на 3-цветных графах 0(УьУ2,У3,Е )е$К(п,3) |Ук|=пк>0, к=1,2,3; максимальные

мощности ПМА и ПМ достигают значений

хи=х=х,

о

(1.3)

причем максимальные мощности \х2{п) = \х2{п) =

а) |я3(пьп2, п3)= \1г{пх,п2,пъ)=0,

б) [13(п1,п2,п3)=-^3(пх,п2,п3) = (£)\,

с)[1ъ((п1,п2,п3) = \х3(п1,п2,п3)--

пх\п2\пъ\

при П3>П1+П2; при п3=п!+п2; при п3<п1+п2.

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

а) ц4 (пьп2> П3;П4)= (я4(й1,п2,и3,л4) =0,

б) \1л(пх,п2,пъ,пА) -\хА{пх,п2,щ,п4) = (^)\,

при П4>-;

при п4=-;

Е

пх\п2\пъ\

Шг (п\ - к)К*г - 4)!(«3 ~1гУ-к, '

з

0 < 1. < Л. , X ^ =П~ 2И4 ,

/=1

где

причем >0,к2>0,к3>0

При Щ=

д) ^МУгМУзМУдИ^

о<1г<^, Ь+Ъ+1^.

Ки/4]4

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

ВО ВТОРОЙ ГЛАВЕ рассматривается вероятностный анализ векторной задачи о сочетаниях на многоцветных графах. Предлагаются полиномиальные алгоритмы решения задачи о совершенных паросочетаниях на многоцветных графах. Алгоритмы применяются к задаче о совершенных паросочетаниях на ш-цветных графах. Для обоснования трудоемкости этих алгоритмов выведены следующие теоремы.

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

т(2|2))<0(п31).

Теорема 2.5. Если в ВЦФ (2.1) число ее критериев (2.2) ограничено сверху полиномом п (Ы < О (пс), с - независящая от п константа), то при выполнении условия (2.20) алгоритм а2 является статически эффективным на множестве двудольных графов в е 9?2(пД,1Ч). При этом для вычислительной сложности нахождения ПМА справедлива оценка т(ос2)<0(п2 N +п3).

Теорема 2.6. Если параметры п, удовлетворяют соотношению (2.34), то АЛ С А является статическим эффективным на множестве 1Н(пД,]Ч) 3-дольных 1\Г-взвешенных графов с равномощными долями и справедлива оценка т (А) < 0(п ).

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

Теорема 2.7. Если параметры пД,К удовлетворяют соотношению (2.22), то для почти всех графов Ое$К2(пД,]чГ) алгоритм а* находит ПМА с вычислительной сложностью т (а2*) < О (п5/2 + п21Ч).

Теорема 2.8. Если параметры n,R,N удовлетворяют соотношению (2.40), то для почти всех графов Ge$R3(n,R,N) алгоритм А* находит ПМА с вычислительной сложностью т(А*) < (n5/2+n2N).

ТРЕТЬЯ ГЛАВА настоящей работе исследуются вопросы разрешимости с помощью АЛСК проблемы нахождения паретовского множества и полного множества альтернатив для задачи о паросочетаниях на многоцветных графах [29]. Полученные в настоящей работе результаты соотносятся с результатами работ других авторов (см. процитированный перечень литературы) следующим образом. По видимому можно считать, что наиболее общие результаты относящиеся к рассматриваемой проблеме, представлены в [29]. Эти результаты базируются на том факте, что так называемые примитивные индивидуальные задачи являются неразрешимыми с помощью АЛСК [19,29,49.51]. В силу того, что она содержит примитивные индивидуальные задачи. Строго говоря, вопрос о разрешимости с помощью АЛСК не примитивных задач о совершенных паросочетаниях остается открытым. Кроме того, этот же вопрос остается открытым и для случаев, когда задача о совершенных паросочетаниях формулируется на m-цветных графах. Обоснованию ответов на вышеуказанные открытые вопросы и посвящена настоящая глава и выведены следующие теоремы.

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

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

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

В заключении сформулированы основные результаты диссертации, которые выносятся на защиту.

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

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Салпагарова, Аминат Абдуллаховна

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Салпагарова, Аминат Абдуллаховна, 1998 год

ЛИТЕРАТУРА

1.Axo А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.:Наука, 1975.-118с.

2. Батищев А.Ф., Перепелица В.А. Об одном алгоритме нахождения оптимального севооборота. В. сб. Оптимальное планирование.-Новосибирск: Ин-т математики СОАН СССР, 1970.

3. Батищев А.Ф., Гришин A.A. Перепелица В.А. Из опыта решения задач по нахождению оптимального севооборота и их внедрения. В сб. Экономико-математические методы и ЭВМ в сельском хозяйстве. - 4.2-Вильнюс: НИИЭСХ ЛССР, 1970- С.141-145.

4. Вилкас Э.И., Майминас Е.З. Решения: теория, информация, моделирование.- М.: Наука, 1982.-256с.

5. Гермейер Ю.Б. Введение в теорию исследования операций.-М.: Наука, 1971.

6. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. //Проблемы кибернетики.-М.: Наука, 1975,- Вып.31.-С.35-42.

7. Гладкий A.A., Янушкевич О.А.О линейной свертке частных критериев векторной задачи минимизации// Тез. докл. IX .Всероссийской конф. « Математическое программирование и приложения.»-Екатеринбунг, 1995-С.65.

8. Гулиев P.P., Коновалов М.Г, Огнивцев С.Б. Моделирование севооборота с помощью управляемых марковских цепей. //Народное хозяйствр Азербайджана. №8, 1982.-С.49-51.

9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982.-416с.

10. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем.-М..;Наука,1986.

11. Емеличев В.А. К оценке сложности многокритериальных транспортных задач // Докл. АН БССР, 1986. Т.ЗО. -N. 7.-С. 593-596.

12. Емеличев В. А., Кравцов М. К. О неразрешимости векторных задач дискретной оптимизаций на системах подмножеств в классе алгоритмов линейной свертки критериев //Докл. РАН,1994. Т. 334. -N1. -С.9-11.

13. Емеличев В. А., Кравцов М. К О задачах векторной дискетной оптимизации на системах подмножеств , неразрешимых с помощью алгоритмов линейной свертки //ЖВМиМФ,1994. T.34.-N7. -С. 1082-1094.

14. Емеличев В. А., Кравцов М.К., Янушкевич O.A. Условия парето-оптимальности в одной дискретной векторной задаче на системе подмножеств// :ЖВМиМФ,1995. T.35.-N11.-C. 1641-1652.

15. Емеличев В.А., Кравцов М.К., Янушкевич O.A. Разрешимость минимаксных задач векторной оптимизации с помощью алгоритма линейной свертки критериев //Тез. докл. IX Всероссийской конф. «Математическое программирование и приложения». -Екатеринбунг, 1995. -С. 88-89.

16. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.- М.: Наука., 1990.

17. Емеличев В.А, Перепелица В.А. О некоторых алгоритмических проблемах многокритериальной оптимизации на графах //ЖВМиМФ, 1989. -N2. -С. 171-183.

18. Емеличев В.А., Перепелица В.А. К вычислительной сложности дискретных многокритериальных транспортных задач //Докл. АН СССР. Техн. Кибернетика, 1988. -N 1. -С. 78-85.

19. Емеличев В. А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика, 1994. Т.6. Вып. 1. -С. 3-33.

20. Емеличев В. А. , Перепелица В.А. Многокритериальные задачи об остовах графа//ДАН СССР,1988. Т. 298. -N3. -С.544-547.

21.Емеличев В.А., Перепелица В.А. К алгоритмическим проблемам векторной оптимизации на графах // Системы программного обеспечения решения задач оптимального планирования: Тез. докл. 9 Всесоюз. симпоз. (Минск, 23 февр. - 3 март. 1986г.) - М.% ЦЭМИ АН СССР, 1986.-С.79-80.

22. Карлин С Математические .методы в теории игр, программировании и экономике .//Кибернетика.-1975 .-№1 .-С. 1 -8.

23. Коршунов А.Д. Об одном алгоритме нахождения паросочетаний в конечных графах.// Кибернетика.- 1975.-№1.-С.1-8.

24. Кочкаров A.M. Асимптотический подход к многокритериальной задаче покрытия графа цепями.// Доклад АН БССР, 1983.-Т.ХХУ, №10.-С.911-913.

25. Кочкаров A.M. Асимптотически точные алгоритмы решения многокритериальной задачи покрытия графа цепями. //Известия АН БССР.-1985.-№4.-С.39-43.

26. Кочкаров A.M., Перепелица В.А. Многокритериальная задача покрытия графа цепями большой и малой длины. //Иззвестия АН БССР.-1983.-№5.-С.39-44.

27. Кристофидис Н. Теория графов. Алгоритмический подход.- М.: Мир, 1978.-432с.

28. Кляус П.С. Минимум суммарных затрат в одной задаче выбора. Математические методы и их применение //материалы 3 конф. Молодых ученых ин-та математики АН БССР и ин-та физики и математики АН Лит. ССр. -Минск, 1977.-78С.

29. Кравцов М.К., Янушкевич O.A. О многокритериальных задачах, разрешимых с помощью алгоритма линейной свертки критериев //Препринт. -Мн.: Ин-т техн. Кибернетики АН Беларуси, 1995. - N 16.-16с.

30. Ларичев О.И. Наука и искусство принятия решения. - М.: Наука, 1979.-200с.

31. Лупанов О.Б. О методах получения оценок сложности и вычисления индивидуальных функций //Дискр.анализ.-1974.- Вып.25.-№1.-с.7-11.

32. Маламед И.И., Сигал И.Х. Исследование линейной свертки критериев в многокритериальном дискретном // Тез. докл. IX Всероссийской конф . «Математическое программирование. и приложения .»-Екатеринбург, 1995.-С.65.

33. Майника Э. Алгоритмы оптимизации на сетях и графах.- М.: Мир, 1981.- 323с.

34. Меламед И.И. Методы оптимизации в транспортном процессе.-М.; Итоги науки и течники,1991.

35. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем.- М.: Наука, 1981.- 287с.

36. Моисеев H.H. Математические задачи системного анализа.- М.: Наука, 1981,-312с.

37. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.- М.: Мир, 1985.- 521с.

38. Перепелица В.А. Мамедов A.A. Исследование сложности разрешимости векторных задач на графах.- Черкесск: КЧТИ, 1995.- 45с.

39. Перепелица В. А. К алгоритмической проблеме для многокритериальных задач проектирования управляющих систем // Проблемы теоретической кибернетики: Тез. докл.7 Всесоюз.конф. (Иркутск, 18-20 сент.1985г.) Иркутск: Иркутск.гос.ун-т, 1985.-4.1.-С.164-165.

40. Перепелица В.А., Сергиенко И.В. Исследование одного класса целочисленных многокритериальных задач. //Журн.вычис.математики мат.физикики.- 1988.-Т.28., №3.-С.400-419.

41. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач М.: Наука, 1982.- 256с.

42. Салпагарова А.А. Исследование векторной задачи о сочетаниях на многоцветных графах / Черкесск. 1997. 22с. //Рукопись деп. в ВИНИТИ РАН № 984 -В97.

43. Семенчин Е.А. Оптимальное управление быстропротекающими случайными процессам// Методы исследования и проектирования элементов и систем автоматического управления: Межвуз. сб. /Моск. инт электрон. Машиностроения.-М.: Изд-во МИЭМ, 1990. -С.33-35.

44. Холл Ф. Комбинаторика М.: Мир, 1970. - 424с.

45. Черкасский Б.В. Новый алгоритм генерации остовных деревьев // Кибернетика.- 1987.- №1.-С.85-89.

46. Эрроу К.Дж., Гурвиц JI., Удзова X. Исследования по линейному и нелинейному программированию.-М.; ИЛ, 1962.

47. Burkard R.E., Keiding Н., Krarup J., Prnzan P.M.A relationship between optimality and efficiency in mujticrteria О -1 programming problems// Computers & Optuations Research, 1981. V.8.-N4.-P.241-247.

48. Bracer P. Discrete parameter optimization problem and essential efficient points // Operat. Res, 1972. V. 16. -N5. -P. 189-197.

49. Burkard R. E., Krarup J., Pruzan P.M. Efficiency and optimality in minisum, minimax 0-1 programming problems // J. Oper. Res . Soc. 1982. V. 33. -N 2. -P. 137-151.

50. Emelichev V.A., Perepeliza V. A. Complexity of vector optimization problems on graphs// Optimization, 1991. V. 22 -N6. -P. 903-918.

51. Edmonds J., Fulkerson D.R. Bootleneck extrema //J.Combin. Thery.-1970.-8№8.-P.299-306.

52. Koopmans T.C. Activity analysis of production. -N. Y.; Wiley, 1951

53. Charnes A., Cooper W. W. Management Models and Jdustrial Application of Linear Programming-N.Y.; Wijey, 1961.

54. Geoffrion.A.M. Proper efficiency and the theory of vector maximization //J. Math. Analysis and Ahhj,1968.V.22-P.-630.

55. Steuer R. Mujticriteria optimization.-N.Y.; Wijey, 1985.

56. Salpagarova A.A., Temirbulatov P.I. On One Systemic Development Of The Problem Of Allocation //Internationals Colloquium über Anwendungen der Informatik und Mathematik in Architektur und Bauwesen- IKM? Bauhaus-Universitat Weimar? Http://www/uni-weimar/de/~ikm/Beitrag 140/1997.

57. Yu P.L. Cone convexity, cone extreme points, and nondominated solutions in decision problems with mltiobjectives// JOTA,1974.V.14.-N3.-P.319-377.

58. Yemelichev V. A.,Kravtsov M K., Yanushkevich O. A. JN solvability of vector problems on systems of subsets using a linear criteria convolution algorithm //Abstracts of the second International Conference «Mathematical algorithms».- Nizhny Novgorod, 1995.-P.21.