Модели и методы решения непрерывных задач оптимального разбиения множества в условиях неполной информации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Р Г Б ОД

г ^ иіші із№

ДІІШРОПЕ’ШШСЬГШЙ ДЕРЖАВШЗЙ .

УШВЕРСКЇ'ЕТ '

ІІи правах рукоиигу

ЛОЗОВСЬІЇЛ Людмила ївапіена ЕШДЕЛЇ ТА МЕТОДИ РОЗВ'ЯЗАННЯ НЕПЕРЕРВНИХ ЗАДАЧ

оитшілдмшга поділу шгожтт в умовах їіеяовіюї.

' ІНФОРМАЦІЇ

Спеціальність 01.01.09 - математична кібернетика

АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня кандидата фшпісо-математіїч'ш.і наук

Д'’'проіютропсм< 1094

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

Робота виконала па ігафздрі обчислювальної математики та математичної кібернетики Дніпропетровського державного уііІЕЄрСИТЄТу. '

Їішуїюшгй керіппгац доктор фізижо-математичиих наук,

професор О.М. Кісальова.

Офіційні опопаптЕ.с _ члеи-кореспондент НАН Україїш,

. доктор фігико^деатематичних наук,

професор НЗ. Шор кандидат фізико-математичних пауз:,

■ доцент ИЗ1. Дейиєкв

ЕЗрввідец усїішоио: Інститут проблем кашибудувашш

. НАН України (ы.ХАРКІВ).

Захист відбудеться

,.у

1004 р. о ^Г ?од, на оасідшші спеціалізованої вченої ради К 03.01.02 по вахисту 'дисертацій па одобуття наукового ступеня кандидата фізико-матекатпчних наук при Дніпрояетроаському державному університеті за адресою: 320044, ьїДншроиетровськ, лр. К.І.-Іаріса 35, корл.- З, ауд,_42. •

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

’ Автореферат розісланий '* ^ 1004 р.

Ечешій секретар спеціапіаоваззої вченої ради кандидат фіа-аіат. наук, доцент

В.А. Турчина

з

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

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

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

Мета роботи. Метою даної роботи являється обгрунтування ієтодів і розробка алгоритмів розв'язання задач оптимального поділу НОЖИНИ з п-розмірного евклідового простору Е„ на підмножини, 4(0 не еретинакггьсп, в умовах неповної інформації про початкові дані, коли ^визначеність ситуації характеризується заданії ям апріорних говірних характеристик параметрів. Для цього необхідно було -ірішити слідуючі задачі:

1. Побудупати детерміноианий еквівалент початкової' !

стохг тичііоі задачі.

2. Одержати оцінку похибки, яка ~и!іикас при «шіні задачі оптимального поділу в умовах неповної інформації на детермінований екпівалонт.

З Розробити алгоритм розв'язання зада'/ олтималыюго поділу 0 умовах Неіюшюї інформації

4. Дослідити чутливість розв'язку до можливих помилок в визначені параметрів випадкових величин задачі.

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

‘ Наукова новизна. В роботі пропонується спрощений метод

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

' Одержані оцінки похибоїс заміни початкової стохастичної задачі

її детермінованим еквівалентом. Ясно, що для функцій лінійних або квадрати” ших -відносно випадкових параметрів, детермінований еквівалент буде точним.

4» '

Розроблені алгоритми розв'язання задач оптимального поділу множини в умовах невизначеності, ««ладовою частішою яких являється Г-алгоритм Н.З. Шора1*. .

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

детермінований еквівалент дає відносно велику похибку.

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

'* Шор Н.З. Методы минимизации иедйф4>еРенЧиРУемых функций и их Кйєз: Наукова душа, 1676. .

Реалізація результатів роботи. Запропоновані в роботі алгоритми користані при розробці математичного забезпечення для вирішення цач оптимального поділу в умовах невизначеності.

Публікації і anp<jC>iiuifi рубит По темі дисертації опубліковано 4 !к>ти. Основні положений та результати ' докладались та 'онорюиились на семінарах "Математичні методи геометричного >сктуітнтГ наукопкі ради ЛН України по проблемі "Кібернетика" иркіи, Запоріжжі!, 1004 р.) ти ни наукових семінарах кафедри іислютиіьіюі математики та математичної кібернетики ДГУ (1098, М p.). '

Структур! та об’єм робіть Дисертація складається із вступу, інрьг*. глив, ;<икіич*>іінн, додатку і списку літератури. Загальний нг роботи 15Н сторінок.

Змі<,і работ *

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

В главі І і»і;>,глндалась однопродуктова задача онтимальнаго Олу множини з Еп без обмежень а визначенням центрів множин в умовах неповної інформації (ОПМУ1ІІ) .

Математична постановка задачі ОПМУНІ мас вигляд:

Нехай Q - обмежена, вимірна по Лебегу ьипукла множина у іірному просторі Ev Потрібно поділити її на N вимірних по Лебегу множин Q,, iiN (серед яких можуть бути пусті) і розташувати три Т,, ..., tN цих підмножин D області П, так щоб

mes(Cit г\ С2к) = 0, і*к, г,кш1,2,...,Ы, (1)

mes(-) - міра Лебегу,

N ■

U Q,— Сі, . . (2)

іи цьому функціонал

Пь~;С1«}р {ті,...,Хлр})-М і f [с(х,Т(Д()'+-‘ЧІ-р(з:,4о)Ле (3)

.

ч. ав мінімального значення.

Тут і в подальшому інтеграли розуміютсн по Лебегу, Точка

—і 6 CJ{ ІМеїіуСТЬСЯ Центром ПІДМНОЖИНИ Q; at, _, О/, -

іні невід'ємні числа; UmQ,t„.„N) -

величини на ймовірному просторі (©,3,Р^ з відомими обмеженим] математичними сподіваннями \ о. ■••> \к і дисперсіями ^о, причому пари 4о»4< Для всіх і»= 1,2,...,ІУ - незалежні випадкові величиш Функції с(х,'1і,уі) дійсні, обмежені, вимірні по аргументу х на деякіі відкритій, обмеженій, випуклій множині випуклі по і, на IV

борелівські по уІ на множині значень випадкової величини £,*(©) длі всіх і=2,2,...,ЛГ; р(зс,у0) - дійсна, невід'ємна, обмежена, вимірна по X ш Й и борелівсьла по у0 ла множині значень випадкової величини %,,(©)■ Позначимо

, /0({£2и~,П«},т,4).==БІ-[с(х,Хі,^) + “і]*Р(^.^о)сіх, , (4)

■ *=ій, .

* Будемо вважати, що функції р(х,40), с(аг,т1,41), с(х,т„,^) -

двічи неперервно диференційовані по ^0, відповідно, на множині

значень випадкових величин £0, навколо їх математичних

сподівань %Я- ' '

Для ’заміни початкової етохастиної задачі її наближеним детермінованим еквівалентом розкл демо функцію/5({С5],...,С5ЛГ},Т,4) п ряд Тейлора навколо Залишаючої в розкладі члени до другого порядку включно і • застосовуючи до обох частин одержаного ряду

• операцію математичного сподівання, одержимо

М/°({Оі......Ом},х,£,)»!)| фі(х,хі)сіх ■

■ Тут і далі •

. ф<(Х, Т<) = £с(х, т<, її) + Оі+ .(х, т і, І і) |^р(х, І о) +

+|[с(;і:.'1ьІі)+о^оР50?0(а;До) (5)

Очевидно, що приблизна рівність в (Б) буде точною для лінійної і квадратичної відносно % функції />({П)1-.,Пдг},г>£).

Введемо характеристичну функцію піданожини £2/.

х*ад-• ' •

і перепишемо задачу (1) - (3) у вигляді:

.* знайти ші-у елементів (Я.(х)д.) (де А..(х)єГ, майже всюди («*.) ХЄО, Т.еСУО таку, що - ’

J(\.(-),x.) = inf ДЛ(-),т), (6)

(Ч-ИеПхП»

ї J(X(-),x)=jjt(pi(x,Xi)li(x)dx, (7)

Г, = {А.(х): А./х)=0 І м.п. длп xeQ, і= l,2,...,N; (8)

Хі(х) = 1 мл.для xeQ; }.

ьі •

Доведено, що оптимальне рішення задачі (6) - (8) має вигляд для

‘1,2,...,N ти майже всіх ХЄС2:

Wx)=lj’ , (9)

[0, хе C2\£2«f

> £3.г= ієй: ©<(х,ті)«гшп аи(х,хк)

І • ы,..,лгт

в якості Т„, Хти вибирається оптимальне рог’ч'язшпш задачі:

С(т) =| ШІП [фї(Х,Т;)] сіх -> тіп (10)

при умовах ТєО^. ' (11)

Сформульований алгоритм рішення задачі (б) - (8), сг-ладовсю істиною якого є ґ-алгоритм, шп використовується для вирішення да-і (10) - (11). '

Серед задач ОПМУНХ з визначенням центрів шдлтножіпі ізглпнута задача являється самою простою (далі, будуть розглядатися гатопродуктові задачі з обмеженнями). А так як в основі методів ізв’язання як указаної задачу- так і . тих, які будуть ■ розглянуті зніше, лежить перехід від податкової безкінечнорозмірної задачі до иечнорозмірної тилу (10) - (11), тому має рацію при діли ті! увагу слідженню властивостей мінімізуємо! функції Сї(т), а тшсоя: говорению ефективності алгоритма розв'язання цієї задачі.

Властивості функції С(т) із (10) для детермінованого випадку . ли досліджені в роботах СШ.Кісельової.

Розглядаючи функцію С(т), визначену на одиничному квадраті

= £2, в випадку, коли <:(х, тЕ,,-) = J(x-x■^ + (у-*{2)) -

гвдоевклідова метрика, р(Х,^0)=СОП5І УхєСІ, й„=0, і

ержавнш і! графічне зображення, та проводячи баготочисленні яіерименти по роза'язьітга ладач поділу випуклих' множин з ‘

з

визначенням координат центрш підмножин із різних початкових наближень, дозволяють зробити висновок, що як і у детермінованому випадку, допустима множина О* задачі (10) - (11) може бути представлена у вигляді об'єднання кінцевого числа випуклих підмножин, на кожній з яких цільова функція С(т) випукла, має точку локального мінімума Причому, значення функції С(т) в цих точках співпадають і являються глобальним розв’язком задачі (10) -( 11). На мал. 1 показана така функція С(т) у випадку, коли N—3.

• В загальному ж випадку задача (10) - (11) багатоекстремапьна

Мал. І.

Експериментально встановлена висока ефективність Г-алгоритму і при знаходженні глобального мінімума. За допомогою багаторазового використання Г-алгоритму а різних початкових наближень, завдяки його високій швидкісті за прийнятний час вдасться знайти глобальный к Ілім ум з вірогідністю, близькою до 1.

Запропонований алгоритм використовувався для розв'язання модельних задач поділу великих розмірностей - на 15, 100 підмножин.

■ Суттєво вдалося збільшити швидкість неграми (до 30%), реалізую*©! підпрограми, що працюють найчастіше на макроассемблером!.

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

В ш?-ЗІ 22 дисертації приводиться математична постановка детермінованого еквіваленту багатопродуктовоі задачі ОПМУНІ з обмеженнями у вигляді: .

Знайти пару елементів (к,{х),Хл) (ДР ^(зОбГІ, майже всюди (м.в.) дня ХЄІ), Т.еО") таку, що

ЛХ.(-),х.ї= тіп ./Ш-),т) , (12)

(У)Л)сГ'і*£3" • •

до •/(>.(•), <Р((х,х.-.ч»;, (із)

_ ЇУ’їм .

1 і = {А,(.г): Х(х) є Г м.в. для хєО, ;=1,2,...,М;

■ + 5р^,(л:.§і)Іі]М(х)сІаг- Ь<,

[р’(-г.§о) + Ь<” ‘-р+і.-^ );

( N.

тут 1 далі Г = |Х(х) : 2 Л.{(лг) =1 ч.ц. для хеО, і= 1,2......М;

0 і. \{(х) < 1 м.в. для жєО, і=1,2,...,ІУ, 3=1,2,...,М; }, срі(х,хл4»^)= •

-[с^(х,^.І{) + а{ + ч>,+ іс",4|(хІТі,І{)|{]р^(*Ді)+

+і[с?'(х,т1-,^) . + <** + чи]р^;(*;и)Іо •

Для розв’язання цієї задачі використовувався метод,

запропонований О.М. Кісельовою, який базується на переході від цієї нескінчміорозмірної задачі оптинізації через функціонал Лагрзнжа, в який вводяться обмеження (14), до сіїр'їженоі кінцевсрозмірнаі задачі, що не залежить від прямих змінних Я(-)- ’

Одержане рішення цієї задачі для і= і х*з. дня

ХєСЗ у вигляді:

ХІД*)»!1, хєа^і ' [О, ігП\ПІ(

де ОІ(= хе О: тіп ф^(х, х*ь,ч;^)|, а в якості

' М,-№ ‘ і

Т,=(їм,...,Т,к), V}/*,вибирається оптимальне рішення двоїстої

задачі, зведеної до вигляду: .

£?(>{/) =тіп 1 Й тіп Г<р{(х, її, ч^Ь{ і -» тах ,

гей" -І. J

прі умовах '{1,20, і=р+1,...,№. ■

§ 2.4 присвячений оцінці похибки дете ^мінованого еквіваленту.

З&ппопоновашій в § алгоритм розв'язання задачі (14) - (15), складовою частиною котрого с Г-алгоритм, генерирує послідовність, яка сходиться в загальному випадку до локального мінімуму.

В § проілюстровано застосування викладеного методу для розв'язуваная модельних задач.

В главі Ш розглядається ЛШ-модель (в термінах Сортирова1’, або •в умовах неприйняття ризику в термінах Ховарда2") багатопродуктової задачі ОПМУНЇ при обмеженнях. Очевидно, що М-модель, розглянута в

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

таких випадках сумнівно вважати "перше" рішення

{хі,._,Тл?}^ кращим ніж "друге"

^{С2},—,Сїя},{Хі,._,Хм}^ , якщо "перше” в порівнянні з "другим"

забезпечує менше значення М/*(-), але' призводить до суттєво більшого розкиду його значень. ‘

В подібній сіітуаціі необхідно знайти розумний- компроміс між бажанням максимально змеш^ити показник в середньому і у той же час не допустити значного збільшення його дисперсії. Таким компромісам можна назвати Г.ГО-модель задачі ОПМУШ.

Ця задача відрізняється від М-моделі задачі ОПМУШ глави П тільки тим, що цільовий функціонал і обмеження доповнені доданком, який включає дисперсії І)/’(-,хД), і=0,2,...,ДО. '

Математична постановка цієї задачі приведена в такому вигляді:

Потрібно поділити множину О з Е„ на М-АГ вимірних пп Лебегу підккожин. 0|, Сі $ (серед котрих можуть бути пусті) і розташувати центрі X,,Х„цих підмножин в області С2 так, щоб

т«(о{г»п{) «0, Ьк, і=1,2..М,

йоІ=Сі, (і;:..

<=-1 1

** Вощит.н АЛ, Сортиров ГР. Оптимизация в условиях неопределенности. //• МЭИ - СССР., Техника - НРБ. - 1989.

Howard Ronald A. Prcorimal decision analyr-s // Management science. -Voi.17., Na9. May, 1071. •

м/*-({0',.х,4) +|г(М/<,)ї>/і({а1................о*Л,*л) -&<.

і=і,...,р, (іб)

*м/*( {о},.... о#}, х, *) + іг(М/°)0/і({0',...,а%},X,$) * Ьі.

. І-Р+1....Л (17)

і щоб функціонал = (18)

досягав мілімаг .ното значення, причому

5-М Й| рі(х, $()дг + |г(М/°)П Й| р*(х,!&)вх <Е Ь< , (19)

0<Ь(<5, і=3,2..ЛГ.

Тут т(-) - та): названа міра неприйняття ризику, невід'ємний ваговий коефіцієнт. Відповідним вибором т(-) можна зняти протиріччя між зменшенням значення функціоналу в середньому і абільшеїшям його дисперсії. Коефіцієнт г(М/®) можна ввести як г(М/°)=» — • де гі(-) - функція корисності, задана у вигляді іі(/й(.)) ~ (і - ^. Б цьому випадку Г міра неприйняття

ризику не залежить під М/° і визначається як ґ(М/°) = у/Д, дэ у^О.

Далі, діючи по схемі розв'язання задачі а глави II, додатково оцінивши дисперсії та вводячи 'характеристичну

функцію підмножини одержано розв'язання нової задачі.

Очевидно, що задача (15) - (18) перетворюється нп задачу з глави II при у=0.

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

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

В закінченні '‘.формульовані • основ», результати роботи, котрі виноситься на захист:

. 1; В дисертації запропоновані наближені методи рози'жіанни деяких задач оптимального поділу множини із знаходженням центрів підмножин и умових неповної інформації:

- однопродуктової задачі оптимального подіну множини ґч-п обмежень;

- багатопррдуктової задачі оптимального поділу множини а

обмеженнями II формі рівнянь та НерііШОІ.ТЄИ.

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

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

8. Проведені дослідження чутливості цільового функціоналу і координат підмножин оптимального поділу множили.

. 4. Розробле'не математичне забезпечення для розв'язання розглянутих неперервних задач оптимального поділу множини

■ в умовах неповної інформації, а також дослідження чутливості.

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

В додатку приводиться опис програмного забезпечення,

розробленого на . мові "С" та "макроасемблерові” в середовищі "Вогіапсі . С++' УЗ.І", і призначеного для розв'язування задачі оптимального поділу множини з обмеженнями в умовах неповної інформації з визначенням центрів підмножин, орієнтованого на розв'язання задач оптимального поділу множин з Ег з' будь-якою кількістю підмножин і "продуктів". Для виконання всіх графічних робіт по виводу уточнек-іх кордонів між підмножинами, дослідженню вигляду функції С(т) і '• чутливості використовується пакет "РС-МаїЬЬАВ".

Конкретна особиста участь автора ц одержані наукових

а

роБртак. Співавтором по публікаціям

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

Ошовні Ейзулмюи ддаептадії 0пу&іштш в розгах:

1. Киселева ЕМ., Гордиешсо (Лояозсі:ап) Л.И. О оценках

погрешностей и алгоритмах оптимального разбиения. .// Решение прикладных задач математической физики и дискретной математики. - Днепропетровск: ДГУ, 1987 г. -с.70-77. ■

2. Киселева Е.М., Гордиегасо (Лозевскші) Л.И. Приближенный

метод решения одной стохастической задачи оптимального разбиения. - // Решение прикладных задач математической физики и дискретной математики. - Днепропетровск: ДҐУ, 1987 г. - с.77-84. • .

3. Киселева Е.М., Гордиенхо (Лозовская) Л.Л. О пріСлшкенном

решении стохастической іінегспродуктовой сада’пі оптимального разбиения с размещением центров тяжести подмножеств.' // Вопросы прикладной 'математики и математического моделирования. - Днепропетровск: ДГУ -1008. - с.8-10. :

• 4. Лозовская Л.И. Оценка погрешности алпрокстимаций одной

непрерывной стохастической еадачи ее детершашрованкым эквивалентом. // К: Деіі. в ДНТБ України 07.02.94, ДЕП 252-УК94. ' 1 ’

'„■■'Г іРо