Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

УДК 519.8

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

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

АВТОРЕФЕРАТ

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

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

РЯБЕНКО АНТОН ЄВГЕНОВИЧ

Дніпропетровськ 2003

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

Робота виконана на кафедрі економічної кібернетики Запорізького державного університету Міністерства освіти і науки України

Науковий керівник: доктор фізико-математичних наук, професор Перепелиця Віталій Опанасович, Запорізький державний університет Міністерства освіти і науки України, професор кафедри економічної кібернетики

Офіційні опоненти: доктор фізико-математичних наук Донець Георгій Опанасович, Інститут кібернетики ім. В.М.Глушкова НАН України, завідувач відділу економічної кібернетики

кандидат фізико-математичних наук, доцент Бурдюк Володимир Якович, Дніпропетровський національний університет Міністерства освіти і науки України, доцент кафедри обчислювальної математики та математичної кібернетики

Провідна установа: Київський національний університет імені Тараса Шевченка, кафедра математичних методів еколого-економічних досліджень, факультет кібернетики

Захист відбудеться 04 грудня 2003 року о 14 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті за адресою: пр. Карла Маркса,35, корп.3, ауд.25, м. Дніпропетровськ, 49044.

З дисертацією можна ознайомитись у бібліотеці Дніпропетровського національного університету за адресою: вул. Козакова, 8, м. Дніпропетровськ, 49050.

Автореферат розісланий 03 листопада 2003 р.

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

спеціалізованої вченої ради К 08.051.09 В.А. Турчина

Загальна характеристика роботи

Актуальність теми дослідження. На сучасному етапі реформування АПК та соціально-економічних відносин в Україні актуальними є питання налагодження сільськогосподарського виробництва, а також організаційні проблеми робочих колективів. Велике значення у вирішенні цих питань має застосування математичних моделей та методів. Математичні моделі, представлені в роботі, відносяться до процесів землекористування орними угіддями конкретного господарства, а також до проблеми формування цільових груп виконавців. В процесі математичного моделювання цих проблем виникли векторні екстремальні задачі на графах.

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

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

Цей напрямок виявився основним для більшості досліджень, присвячених математичному моделюванню дискретних систем та процесів в умовах багатокритеріальності. У створення цієї теорії вагомий внесок зробили дослідження відомих спеціалістів у галузі дискретної оптимізації: Михалевича В.С., Сергієнка І.В., Волковича В.Л., Перепелиці В.О., Червака Ю.Ю., Ларічева О.І., Подіновського В.В., Колоколова О.О., Ємелічева В.О., Кравцова М.К., Гірліха Е., Ковальова М.М. та інших учених. У ході становлення математичного моделювання дискретних задач в умовах багатокритеріальності визначилися напрямки, які включають дослідження структури та властивостей різних класів задач, розробку алгоритмів їх розв'язання, отримання оцінок трудомісткості розв'язку та інші аспекти. Проте не можна стверджувати, що теорія дискретної оптимізації в умовах багатокритеріальності достатньо розвинена.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертацію виконано на кафедрі економічної кібернетики Запорізького державного університету в межах загального плану науково-дослідної роботи кафедри, індивідуального плану підготовки аспіранта та науково-дослідної роботи за держбюджетною темою Міністерства освіти і науки України “Математичне моделювання, розробка методів багатокритеріального оцінювання для задач підтримки прийняття рішень в умовах невизначеності, розробка програмного забезпечення для візуалізації методів прийняття рішень, застосування методів теорії катастроф, детермінованого хаосу та фрактальної геометрії” (номер держреєстрації 0100V001723).

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

Поставлена мета визначає такі задачі:

побудувати математичну модель практичних задач, що розглядаються;

у загальній постановці векторної задачі покриття графа типовими підграфами виділити та дослідити NP-важкі та важкорозв'язувані задачі;

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

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

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

вирішити проблему розв'язуваності за допомогою алгоритмів лінійної згортки задачі покриття зірками графа з інтервальними вагами ребер.

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

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

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

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

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

здійснено обґрунтування оцінок обчислювальної складності для нових постановок задачі покриття графа, що досліджується, у тому числі виділено клас NP-важких оптимізаційних задач, встановлено важкорозв'язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у векторній цільовій функції (ВЦФ) двох критеріїв вигляду MAXSUM;

виділено нові поліноміально розв'язувані підкласи одно- та двокритеріальних задач у класах NP-важких та важкорозв'язуваних задач покриття графа зірками та ланцюгами. Розроблено відповідні алгоритми їх розв'язання, обґрунтовано поліноміальні оцінки їх обчислювальної складності;

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

побудовано малотрудомісткий алгоритм градієнтного типу для оптимізаційної задачі покриття графа скінченою множиною ланцюгів та доведено теореми про достатні умови його асимптотичної точності;

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

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

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

Результати роботи впроваджені в навчальний процес Запорізького державного університету при викладанні дисциплін “Дискретна математика”, “Методи дослідження операцій”, спеціального курсу “Багатокритеріальні методи прийняття рішень”, при виконанні курсових та дипломних робіт.

Особистий внесок здобувача. Результати, викладені в дисертаційній роботі, яка подається до захисту, отримані автором особисто. У працях, що написані у співавторстві з Перепелицею В.О., дисертанту належать: у [1] - розрахунок оцінок надійності для різних виглядів типових графів із множини припустимих 4-вершинних зв'язних графів; у [2,5] - доведення теореми про NP-повноту векторної задачі покриття графа типовими підграфами вигляду Н_3, обґрунтування достатньої умови важкорозв'язуваності багатокритеріальної задачі в загальному випадку та доведення відповідної теореми; у [3] - знаходження та обґрунтування властивостей поліноміально розв'язуваного підкласу оптимізаційних задач покриття графа зірками; розробка точного алгоритму для задачі покриття багатодольного графа ланцюгами; у [6] - обґрунтування достатньої умови існування одноелементної шуканої повної множини альтернатив для інтервальної задачі. У роботі [4], що опублікована у співавторстві із Заховалко Т.В., дисертанту належить доведення теореми про нерозв'язуваність цієї задачі за допомогою алгоритмів лінійної згортки критеріїв.

Апробація результатів дисертації. Основні результати досліджень, що включені до дисертації, доповідалися та обговорювалися на VI Всеукраїнській науково-методичній конференції з проблем економічної кібернетики (м.Київ, 2000); Міжнародній конференції “Моделювання й оптимізація складних систем (МОСС-2001)” ( м.Київ, 2001), на Міжнародній школі-семінарі “Теорія прийняття рішень” (м.Ужгород, 2002), Міжнародній науковій конференції "Problems of Decision Making and Control (PDMU-2002)" (м.Київ, 2002).

Публікації. Основні положення дисертаційної роботи опубліковані у 7 наукових працях. З них 4 статті у виданнях, затверджених ВАК України, 3 - тези доповідей на наукових конференціях.

Обсяг і структура роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел з 109 найменувань. Загальний обсяг дисертації становить 136 сторінок, містить 2 таблиці, 14 рисунків.

Основний зміст дисертаційної роботи

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

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

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

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

В існуючих теоретико-графових моделях формальне визначення припустимого рішення зводилося до знаходження системи циклів, що попарно не перетинаються, на заданому графі. Проте, на довжину циклів (сівозмін) у зазначених вище роботах не накладалося ніяких обмежень, що істотно звужувало адекватність запропонованих моделей агротехнічним вимогам. Також не здійснювалася “прив'язка” культур до конкретних ланів господарства. При цьому задачі розглядалися в однокритеріальній постановці, що також призводило до звуження адекватності цих моделей. При необхідності одночасного врахування всіх показників ефективності землекористування приходимо до математичного моделювання в умовах багатокритеріальності.

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

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

-вершинний N-зважений граф із множиною вершин, множиною ребер; кожне ребро зважене N-мірним вектором ваг, д ;

множина типових підграфів (ТП).

Для заданої пари всякий припустимий розв'язок є таким остовним підграфом графа, у якому кожна компонента зв'язності ізоморфна деякому типовому графу (типовому підграфу). Через позначаємо множину всіх припустимих розв'язків (МПР) на заданому графі .

При моделюванні реальних ситуацій (чи-це землекористування, чи формування цільових груп та ін.) якість припустимих розв'язків оцінюється низкою часткових критеріїв, що складають векторну цільову функцію (ВЦФ).

У визначенні критеріїв (2)-(3) параметри, є вагами, які приписані ребрам. Змістовно вага може відповідати, наприклад, врожайності певної культури в задачах землекористування або мірі психологічної сумісності пари виконавців у задачах формування цільових груп. Зазвичай критерії вигляду MAXSUM (2) відповідають сумарному економічному ефекту, а критерії вигляду MAXMIN (3) (критерії “вузького місця”) - “оцінці за найгіршим”, що відноситься до екологічних або інших критичних показників. Прикладом такого показника в задачах землекористування є показник відсоткового вмісту гумусу в орному прошарку.

Подана виразами (1)-(3) ВЦФ визначає в множині припустимих розв'язків паретовську множину (ПМ), що складається з паретовських оптимумів (ПО). Підмножина називається повною множиною альтернатив (ПМА), якщо при виконанні рівності її потужність мінімальна. Шуканим розв'язком багатокритеріальної задачі будемо вважати ПМА.

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

У розділі 2 “Дослідження обчислювальної складності знаходження ПМА для різних постановок задачі покриття графа типовими підграфами” ставиться за мету аналіз й отримання оцінок обчислювальної складності задач, що є математичними моделями поданих вище змістовних проблем. На сьогодні відсутні оцінки обчислювальної складності і однокритеріальних, і багатокритеріальних постановок задач покриття графів 4-вершинними зірками та ланцюгами.

Поняття "обчислювальна складність задачі" визначається в класичному сенсі - згідно з оцінками "за найгіршим випадком", які належать загальноприйнятій шкалі вигляду: “поліноміальні задачі”-“NP-важкі задачі” - “важкорозв'язувані задачі”. Зауважимо також, що поняття NP-важкої задачі означає оптимізаційну постановку NP-повної задачі розпізнавання.

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

Розглядається послідовність множин l-вершинних типових графів,; - множина всіх непорожніх підмножин елементів із,. З алгоритмічної точки зору задача покриття графа типовими підграфами стає нетривіальною, починаючи з l=2. При l=4 множина складається із шести типових підграфів, поданих на рис. 1.

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

Лема 2.1. При n, кратному 4, задача покриття n-вершинного графа типовими підграфами вигляду H₃ (“ракеткою”) є NP-повною.

Теорема 2.1. Оптимізаційна задача покриття 1-зваженого графа типовими підграфами вигляду з частковими критеріями MAXSUM(2) чи вигляду MAXMIN(3) є NP-важкою.

У п. 2.2. отримано оцінки обчислювальної складності оптимізаційної задачі покриття графа 4-вершинними типовими підграфами довільного типу. Доведено узагальнення теореми 2.1 на випадок, коли при визначенні МПР множина припустимих ТП (МПТП) складається з двох чи більшої кількості елементів. Цей результат сформульовано у вигляді наступної теореми.

Теорема 2.2. Для будь-якої МПТП оптимізаційна задача покриття 1-зваженого графа типовими підграфами з цільовою функцією вигляду MAXSUM (2) чи вигляду MAXMIN (3) є NP-важкою.

У п.2.3. доведена достатня умова важкорозв'язуваності векторної задачі покриття графа 4-вершинними підграфами для однорідних графів. Як відомо, всяку масову задачу прийнято називати важкорозв'язуваною, якщо трудомісткість її розв'язання не можна обмежити зверху поліномом від розмірності задачі. Для обґрунтування достатніх умов важкорозв'язуваності однорідних задач використана відома властивість повноти багатокритеріальної задачі (БКЗ). Надалі використані такі визначення й позначення.

Умовимося нумерувати перші шість одноелементних варіантів МПТП відповідно індексом. Через Z_q позначимо задачу у випадку, якщо при визначенні її МПР Х використовується МПТП.

Нехай Х - деяка індивідуальна МПР задачі , для якої заданий вигляд кожного з критеріїв (2), (3) ВЦФ (1). Багатокритеріальна задача (БКЗ) називається повною на МПР Х, якщо існує така індивідуальна ВЦФ , що для індивідуальної задачі ( ) виконуються рівності. БКЗ називається повною, якщо вона є повною на будь-якій індивідуальній МПР задачі .Вводяться також такі означення.

Означення 2.1. Розглянута МПТП називається -однорідною за ребрами або, просто, -однорідною, якщо всякий її типовий граф має одну й ту ж кількість ребер Т.

Розіб'ємо множину ТП на підмножини , де складається з Т-реберних 4-вершинних типових графів:

Означення 2.2. Векторну задачу називаємо однорідною, якщо її МПР визначена деякою підмножиною -однорідної МПТП.

Доведено, що виконується така лема.

Лема 2.4. Будь-яка однорідна задача з ВЦФ (1)-(3) є повною, якщо її ВЦФ містить критеріїв вигляду МАХSUМ (2).

Оскільки шуканим розв'язком БКЗ є ПМА, то максимальна потужність ПМА може служити нижньою оцінкою обчислювальної складності розв'язання задачі.

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

Доведено, що справедливою є така лема.

Лема 2.8. Для всякої задачі , нижня оцінка максимальної потужності її множини припустимих рішень визначається нерівністю:

Ця лема узагальнює відому формулу А.Д.Коршунова для обчислення потужності множини паросполучень у повному графі.

За визначенням важкорозв'язуваної задачі з лем 2.4 і 2.8 випливає теорема:

Теорема 2.3. Будь-яка однорідна задача з ВЦФ (1)-(3) є важко-розв'язуваною, якщо її ВЦФ містить критеріїв вигляду МАХSUМ (2).

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

У розділі 3 “Поліноміально розв'язувані підкласи задач покриття графа типовими підграфами” виділені поліноміально розв'язувані підкласи задач покриття графа 4-вершинними підграфами.

Спочатку розглядається однокритеріальна математична постановка задачі. Задано 4-частковий -вершинний граф з рівнопотужними частками потужності,,. Ребра зважені числами. Припустимим розв'язком задачі на заданому графі є такий остовний підграф, у якого будь-яка компонента зв'язності містить по одній вершині з кожної частки, і ізоморфна заданому ТП (є або зіркою, або ланцюгом); - МПР задачі. На МПР визначена цільова функція (ЦФ).

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

Теорема 3.1. Сформульована на n-вершинному 4-частковому графі оптимізаційна задача покриття графа 4-вершинними зірками з центрами, які є вершинами тільки однієї частки, поліноміально розв'язувана з обчислювальною складністю.

Доведення теореми є конструктивним, тобто для розв'язання задачі побудовано алгоритм та обгрунтовано поліноміальну оцінку його трудомісткості.

Аналогічний результат доведений для підкласу задач покриття графа 4-вершинними ланцюгами (тобто ТП виду ).

У п.3.2. побудовані й обгрунтовані поліноміальні алгоритми знаходження ПМА для 2-критеріальних задач покриття 4-часткового графа зірками і ланцюгами.

В одно- і двокритеріальних постановках розглядаються такі задачі:

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

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

У розглянутому -вершинному графі ребрам приписано вектор ваг. ВЦФ задач складається з критеріїв вигляду (2) та (3).

Проведено обґрунтування поліноміальної розв'язуваності підкласу векторних задач покриття 4-часткових графів зірками й ланцюгами. Доведена така теорема.

Теорема 3.3. Проблема знаходження ПМА 2-критеріальної задачі покриття 4-вершинними зірками 4-дольного графа, із рівнопотужними частками розв'язувана з поліноміальною обчислювальною складністю.

Аналогічний результат доведений конструктивно для задачі.

Поліноміальна складність знаходження ПМА доведена також для задачі-задачі про реберне покриття мінімальної ваги на 1-зваженому графі.

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

Нехай заданий 1-зважений n-вершинний граф і МТП,. У розглянутих вище постановках при визначенні МПР не накладалося ніяких умов на кількість підграфів кожного типу в припустимому розв'язку. Проте, в реальних ситуаціях умови такого виду зустрічаються. Наприклад, при формуванні цільових груп залежно від конкретики виконуваних завдань заздалегідь визначається структура групи. Аналогічна ситуація виникає, коли шукана система сівозмін складається з елементарних сівозмінних циклів заданої “польності”.

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

Для всякого припустимого покриття є однозначно визначеною його структура, де число - це кількість -вершинних ТП, які входять до покриття ,,. Позначимо через множину всіх структур, що притаманні покриттям. Необхідність знаходження розв'язків діофантового рівняння (4) і називатимемо терміном "умова діофантовості". Множину всіх рішень цього рівняння позначимо через, де. Доведена така лема.

Лема 3.5. Для того, щоб була непорожньою МПР індивідуальної задачі покриття заданого n-вершинного графа G підграфами із заданою МТП , необхідне існування хоча б одного розв'язку діофантового рівняння (4).

На основі леми 3.5. обгрунтована така необхідна й достатня умова непорожності МПР Х для повних графів.

Лема 3.6. Для того, щоб була непорожньою МПР задачі покриття повного n-вершинного графа G підграфами з деякою заданою МТП , необхідно й достатньо існування хоча б одного розв'язку діофантового рівняння (4).

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

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

Теорема 3.5. Верхня оцінка обчислювальної складності алгоритму знаходження множини всіх невід'ємних розв'язків діофантового рівняння (4) визначається нерівністю.

У п.3.6. виділений поліноміально розв'язуваний підклас оптимізаційних задач покриття графа зірками довільного типу з урахуванням умови діофантовості. Для обґрунтування цього підкласу розглядається задача покриття заданого графа зірками на графі , ребрам якого приписані скалярна вага, і на МПР визначена цільова функція, де множина визначена з урахуванням умови діофантовості (4).

Поліноміально розв'язуваний підклас визначається на 2-частковому графі, у якому вершини першої частки (другої частки) пронумеровані індексом, (індексом,). Будь-яке припустиме покриття складається із зірок, у яких центр є вершиною, що належить першій частці, а друга частка є множиною всіх висячих вершин зірок. Із цієї умови випливає, що в МПР X усяке покриття складається з однакової кількості зірок. Тобто, якщо пара, то для структур, виконуються рівності.

Нехай фіксована деяка структура, що задовольняє умові (5). Тоді вдається здійснити поліноміальне зведення задачі покриття n-вершинного 2-часткового графа зірками фіксованої структури до транспортної задачі. Доведена така теорема.

Теорема 3.6. Задача покриття n-вершинного 2-часткового графа зірками при фіксованій структурі z виду (5) розв'язувана з обчислювальною складністю.

Для деякої фіксованої множини типів зірок розглянемо послідовність діофантових рівнянь,. Оскільки значення T фіксовано, то фактично розглядається сімейство діофантових рівнянь зі скінченним числом змінних. Кількість різних розв'язків таких рівнянь, як відомо, обмежена зверху поліномом від . Це обмеження буде також виконуватися, якщо ці розв'язки задовольняють рівності (5). Тоді з урахуванням сказаного з теореми 3.6 випливає наслідок.

Наслідок 3.2. Задача покриття 2-часткового графа зірками при фіксованій множині їхніх типів є поліноміально розв'язуваною.

У п. 3.7 розглядається оптимізаційна задача покриття h-часткового графа h-вершинними ланцюгами. Для задачі побудований точний алгоритм її розв'язання і доведена теорема, що обґрунтовує його поліноміальність:

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

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

Твердження 3.2. Обчислювальна складність знаходження оптимального покриття 3-ланцюгами n-вершинного 2-часткового графа G не перевищує.

У п. 3.8. обгрунтовані поліноміально розв'язувані підкласи 2-критеріальних задач покриття 2-часткового графа зірками і ланцюгами. Розглядається задача 1 - покриття 2- часткового графа, зваженого вектором ваг, зірками, типи яких належать до заданої множини типів зірок (МТЗ), і структура покриття фіксована з урахуванням рівності (5). ВЦФ задачі складається з двох критеріїв - MAXSUM (2) і MAXMIN(3). Для задачі 1 розроблено алгоритм і обгрунтована його поліноміальна трудомісткість:

Теорема 3.8. Задача 1 розв'язувана за допомогою алгоритму з обчислювальною складністю.

Нехай позначає поліном, що служить верхньою оцінкою трудомісткості знаходження всіх розв'язків діофантового рівняння (4), які задовольняють рівності (5). Тоді з урахуванням наслідку 3.1. із теореми 3.8 випливає справедливість такої теореми.

Теорема 3.9. У випадку 2-критеріальної ВЦФ, яка складається з критеріїв вигляду MAXSUM і MAXMIN, задача покриття 2-часткового графа зірками є поліноміально розв'язуваною для будь-якої скінченної МТЗ. При цьому верхню оцінку обчислювальної складності знаходження ПМА можна подати добутком.

Аналогічний результат отримано для задачі 2 - 2-критеріальної задачі покриття наскрізними ланцюгами -часткового n-вершинного графа G. Для знаходження ПМА побудовано алгоритм і обгрунтована його поліноміальна оцінка трудомісткості.

Подані в розділі 4 “Наближені алгоритми для розв'язання задачі покриття графа типовими підграфами” є актуальними у зв'язку з песимістичними оцінками обчислювальної складності для досліджуваних задач, що отримані в розділі 2, і відносяться до двох класів алгоритмів: алгоритми з оцінками та алгоритми лінійної згортки критеріїв.

На відміну від традиційної міри обчислювальної складності “за найгіршим випадком” алгоритми з оцінками характеризують “типову” поведінку алгоритму або поведінку, що зустрічається найчастіше. Нехай задано: клас однокритеріальних задач, деяке сімейство Р імовірнісних мір p, визначених на К, і деякий алгоритм, що може бути застосований до будь-якої задачі z класу К. Вважатимемо, що алгоритм має тип щодо Р, якщо ймовірність для всіх.

Тут:- оптимальне значення ЦФ функції для індивідуальної задачі; - значення цільової функції на припустимому (не обов'язково оптимальному) розв'язку задачі z, що отриманий у результаті застосування алгоритму; - відносне відхилення від оптимуму значення ЦФ, яка отримана в результаті застосування алгоритму.

Надалі будемо говорити про клас К(n), сімейства, оцінки та їхні властивості залежно від параметра n.

Алгоритм з оцінками щодо сімейства розподілів Р(n) називається асимптотично точним щодо Р(n), якщо і при.

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

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

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

- множина всіх n-вершинних графів G=(V,E), у кожного з яких будь-яке ребро зважене N вагами.

Розглядається (N+1)-критеріальна задача про покриття графа G ланцюгами з МТЛ з ВЦФ, що складається із критеріїв вигляду MINSUM (2) та MINMAX (3), а також містить критерій кількості ланцюгів у покритті х:

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

Теорема 4.4. Якщо і , то для майже всіх графів алгоритм знаходить розв'язок, оптимальний за першими -критеріями ВЦФ (4.1), а за критерієм має відносне відхилення, що не перевищує.

У п..4.3 пропонується асимптотично точний алгоритм для задачі про покриття повного -вершинного графа скінченою множиною ланцюгів. Нехай Y - монотонно зростаюча послідовність чисел () на відрізку;;;;- довжина відрізка. Кожному ребру, () приписана вага, де - числа з послідовності . Для фіксованих і Y множину всіх таких графів позначимо через. У загальному випадку Y є функцією від : для будь-якого, і, причому значення завжди обмежене знизу деякою додатною константою. Припустимим розв'язком є скінчена множина ланцюгів графа , що є його реберним покриттям. Цільовою функцією є сума ваг ребер цих ланцюгів, що мінімізується.

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

Теорема 4.5. Якщо послідовність Y опукла і , то для майже всіх графів розв'язок x^* є асимптотично точним.

Наслідок 4.2. Нехай елементами послідовності Y є натуральні числа 1,2,.... Тоді при для майже всіх графів розв'язок є асимптотично точним.

У п. 4.5. досліджено питання про розв'язуваність інтервальної задачі покриття графа зірками за допомогою алгоритмів лінійної згортки критеріїв. Розглянуто задачу на заданому n-вершинному графі, кожне ребро якого зважене інтервалом, тобто відрізком, де.

В результаті здійснено зведення інтервальної задачі покриття графа зірками до відповідної 2-критеріальної задачі. У розділі 2 доведено, що 2-критеріальна задача покриття графа зірками з двома критеріями MINSUM є важкорозв'язуваною. Тому виникає необхідність у побудові наближених алгоритмів знаходження її розв'язку. Одним із підходів, що може забезпечити отримання шуканого розв'язку, є застосування алгоритмів лінійної згортки критеріїв (АЛЗК), яка має вигляд, де вектор,. Доведена така теорема.

Теорема 4.7. Для будь-якої пари n, h, де n кратне h, інтервальна задача покриття графа h-вершинними зірками з критеріями вигляду MINSUM нерозв'язувана за допомогою АЛЗК.

Висновки

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

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

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

Здійснено обґрунтування оцінок обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, в тому числі : знайдено NP-важкий клас в оптимізаційній постановці, встановлено важкорозв'язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у ВЦФ двох критеріїв вигляду MINSUM. Виділено нові поліноміально розв'язувані підкласи одно- та двокритеріальних задач у класах NP-важких та важкорозв'язуваних задач покриття графа зірками та ланцюгами. Розроблено відповідні алгоритми їх розв'язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності.

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

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

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

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

Список опублікованих праць за темою дисертації

Перепелиця В.О., Рябенко А.Є. Оцінки надійності в задачах формування цільових груп// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. 2000. №1. С. 90-93.

Перепелиця В.О., Рябенко А.Є. Дослідження обчислювальної складності теоретико-графової задачі формування цільових груп// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. 2000. №2. С. 100-104.

Перепелиця В.О., Рябенко А.Є. Ефективні алгоритми для задач покриття графів зірками і ланцюгами// Вісник Запорізького державного університету. Фізико-математичні науки. Біологічні науки. 2002. №2. С. 74-80.

Заховалко Т.В., Рябенко А.Е. Исследование разрешимости интервальной задачи покрытия графа звездами с помощью алгоритмов линейной свертки критериев// Питання прикладної математики та математичного моделювання.Дніпропетровськ: РВВ ДНУ, 2003. С. 55-65.

Перепелиця В.О., Рябенко А.Є. Теоретико-графова модель задач формування цільових груп//Економічна кібернетика: проблеми методології та підготовки фахівців. Матер. V Всеукр. наук.-метод.конф. К.: КНЕУ, 2000. С. 138 - 139.

Перепелица В.А., Рябенко А.Е. О принятии решений в задачах с интервальными данными//"Problems of Decision Making and Control (PDMU-2002)". Abstract. Киев, 2002. С. 85.

Рябенко А.Є. Оптимізація рішень для інтервальних задач на графах//Праці Міжнар.шк.-семінара “Теорія прийняття рішень”. Ужгород, 2002. С. 60.

Анотація

Рябенко А.Є. Математичні моделі та методи для векторних задач оптимізації організаційних структур та землекористування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02- математичне моделювання та обчислювальні методи. Дніпропетровський національний університет. Дніпропетровськ, 2003.

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

Основні результати полягають у наступному.

Запропонована узагальнена математична модель, що сформульована у вигляді векторної задачі покриття графа типовими підграфами.

Здійснено обґрунтування оцінок обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, у тому числі знайдено новий NP-важкий клас в оптимізаційній постановці, встановлено важкорозв'язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у ВЦФ двох критеріїв вигляду MAXSUM.

В класах NP-важких та важкорозв'язуваних задач покриття графа зірками та ланцюгами виділено нові поліноміально розв'язувані підкласи одно- та двокритеріальних задач. Розроблено відповідні алгоритми їх розв'язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності.

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

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

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

Размещено на http://www.allbest.ru/

Аннотация

Рябенко А.Е. Математические модели и методы для векторних задач оптимизации организационных структур и землепользования. - Рукопись.

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

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

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

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

Annotation

Rjbenko А.E. Mathematical models and methods for vector tasks of optimization of organizational structures and land tenure. - Manuscript.

The dissertation on competition of a scientific degree of the candidate of physical and mathematical sciences on a speciality 01.05.02- mathematical modelling and computing methods. The Dniepropetrovsk national university. Dniepropetrovsk, 2003.

The dissertation is devoted to the creation and research of the mathematical model for processes of forming of organizational structures and the use arable land.

The basic results are : the generalized mathematical model of processes under investigation, which is formulated as a vector task of a graph covering by the typical subgraphs has been constructed; the justification of the computing complexity estimations of the different formulations of the problem, connected with the graph covering by the typical subgraphs has been realized; the new polynomial solvable subclasses of one- and becriteria tasks have been allocated; the approximate algorithms with estimations have been developed and proved; the interval task of the graph covering by stars is reduced to becriteria statement and its unsolvability by the algorithms of linear criteria's convolution has been proved.

Кey words: mathematical model, organizational structure, land use, graph, vector optimization, computing complexity, polynomial algorithms, algorithms with estimations, interval task.

Размещено на Allbest.ru

...