Книги, научные публикации
На правах рукописи
Темирова Лилия Гумаровна ДВУХУРОВНЕВОЕ МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ ЭВОЛЮЦИОННЫХ ПРОЦЕССОВ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ Специальность 05.13.18 - математическое моделирование,
численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Ставрополь-2004
Работа выполнена //Известия вузов. Северо-Кавказский регион.- 2003.- №4.- С.67-76.
в Карачаево-Черкесской государственной технологической академии 12. Касаева М.Д., Перепелица В.А., Темирова Л.Г. Прогнозная модель на кафедре Прикладная математика урожайности на базе линейного клеточного автомата //Современные аспекты экономики - 2003. - №4(32). - С.190-206.
Научный консультант: доктор физико-математических наук, профессор 13. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Математическая модель Перепелица Виталий Афанасьевич землепользования на базе нечетких множеств и клеточных автоматов //Электронный журнал Исследовано в России.- 2003.- С. 2429-2438,
Официальные оппоненты: доктор физико-математических наук, профессор zhurnal.ape.relarn.ru/articles/003/207.pdf.
Наац Игорь Эдуардович 14. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Об одном подходе к оценке глубины фрактальной памяти временных рядов уро доктор технических наук, профессор жайностей. Международный Российско-Узбекский симпозиум Урав Винтизенко Игорь Георгиевич нения смешанного типа и родственные проблемы анализа и информа тики, Нальчик - п.Эльбрус, 21-25 мая 2003 г.- Нальчик: НИИ ПМА
Ведущая организация: Кабардино-Балкарский государственный КБН - РАН, 2003. - С.59-61.
университет им. Бербекова Х.М., г. Нальчик 15. Перепелица В.А.,Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Прогноз ная модель урожайности на базе клеточных автоматов и нечетких мно жеств /Труды III Международной конференции Новые технологии в управлении, бизнесе и праве, г.Невинномысск, 2003, 30 мая 2003 г., - Невинномысск: ИУБиП, 2003. - С.163-167.
Защита состоится 12 марта 2004 г. в 16.00. часов на заседании диссертацион- ного совета Д 212.256.05 по присуждению ученой степени кандидата физико математических наук в Ставропольском государственном университете по адресу: 355009, г. Ставрополь, ул. Пушкина, 1, ауд.
С диссертацией можно ознакомиться в научной библиотеке СГУ по адресу:
г. Ставрополь, ул. Пушкина, 1.
Автореферат разослан л февраля 2004 г.
Формат 60х84 1/16 Подписано в печать Бумага офсетная Усл.печ.л. 1,1 06.02. Тираж 100 экз. Заказ Отпечатано в Издательско-полиграфическом участке Карачаево-Черкесской государственной технологической академии
Ученый секретарь 369000, г. Черкесск, ул. Ставропольская, 36.
диссертационного совета канд.физ.-мат. наук, доцент Л.Б.Копыткова 3. Темирова Л.Г., Петова Е.Х. Об одном подходе к моделированию про-
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
цесса формирования состава малых групп. Решение научно- технических и социально-экономических проблем современности /Сб. Актуальность проблемы. Диссертационная работа посвящена разра трудов IV научно-практической конференции. Часть II.- Черкесск: Изд- ботке методов математического моделирования дискретных слабо структу во КЧГТИ, 2002. - С.42-44. рированных процессов, для которых характерны множественность критери 4. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Моделирование экстре- ев, стохастичность, интервальность или нечеткость значений исходных дан мальных задач на графах с нечеткими данными /Труды участников ных. Дальнейшее развитие каждого такого процесса существенным образом Международной школы-семинара по геометрии и анализу памяти Н.В. зависит от его состояния на предыдущих этапах эволюционирования.
Ефимова, Абрау-Дюрсо, 5-11 сентября 2002 г. - Ростов-на-Дону: МГУ, Как часть этой проблемы в настоящей работе рассматриваются различ РГУ, 2002. - С.267. ные постановки задачи землепользования и предлагается двухуровневый 5. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Дискретное программи- подход к их моделированию. Классические подходы моделирования таких рование с нечеткими данными. Сб.науч.трудов V Всероссийского сим- задач оказываются недостаточными по той причине, что представление па позиума. Математическое моделирование экономических и экологи- раметров этих задач четкими числовыми значениями оказывается в принци ческих систем, г. Кисловодск, 17-19 октября 2002г.ЦКисловодск: пе неадекватным в силу их слабой структурированности, изменчивости во Изд.центр КИЭП, 2002. - С.7-10. времени и неопределенности.
6. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи Авторская концепция двухуровневого моделирования задач землеполь землепользования //Современные аспекты экономики. - Санкт- зования состоит в том, что исходные данные для многокритериальных задач Петербург. - 2002 г.- №15(28). - С.47-56. верхнего уровня должны базироваться на прогнозных значениях, получае 7. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Об одной задаче земле- мых на нижнем уровне моделирования. В свою очередь исходными данны пользования в условиях неопределенности. Математические методы и ми для нижнего уровня служат временные ряды, отражающие эволюцию информационные технологии в экономике, социологии и образовании: основных показателей рассматриваемых процессов. К настоящему времени Сб. статей X Международной научно-технической конференции.- 24-25 математическое моделирование на нижнем уровне исходных данных (т.е.
декабря 2002 г. - Пенза, 2002. - С.69-71. численных значений параметров, коэффициентов и т.п.) для классических 8. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Новый метод прогнози- оптимизационных моделей верхнего уровня находится еще в зачаточном рования на базе клеточных автоматов и нечетких множеств /Тезисы состоянии. Вместе с тем уже появилась ясность того, что наиболее подхо докладов VIII Международной конференции серии Нелинейный мир, дящим математическим аппаратом для моделирования задач верхнего уров г. Астрахань, 15-20 сентября 2003г. - Астрахань: ГУП Издательско- ня является инструментарий теории графов. При этом заслуживает внима полиграфический комплекс, Волга, 2003.- С.240. ния тот факт, что к настоящему времени отсутствуют достаточно эффектив 9. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г, Касаева М.Д. Построе- ные, имеющие полиномиальную трудоемкость, алгоритмы практически для ние прогнозной модели урожайности на базе клеточных автоматов и всех дискретных экстремальных задач. Поэтому актуальной является разра нечетких множеств /Менеджмент, экономика и финансы, региональ- ботка малотрудоемких приближенных алгоритмов, которые всегда или поч ное управление. Труды III Международной научно-практической ти всегда гарантируют нахождение приемлемых решений.
конференции Проблемы регионального управления, экономики, права Цель и задачи диссертационного исследования. Основной целью на и инновационных процессов в образовании, г. Таганрог, 10-13 сентяб- стоящей работы является разработка (на содержательном примере задач ря 2003 г. - Таганрог: Изд-во Таганрогского института управления и землепользования) двухуровневого подхода к математическому моделиро экономики, 2003. - С.182-185. ванию дискретных эволюционных процессов, числовые параметры которых 10. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г. Фрактальный анализ ус- являются слабо структурированными. Поставленная цель требует решения тойчивости развивающихся агросистем. Материалы III Международной следующих задач:
научно-практической конференции Математическое моделирование в - разработка общей структурной схемы двухуровневого моделирования и образовании, науке и производстве. Тирасполь, 17-20 сентября, 2003 г. численных методов его реализации;
- Тирасполь: РИО ПГУ, 2003. - С.56-59. - разработка в качестве основной составляющей модели нижнего уровня 11. Перепелица В.А., Тебуева Ф.Б., Темирова Л.Г., Касаева М.Д. Исполь- новых методов прогнозирования эволюционных процессов на базе ли зование инструментария клеточных автоматов для формирования про- нейных клеточных автоматов, математического аппарата теории нечет гнозных нечетких значений урожайностей на базе временного ряда ких множеств и инструментария теории детерминированного хаоса;
18 - осуществление анализа известных теоретико-множественных определе- ставить в виде следующего перечня:
ний операции суммирования нечетких множеств и вместе с тем пред- 1. Сформулирована авторская концепция двухуровневого моделирования ставление нового обоснованного определения операций суммирования и задач землепользования: математическая модель верхнего уровня - это сравнения нечетких весов для исследуемой задачи землепользования;
модель теории оптимизации, на базе которой строится и обосновывает - исследование вычислительной сложности рассматриваемых задач на ся наиболее целесообразное управление рассматриваемым процессом;
графах с нечеткими или интервально заданными весами ребер, пред- на нижнем уровне осуществляется моделирование исходных данных ставляющими урожайность;
для модели верхнего уровня;
исходными данными для нижнего уровня - исследование разрешимости с помощью классических подходов (в част- служат временные ряды, отражающие эволюцию основных показате ности, алгоритмов линейной свертки критериев) рассматриваемых экс- лей рассматриваемых эволюционных процессов;
изложена необходи тремальных задач на графах с интервальными весами;
мость многокритериального подхода и суть его реализации.
- разработка малотрудоемких алгоритмов для экстремальных задач по- 2. На базе инструментария фрактального анализа выявлены такие свойст крытия графа типовыми подграфами (паросочетаниями, звездами, 4- ва временных рядов, как долговременная память с оценкой ее глубины, циклами) и обоснование достаточных условий статистической эффек- трендоустойчивость, квазицикличность;
для выявления этих свойств тивности предлагаемых алгоритмов. разработан метод фазового анализа временных рядов;
на базе инстру Методы исследования. Для решения поставленных в работе научных ментария линейных клеточных автоматов и нечетких множеств разра задач использованы методы теории алгоритмов с оценками, теории графов, ботана новая прогнозная модель, включая алгоритмы ее валидации и многокритериальной оптимизации, теории вероятностей и математической вычисления оценок точности прогнозирования.
статистики, теории нечетких множеств и интервального исчисления, методы 3. В качестве конкретной реализации двухуровневого моделирования прогнозирования временных рядов. представлена математическая постановка экстремальных задач покры Достоверность и обоснованность полученных в диссертационной ра- тия графа 4-циклами (паросочетаниями, звездами);
показана неприме боте теоретических результатов и формулировок обеспечивается коррект- нимость известных в научной литературе определений операций сло ным применением аппарата теории графов, математического программиро- жения и сравнения нечетких весов;
представлено новое определение вания и теории вычислительной сложности алгоритмов, математической операций суммирования и сравнения нечетких весов, которые адекват статистики, математического аппарата нечеткой и интервальной математи- ны рассматриваемым задачам землепользования.
ки, методов теории детерминированного хаоса. Информационную базу ис- 4. Исследована на разрешимость с помощью алгоритмов линейной сверт следования составили аналитические и статистические материалы Госком- ки критериев векторная задача покрытия графа 4-циклами с интерваль стата России, в частности по Ставропольскому краю и Кабардино- ными весами;
осуществлено ее сведение к 2-критериальной задаче и Балкарской республике (КБР). Эффективность предложенных методов под- установлена ее неразрешимость.
тверждается валидацией результатов, полученных путем проведения чис- 5. В качестве базы для использования алгоритма линейной свертки разра ленных расчетов. ботан малотрудоемкий алгоритм покрытия графа 4-циклами и доказа На защиту выносятся следующие основные положения: ны достаточные условия, при которых он является статистически эф 1. Концепция двухуровневого моделирования эволюционных дискретных фективным.
процессов в условиях многокритериальности и неопределенности дан Список основных трудов по теме диссертации ных.
1. Темирова Л.Г. Полиномиально разрешимый подкласс теоретико 2. Конкретный алгоритм реализации фрактального анализа временных ря графовой модели для задачи землепользования /Тезисы II Междуна дов урожайности с целью выявления в них наличия долговременной па родной конференции Нелокальные краевые задачи и родственные мяти как предпосылки для построения прогнозной модели.
проблемы математической биологии, информатики и физики. КБН - 3. Построенная для нижнего уровня на базе инструментария клеточных ав РАН, 3-7 декабря 2001 г. - Нальчик, 2001. - С.45-46.
томатов и теории нечетких множеств математическая модель и метод 2. Темирова Л.Г. Статистически эффективный алгоритм для одной задачи прогнозирования урожайности основных культур, выращиваемых в зонах формирования целевых групп. Материалы Северо-Кавказской регио рискового земледелия.
нальной научной конференции молодых ученых, аспирантов и студен 4. Разработанные для верхнего уровня специальные подходы к моделирова тов Перспектива-2001.- Нальчик, 2001.- С.191-198.
нию задач землепользования с нечеткими весами, включая обоснование операций суммирования и сравнения, адекватных реальному содержанию 4 поставленной в соответствие вершине b. При этом ребру приписывает- задач землепользования.
5. Результаты анализа применимости классических подходов, в частности, ся вес. Если же пара рёбер e, e, удовлетворяющая W(0 ) = w(e ) + w(e ) алгоритмов линейной свертки критериев к конкретной задаче землеполь указанным условиям (10) и (11) отсутствует в данном графе, то соответ G зования, сформулированной как задача покрытия графа 4-циклами с интервальными весами.
ственно ребро не включается во множество.
6. Разработанный для верхнего уровня моделирования задачи землепользо Четвертый вычислительный этап состоит в том, что с помощью соот вания алгоритм отыскания оптимального покрытия графа 4-циклами, ветствующего алгоритма в двудольном графе (V, B,) выделяется оп D = включая обоснование достаточных условий его статистической эффек тимальное паросочетание, затем для каждого ребра, принадле M4 = {} тивности.
Научная новизна. Научную новизну диссертационного исследования жащего выделенному паросочетанию, в графе выделяется соответст M4 G содержат следующие положения:
вующая ему пара рёбер e и e, которая замыкает соответствующую цепь 1. Предложен двухуровневый подход к моделированию эволюционных в 4-вершинный цикл. Работа алгоритма за c = [v1,v2,v3] c = [v1,v0,v3,v2] задач землепользования в условиях многокритериальности и неопреде ленности данных.
вершается проверкой, все ли вершины исходного графа оказались по G 2. На базе R/S-анализа разработан и реализован метод фрактального анализа крытыми выделенными 4-циклами. В случае положительного исхода мно временных рядов с целью выявления в них долговременной памяти и жество выделенных циклов представляется в виде допустимого решения оценки степени применимости инструментария клеточных автоматов и задачи о покрытии графа 4-циклами.
нечетких множеств для построения прогнозной модели.
Пусть = (n)- сколь угодно медленно растущая функция от n, 3. В качестве реализации модели нижнего уровня построена прогнозная. (n, R)= {G}- множество всех n - вершинных графов (n) 0 модель на базе клеточных автоматов, а также разработаны алгоритмы прогнозирования, валидации и вычисления оценки погрешности резуль, в каждом из которых всякому ребру, приписан вес G = (V, E) e E татов.
;
. Для всякого n обозначим через под w(e) {1,2,3,..., R} R = R(n) (n, R) 4. С учетом принципиальной нечеткости исходных данных, получаемых на множество таких графов, для каждого из которых определен G (n, R) нижнем уровне, оценена степень пригодности известных теоретико множественных определений арифметических операций для нечетких ный алгоритм находит оптимальное покрытие 4-циклами. Если отноше множеств и предложены новые способы операций сложения и сравнения, (n, R) ние мощностей n, то алгоритм называется ста- отвечающие содержательному смыслу рассматриваемых задач земле 1 при (n, R) пользования.
5. В качестве математической модели для верхнего уровня сформулирована тистически эффективным. Достаточное условие статистической эффектив и исследована векторная задача покрытия графа 4-циклами и паросочета ности предложенного выше алгоритма представляет ниями. Первая из этих задач исследована для случая интервальных дан n Теорема 2. При выполнении неравенства алгоритм R ных: осуществлено ее сведение к 2-критериальной задаче и установлена 4 ln n + ее неразрешимость с помощью алгоритмов линейной свертки критериев является статистически эффективным.
(АЛСК).
В процессе своей работы алгоритм рассматривает каждое ребро 6. В качестве базы для использования АЛСК разработан малотрудоемкий данного графа G = (V, R) не более нескольких раз, откуда вычислительная оптимизационный алгоритм покрытия графа 4-циклами и доказаны дос сложность его первых трех этапов составляет. Отсюда вычис- таточные условия, при которых он является статистически эффективным.
O( E ) O(n2) Практическая ценность полученных результатов и их реализация.
лительную сложность алгоритма можно оценить через вычислительную Практическая значимость результатов исследования заключается в том, что сложность четвертого этапа (нахождения совершенного паросочетания):
предложенные подходы, математические модели и алгоритмы универсальны.
() O(n2) + O(n3) = O(n3) и позволяют решать широкий круг агроэкономических задач. Построенные ЗАКЛЮЧЕНИЕ на базе клеточных автоматов модель и метод прогнозирования временных рядов урожайности могут быть использованы всюду, где поведение рас Основные результаты, полученные в ходе исследований можно пред сматриваемого эволюционного процесса с памятью не подчиняется нор 16 мальному закону.
ставленное в главе 1 МДР невозможно определить системой линей X ={x} Предложенные методы, методики и алгоритмы моделирования на ниж ных равенств и неравенств, т.е. невозможно представить в виде многогран нем уровне были погружены в модельные и реальные экономические про ника в соответствующем пространстве.
цессы и оправдали себя. Их корректность подтверждается расчетами на Разработанный алгоритм состоит из подготовительного этапа, четы конкретных материалах прогнозирования;
оценки точности прогнозирова рех вычислительных этапов и заключительного этапа формирования резуль ния вычислены в процессе валидации по заказу Министерства сельского татов.
хозяйства Ставропольского края;
прогнозное значение урожайности озимой Подготовительный этап заключается в разбиении в данном - вершин n пшеницы за период с 1952 г. по 2002 год уклонялось от реального времен ном графе множества V на четыре равномощных подмножества G = (V, E) ного ряда в среднем не более, чем на 10%.
n Разработанная модель и математический аппарат их количественного Vs мощности,, (ребрам приписаны веса e E s = 1, Vs = m = анализа и прогнозирования включены в лекционные курсы следующих дис циплин: Теория рисков, Дискретное программирование с нечеткими ). Далее, для двух пар и строятся два двудольных w(e){1,2,....,R} V1,V2 V2,V данными, читаемых на факультете прикладной математики и информатики графа, где множество Est состоит из всех та Gst = (Vs,Vt, Est) 1 s < t 3, КЧГТА, а также использованы при выполнении курсовых и дипломных про ектов.
ких ребер, у каждого из которых один конец, а другой e = (v,v ) E v Vs Апробация работы. Результаты исследования и основные его положе конец.
v Vt ния докладывались и обсуждались на заседаниях научно-методического Второй этап состоит из двух вычислительных подэтапов. Работа подэ семинара кафедры прикладной математики (КЧГТА, г. Черкесск, 2001- гг.) и получили положительную оценку на следующих конференциях и сим- тапов заключается в том, что в каждом из двудольных графов и G12 G позиумах, проводимых различными академическими учреждениями и выс осуществляется нахождение оптимальных совершенных паросочетаний, шими учебными заведениями России:
которые обозначим соответственно через и M23. Для нахождения каж M - на IV Всероссийском симпозиуме Математическое моделирование и дого из таких паросочетаний можно воспользоваться каким-либо компьютерные технологии (Кисловодск, 2001);
Mst = {e} - на Северо-Кавказской региональной научной конференции молодых известным алгоритмом (например, венгерским методом или алгоритмом ученых, аспирантов и студентов ПерспективаЦ2001 (Нальчик, 2001);
Лоулера).
- на II Международной конференции Нелокальные краевые задачи и род Объединяя паросочетания и, получаем m пар пересекаю M M ственные проблемы математической биологии, информатики и физики щихся рёбер вида. Такие пары рёбер объединяем e = (v1, v2 ), e = (v2, v3 ), (Нальчик, 2001);
- на IV научно-практической конференции аспирантов и студентов Ре в 3-вершинные цепи вида, множество этих цепей обозначим c = [v1,v2,v3] гиональная экономика управления и права (Черкесск, 2002);
.
C = {c} - на Международной школе-семинаре по геометрии и анализу памяти Третий этап состоит в построении специального двудольного графа Н.В. Ефимова (Абрау-Дюрсо, база отдыха Ростовского госуниверситета. Доля с равномощными долями мощности B = {b} D = (V4, B,) V4 = B = m Лиманчик, 2002);
- на Х Международной научно-технической конференции Математиче состоит из вершин, которые поставлены во взаимнооднозначное соот b B ские методы и информационные технологии в экономике, социологии и ветствие цепям. Если ребро содержится в, то оно опре с С 0 = (v0,b) образовании (Пенза, Приволжский Дом знаний, 2002);
- на III Международной конференции Новые технологии в управлении, деляется следующим образом: ребро включается в состав 0 = (v0,b) бизнесе и праве (Невинномысск, 2003г.);
тогда и только тогда, когда в исходном графе множество E со G = (V, E) - на VIII Международной конференции серии Нелинейный мир (Астра держит пару рёбер e, следующего вида:
хань, 2003).
,, (10) Теоретические и практические результаты диссертационной работы e = (v0, v1) e = (v0, v3 ) использованы при выполнении НИР по гранту РФФИ, проект № 00-01 где v1 и v3 являются висячими вершинами цепи 00652 Математическое моделирование структуры слабо формализованных, (11) систем в условиях неопределенности. c = [v1, v2, v3] 6 Публикации. Материалы диссертации опубликованы в 4 научных ком, где. Подграф x = (Vx, Ex ),, w(e) = [w1(e), w2(e)] w(e1) w2(e) Vx V статьях (из них 2 - в рецензируемых журналах) и в 11 тезисах докладов.
представляет собой допустимое решение рассматриваемой задачи.
Ex E Структура и объем работы. Диссертация состоит из введения, четы Обозначим через МДР рассматриваемой задачи, на котором опреде X = {x} рех глав, заключения, приложений и списка литературы, содержащего лена интервальная целевая функция (ИЦФ) наименования.
(8) КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
w(x) = w(e) max eEx Во введении обосновывается актуальность темы диссертационного ис или ИЦФ следования, сформулирована цель работы, описана структура и дан краткий. (9) w(x) = min w(e) max eEx обзор работы, изложены основные научные результаты, выносимые на за щиту, раскрыта научная новизна и практическая значимость полученных Значение этих ИЦФ можно получить из свойств операций сложения результатов.
интервалов и сравнения интервалов, представляющих значение ИЦФ В главе 1 дано содержательное описание предложенного двухуровне, где. Под решением интер w(x)= [w1(x), w2(x)] wi (x)= (x), i = 1, wi вого подхода к моделированию эволюционных агроэкономических процес eEx сов, показатели которых не подчиняются нормальному закону распределе вальной задачи понимается такой элемент x0 X, на котором значение ния.
ИЦФ (8) или (9) достигает требуемого экстремума.
Математическая модель верхнего уровня - это модель теории оптими В случае интервальных весов нахождение оптимума наталкивается на зации, на базе которой строится и обосновывается наиболее целесообразное проблему выбора наиболее целесообразного решения из множества несрав управление рассматриваемым процессом. На нижнем уровне осуществляет нимых альтернатив. Отношения предпочтения, эквивалентности и несрав ся моделирование исходных данных для модели верхнего уровня.
нимости определены в главе 3 настоящего исследования.
На верхнем уровне формируются теоретико-графовые модели задач Отношения предпочтения и несравнимости порождают на МДР X па землепользования. В качестве таких постановок рассмотрены задачи покры ~ ретовское множество (ПМ), состоящее из паретовских оптимумов X X тия графа 4-циклами, звездами и ребрами. Если задача формулируется на (ПО). графе, то ее допустимое решение представляет собой такой ос G =(V,E) ~ Определение 3. Для задачи с ИЦФ (8) решение x X называется ПО, товный подграф x =(V, Ex), Ex E, в котором каждая компонента связ ~ если не существует такого, что x* f x.
x* X ности является соответственно 4-циклом, звездой или ребром. Эти задачи В качестве искомого решения сформулированной задачи можно рас являются многокритериальными, т.е. на множестве допустимых решений ~ (МДР) {x} определена векторная целевая функция (ВЦФ) X = сматривать как ПМ X, так и используемое в многокритериальной оптими, F(x)= (F1(x), F2(x),..., FN (x)) зации понятие ПМА X.
~ Определение 4. ПМА есть подмножество минимальной мощ X X состоящая из критериев вида MAXSUM ности, содержащее по одному представителю на каждое значение, w(x), =1, N1, N1 N F (x)= (e) max w ~ eEx, где есть значение ИЦФ (8).
x X w(x) и критериев вида MAXMIN Теорема 1. Для всякого -вершинного графа ( n кратно 4), интер n G, F (x)= min w (e) max, = N1 + 1, N вальная задача покрытия графа 4-циклами с критериями вида MAXSUM не eEx разрешима с помощью АЛСК.
где w (e)- веса, приписанные ребрам e E данного графа. Критерии вида В качестве базы для реализации АЛСК предлагается приближенный MAXSUM представляют собой обычно экономические показатели, а крите алгоритм покрытия графа 4-циклами и произведено обоснование его стати рии вида MAXMIN - агроэкологические показатели, например, процентное стической эффективности. Необходимость разработки такого алгоритма обусловлена тем обстоятельством, что для решения рассматриваемых задач содержание гумуса в почве. ВЦФ определяет в МДР X паретовское F(x) верхнего уровня неприменимы какие-либо известные алгоритмы, в том чис ~ множество (ПМ) X. Искомым решением векторной N - критериальной ле и алгоритмы линейного или целочисленного программирования. Указан ная неприменимость, в свою очередь, обусловлена тем фактом, что пред 14 тен варианту x2 ), или в другой терминологии, x2 доминируется вариантом задачи является полное множество альтернатив (ПМА) X. Термин ПМА ~ означает подмножество, удовлетворяющее двум условиям:
X X x1, если выполняются неравенства,, (x1 f x2) (x1) (x2) w(x1) w(x2 ) 1. Мощность - минимальна;
X среди которых хотя бы одно является строгим (равенства, (x1) = (x2 ) ~ * * 0 * 2., где.
). Эквивалентность этих вариантов обозначаем через x1 ~ x2.
F(X )= F(X) F(X )={F(x): x X } X X w(x1) = w(x2) В главе 2 предлагаются инструментальные и математические методы Определение 2. Варианты x1 и x2 являются несравнимыми(x1 x2 ), моделирования временных рядов, которые обладают долговременной памя если в паре интервалов,, один из них является строгим [ (x ), w(x )] j = 1, j j тью и вместе с тем в характере их поведения проявляется хаотичность. На личие такой памяти исключает независимость наблюдаемых значений эле- включением другого.
В главе 4 исследуется разрешимость интервальной задачи покрытия ментов временных рядов, что, в свою очередь является причиной неподчи графа 4-циклами с помощью алгоритмов линейной свертки критериев нения этих рядов нормальному закону распределения. Этот факт подтвер ждается также такими результатами статистического анализа, как аномально (АЛСК). Предлагается малотрудоемкий алгоритм покрытия графа 4 циклами с оценкой его эффективности.
большие значения коэффициентов эксцесса и асимметрии. С учетом выяв Следует отметить, что интервальные задачи являются крайним случаем ленных ситуаций становится неправомерным использование классических методов прогнозирования, которые базируются на вычислении скользящей неопределенности, т.к. возникают в условиях неточных данных параметров средней и авторегрессии. задачи. Вопрос разрешимости интервальной задачи покрытия графа 4 циклами с помощью АЛСК до настоящего времени оставался открытым. В В главе осуществлено построение прогнозной модели для нижнего уровня на базе аппарата нечетких множеств и клеточных автоматов. Разра- главе 4 обосновывается сведение интервальной задачи покрытия графа 4 ботаны и представлены методы и алгоритмы для выявления фундаменталь- циклами к 2-критериальной и доказывается ее неразрешимость с помощью АЛСК, а следовательно, и соответствующей ей интервальной задачи.
ных качественных и системных свойств, а именно: глубина долговременной памяти и ее оценка, мера хаотичности или, наоборот, трендоустойчивости, Алгоритмы линейной свертки критериев являются традиционными ме тодами нахождения парето-оптимальных решений многокритериальных квазицикличность, самоподобие.
задач. На сегодняшний день построение эффективных АЛСК для многокри Предлагаемая новая прогнозная модель для временного ряда с памятью состоит из следующих пяти этапов, т.е. отдельных алгоритмов или проце- териальных задач остается одной из основных проблем оптимизации.
Утверждение 1. Для любого вектора дур.
Этап 1. Оценка степени прогнозируемости данного семейства времен элемент x*, = = (1,2,...,N ): = 1, > 0, = 1,2,..., N ных рядов осуществляется на базе фрактального анализа некоторой выборки N из этого семейства. На выходе вычислительного алгоритма фрактального анализа получаются оценки следующих характеристик для рассматривае максимизирующий на МДР X линейную свертку критериев N мых рядов: признаки наличия трендоустойчивости и долговременной памя (x), F (x)= F (x) целевых функций F = 1,2,..., N, является ПО.
ти, оценка ее глубины;
цвет шума, достаточно удаленный от зоны белого = шума.
Заметим, что АЛСК не всегда гарантируют нахождение всех ПО Этап 2. Преобразование исходного числового временного ряда (ВР) в ~ ~ ~. Если ПМ индивидуальной интервальной задачи и 2 x X X лингвистический временной ряд (ЛВР) с целью создания базиса памяти клеточного автомата. Для выполнения этапа 2 разработан лалгоритм преоб- критериальной задачи содержит такой элемент x*, на котором не достигает разования ВР в ЛВР. На начальном этапе этого алгоритма формируется максимума значение свертки F (x) ни при каком, то эти задачи терм-множество характерных состояний исходного ВР, в частности U ={u} неразрешимы с помощью АЛСК. Из неразрешимости хотя бы одной инди трехэлементное множество : - низкая урожайность, U = {Н, С, В} u = H видуальной задачи вытекает неразрешимость соответствующей массовой u = B u = C - средняя урожайность, - высокая урожайность. Алгоритм пре задачи.
образования ВР в ЛВР является вполне детерминированным, за исключени В качестве частного случая задачи на графах с НВ сформулируем ин тервальную экстремальную задачу на графах. В заданном n -вершинном ем процедуры принятия решения о мощности U формируемого терм графе каждое ребро взвешено интервалом, т.е. отрез G = (V, E) e E w(e) множества (экспертная оценка).
8 ставляется в виде нечеткого множества Этап 3. Алгоритм формирования оперативной памяти клеточного авто (3) мата. Эта память может иметь комбинаторное или теоретико-графовое, w(z1) (+) w(z2 )={((w (z1)+ w (z2 ));
(w (z1)+ w (z2 ))): W } представление. В последнем случае она строится в виде множества 2 где функция принадлежности при этом определяется выражением:
дольных ориентированных графов, в каждом из которых вершины правой L (z1, z2 ) (4), доли взаимнооднозначно представляют собой элементы терм-множества, U (w (z1) (+) w (z2 ))= N (z1, z2 ) а вершины левой доли - фиксированные l - конфигурации;
значения где, L (z1, z2 )= w (z1) (z1)+ w (z2 ) (z2 ), где l = 1,2,..., L L- глубина памяти ЛВР. Дугам этих орграфов приписаны,.
N (z1, z2 )= w (z1)+ w (z2 ) W веса, означающие собой частости переходов заданной конфигурации в соот ветствующие состояния из.
Математическая постановка рассматриваемой задачи завершается оп- U = {u} ределением бинарной операции сравнения. Практически все известные ме Этап 4. Алгоритм формирования прогноза для данного ЛВР ui, тоды сравнения оперируют исключительно только функциями принадлеж. Алгоритм вычисляет и представляет прогнозируемый элемент i =1,2,.., n ности, без учета численных значений элементов-носителей сравниваемых НВ. Такой способ сравнения не соответствует содержательному смыслу за un+1 в виде нечеткого множества (НМ), где - зна U ( ) = {(u, )} n +1 j j j дачи землепользования. Предлагаемый в настоящей главе метод упорядоче чение функции принадлежности элемента. По u U, j = 1,2,..., m, m = U ния НВ по предпочтительности базируется на процедуре полной дефазифи j кации. Прежде, чем приводить описание этой процедуры, отмечаются усло скольку перечень элементов является известным, то формирование u U j вия, при которых операция сравнения считается определенной. Рассматри прогноза в виде НМ сводится к вычислению значений , путем j = 1, m ваются два допустимых решения, на которых ЦФ (1) принимает x1, x2 X j значения в виде двух НВ суммирования и нормирования весов соответствующих дуг в последова,,. (5) тельности орграфов, затребованных из оперативной памяти. По своему со F(x )= {(w(x );
(x ))} {Н,С, В} j = 1, j j j держательному определению эти веса отражают долговременную память о Тогда, рассматривая величины и в качестве максимизи w(x ) (x ) j j поведении рассматриваемого ЛВР, а затребованная последовательность орг рафов определяется завершающим отрезком длины в рассматриваемом L руемых показателей, можно утверждать, что вариант x1 предпочтительнее ЛВР.
варианта x2, если выполняются следующие неравенства Этап 5. Алгоритм трансформации полученного прогноза в виде нечет (6) кого терм-множества в числовой прогноз. В качестве подходящих числовых w (x1) w (x2 ), (x1) (x2 ),, {Н,С, В} значений элементов, где u выбираются в ВР ближай u U, j = 1,2,...,m, среди которых хотя бы одно является строгим.
j j В случае невыполнения условия (6) предлагается применить новый шие к ним низкие, средние и высокие урожайности, которые затем усред способ сравнения двух НВ. Для этого сначала вычисляются величины:
няются. Применяя к полученному нечеткому множеству операцию дефази L(x )= w(x ) (x ), M (x )= (x ), )= (x ), j =1,2, фикации имеем прогнозное значение урожайности в обычном числовом ви N(x j j j j j j w j 0 0 W W W де.
а затем и соответствующие им носители и степени принадлежности:
Для проведения валидации, т.е. проверки соответствия полученных на,. (7) w(x )= L(x ) M (x ) (x )= L(x ) N(x ) основе модели данных реальному процессу, последовательно рассматриваем j j j j j j лингвистические временные ряды Пару условимся называть сверткой нечетких весов. Для (w(x );
(x )) j j m = n, ui,i = 1,2,...,m, - r, - k r =1, n упорядочения вариантов, по предпочтительности осуществляет j = 1, x j которые получаются путем последовательного удаления из ЛВР последних ся операция сравнения интервалов,. При этом границы [(x ), w(x )] j = 1, r его членов. Для каждого фиксированного индекса m строим прогноз j j этих интервалов рассматриваются в качестве максимизируемых показате терма um+1, представляемого в виде НТМ.
U = {(H;
H ),(C;
C ),(B;
B )} m+ лей.
Пусть, в полученном НТМ, среди чисел , C, макси Um+ H B Определение 1. Вариант x1 предпочтительнее варианта x2 (эквивален мальным является то число ,, у которого индекс совпада {H,C, B} 12 k k ляет собой звезду,, V2k V2, с центром ет с термом um+1 рассматриваемого ряда. Тогда, говорим, что для рассмат- xk = ({vk},V2k, Ex ) vk V1 Ex Ex риваемого индекса m прогнозная нечеткая модель привела к непротиворе- k в определенной вершине vk из первой доли и множеством висячих V1 V чивому прогнозу. В противном случае, говорим о противоречивом прогнозе вершин из второй доли. На МДР графа определена целевая функция G V для терма um+1.
(ЦФ) следующим образом. Для каждой пары,, F(x) max (vk, vi ) vk V Валидация результатов прогнозирования осуществлена на примере вре k,i определен объем ожидаемого урожая культуры на поле.
vi V2 W k i менных рядов урожайности озимой пшеницы по Ставропольскому краю и m КБР. Для числового прогноза отклонение от реальных значений в среднем k Допустимым является всякое такое решение,, для x = (V1,V2, Ex ) Ex = не превысила 10%. UEx k = В главе 3 сформулирована задача верхнего уровня моделирования, ко которого выполняются неравенства торая представляет собой теоретико-графовую модель задачи землепользо w(e) dk, k = 1, m ;
X = X(G) = {x} - k eEx вания с нечеткими данными.
Для математической постановки задачи землепользования введены множество всех допустимых решений на графе. Если целевой функцией G следующие обозначения. Считается заданным n -вершинный граф, в кото (ЦФ) является экономический эффект, то она определяется на МДР F(x) ром:
k = 1,2,..., m - индекс, которым занумерованы выращиваемые в хозяйст X следующим образом:
m m ве культуры;
i = 1,2,..., n - индекс, которым занумерованы засеваемые этими (1) F(x) = w(e) = w(e) max.
ck сk культурами поля;
c - стоимость единицы -ой культуры;
si - площадь -го k k k i k =1 k = k eEx eEx Задача состоит в том, чтобы найти максимизирующее значение ЦФ (1) поля;
dk - директивное ограничение на минимальный объем выхода культу решение, т.е. построить и обосновать достаточно эффективный алгоритм ры ;
k G = (V1,V2, E)- двудольный граф, в котором вершины первой доли нахождения указанного оптимума. При верификации модели возникла про, а вер перенумерованы индексами культур V1 = {v1,...,vk,...,vm} k = 1,2,..., m блема адекватного суммирования нечетких весов. Анализ известных теоре тико-множественных операций суммирования нечетких множеств показал шины второй доли перенумерованы индексами полей V2 = {v1,...,vi,...,vn} их несоответствие содержательному смыслу суммирования НВ в ЦФ (1).
;
G i = 1,2,..., n E = {e}- множество ребер графа, которое содержит ребро Этот факт обусловил приведение нового способа суммирования л(+) не тогда и только тогда, когда в прогнозируемом году разрешается e = (vk,vi ) четких весов, основанный на принципе частичной дефазификации. Суть этого суммирования состоит в следующем. Если конкретное допустимое засевать культуру k на пахотные угодья поля i. Каждому ребру, e E k k k,i решение состоит из звезд,,, то НВ x X(G) z = (vk, E ) vk V1 k = 1, m приписан вес, представляющий собой нечеткое множество W k,i k k k k k,i k k k и являющееся результатом w(e)=W ={(WH,i ;
H ),(WC,i ;
C ),(WB ;
B)} одной звезды z определяется выражением:
w(z ) k k,i k k k (2) моделирования на нижнем уровне. Элемент-носитель, WH,i = ck si U w(z )= (+) w(e)= {(w(z );
): W } H k eEx k k k k,i ( ) содержательно означает ожидаемый WC,i = ck si UC,i, WB,i = ck si U B где значение w(zk ) элементов-носителей определяется их скалярным объем выхода продукции в рублях культуры k с поля i в случае низкого k,i k k,i суммированием W k = 1, m w(zk )= (e),,, а функция принад (среднего, высокого) прогнозируемого урожая. В общем w U (UC,i,U ) H B k eEx k случае единицей измерения каждого веса, могут быть W,i {H,C, B} k лежности вычисляется операцией дефазификацией.
рубли, протеиновые единицы и др.
Для определения операции суммирования НВ, относящихся к различ Теоретико-графовая постановка сформулированной выше задачи пред k1 k ставляет собой задачу покрытия 2-дольного графа звездами. ным культурам рассматриваются две звезды z1 = z и z2 = z, для G = (V1,V2, E) k1, k Допустимое решение представляет собой такой его остовный подграф которых вычислены их НВ согласно принципа частичной дефазификации (2). Результирующая сумма (+) нечетких весов этих двух культур пред, Ex E, в котором каждая компонента связности представ x = (V1,V2, Ex ) 10
Книги, научные публикации