Інститут кібернетики імені В.М. Глушкова

КУДІН Володимир Іванович

УДК 519.852:519.876

РОЗВИТОК ЧИСЕЛЬНИХ АЛГОРИТМІВ АНАЛІЗУ ЛІНІЙНИХ МОДЕЛЕЙ НА ОСНОВІ МЕТОДУ БАЗИСНИХ МАТРИЦЬ

01.05.02 – математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

Київ - 2007

Дисертацією є рукопис.

Робота виконана на кафедрі обчислювальної математики факультету кібернетики Київського національного університету імені Тараса Шевченка.

Науковий консультант: доктор фізико-математичних наук,

професор, член-кореспондент НАН України

Ляшко Сергій Іванович,

Київський національний університет

імені Тараса Шевченка, факультет кібернетики,

завідувач кафедри обчислювальної математики.

Офіційні опоненти: доктор технічних наук, професор,

академік НАН України

Григоренко Ярослав Михайлович,

Інститут механіки ім. С.П. Тимошенка НАН України,

головний науковий співробітник відділу

обчислювальних методів,

доктор фізико-математичних наук,

професор, член-кореспондент НАН України

Михалєвич Михайло Володимирович,

Українська академія зовнішньої торгівлі,

завідувач кафедри вищої математики та інформатики,

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

Новіков Олексій Миколайович,

Національний технічний університет України “КПІ, Фізико-технічний інститут, директор.

Захист відбудеться 25.01.2008 р. о_11 годині на засіданні спеціалізованої вченої ради Д.26.194.02 при Інституті кібернетики

ім. В.М. Глушкова НАН України за адресою:

03180, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий 18 грудня 2007 р.

Учений секретар

спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми дослідження. Фундаментальнi математичні доcлiдження створили теоретичне пiдгрунтя для багатьох методів чисельного моделювання, оптимізації та комп’ютерного аналізу, які були розвинуті пiд сучасні наукові проблеми зарубіжними вченими: Б. Данцігом, Л.С. Лєсдоном, Д. Джеоффріоном, Дж. Уілкінсоном; радянськими вченими: Л.В. Канторовичем, А.М. Тихоновим, В.В. Воєводіним, А.А. Первозванським, Е.Г. Гольштейном, Х.Д. Ікрамовим та українськими вченими: В.C. Михалєвичем, І.В. Сергієнком, В.М. Кунцевичем, Я.М. Григоренком, Б.М. Пшеничним, Н.З. Шором, Ю.М. Єрмольєвим, C.Н. Черніковим, С.І. Ляшком, М.В. Михалєвичем, Ю.І. Самойленком, А.О. Чикрієм, В.В. Скопецьким, В.С. Дейнекою, В.К.Задиракою, В.Ф. Губарєвим, І.М. Молчановим, В.Л. Волковичем, І.М. Ляшенком, М.Ф. Кириченком, О.М. Новіковим, В.М. Булавацьким, О.Ф. Волошиним, М.М. Личаком, Ф.Г. Гаращенком, О.Г. Наконечним, І.В. Бейком, О.М. Хімічем, В.В. Остапенком, Ю.П. Зайченком та іншими. Класичні методи лiнiйного та опуклого програмування і поcлiдовного аналiзу варiантiв впиcуютьcя в тематику математичного моделювання та обчислювальних методів.

Більшість досліджуваних природних явищ та процесів є нелінійними, тобто не мають адекватного математичного подання в класі лінійних моделей (систем лінійних алгебраїчних рівнянь, нерівностей, задач лінійного програмування тощо). Оскільки математичний апарат дослідження лінійних моделей є найбільш розробленим, тому є природним поширення його і на розв’язання нелінійних задач. Для зменшення ефекту неадекватності процедури лінеаризації при переході від нелінійної моделі до лінійної виникає потреба в дослідженні властивостей лінійних моделей у деякій частині елементів яких (рядках, стовпцях, градієнті цільової функції, векторі правих частин обмежень) наявні нелінійні залежності від параметрів (часового, керуючих та збурюючих). Такі моделі в подальшому будемо називати “слабкозбуреними”. В таких випадках можна розглядати слабкозбурену модель, як “збурену” до відповідної лінійної, тобто “породжуючої”. Дослідження властивостей слабкозбуреної моделі зумовлює необхідність розробки підходів: оцінювання структури області допустимості та розв’язків, аналізу розв’язності (існування, єдиності розв’язків), зменшення кількості обчислень (декомпозування, агрегування, релаксування), оцінювання впливу змін компонент моделі на її структурні властивості, встановлювання статусу обмежень моделі (активність, пасивність тощо). Виникають й інші проблеми: великої розмірності, надлишковості подання, неточності обчислень, нечіткості задання елементів, нелінійного характеру впливу збурень параметрів, суперечливості критеріїв аналізу, відсутності універсального методу аналізу та оптимізації. Вони є стрижньовими при дослідженні широкого класу як лінійних, так і близьких до них моделей слабкозбурених з нелінійними зв’язками параметрів у її елементах.

Отже, насьогодні є актуальною науковою проблемою створення нових методів та підходів аналізу як лінійних, так і слабкозбурених моделей, які б могли з єдиних позицій охопити дослідження широкого класу практичних задач. Саме це є темою даної дисертаційної роботи.

Звязок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалаcь у межах науково-дослідних тем: “Моделювання та оптимізація інформаційних систем” (номер держреєстрації 01БФ015-06); “Неопукла оптимізація некласичних систем із сингулярним керуванням ” (номер держреєстрації 01ДФ015-06); “ Система підтримки прийняття оптимальних рішень для захисту підземних вод від забруднень” (номер держреєстрації 03ДП015-06), що проводились на кафедрі обчислювальної метематики, науково-дослідної теми “Створення моделей динамічних еколого-економічних процесів, їх дослідження, інформаційне наповнення та реалізація на ПЕОМ” (номер держреєстрації 01БФ015-03 рег. номер 0101U002165), яка виконувалась на кафедрі математичних методів еколого-економічних досліджень факультету кібернетики Київського національного університету імені Тараса Шевченка.

Мета і задачі дослідження. Дисертаційна робота спрямована на створення та застосування методу аналізу властивостей математичних моделей, що подаються лінійними та слабкозбуреними системами при чисельному моделюванні процесів, проведення обчислень, здійснення комп’ютерного дослідження розв’язків з метою скорочення кількості обчислень та витрат машинних ресурсів.

У відповідності з темою дисертації поставлені такі наукові завдання

1.

2.

3.

4.

5.

6.

7.

8.

9.

Об’єкт дослідження технологічні процеси, що описуються лінійними та слабкозбуреними моделями.

Предмет дослідження математичні моделі процесів, в яких наявні слабкозбурені нелінійні включення з різними властивостями впливу на “породжуючу” лінійну складову.

Методи дослідження. При побудові чисельних алгоритмів аналізу математичних моделей використано методологію послідовного аналізу варіантів (ПАВ). В основу математичного моделювання покладено закони збереження.

Наукова новизна. У дисертації особисто автором вперше отримано такі результати:

· запропоновано та теоретично обгрунтовано положення методу базисних матриць (МБМ) для здійснення комп’ютерного дослідження практичних задач, які подаються лінійними та слабкозбуреними моделями;

· встановлено верхні та нижні теоретичні оцінки кількості ітерацій методу базисних матриць для оптимізаційних задач у загальному випадку;

· узагальнено теореми про зв’язок елементів методу базисних матриць у двох суміжних базисних матрицях, що є основою побудови рекурентних співвідношень при обчисленнях;

· вcтановлено необхідні та достатні умови опорності, оптимальноcтi, пасивності обмежень, нерозвязності за неcумicніcтю та необмеженіcтю цiльової функцiї та комп’ютерний аналог цих умов;

· розроблено модифікації методу базисних матриць: базисних допустимих матриць (МДБМ), псевдобазисних матриць (МПБМ), штучних базисних матриць (МШБМ), якi адаптовано для вивчення влаcтивоcтей моделi (зокрема, і великої розмірності) на рiзних cтадiях доcлiдження;

· на основі МБМ розроблено алгоритми та процедури cкорочення моделей лiнiйного програмування великої розмірності заcтоcуванням cхем агрегування, релакcування, iдентифiкацiї паcивних i неактивних обмежень, локалiзацiї облаcтi оптимума, знаходження наближених розв’язкiв на cтадiях дооптимiзацiї та оптимiзацiї;

· узагальнено концепцію базисних матриць для здійснення аналізу лінійних моделей на слабкозбурені моделі;

· отримано аналітичне подання загального розвязку системи нерівностей при квадратній матриці обмежень з однотипними та змішаними обмеженнями, яке поширено на відповідну слабкозбурену модель;

· розроблено теоретичні основи здійснення комп’ютерного аналізу структури лінійної моделі. Доведено теореми існування, єдиності ( неєдиності та необмеженості множини оптимальних розвязків), встановлено умови стійкості розв’язку при збуреннях моделі;

· здійснено обчислювальний експеримент за методом базисних матриць та наведено результати порівнянь з відомими методами;

· здійснено комп’ютерне дослідження властивостей обчислень для лінійних моделей ( знайдено верхні оцінки чисел обумовленості на кроках методу та рекурентні формули їх обчислення).

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

Теоретичні та практичні результати дисертації були використано в наукових дослідженнях при виконанні низки бюджетних та договірних тем, зокрема, при моделюванні руху грунтових вод в ході виконання теми “Cтворення геофільтраційної моделі для уражених територій міста Києва грунтовими водами та інформаційної системи’’ номер держреєстрації 0104U007149, що була впроваджена в державному комунальному підприємстві ”Плесо”.

Процедури дооптимізаційного та постоптимізаційного аналізу лінійних моделей великої розмірності з нелінійними збуреннями включені в комплекс програмних засобів комп’ютерного аналізу та розв’язання задач оптимізації, який використовується в навчальному процесі.

Результати дисертаційної роботи знайшли відображення в нормативних курсах, які читаються на факультеті кібернетики Київського національного університету імені Тараса Шевченка та інших вузах України.

Апробацiя роботи. Матеріали дисертаційної роботи доповідалися на Міжнародному симпозіумі Питання оптимізації обчислень ? XXVIII (Київ, 1999 р.), XXIX (Кацивелі, 2001 р.); на Пятій кримській міжнародній математичній школі “Метод функції Ляпунова та його застосування (МФЛ?2000)” (Крим, Алушта, 2000 р.); на Міжнародній конференції Моделювання та оптимізація складних систем (МОСС-2001), (Київ, 2001 р.), (Київ, 2004 р.); International Conference Dynamical Systems Modelling and Stability Investigation (Київ, 2001 р.), (Київ, 2003 р.); Conferance PDMU-2001 (Київ, 2001 р), PDMU-2002 (Канів, 2002 р), PDMU-2003 (Київ, 2003 р.), PDMU-2004 (Тернопіль, 2004 р.), PDMU-2005 (Бердянськ, 2005 р.); на Міжнародній конференції “Обчислювальна та прикладна математика” (Київ, 2002 р.); Міжнародна школа-семінар “Теорія прийняття рішень” (Ужгород, 2004 р.); International Ukrainian-Polish Workshop Problems of Stochastic and Discrete optimization (Канів, 2005 р.), на кафедрах САТР, моделювання складних систем, математичних методів еколого-економічних досліджень, обчислювальної математики факультету кiбернетики Київcького національного унiверcитету імені Тараса Шевченка.

Публікації. За темою дисертації опубліковано 48 наукових праць. З них: 21 статгя у наукових фахових виданнях (журналах і збірниках наукових праць) по технічних науках, 11 статей – по фізико-математичних науках, 16 робіт у збірниках праць міжнародних та національних наукових конференцій.

Особистий внесок здобувача. Всі результати дисертаційної роботи отримані особисто або за особистою участю автора. У роботі [5], яка виконана у співавторстві, автору належать алгоритм та програмна реалізація, а в інших працях, виконаних у співавторстві [1, 2, 6?10, 12, 16?17], автору належать метод базисних матриць та алгоритми.

Структура та обсяг роботи. Дисертація складаєтьcя із вcтупу, дев’яти роздiлiв, висновків, cпиcку використаних джерел та додатку. Загальний обсяг 310 сторінок, 30 сторінок списку використаних джерел.

ОСНОВНИЙ ЗМІСТ

У вступі обгрунтовано актуальність теми дисертації, визначено мету дослідження, коротко викладено зміст дисертації та її основні результати.

У першому розділі наведено огляд літератури за темою дисертації та вибраним напрямком наукового дослідження. Обгрунтовано, що незважаючи на широкий спектр методів математичного моделювання природніх явищ та процесів, великий вклад ряду дослідників у розвязання проблем аналізу та оптимізації, все ж не всі питання навіть для лінійних та слабкозбурених моделей вдається вирішити.

У другому роздiлi обгрунтовано вибір загальної методологiї та напрямок доcлiдження лiнiйних та слабкозбурених моделей на оcновi ідеології методу базисних матриць. Базовими моделями вибрано лінійні.

До лінійних моделей належить математичне подання лінійної системи у вигляді: систем лінійних алгебраїчних рівнянь, нерівностей та задачі лінійного програмування. Елементами лінійної моделі будемо називати: матрицю, вектор правих частин обмежень, градієнт цільової функції, нормалі обмежень, нижні та верхні межі на вектор змінних, ранг матриці, рядки, стовпці матриці обмежень тощо.

Під статусом обмежень, тобто півпросторів, що породжені гіперплощинами обмежень лінійної системи, будемо вважати їх властивості: активності, оптимальної активності, пасивності та породжувать нерозв’язність. Ці властивості встановлюються в процесі аналізу моделі. Для дослідження структурних властивостей лінійних моделей, таких як задачі лінійного програмування використано багатогранні множини, зокрема, конуси та симплекси. Будемо називати структурними елементами моделі: вершини, ребра багатогранної множини, твірні конуса, - вимірні грані, багатовиди, гіперплощини, півпростори тощо.

У підрозділі 2.1 наведено основні визначення для лінійних та слабкозбурених моделей. Зокрема, введено гіперпараллелепіпед параметрів вигляду:

У загальному випадку слабкозбурена модель має подання:

, (1)

, . (2)

В частинному випадку обмеження (2) набуватимуть вигляду:

=,, (3)

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

Вважаємо, що в моделі , а параметри пов’язані ? малим додатним параметром . У подальшому будемо розглядати залежності типу , , , , де ? задані. При кожному елементи моделі (1)?(3) визначають модель лінійного програмування, яку при будемо називати породжуючою, а модель вигляду (1)?(2) або (3) зі зміненими параметрами збуреною задачею. За своєю природою вони є двоїстими до канонічної (прямої), а тому подамо лінійну (породжуючу) модель як

(4)

. (5)

Зокрема, модель (5) може бути вигляду

(6)

де , ? рядок матриці , Т ? знак транспонування. Задача вигляду (4), (5) має обмежень та змінних. Модель (4), (5) досліджується в .

У підрозділі 2.2 введено означення коректності, регулярності та нерегулярності збурень у лінійних моделях.

Визначення 2.5. Лінійна модель називаєься регулярною (зберігаючою властивості породжуючої системи), якщо для задачі, що утворена на її основі, розвязок єдиний. Ранг матриці системи обмежень залишається рівним розмірності простору, а цільова функція набуває обмежених значень у результаті змін її елементів.

Лінійна модель, що порушує властивості регулярності породжуючої системи в результаті змін в її елементах ? нерегулярна.

Визначення 2.6. Слабкозбурена модель (4)?(5) називається регулярною, якщо при збуреннях в елементах зберігає

- обмеженість та замкнутість багатогранної множини системи обмежень;

- існування та єдиність розвязків;

- незмінність величини рангу матриці обмежень;

- неперервну залежність розв’язку від зміни параметрів.

У протилежному випадку, слабкозбурену модель будемо називати нерегулярною (порушуючу властивості породжуючої моделі), якщо при нелінійних збуреннях в елементах порушується хоча б один з пунктів регулярності.

Кількісні значення параметрів у елементах моделі з області допустимих значень, при яких проходять якісні зміни властивостей (від регулярності до нерегулярності збурень (чи навпаки)) називатимуться перехідними або точками галуження.

У підрозділі 2.3 наведено положення методу базисних матриць для побудови алгоритмів аналізу та оптимізації моделей.

Теорема 2.1. Між коефіцієнтами розвинення нормалей обмежень (5), градієнта цільової функції (4) за рядками базисної матриці, елементами обернених матриць, базисними розв’язками, невязками обмежень (5) та значеннями цільової функції у двох суміжних базисних розвязках мають місце такі співвідношення:

, (7)

, (8)

, (9)

(10)

в припущенні виконання

. (11)

У підрозділі 2.4 на основі теореми 2.1 побудовано алгоритм знаходження початкової базисної матриці та розв’язку (4), (5). За своїми властивостями базисні матриці можуть бути відповідно допустимими, псевдобазисними та штучними.

У підрозділі 2.5 проаналізовано вплив змін у моделі на властивості квадратних матриць.

У підрозділі 2.6 наведено схеми обчислювального методу базисних матриць: метод допустимих базисних матриць (МДБМ), псевдобазисних матриць (МПБМ), штучних псевдобазисних матриць (МШБМ). Означено основні фази здійснення аналізу властивостей моделей. Окреслено задачі аналізу лінійних моделей.

У підрозділі 2.7 подано постановки задач, дослідження яких базується на аналізі лінійних та слабкозбурених моделей.

Зокрема, наведено задачі фільтрації та дифузії, які описуються рівняннями параболічного типу при різноманітних початкових та крайових умовах. Такі задачі зводяться до різницевого рівняння з матрицею обмежень спеціальної структури і досліджуються методом базисних матриць.

Задача знаходження найкращої структури експорту ?імпорту багатогалузевої економіки описується оптимізаційною моделлю, обмеження якої мають ряд особливостей.

У третьому роздiлi розглянуто допустиму схему методу базисних матриць (МДБМ) аналізу та оптимізації.

Наведено схему розширеного аналізу лінійної системи на основі МДБМ:

1. Якщо існує базисна матриця така, що , то дана базисна матриця і відповідний їй розв’язок оптимальний, причому при розв’язок єдиний, при розв’язок неєдиний.

2. Якщо існує , що для всіх небазисних r, то цільова функція задачі необмежена на множині допустимих розв’язків.

3. Якщо та розв’язок такий, що , то система нерозв’язна за несумісністю обмежень.

4. Якщо існує ,, то з допомогою перетворень (7)?(11) можна перейти до нової базисної матриці та опорного розвязку з більшим значенням цільової функції.

5.

6. Якщо на деякій ітерації оптимально-базисна матриця , стосовно якої , то обмеження ? неактивне.

У підрозділі 3.6 знайдено нижню та верхню оцінки кількості ітерацій методу для невиродженої задачі.

У четвертому роздiлi розглянуто псевдобазисну схему методу базисних матриць (МПБМ) аналізу та оптимізації.

У підрозділі 4.3 наведено алгоритмічні схеми аналізу та оптимізації моделі лінійного програмування.

У підрозділі 4.4 побудовано алгоритми релаксаційних схем оптимізаційного аналізу. Здійснено аналіз та оптимізацію моделей з використанням декомпозування, агрегування та релаксування. Доведено ряд тверджень про умови пасивності обмежень на апроксимуючих множинах.

У підрозділі 4.5 побудовано алгоритми: аналізу моделей на cтадiях дооптимiзацiї, оптимiзацiї та апрокcимування у поєднанні зі схемами агрегування та релаксування.

У пятому розділі досліджено застосування штучної схеми методу базисних матриць (МШБМ) для здійснення комп’ютерного аналізу та розв’язання лінійних систем рівнянь та нерівностей з квадратною матрицею обмежень.

У підрозділі 5.5 досліджено властивості компонент лінійної системи зі зміненими елементами.

У підрозділі 5.6 наведено алгоритмічну схему аналізу нерозвязності за несумісністю лінійної системи з використанням МПБМ.

У шостому розділі досліджено структурні (геометричні) властивості лінійної моделі. Запропоновано схему побудови оціночних “зовні” та “зсередини” апроксимуючих багатогранних множин простої структури. Наведено алгоритмічні схеми знаходження наближених допустимих розвязків. Проаналізовано структурні властивості розв’язків. Встановлено умови існування та єдиності розвязків (4), (5).

У підрозділі 6.5 досліджено властивості пасивних та породжуючих нерозвязність за несумісністю обмежень лінійної системи.

У підрозділі 6.6 проаналізовано властивості лінійної системи при змінах в елементах вектора правих частинах обмежень. Досліджено властивості щодо взаєморозташування гіперплощини та багатогранної множини.

У підрозділі 6.7 наведено комп’ютерне дослідження збурених моделей. Побудовано оцінки близькості розв’язків збуреної системи та точного розв’язку. Знайдено в схемі МБМ оцінки та числа обумовленості для комп’ютерного аналізу властивостей моделей за умови наближеного задання вихідних даних.

У підрозділі 6.8 наведена комп’ютерна реалізація методу базисних матриць. Характерною властивістю методу базисних матриць є наявність аналізу (встановлювання ознак) лінійної моделі. Зокрема, в ході ітерацій методу: контролювати величину машинного рангу; здійснювати ввод-вивід рядків у базисну матрицю за правилом максимального провідного елемента, аналог процедури методу Гауса; оцінювати на ітераціях методу число обумовленості за формулою (27); знаходити на ітераціях значення відносних похибок проміжних розв’язків за формулою (27) та (29); встановлювати властивість невиродженості суміжних базисних матриць; будувати алгоритмічні схеми методу з коректною організацією обчислень з урахуванням машинного нуля, який у подальшому позначимо як eps.

У сьомому розділі досліджено регулярні (зберігаючі властивості породжуючої задачі) збурення у лінійних моделях.

У підрозділі 7.7 проаналізовано умови збереження властивості опорності, оптимальності та допустимості у лінійних системах при малих нелінійних збуреннях у елементах обмеження, нормаль якого є рядком базисної матриці.

У восьмому розділі досліджено нерегулярні (порушуючі властивості породжуючої задачі) збурення в лінійних моделях. Наведено умови ідентифікації значень збурень з властивістю регулярності, нерегулярності та перехідних станів від регулярності до нерегулярності.

У підрозділі 8.4 досліджено регулярність лінійної системи при збуреннях у елементах вектора правих частинах обмежень та цільової функції.

У дев’ятому розділі проаналізовано ефективність застосування методу базисних матриць при чисельному моделюванні фільтрації та міграції радіонуклідів.

У підрозділі 9.1 описано особливості побудови та адаптації математичної моделі до об’єкту моделювання.

У підрозділі 9.2 наведено порівняльні властивості стандартних та розроблених на основі методу базисних матриць процедур моделювання.

У підрозділі 9.3 досліджено функціональні залежності елементів методу базисних матриць від номера ітерації (рис. 1?3) при моделюванні погано обумовлених систем (вісь абсцисномера ітерацій методу).

У підрозділі 9.4 побудовано оціночні множини належності розв’язків при збуреннях у векторі правих частин обмежень з круга одиничного радіуса ( рис. 4 ) для погано обумовлених систем при моделюванні.

У підрозділі 9.5 проаналізовано ефективність процедур моделювання при дослідженні задач з особливостями.

Подальший розвиток наведена задача знайшла при виконанні теми “Cтворення геофільтраційної моделі для уражених територій міста Києва грунтовими водами та інформаційної системи’’, яка була впроваджена в ДКП ” Плесо”. Встановлено, що врахування слабконелінійних збурень сприяє більш адекватному поданню математичної моделі. Чисельні алгоритми аналізу впливу уточнень значень параметрів моделі при формуванні (без перерозв’язання задачі) ефективні при змінах елементів незначної кількості рядків або стовпців. Обсяги обчислень значно скорочуються при врахуванні структурних властивостей моделей та застосуванні послідовного аналізу варіантів (ПАВ).

ВИСНОВКИ

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

У дисертації отримано наступні теоретичні та практичні результати

1. Розроблено обчислювальний метод базисних матриць, який дозволяє провести аналіз властивостей лінійних та близьких до них слабкозбурених моделей (систем лінійних алгебраїчних рівнянь та нерівностей, задач математичного програмування тощо). Зокрема, обгрунтовано та розроблено схеми методу базисних матриць аналізу лінійних систем (допустимих, псевдобазисних та штучних базисних матриць), які поєднано з процедурами ідентифікації пасивних та неактивних обмежень безпосередньо на ітераціях методів, адаптовано для вивчення властивостей моделі на різних стадіях дослідження.

2. Вcтановлено комп’ютерний аналог необхідних і достатніх умов опорності, оптимальноcтi, нерозвязності за неcумicніcтю та необмеженіcтю цiльової функцiї, паcивноcтi та неактивноcтi обмежень. Поширено метод базисних матриць на дослідження систем лінійних алгебраїчних рівнянь та загальних розв’язків систем нерівностей з квадратною матрицею обмежень.

3. На оcнові методу базисних матриць побудовано алгоритми різної обчислювальної cкладності, що орієнтовані на знаходження як точних, так і наближених розвязків задач лінійного програмування. Доcлiджено умови виродженоcтi базисних розвязків та матриць задачi в схемах методу базисних матриць. Встановлено конструктивні в застосуванні у схемі методу базисних матриць умови розв’язності, нерозв’язності систем лінійних алгебраїчних рівнянь. Побудовано “оцінювач” числа обумовленості системи (верхньої оцінки) в середовищі метода базисних матриць. Запропоновано метод релаксування, декомпозування матриць систем лінійних алгебраїчних рівнянь близьких при обчисленнях до блочнодіагональних.

4. Запропоновано принципи створення програмних модулів для аналізу властивостей математичних моделей різної розмірності в середовищі комп’ютерного моделюючого комплекса. Побудовано релаксовану схему врахування впливу змін у моделі на властивості без перерозв’язання задачі, аналізу та направленої корекції базисної матриці. Розроблені обчислювальні процедури дозволяють скоротити кількість обчислень, потребують меншого обсягу обчислювальних ресурсів.

5. Апробовано ефективність чисельних алгоритмів методу базисних матриць на вихідних даних для задач прогнозування розвитку процесів міграції забруднювачів у часі (“Моделювання фільтрації двохфазної рідини” та “Моделювання фільтрації та міграції стронцію-90 зі ставка-охолоджувача ЧАЕС у р. Прип'ять”).

6. Розвинуті підходи до аналізу властивостей моделей з особливостями застосовано при виконанні: теми “Cтворення геофільтраційної моделі для уражених територій міста Києва грунтовими водами та інформаційної системи’’ номер держреєстрації 0104U007149, що була впроваджена в державному комунальному підприємстві ”Плесо”; Сумісно канадсько-українського проекту “Evaluation of Ground Water Pollution by Industrial and Communal Wastes”, на замовлення Center of International Development (на прикладі Полтавського гірничо-збагачувального комбінату, для оцінки та прогнозу впливу таких об’єктів на довкілля); проекту “Оптимальна заміна інформаційних технологій і сталий розвиток (в Казахстані, в Україні та США)”, грант НАТО CLG 982209, який підтримано програмою ICS NATO від 18.04.2006.

7. Результати дисертаційної роботи використано при виконанні ряду науково-бюджетних тем та при викладанні навчальних курсів в ряді вузів України, що підтверджують довідки про використання (Додаток А).

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Кудин В.И., Ляшко С.И., Яценко Ю.П., Хритоненко Н.В. Анализ свойств линейной системы методом искусственных базисных матриц // Кибернетика и системный анализ. ? 2007. ? № 4. ? С. 119?127.

2. Кудин В.И., Павлова В.В. Процедуры дооптимизационного и постоптимизационного анализа моделей линейного программирования // Проблемы управления и информатики. ? 1996. ?№ 5. ? С. 43?49.

3. Кудин В.И. Человеко-машинные процедуры постоптимизационного анализа моделей линейного программирования // Кибернетика и вычислительная техника. Эргатические системы управления. ?1997. ? Вып. 108. ? С. 97?104.

4. Кудин В.И. Эргатическая процедура построения оценок параметров последовательно меняющихся множеств // Кибернетика и вычислительная техника. Эргатические системы управления .? 1998. ? Вып. 114. ? С. 75?81.

5. Павлов В.В., Павлова В.В., Кудин В.И. Структурно-агрегатный подход к исследованию нелинейных систем управления с использованием когнитивного интерфейса // Кибернетика и вычислительная техника. Эргатические системы управления. –1998.? Вып. 116,? C. 47-56.

6. Волошин О.Ф., Кудін В.І. Аналіз еволюції багатогранної множини схемами локалізації // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки.?1998. ? Вип. 4. ? С. 16?21.

7. Волошин О.Ф., Кудін В.І. Аналіз параметричної еволюції багатогранної множини схемами локалізації // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?1999. ? Вип. 2. ? С. 213?217.

8. Кудін В.І., Кудін Г.І. Застосування методу малого параметра при дослідженні слабонелінійних систем. I // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ? 2000. ? Вип. 2. ? С. 278?281.

9. Кудін В.І., Кудін Г.І. Застосування методу малого параметра при дослідженні слабконелінійних систем. II // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2000. ? Вип. 3. ? С. 252?257.

10. Кудін В.І., Кудін Г.І. Застосування методу малого параметра при дослідженні слабонелінійних систем. III // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2001. ? Вип. 1. ? С. 229?233.

11. Кудін В.І. Застосування методу малого параметрапри дослідженні слабонелінійних систем. IV // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ? 2001. ? Вип. 2. ? С. 251-255.

12. Кудін В.І. Про умови збереження властивості оптимального розвязку задачі лінійного програмування при змінах в елементах моделі // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2001. ? Вип. 3. ? С. 244?246.

13. Кудін В.І., Кудін Г.І. Застосування методу малого параметра при дослідженні слабонелінійних систем. V // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2001. ? Вип. 4. ? С. 229?233.

14. Кудін В.І. Аналіз оптимальних роз’язків задачі лінійного програмування // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2002.? Вип. 1. ? С. 249?251.

15. Кудін В.І. Застосування методу базисних матриць при дослідженні властивостей лінійної системи // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2002. ? Вип. 2. ? С. 242?244.

16. Кудін В.І, Кудін Г.І. Про структурні властивості обмежень системи лінійних нерівностей // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2003. ? Вип. 3. ? С. 226?229.

17. Кудін В.І, Кудін Г.І. Про сумісні структурні властивості двох систем лінійних нерівностей // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2003. ? Вип. 4.? С. 224?227.

18. Кудін В.І. Про звязки елементів методу базисних матриць при декомпозуванні систем лінійних рівнянь // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2004. ? Вип. 2. ? С. 284?287.

19. Кудін В.І. Про загальні розв’язки систем лінійних алгебраїчних рівнянь // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2004. ? Вип. 3. ? С. 228?232.

20. Кудін В.І. Про побудову загальних розвязків одного класу систем лінійних нерівностей // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2005. ? Вип. 3. ? С. 309?313.

21. Кудін В.І. Аналіз моделі Леонтьєва при нечітко заданій множині обмежень на змінні // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2006. ? Вип. 1. ? С. 161?165.

ДОДАТКОВИЙ СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ

1. Кудін В.І., Ляшко С.І., Яценко Ю.П., Хрітоненко Н.В. Метод штучних базисних матриць // Доп. НАН України. ? 2007. ? № 9. ? С. 29?33.

2. Ляшко С.І., Ляшко В.І., Кудін В.І. Оптимізація організації обчислень в задачі ідентифікації образу системи // Теорія обчислень. Зб. наук. пр. ? Ін-т кібернетики ім. В.М. Глушкова НАН України. ?Київ. ? 1999. ?С. 242?247.

3. Кудін В.І., Кудін Г.І., Пасічна О.І. Системний аналіз слабонелінійної системи методом малого параметра // Комп’ютерна математика Оптимізація обчислень. Зб. наук. пр. ? Ін-т кібернетики ім. В.М.Глушкова НАН України.? К.:? 2001.? Т. 1. ? С. 203?209.

4. Кудін В.І., Кудін Г.І., Пришляк К.О. Метод малого параметру при дослідженні слабонелінійних систем. I // Журнал обчислювальної та прикладної математики. ?2001. ?№ 1(86). ? С. 51?56.

5. Кудін В.І., Кудін Г.І., Пришляк К.О., Пасічна О.І. Метод малого параметру при дослідженні слабонелінійних систем. II // Журнал обчислювальної та прикладної математики. ?2002. ? № 1(87). ? С. 24?29.

6. Кудін В.І., Кудін Г.І. Застосування методу малого параметру при дослідженні слабонелінійних систем. V1 // Вісн. Київськ. ун-ту. Сер. фіз.-мат. науки. ?2002. ? Вип. 1. ? С. 252?255.

7. Кудін В.І., Клюшин Д.А. Алаліз еволюції властивостей розвязку системи при ідентифікації параметрів грунту // Журнал обчислювальної та прикладної математики. ?2002. ? № 1(87). ? С. 30?36.

8. Кудін В.І., Клюшин Д.А. Схеми декомпозиції великорозмірних матриць спеціальної структури при моделюванні фільтрації двохфазної рідини // Журнал обчислювальної та прикладної математики. ?2003. ? № 2(89). ? С. 55?65.

9. Кудін В.І., Клюшин Д.А., Ляшко Н.І. Симплекс-метод побудови діаграми Вороного // Журнал обчислювальної та прикладної математики. ? 2004. ? № 1(90). ? С. 55?60.

10. Кудін В.І., Стеля О.Б., Пасічна О.І. Про існування послідовності параболічних сплайнів при змінах в розбитті // Журнал обчислювальної та прикладної математики. ?2004. ? № 1(90). ? С. 112?115.

11. Кудін В.І., Стеля Б.О., Пришляк К.О. Про коректність збурення одної лінійної системи в задачі побудови сплайна при змінах в розбитті // Журнал обчислювальної та прикладної математики. ? 2004. ? № 2(91). ? С. 71?74.

АНОТАЦІЯ

Кудін В.І. Розвиток чисельних алгоритмів аналізу лінійних моделей на основі методу базисних матриць. ? Рукопис.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 01.05.02. ? математичне моделювання та обчислювальні методи. Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2007.

Розроблено метод базисних матриць для аналізу та здійснення обчислень на лінійних та нелінійно збурених моделях від моделей лiнiйного програмування з поcтiйними елементами до слабкозбурених з функціональними зв’язками параметрів у її елементах.

Обгрунтовано модифікації методу базисних матриць: базисних допустимих матриць (МДБМ), псевдобазисних матриць (МПБМ), штучних базисних матриць (МШБМ), якi адаптовано для вивчення влаcтивоcтей моделей, зокрема, і великої розмірності. Розвинуто концепцію аналізу та оптимізації лінійних моделей методом базисних матриць на слабкозбурені.

Ключові слова: лінійна модель, обчислювальний метод, аналіз, оптимізація, базисна матриця, базисний розв’язок, пасивні та активні обмеження, малий параметр, регулярні збурення.

АННОТАЦИЯ

Кудин В.И. Развитие численных алгоритмов анализа линейных моделей на основе метода базисных матриц. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.02. ? математическое моделирование и вычислительные методы. Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2007.

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

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

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

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

Разработаны модификации метода базисных матриц: базисных допустимых матриц (МДБМ), псевдобазисных матриц (МПБМ), искусственных базисных матриц (МШБМ), которые адаптированы для изучения свойств модели, в частности, и большой размерности, на разных стадиях исследования.

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

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

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

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

Обоснованы условия устойчивости решения при возмущении модели.

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

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

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

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

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

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

ABSTRACT

Кudin V.І. Development of numerical algorithmes analysis linear models with application of mеthod of basic matrix.- Manuscript.

Thisis submitted for a Doctors degree in Technics on a speciality 01.05.02 ? mathematical simulation and computing methods. ? V.M. Glushkov Institute of Cybernetics National Academy of sciences of Ukraine, Кiev, 2007.

Mеthod of basic matrix for аnalysis and computation of linear and nonlinear models from models of linear programming with constant elements to weakly nonline model with small perturbation, is developed.

The modification of method of basic matrix: basic acceptable matrix, basic artificial matrix, basic pseudo matrix for analysis and optimization of behavior models such as large scale linear systems equation, inequality, is investigated.

The analysis and optimization linear and feeble nonlinear systems of methods

basic matrix to regulare and irregular perturbation, is developt.

Key words linear modes, method of base matrix, analysis, optimization, small parameters, feeble nonlinear systems, regulare, irregular, small perturbation, linear programming, basic matrix, psevdobazis matrix, basic solution, passive and актive restrictions.