Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
22
ДНІПРОПЕТРОВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
ПОЗДНЯКОВА Анастасія Юріївна
УДК 519.8
РОЗВИТОК ДЕЯКИХ МЕТОДІВ МОДЕЛЮВАННЯ ДИСКРЕТНИХ НЕЛІНІЙНИХ СИСТЕМ
01.05.02 –математичне моделювання та обчислювальні методи
Автореферат дисертації на здобуття наукового ступеня
кандидата фізико - математичних наук
Дніпропетровськ –
Дисертацією є рукопис.
Робота виконана в Запорізькому державному університеті Міністерства освіти і науки України.
Науковий керівник доктор фізико-математичних наук, професор Перепелиця Віталій Опанасович, Запорізький державний університет, завідувач кафедри економічної кібернетики
Офіційні опоненти:
доктор фізико-математичних наук, старший науковий співробітник Донець Георгій Панасович, Інститут кібернетики ім. В. М. Глушкова НАН України, завідувач відділом економічної кібернетики;
кандидат фізико-математичних наук, доцент Бурдюк Володимир Якович, Дніпропетровський національний університет, кафедра обчислювальної математики та математичної кібернетики, доцент.
Провідна установа
Інститут проблем машинобудування ім. А. М. Підгорного НАН України, відділ математичного моделювання і оптимального проектування, м. Харків.
Захист відбудеться “ 02 ” листопада 2001 р. о 16 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті за адресою: 49050, м. Дніпропетровськ, просп. К.Маркса, 35, корп.3, ауд.25.
З дисертацією можна ознайомитись у науковій бібліотеці Дніпропетровського національного університету за адресою: 49050, м. Дніпропетровськ, вул. Козакова, 8.
Автореферат розісланий “ 29 ” вересня 2001 р.
Вчений секретар
спеціалізованої вченої ради Турчина В. А.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. У нинішній час спостерігається підвищений інтерес до складних дискретних систем, більшість з яких є нелінійними. Для їх адекватного опису потрібні нові, порівняно з добре розвинутими методами лінійного аналізу, методи моделювання. У дисертаційній роботі їх розробка та дослідження проводились за трьома напрямками.
По-перше, узагальнення математичної моделі задачі інвестора з урахуванням дисконтування, що призвело до перетворення її на нелінійну, суттєво змінило властивості цієї задачі і викликало необхідність розробки нових методів та надало можливість використовувати нову математичну модель у реальних економічних умовах.
По-друге, важливою науковою проблемою є розробка адекватного універсального підходу до розв’язання багатокритеріальних задач комбінаторної оптимізації, який спирається на методи математичної візуалізації та методи нелінійної динаміки. Також принциповим із точки зору теоретичного дослідження та практичного вживання є розробка в дисертаційному дослідженні комбінованого підходу до аналізу часових рядів, який поєднує класичні статистичні методи з методами нового наукового напряму –теорії динамічного хаосу.
По-третє, аналіз нових базових моделей нелінійної динаміки (динамічних систем із джокером та фрактальних графів), які удосконалюють математичне моделювання, має теоретичну та практичну цінність.
Отже, обрана тема, у межах якої проведено аналіз та модифікацію деяких математичних моделей дискретних нелінійних систем та розвинуто методи їх математичного моделювання в умовах неповних даних (на базі часового ряду), є актуальною.
Зв’язок роботи з науковими програмами, планами, темами. Проведені в дисертаційній роботі дослідження виконані в рамках держбюджетних тем “Дослідження екстремальних задач в умовах невизначеності та розробка методів їх розв’язання” (№ ДР 0197У012777) та "Математичне моделювання, розробка методів багатокритеріального оцінювання для задач підтримки прийняття рішень в умовах невизначеності, розробка програмного забезпечення для візуалізації методів прийняття рішень, застосування методів теорії катастроф, детермінованого хаосу та фрактальної геометрії" (№ ДР 0100У001723).
Мета і задачі дослідження полягають у виконанні таких розробок: аналіз та модифікація математичної моделі задачі інвестора для випадку довгострокового інвестиційного процесу; розвиток адекватного універсального підходу до розв’язання багатокритеріальних задач дискретної оптимізації; розробка комбінованого підходу до аналізу часових рядів (математичне моделювання дискретних нелінійних динамічних систем в умовах неповних даних); розв’язання задачі тестування динамічних систем на присутність джокера; одержання оцінок числових характеристик повних передфрактальних та фрактальних графів.
Об’єктом дослідження є математичні моделі дискретних нелінійних систем, а саме математична модель задачі інвестора, нелінійні динамічні системи та фрактальні графи. У дослідженнях було використано методи комбінаторної оптимізації, теорії розкладів, математичної візуалізації, нелінійної динаміки та теорії графів.
Наукова новизна одержаних результатів. У дисертації вперше сформульовано постановку задачі інвестора з дисконтуванням, яка є модифікацією відомої задачі комбінаторної оптимізації, досліджено її властивості, розроблено поліноміальний алгоритм розв’язання одного підкласу модифікованої задачі.
Розроблено метод аналізу структури образу критеріального простору векторної задачі комбінаторної оптимізації, що базується на методах математичної візуалізації та нелінійної динаміки.
Розроблено метод математичного моделювання дискретних нелінійних динамічних систем в умовах неповних даних (на базі часового ряду), який синтезує класичні статистичні методи аналізу часових рядів та методи детермінованого хаосу.
Проаналізовано нові базові математичні моделі –динамічні системи з джокером та фрактальні графи. Запропоновано метод тестування системи на наявність джокера. Одержано оцінки числових характеристик повних передфрактальних та фрактальних графів.
Вірогідність та обґрунтованість одержаних результатів. Дослідження, які проведені в роботі, базуються на відомих результатах дискретної оптимізації, теорії графів та теорії детермінованого хаосу. Вірогідність отриманих результатів підтверджується коректністю постановок розглянутих задач, строгістю математичних викладок, математичним обґрунтуванням застосованих методів. Для ряду задач проведені модельні експерименти на ПЕОМ, числові результати яких є підтвердженням теоретичних результатів досліджень.
Практичне значення одержаних результатів. Одержана математична модель задачі інвестора з дисконтуванням може бути використана для довгострокового планування інвестиційного процесу.
Розроблена інтерактивна автоматизована процедура побудови математичної моделі на базі часового ряду може бути застосована до аналізу реальних систем, зокрема, економічних.
Запропонований критерій наявності джокера в експериментальних даних дасть змогу відрізняти системи з потенціальною можливістю катастроф від динамічних систем із складною поведінкою.
Одержані оцінки топологічних інваріантів повних передфрактальних графів можуть бути використані при розв’язанні оптимізаційних задач на графах.
Частина результатів використана для виконання робіт за вищезазначеними науковими темами, а також у навчальному процесі в Запорізькому державному університеті.
Особистий внесок здобувача. У працях, що написані у співавторстві, дисертанту належать: [1] –доведення теореми про неспівпадання множини оптимальних розв’язків задач інвестора з дисконтуванням та без дисконтування з критерієм MINSUM; [3, 9, 14] –застосування методу узагальненого часового ряду до двокритеріальної задачі інвестора; [4] - доведення леми та теорем про оцінки числових характеристик повних передфрактальних графів; [4, 10-11] –отримання формули розрахунку фрактальної вимірності повного фрактального графу; [5, 17] – розробка методу аналізу структури образів критеріального простору; [6, 15] –обґрунтування можливості застосування графічного тесту хаосу для виявлення присутності точкового та інтервального джокера за експериментальними даними; [7, 12-13] –розробка алгоритму вилучення часткового лінійного тренду та процедури розрахунку фрактальної вимірності економічних часових рядів; [8] –встановлення неспівпадання множини оптимальних розв’язків двокритеріальних задач інвестора з дисконтуванням та без дисконтування; [16] – дослідження стійкості множини альтернатив задачі інвестора з дисконтуванням .
Праці [1, 3-4, 8-9, 11-12, 16-17] опубліковані у співавторстві з В.О.Перепелицею та Л.Н.Сергєєвою; [7] –із П.О.Мачковським, Л.Н.Сергєєвою, О.М.Стрюком; [10] –із В.О.Перепелицею, Л.Н.Сергєєвою та В.П.Пінчуком; [5-6, 13, 15] –із Л.Н.Сергєєвою; [14] –із В.О.Перепелицею.
Апробація результатів дисертації. Окремі результати дисертаційної роботи доповідались на: ІV Міжнародній конференції “Математика. Комп’ютер. Освіта” (Пущино, 1997 р.); Міжнародному колоквіумі математиків “IKM’” (Веймар, 1997 р.); Міжнародній науковій конференції “Статистичний та прикладний аналіз часових рядів” (Брест, 1997 р.); науково-практичній конференції “Проблеми становлення ринкової економіки: інформаційне та фінансове забезпечення діяльності підприємницьких структур” (Севастополь, 1998 р.); Міжнародній науковій конференції “Розробка та застосування математичних методів у науково-технічних дослідженнях” (Львів, 1998 р.); VI Міжнародній конференції “Математика. Комп’ютер. Освіта” (Пущино, 1999 р.); VII Міжнародній конференції “Математика. Економіка. Екологія. Освіта” (Ростов-на-Дону, 1999 р.); XXI Науковому семінарі “Дискретна математика” (Одеса, 1999 р.); ІІ Всеукраїнській конференції “Сучасні економіко-математичні методи у ринковій економіці” (Київ, 2000); Міжнародній науково-практичній конференції “Ризикологія в економіці та підприємництві” (Київ, 2001); ІІ Міжнародній науково-практичній конференції “Проблеми впровадження інформаційних технологій в економіці та бізнесі” (Ірпінь, 2001); щорічних наукових конференціях у Запорізькому державному університеті (1997-2001 рр.).
Дисертаційна робота в цілому обговорювалась на науковому семінарі кафедри економічної кібернетики Запорізького державного університету, міжвузівському науковому семінарі “Актуальні проблеми прикладної математики та механіки” в Запорізькому державному університеті (2000 р.).
Публікації. Основні результати дисертації викладено в 17 наукових працях, із них 9 статей у збірниках наукових праць (5 статей у наукових фахових виданнях), 4 матеріали та 4 тези доповідей на міжнародних наукових конференціях.
Структура та обсяг роботи. Дисертаційна робота складається зі вступу, п’яти розділів, висновків, списку використаних джерел та додатків. Повний обсяг дисертації становить 153 сторінки, серед яких рисунки (30), таблиці (5), додатки (1) займають 20 сторінок, бібліографія подається на 10 сторінках і нараховує 116 найменувань.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі обґрунтовано актуальність теми дисертаційної роботи; зазначено її зв’язок з науковими програмами, планами, темами; сформульовано мету і задачі дослідження; подано характеристику наукової новизни, теоретичного та практичного значення одержаних результатів; відзначено особистий внесок здобувача в публікаціях, виконаних у співавторстві, а також ступінь апробації результатів.
У першому розділі зроблено огляд стану досліджуваної проблеми і вибір напрямків досліджень.
Дисертаційна робота присвячена аналізу та модифікації математичних моделей дискретних нелінійних систем та розробці методів математичного моделювання дискретних нелінійних систем в умовах неповних даних.
Перша базова математична модель, що досліджується (математична модель задачі інвестора), має відношення до класу комбінаторних задач дискретного програмування. Значний внесок у розвиток дискретного програмування зроблено вітчизняними вченими, імена яких відомі як у нашій державі, так і за її межами. Це, перш за все, академіки В.М.Глушков, В.С.Михалевич, І.В.Сергієнко, М.З.Шор, Ю.Г.Стоян, доктори фіз.-мат. наук Ю.Ю.Червак, В.В.Шкурба, В.О.Трубін, В.О.Перепелиця, О.М.Кісельова, С.В.Яковлєв, Г.О.Донець, О.О.Ємець та інші. На сучасному етапі дискретне програмування розвивається в багатьох напрямках. Увага дисертаційної роботи зосереджена на двох із них –це застосування дискретної оптимізації в економіці та векторна (багатокритеріальна) оптимізація.
При математичному моделюванні реальних економічних процесів за допомогою класичних методів виникає необхідність урахування специфічних властивостей економічного середовища, що призводить до модифікації математичної моделі (зміни функцій цілі та обмежень). Прикладом такої модифікації є введення в математичну модель дисконту часу –операції, що часто застосовується в економічних розрахунках. Дисконтування дозволяє урахувати нерівноцінність витрат та результатів, що відносяться до різних моментів часу. Так, у роботі Л.В.Тонкова та О.Г.Ченцова досліджується проблема оптимального вибору маршруту в умовах дисконтування часу, тобто розглядається модифікація задачі комівояжера.
До якості багатьох економічних, технічних, організаційних рішень майже завжди ставлять одночасно декілька (найчастіше суперечливих) вимог. Тобто, принциповою рисою практично будь-якого проекту є його конфліктність та багатокритеріальність. При розв’язанні векторних (багатокритеріальних) задач дискретної оптимізації, для яких не існує ефективних алгоритмів, із зростанням розмірності задачі виникають певні труднощі. Це пов’язано з властивістю множини припустимих розв’язків векторних задач дискретної (комбінаторної) оптимізації –її потужність експоненціально залежить від розмірності задачі. Тобто, якщо поліноміального алгоритму знаходження множини альтернатив не існує, то для пошуку оптимального розв’язку необхідно здійснити перебір всіх варіантів, але зі зростанням розмірності його не зможе здійснити ніяка ЕОМ. Крім того, існують повні задачі, тобто такі, у яких збігаються множина припустимих розв’язків та множина альтернатив, яку треба знайти.
У роботі Е.Гірліха, В.О.Перепелиці та Л.Н.Сергєєвої доведена властивість важкорозв’язуваності класичної задачі інвестора в багатокритеріальній постановці. Із метою подолання обчислювальних складностей, обумовлених цією властивістю, запропоновано новий підхід одержання якісних (асимптотичних) характеристик множини припустимих розв’язків досліджуваних задач, який базується на методах математичної візуалізації та нелінійної динаміки. Певні кроки в розробці методів візуалізації стосовно задач неперервної багатокритеріальної оптимізації були виконані групою московських учених під керівництвом А.В.Лотова.
Нелінійна динаміка (англійський термін nonlinear science –нелінійна наука) фокусує свою увагу на нових типах поведінки в нелінійних системах, а саме, динамічному хаосі –виникненні нерегулярних рухів у детермінованих системах, у яких без джерел випадкових шумів можливі складні незавбачувані рухи. Важливою задачею нелінійної динаміки є задача реконструкції атрактора –необхідно за рядом спостережень динамічної змінної відновити динамічну систему, що описує цей ряд. Розв’язання цієї задачі особливо актуальне при аналізі економічних часових рядів, які до останнього часу досліджувались переважно статистичними методами. Застосуванню методів теорії хаосу до економічних задач присвячено роботи багатьох західних учених, зокрема, W.A.Brock, D.W.Dechert, J.A.Scheinkman, B.LeBaron, C.G.Gilmore, C.L.Sayers, M.Frank, T.Stengos. На жаль, цей напрямок майже не розроблений вітчизняними ученими.
У нелінійній динаміці сформувалась концепція ієрархії спрощених моделей, для якої характерна наявність базових математичних моделей, тобто таких математичних об’єктів, дослідження яких дозволяє ефективно будувати та вивчати великі класи моделей різних явищ. За останні п’ять років було запропоновано декілька таких моделей, серед яких можна виділити динамічні системи з джокером, що введені в роботах московських учених Г.Г.Малинецького та Л.В.Бєлайчук, а також фрактальні графи, які запропоновані В.О.Перепелицею та Л.Н.Сергєєвою.
Проведений аналіз виявив, що в працях попередників залишилися невирішеними такі питання:
У дисертаційній роботі для вирішення цих питань запропоновано виконати такі дослідження:
- отримати оцінки радіуса повного передфрактального графу та формулу розрахунку фрактальної вимірності повного фрактального графу.
У другому розділі розглянуто базові математичні моделі, що досліджуються в дисертаційній роботі (математична модель задачі інвестора, динамічні системи з джокером, фрактальні та передфрактальні графи), а також наведено загальну методику проведення дисертаційних досліджень.
Третій розділ присвячений дослідженню властивостей задачі інвестора з урахуванням дисконтування грошових потоків. Ця задача є модифікацією класичної задачі інвестора, багатокритеріальна (векторна) постановка якої полягає в такому. Розглядаються об’єктів інвестування, які пронумеровані індексом , - тривалість інвестиційного періоду для i - го об’єкта, - очікуваний прибуток за одиницю часу від i - го об’єкта після здачі його в експлуатацію, - директивний термін, по витіканні якого за кожну прострочену одиницю часу нараховується штраф у кількості одиниць. Кожний припустимий розв’язок задачі інвестора являє собою одне з переставлень чисел (i позначає номер об’єкта, k –порядковий номер цього об’єкта в переставленні). - множина всіх припустимих розв’язків (МПР) цієї задачі. На множині всіх переставлень визначена векторна цільова функція (ВЦФ)
(1)
яка складається з мінімізованих критеріїв, тобто частинних цільових функцій (ЦФ)
, де
(2)
, (3)
де - календарний час здачі об’єкта в експлуатацію.
Зміст критерію (2) (вигляду MINSUM) полягає в мінімізації втрат інвестора, а критерію (3) (вигляду MINMAX) –у мінімізації найгіршого виходу (тобто найбільших втрат прибутку через затримку інвестування) серед об’єктів інвестування.
Недоліком такої математичної моделі є те, що вона надає однакової ваги грошовим потокам, які відносяться до різних моментів часу. Урахувати суттєву зміну вартості одиниці ресурсу можна за допомогою операції дисконтування. У результаті отримуємо математичну модель задачі інвестора з дисконтуванням. Постановка задачі інвестора з дисконтуванням співпадає з класичною, але суттєво відрізняється виглядом ВЦФ. На МПР задачі інвестора з урахуванням дисконтування визначена ВЦФ вигляду
(4)
яка складається з мінімізованих критеріїв, тобто частинних ЦФ
,
де
(5)
, (6)
де - річна ставка дисконту.
Таким чином, при уведенні в математичну модель задачі інвестора дисконту часу, початкова ВЦФ (1-3) перетворюється на суттєво нелінійну (4-6). Постає питання впливу операції дисконтування на множину парето-оптимальних розв’язків задачі інвестора. Результат дослідження викладено в такому узагальненому твердженні.
Теорема 3.1. Урахування умови дисконтування грошових потоків у задачі інвестора змінює множину оптимумів у випадку, коли цільова функція містить критерії вигляду MINSUM та MINMAX у довільній комбінації. До того ж існують такі індивідуальні задачі, для яких множини оптимальних розв’язків не перетинаються.
Після доведення неспівпадання паретовських множин (ПМ) класичної задачі інвестора та задачі інвестора з дисконтуванням було проаналізовано, як саме співвідносяться їх ПМ, а також стійкість розв’язку задачі (паретовської множини) відносно зміни коефіцієнта дисконтування . Для цього було розроблено програму, яка методом повного перебору визначає паретовські множини для двокритеріальних задач із різними комбінаціями критеріїв MINSUM та MINMAX розмірності до =10 включно. Програма дозволяє варіювати значення коефіцієнта дисконтування . Ілюстрацію результатів роботи програми для двох індивідуальних задач подано в додатку А.
Проведений аналіз дозволяє свідчити про задачу інвестора з дисконтуванням як про самостійну задачу, що потребує індивідуального підходу в побудові ефективних алгоритмів пошуку парето-оптимальних розв’язків. На цьому етапі дисертаційного дослідження було знайдено підклас однокритеріальної задачі інвестора з урахуванням дисконтування з критерієм вигляду MINSUM (5), для якого є вірними такі теореми.
Теорема 3.2. Розв’язувальні правила, які гарантують знаходження з поліноміальною трудомісткістю оптимального розв’язку задачі інвестора з ЦФ вигляду (5), існують для такої області значень параметрів задачі: ; , - довільна стала; ; - кількість об’єктів інвестування.
Теорема 3.3. Трудомісткість алгоритму : .
Доведення теореми 3.2 є конструктивним, тобто в процесі доведення побудовано алгоритм , який гарантовано будує оптимальний розв’язок задачі інвестора з дисконтуванням із визначеними параметрами. У випадку, коли коефіцієнт дисконту =0, запропонований алгоритм зводиться до відомого поліноміального алгоритму розв’язання однокритеріальної задачі інвестора з критерієм вигляду MINSUM (2). Вірогідність розробленого алгоритму підтверджується також абсолютним збігом розв’язків, отриманих за допомогою алгоритму та за допомогою програми повного перебору.
Четвертий розділ присвячений аналізу дискретних систем методами нелінійної динаміки, зокрема, методами теорії хаосу та фрактальної геометрії.
У першому підрозділі комбінація цих методів із методом математичної візуалізації використана при дослідженні образів критеріального простору задач дискретної багатокритеріальної оптимізації на прикладі двокритеріальної задачі інвестора, ВЦФ якої має вигляд
. (7)
Образом критеріального простору (ОКП) у декартовій системі координат будемо називати множину точок () із координатами . Необхідно встановити, чи зберігається структура ОКП різноманітних індивідуальних задач деякої масової двокритеріальної задачі при зміні параметрів та зі зростанням її розмірності. Дві множини точок будемо називати подібними за структурою, якщо вони мають однакові оцінки фрактальної вимірності. Для визначення фрактальної вимірності образу критеріального простору пропонується застосувати метод узагальненого часового ряду.
Візуалізацію критеріального простору (7) можна здійснювати трьома способами (формами) –точковим, графіком та узагальненим часовим рядом. Наприклад, на рис.1 наведено перше зображення ОКП задачі інвестора для . Точками позначено неоптимальні розв’язки, квадратами –елементи паретовської множини. Якщо на осі абсцис кожну пару сусідніх точок визначаємо (відзначаємо) так, щоб виконувалась рівність , тобто значенням ставимо у відповідність цілочислові точки відрізка , то визначена таким чином діаграма критеріального простору являє собою узагальнений часовий ряд і є третьою формою зображення критеріального простору. На рис.2 наведено узагальнений часовий ряд для 2-критеріальної задачі інвестора з критеріями MINSUM та MINМАХ (=5).
Наступним етапом аналізу структури ОКП є оцінка фрактальної вимірності, яку можна отримати на підставі процедури Паккарда-Такенса (метод псевдофазового простору). У дисертаційній роботі розроблено алгоритм оцінки фрактальної вимірності узагальненого часового ряду за допомогою кореляційного показника, який можна застосовувати до відносно коротких часових рядів (декілька сотень спостережень).
Цей алгоритм покладено також в основу комбінованого підходу до аналізу часових рядів, який поєднує традиційні статистичні методи з методами теорії детермінованого хаосу. Розробці цього підходу присвячений другий підрозділ. Якщо одержано скінченне неціле значення кореляційної вимірності , то, згідно з теоремою Такенса, ми спостерігаємо такий часовий ряд, який породжується детермінованою нелінійною динамічною системою, поведінку якої визначають []+1 змінні. Підбір типу залежностей між змінними базується на інформації, здобутій при аналізі псевдофазових просторів, теорії універсальностей Фейгенбаума, а також методах регресійного аналізу. Побудована математична модель може бути використана для прогнозування еволюції системи, причому горизонт прогнозу визначається за допомогою найбільшого показника Ляпунова. У межах цього підходу було також розроблено алгоритм вилучення лінійного тренду, який охоплює частину ряду. Для реалізації комбінованого підходу було розроблено програмне забезпечення на мові програмування Turbo Pascal, яке було апробовано на модельному часовому ряді. Як приклад застосування запропонованої процедури розглянуто побудування математичної моделі, де за початкові дані для аналізу обрано курс долара США на УМВБ за період із 1.09.95 по 5.04.97.
Третій підрозділ присвячений аналізу нового класу математичних моделей –динамічних систем із джокером. Фазовий простір такої системи складається з двох областей –області , поведінка в якій визначається відображенням (змінна може являти собою вектор) і області –області джокера. При цьому задане правило, за яким система з точки потрапляє в точку . Залежно від вимірності області та заданого правила джокери можна класифікувати як одновимірні та -вимірні ( менше або дорівнює вимірності фазового простору) і як точкові та інтервальні.
При аналізі цього нового класу математичних моделей виникло питання: чи існує такий тест серед відомих тестів детермінованого хаосу, який дозволить ефективно виявляти присутність джокера в системі по часовому ряду даних, чи необхідно розроблювати новий? Аналіз існуючих тестів детермінованого хаосу показав, що для виявлення присутності джокера в системі можна використовувати графічний тест хаосу (тест Гілмора). Суть цього методу полягає в тому, що він виявляє нестійкі періодичні орбіти, укладені в дивному атракторі. Для того, щоб виявити області “тісного повернення” у множині даних, потрібно програмно реалізувати алгоритм побудови спеціальним способом розфарбованого графіка. На наявність тісного повернення в даних указують горизонтальні відрізки прямих. Якщо множина даних стохастична, то виникне область рівномірно розподілених чорних точок. Періодичний сигнал може бути виявлений по суцільних чорних лініях, що проходять горизонтально вздовж усього графіка через інтервали, які визначені періодичністю вимірів в одиницях часу спостережень. Квазіперіодичні орбіти, що складаються з двох частот, виробляють зображення, яке подібне до карти, що накреслена в горизонталях. Для графіка з інтервальним джокером характерна присутність “порожніх”областей, що не містять точок, та областей із горизонтальними паралельними відрізками.
Наприклад, на рис.3 наведено ілюстрацію графічного тесту хаосу логістичного відображення: , із параметром =3,7. Відомо, що при такому значенні параметра послідовність даних є хаотичною. На рис.4 наведено ілюстрацію графічного тесту хаосу логістичного відображення з точковим джокером (=3,7).
П’ятий розділ присвячений оцінці числових характеристик повних фрактальних та передфрактальних графів –нового математичного об’єкта, запропонованого В.О.Перепелицею та Л.Н.Сергєєвою як засіб моделювання структурного хаосу. Індуктивне визначення перед-фрактального і фрактального графів полягає в такому.
Нехай –граф (скінченний або нескінченний), де - множина вершин графу, а - множина його ребер. Терміном "ініціатор" будемо називати зв'язний -вершинний граф .
Як утворююче правило введемо операцію “заміщення вершини ініціатором” (ЗВІ). Суть цієї операції полягає в реалізації таких етапів. 1. У даному графі виберемо вершину і виділимо її оточення, тобто множину усіх вершин , суміжних із вершиною . Позначимо цю множину : . Множину всіх ребер, інцидентних вершині , позначимо . 2. Із множини вершин видалимо вершину і додамо множину вершин ініціатора . 3. Із множини ребер видалимо множину і додамо множину , обумовлену деяким взаємно однозначним відображенням (тобто кожне ребро з заміщається ребром, що з'єднує вершину зі “старого”ребра з деякою вершиною ініціатора), крім того додамо ребра ініціатора . У такий спосіб ЗВІ може бути подане як відображення .
ВИСНОВКИ
Основні результати дисертаційної роботи полягають у наступному:
1. Проведено аналіз та модифікацію математичної моделі задачі дискретної оптимізації (задачі інвестора). Доведено, що урахування умови дисконтування грошових потоків у задачі інвестора змінює множину оптимумів у випадку, коли цільова функція містить критерії вигляду MINSUM та MINMAX у довільній комбінації; існують такі індивідуальні задачі, для яких множини оптимальних розв’язків не перетинаються.
2. Одержано розв’язувальні правила (алгоритм), які гарантують знаходження з поліноміальною трудомісткістю оптимального розв’язку задачі інвестора з дисконтуванням з ЦФ вигляду MINSUM для визначеної області значень параметрів задачі.
. Розвинуто підхід до аналізу образів критеріального простору векторних задач комбінаторної оптимізації, а саме, їх структури (метод узагальненого часового ряду).
4. Стосовно математичного моделювання в умовах неповних даних розроблено алгоритм вилучення часткового лінійного тренду та метод розрахунку кореляційної вимірності за відносно короткими часовими рядами.
. Обґрунтовано можливість використання графічного тесту хаосу для виявлення присутності джокера в експериментальних даних.
6. При аналізі повних передфрактальних та фрактальних графів одержані нижня та верхня оцінки радіуса та доведено їх досяжність; доведено, що повний фрактальний граф є самоподібним, причому одержано формули розрахунку фрактальної вимірності.
СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ
АНОТАЦІЯ
Позднякова А.Ю. Розвиток деяких методів моделювання дискретних нелінійних систем. –Рукопис.
Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 –математичне моделювання та обчислювальні методи. –Дніпропетровський національний університет, Дніпропетровськ, 2001.
Дисертаційну роботу присвячено аналізу та модифікації математичних моделей дискретних нелінійних систем та розробці методів математичного моделювання дискретних нелінійних систем в умовах неповних даних. Досліджено властивості модифікованої задачі дискретної оптимізації –задачі інвестора з урахуванням дисконтування грошових потоків. Розроблено поліноміальний алгоритм розв’язання одного підкласу цієї задачі. Розвинуто підхід до аналізу структури образу критеріального простору векторних задач дискретної оптимізації. Розвинуто комбінований підхід до математичного моделювання в умовах неповних даних, який поєднує класичні статистичні методи аналізу часових рядів з методами детермінованого хаосу. Проаналізовано нові базові математичні моделі нелінійної динаміки –динамічні системи з джокером та фрактальні графи.
Ключові слова: дискретна нелінійна система, багатокритеріальна дискретна оптимізація, динамічна система з джокером, фрактальний граф.
ANNOTATION
Pozdniakova A.Yu. Development Some Methods Of Discrete Nonlinear Systems Modeling. –Manuscript.
The dissertation is the manuscript presented for the scientific degree of Candidate of Physical-Mathematical Sciences on the specialty 01.05.02 –mathematical modeling and computational methods. – Dnipropetrovsk National University, Dnipropetrovsk, 2001.
The dissertation is devoted to analysis and modification of mathematical models of discrete nonlinear systems and development methods of discrete nonlinear systems modeling in non-full data conditions. The property of modify discrete optimization problem –investor problem with discount –was investigated.
The polynomial algorithm of one subclass this problem solution worked out. Developed was the approach to analyses of criterial space image structure of vector discrete optimization problems. The combine approach to mathematical modeling in non-full data conditions was developed. This approach unites classic statistical methods of time series analyses with methods of deterministic chaos. Analyzed are the new basic mathematical models of nonlinear science - dynamical systems with joker and fractal graphs.
Key words: discrete nonlinear system, multicriterial discrete optimization, dynamical system with joker, fractal graph.
АННОТАЦИЯ
Позднякова А.Ю. Развитие некоторых методов моделирования дискретных нелинейных систем. –Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 –математическое моделирование и вычислительные методы. –Днепропетровский национальный университет, Днепропетровск, 2001.
В диссертационной работе проведен анализ и модификация некоторых математических моделей дискретных нелинейных систем, а также развиты методы математического моделирования дискретных нелинейных систем в условиях неполных данных. В качестве базовых математических моделей выбраны: задача одного станка, динамические системы с джокером и фрактальные графы.
В диссертации впервые сформулирована и исследована постановка задачи инвестора с дисконтированием, которая является модификацией известной задачи комбинаторной оптимизации –задачи одного станка. Доказано, что в принципе как угодно малый коэффициент дисконтирования может изменить искомое паретовское множество. Исследована устойчивость паретовского множества относительно значения коэффициента дисконтирования. Выявлен полиномиально разрешимый подкласс задачи инвестора с учетом дисконтирования денежных потоков. Полученная математическая модель может быть использована при долгосрочном планировании инвестиционного процесса.
В рамках разработки адекватного универсального подхода к решению многокритериальных задач комбинаторной оптимизации предложен метод анализа структуры образов критериального пространства (метод обобщенного временного ряда). Даны определения образа критериального пространства, подобия структуры двух множеств. Разработан алгоритм оценки фрактальной размерности обобщенного временного ряда с помощью корреляционного показателя, который можно применять к относительно коротким временным рядам. Для иллюстрации предложенного метода выбрана двукритериальная задача инвестора.
Развит комбинированный подход к анализу временных рядов, который объединяет традиционные статистические методы и методы теории детерминированного хаоса. Разработана интерактивная процедура построения математической модели дискретной нелинейной динамической системы, поведению которой присущи признаки динамического хаоса, в случае, когда исследователю известна реализация лишь одной из фазовых переменных –временной ряд.
Исследован новый класс математических моделей нелинейной динамики (динамические системы с джокером) и предложен метод обнаружения присутствия джокера в экспериментальных данных –графический тест хаоса Гилмора. Этот критерий дает возможность отличать системы с потенциальной возможностью катастроф от динамических систем со сложным поведением.
Проведен анализ полных предфрактальных и фрактальных графов с точки зрения оценки их числовых характеристик. Получены верхняя и нижняя оценки радиуса полного предфрактального графа. Кроме классических характеристик графа, рассмотрены показатели, присущие фрактальным объектам, – фрактальные размерности. Получены формулы расчета размерности Хаусдорфа-Безиковича и размерности подобия полного фрактального графа, их совпадение свидетельствует о самоподобности фрактального графа. Полученные оценки топологических и метрических инвариантов полных предфрактальных и фрактальных графов могут быть использованы при решении оптимизационных задач на графах.
В совокупности предложенные модели и методы решения направлены на развитие математического моделирования и вычислительных методов как инструментальных средств построения и исследования математических моделей дискретных нелинейных систем.
Ключевые слова: дискретная нелинейная система, многокритериальная дискретная оптимизация, динамическая система с джокером, фрактальный граф.