автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Математическое моделирование и проектное обоснование стоимости некоторых классов гидросооружений

. - Академ1я наук УкраУни

г I О и Институт кибернетики 1мен5 В. М. Глушкова

На правах рукопису

ЛЯШКО Ольга Вжтор1вна

МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ТА ПРОЕКТНЕ ОБГРУНТУВАННЯ ВАРТОСТ1 ДЕЯКИХ КЛАС1В Г1ДРОСПОРУД

05.13.16 — застосування обчислювальноУ техн!ки, математич-ного моделювання 1 математичних метод1в у наукових дослщженнях

Автореферат дисертацп на здобуття наукового ступени кандидата ф)зико-математичних наук

КиТв 1994 Ш/с^у^

Дисертащею е рукопис.

Робота виконана в 1нституи тбернетики ¡мен! В. М. Глуш-кова АкадемП наук Укра1ни.

Науков1 кер1вники: академт АН Укра1ни

СЕРГ16НК0 1ван Васильович,

доктор (}йзико-математичних наук ДЕЙНЕКА Василь Степанович.

ОфщШт опоненти: академ1к АН Украши

ГРИГОРЕНКО Ярослав Михайлович,

кандидат <}мзико-математичних наук ГУЛЕНКО Володимир Петрович.

Провщна оргашзащя: КиТвський университет ¡меш Т. Г. Шевченка.

Захист в1дбудеться « ^ » — 199 / р. о ———

год. на засщанш спещал130ван01 вченоТ ради Д 016.45.01 при 1нститут1 шбернетики ¡меш В. М. Глушкова АН Украши за адресою:

252650 КШв МСД 22, проспект Академжа Глушкова, 40.

3 дисертащею можна ознайомитись у науково-техшчному арх1в! шетитуту.

Автореферат розкланий « ^ »

Учений секретар спешалвовано! вчено! ради

СИНЯВСЬКИЙ В. Ф.

ЗЛГАЛЫ1А ^.АРЛКТЬТ^СТИ-'Л РОГОТИ

Актуальность тоги, оа остзнш роки увага ^.атематиклв до розлитку, досшдженпя та шфоиадшшн 1..етод1в розв"язувэюш задач дискретного прогнозушшш не послоЛиисться. Це, нэсэм-перед, обумовлено тт.;, цо розв"язок богатьох практично важли-вих задач тин чи inim; шляхог: зводиться до рочв"язувашш задач дискретного програоднэння,-""эк, наприклад, побуд^ва ггд-ротеиично1 споруди, як правило,, поз"язана is Heo6xi,"Hic'fio tdнгniзацг1 деякого функционалу, в який ¡/.ore бути закладено сенс po3wiргв, склэдностг, варгостс, високиЛ ревень надп:ио-cti та in. Розв"язок таких задач ticho пов"язаиий з викорис-таинягл мэделе»; i метод! в дискретнся оптиигзацп при деяких обмехеннях но ¡рльтраш,;)п характеристики, до них же задач можнв В1днести деяй еколохччнг проблеми, до вимагаеться ура-хувакня rirpauii забруднень, процесхв переносу вологи i тепла щж розрзхунку конструкцЫ г/.пш/.ально! взги з обмежеюш-ыи на характррнстики . . itfunocTi та бзгато псиих задач.

На доний момент часу в областх дискретно? оптиизацТ? проводиться iнтснсивн! досшдження 3 розрос'ки метод!в роз-в"яэування pismjx miacis задач. У зв"язку з цик потрхбно вгд-MI тяти робот и ii. С.Михалевича, I.B.CeprieHKa, ЮЛ .1'ур. вльова, H.S.L'opa, В.А.Трубхна, Дк.аЗнцхгз,Лх.Бовдерсэ то хнеих як вгтчизняних, так i закордошшх вчених. Але посп.'лш зростоючг потреби практики шгагаоть додаткових доелгджень у nil. обло-стх знань. 'Гак, наприклад, при побудовг катшлатичкох !.;одел1 задач! t.'inir.'i зо!Ц'' вартосп пдроспорудп г,:и приходпмо до задач! гоготонного щлочиселъного програцувэння, тэбто до 1:зда-ч!, цхльопэ г у ниш я i о'гсг.ення hkoi с гонотоннш.-д (¡ункцхяг/.и. Природ:«!- при ш>01 у сгзс пптзтпш розробки [.-.етоду розв"язувои-№, як п.: лрохолував Си ui особлипостг задач!. ' :

Усе дозволяя зроблта висновок, що побудо-

па котеготичнях молодо.: задач про кхнгшзяцго пзртгетх ргз-них пдтоспоруд га розроСт eqcizrumix г.етол'ги ix роза"язу-взння е актуальною ззд,т?<""о.

!.>"гэ робот»: Г. Побуду вата 7'.отс-1.-ат::ч!:т мод ел г задач про tdi!ii.'.i33!rin BDjiTocT! piar.nx гхдроспоруд як зздачх г.зтекэтич-ного iiporpnryna'Ui.i. < ' i'/л .

- ц

2. Добудувати е^ективний алгоритм розв"язування задач ui-лочисельного програиування, а -¡ких шльоаа (р.ункщя i обнажение, с. МО но юн» ни и функциями.

3. На ocHoai побудоваиого алгоритму отриыати чисельний

' рс.,в"язо;< практично вагливоК задач! про uíHÍui3auÍD вартост! Ндроспоруди при задания уловах руху грунтових вод.

Методика доцпдкення полягае у використанн1 апарату тео-р i Y ф1льтрапП i Teopi'í дискретного програиування.

Наукова новизна. В дисертацП' побудован! «атеиатичн! ио-дел1 задач j'iiiiuí3auií вартост! широкого класу г1дроспоруд. Побудований алгоритм для розв"язування задач ионотонного ui-лочисельного програыуьання i показана doro ефективн!сть на да-ному клас! задач. Отрицал! результат« е новили.

Практична i теоретична ц!нн!сть. Використаиий у дисерта-uifiiiiíi pcíoTÍ пi^xiд дав зыогу розглядатн задач! про ы!н1и!за~ uic вартост! г!дроспоруд при задаиих уиовах руху грунтових вод як задач! дискретного програиування.Побудована на основ! зап-ропонованого цегоду роэрахункова нетодмка i розроблеиий коип-лекс ирограм викорнстан! для роэв"язання важливоУ прикладноУ задач!.

Основн! досл!джения проводилися в райках науково-дослЦ-лих -зец "Гсгрсбка автоиатиэовано? систеии ыоделивання процес!в »еплоиасопереносу" (ноиер дерхрее страцП б.О*» .01/014 за прог-раиос ДКНТ УкраКик) ! "Роэробка теоретичних основ автоыатизацП чисельного коделюваиня i оптюЛзацН ф1зичних пол!в на персональных коип"ютерах" (ноиер держреегтрицй" I/2IA Дераавиого фонду э фунданелтальимх досл1дхень- ДКНТ Украшай).

Реал!зац!я реэультат!в роботн. Результата дисертац1йно? роиоти використак! в 1иститут! г!дротехн!ки та ыел!орацИ Укра-'ÍHCbKO'i Аквдоый' аграриях ваук при проектуванн1 нових г!дротех-НÍ41UÍX споруд.

Anpodaui« роботи. Основн! результати дисергац!йноТ роботи допов!далмся i обговорсвалися на науково-техн!чних кокференц!-ях "Застосувания 0<5числ1>валы1О1 Texuiwi, иатеыатичних метод!в i иоделювання в автоиатизац!! експерииентальиих досл!д1вннь" (ы.Шв, 1987 р., ц.Ш&цьк, 1988 р.), ЕсеукраУнськ1П науков!й ковференцП паи"ят! Г.Ц.Поло*!я (и.Шв, 1994 р.), наукових се-uiuapax кафедри обчисл свально? иатеиатики КиУнського yHÍEepcH-

тету (u.KhYb, 1986-1994 p.p.)« I Укра^'яськ1й конференц!! э ав-тоиаткчного управляй* (м.Шв, 1994 р.).

Публ1кац1Е. За темою дисертац1йно? роботи опублхковано 6 друкованих праць.

Огруктура роботк. Дисертацииа робота складаеться 1з всту-пу, трьох глав, висиовку, списку осиовяо? використано? л!тера~ турк.

3UICT РОБОТИ

У вступ! зроблеио огляд результат1в досл1диень, поз"яза-них з темою дисергацП, обгрунтовако актуальном. обраиоУ теня, визяачено метод дисертацШю! роботи, подано короткий виг-ляд П зихсту.

У nepmifl глав! побудовап1 математичя1 иодед1 задач utni-uisauii Bapiocit широкого класу г!дроспоруд.

У поршоыу параграф! розглядавться задача и1нШзац!У вар-Tocti одношпунтового флвтбета при заданих умовах руху грунто-вих вод. У п.1.1.1. цього параграфа будуеться цатеиатична модель вкщевказано? задач! як задач! иачеи&ттпого лрограиуван-ля: серед ycix одношпунгових флютбе^в доваинов ta posuipa-ии шпунта В© (иал.1) знайти той, який нодае ыШыуц функц!-оналу вартостг

] + -»-nun , (I)

о О 0

Де АС , С« Ос) - функц!я вартост! одиннц{

дсвзани фяксбета в точи (ас, о) , - функц!я вартост!

одиииц! довяини шпунта в точц! ,

.U 'ZssyF'/A \ -yltTz-- -- ------ _

^И» шт ш» в» —- —— — — —

А» А* А ь ? ) с с. ' & с*

при 1йЦлх обиеяеинях иа ф1льтрац1йн! характеристике;

де Ус - ивидк1сть р1динн в к1нцевШ точц! флютбетйС | ^ I ' -^ 9 ^ * " Д0ПУст1* значения витрат води п!д г1-дроспорудоп, тнску п!д фявтбетом 1 ивидкост1 ф1льтрац1йного потоку в точц! С • Значения них ъеличпи повиин! эабззпечити запас и1цност! 1 спвкост! Ндрослоруди, як! гарантуваткауть И роботу в реальних уковах експлуйтац!I.

©*льтрац1йн! характеристики потоку ( 0. - витрати р1диак п1д г!дроспорудов, Р - тиск, Vе IVI ) визначаються через значения функцП твчгГ ^(ас,^) чи потенц1алу ивадкост! ян! пов"язан1 1иж собов умовами Нош1-Р1иана;

V*-Д^-гдт»,

де Г - л!н<я течЛ, Э - вектор дотичноХ до л!и11 тачх*

Функц1я е розв"яэкоы крайовоУ задач! для р1вгян-

пя Лапласа ^ ^

^ + Ъ^ ~ 0

кМ О

со

Пареит!, довдина флютбета 1 шпунта повинн! задовольняты деякнм обиеженняи Ьиенерного характеру:

а 4 АС 6 с , •

а (5)

О ^ В£> £ о ,

- 7 -

де & - глибииа эалягання водогривкостх

Матеиатична модель (1)-(5) б задача иатеиатичного програ-иуваиня.

8 п.1.1.2. задача иатеиатичного програмування (1)-(5) за-ы!нозться на задачу ц!лочисельного програмування. Для цього область &■ розв"язку задач1 покривасться соковое цножиною

таким чиной, шоб вшсонувалксь р1вност1 де

ос. - цШ <14,2,3 )

а- а- Ц ькх., зс^/о, (б)

в

®ушсц1онгл (I) при цьоау переходить у хакий:

* Фо(1&Л), 1(хА),К^ 1))- ,7Л

а обнажения (2) запишуться у виглядг

О^ЭС^Х^- Рд" ШХКХ % г

Сз:,( ОС,,ого - ^ % - ,

(б>

Такии чиной, отрицали задачу ц1почиселыюго програиуван-ня* зиайти точку ОС*) , яка и1н1и1зуе функц1онал

(1) при обиехеннях (6), (8), (9).

1з вар1ац1йних теореи Г.Ы.Полож!я доведен! два вакливих твердяення. __

Твердяення I. функц!¥ и^О*«,^»,^) 0 = 1,4 ), виэначе-н! р1вностяии (9), е монотонно зростасчиыи

Твердяення 2. Фунадонал Г«(.з\,зсг<а:,) , визкачений р!в-и!ств (7), в монотонно зростаючв функция своУх аргуиент!в.

Наприк!зц1 первого параграф зроблен1 деяк1 зауважения що-до, коректносг! заи1ни задач! (1)-(5) П чисельною иоделлв, тобто показано, що розв"язок задач! (6)-(9) иохе бути як зав-годно блкзыши до розв"язку задач! (1)-(5).

У другому параграф! першоУ глави розглянут1 деяк! 1нш1 . практичн! задач1 про и!н1и1зац1в вартост! г!дроспоруд при за-даних уиовах руху грунтових вод. Так, побудован1 матеиатичн1 иодел1 задач! про оптиы!зац!в флстбета з перепадами, шпунтами, заглиблен 1ши частицами ! дренаии; задач! ф1льтрац!г' через землян! переиички, даиби, плотини, причоыу 1з узагалъненняыи на виплдок введения енранушого ядра (непроникногв :• або слабо-проникного " включения в переыичку); иатеиатична ыодель задач! вибору оптимально! систеии древ1в. Для вс!х перел^^ених клас!в задач побудован! функционали вартостей 1 обмекевия 1 показана Ух ионотонн1сгь.

В третьему параграф! сфорцульована загальва задача ц1ло-чиселаного иатематичного програмуваиия, до яноК заеден! вс! приклади, розглянут! в попередн!х параграфах: наобх!дяо знайти точку , яка надае и!н!иуи фунхц!оналу

ГС*) —

тДп.

>

<ю)

при уыовах

0.1 (X) >/0 ,

• и* >.. I > 1М >

де <*;',-&; С ¿=<Л ) - числа; Г(Х), (¿Ч.т).

виэначвн! 1 зростасч1 на кнояии! А. фуикцП, причому эойра-нення фуккц1й5{(Х) У знглядх ябних анал1тичних вираэ!в ие обовмяэкове; фуикц1 ¥ 2а-ДХ) ) визначен! на мнояин!

А 4 иають явний анал!тичниЯ вигляд.

Задачу (10), (II) назвеио задачею монотонного ц!лочи-сельного програиування (ЗМЩ1).

Для перев1ркк точки Х^-А на виконання обиекзиь (II) необх!дно кожного разу розв"язухати крайозу задачу теор1'х фиьтрацН'. Тому, неэвгяавчи на ск1нчешпсть икояини А , <5еэпоов'оеди1й переб!р ус2х II. точок даноиу клас1 задач иеиожлмвнй. Ця обставина I привела до необхиност! розробки итод1э розвиязку ШШ (10), (II), в яких обкеження церев1рялиоя 6 лаймвнш ыохдив1й к1Дькост1 точок иножини Л.

Означения Точка X £> = А А В , де

В * { XI <3(Х) » о} , СИХ)• »Ж» { & С Х^

вазиваеться допустимов точное.

Оаначеяня 2. Иножиною точок, як! п!дходять для значения $ 6 » иязиваеться ыножина

Лексикограф1чно упорядковану в порядку спадання иножину

будецо позлачати З3^) Доведена теорема, на як!й базуеться ооновна 1дея алго-ритку роэв"язування 311Щ.

Теорема {. Нахай Х<£ £> . "Ь ГС*) . Тод1:

а) якщо ГУ О 55 0 , то X - розв"яэок задач1;

б) яйцо Х\ не в роэв"язкои 311Ш, то розв"язок знаходиться в ынокин! 3*( 1) .

Загальиа 1дея алгоритму розн"яэування ЗйЦП (10), (II)

така.

Нехай 25 тй 0 , в!дои1; точка И , значения £*ГСХ*) , «ноаина

, деяка поелиовшсть тонок , Р«0/1 ) 1 в1дпов1дна '¿я посл1довн1сть чисел -к- р), де £ ъ О - дсякс число, причоиу

{Н^Р-оМ01 ^ А Т($а)> (12)

На початку ?Н-ИтерацН аш»ходяення розв"язку_ X* задач! (10), (II) будуеио инохину . Надо ЗЧ-К)?- 0, то Х*= .В 1нзоиу випадку проводило посл1довний перегляд точок кнокиии » почкнавчк з перяоГ. П1~, переглядом точки роэу1пеио перез!рку И на налеан!оть облает! (II) шляхом обчиелення в ц!й точц1 значения функцП

йсх)> »»^{сисзо}.

— 1 ^

Шацо в инозин! 34"К) допуеттшх точок не 1онуе, то ¿Г розв"язок задач!. Якщо ж допустима точка зкайдепа, то зб!ль-иуеио % на одиницю, знайдену яочку прийиаеио за'елвиент £ послхдовност! ! розв"язок задач! продомузко. При цьоцу уиови (12) виконуються.

Доведена

Теорема 2. Залропонований 1терац1шшй алгоритм с ск!кчен-ноо процздурор.

Обгрунтоване твердкення про те, ко для эвахедяеиия розв"-язку задач1 число точок, в якпх необхщга обчкслвЕЕти значения функцН аСХ) , значно иениз{Л\ .

Друга глава дисертацП сгладаеться чотирьох парагра-ф!в I присвячена кошсретизацЦ загальнса где 1' алгоритму, Пого по!фоково1 побудови, питаниям ефективност!, а такок побудов! алгоритму зиаходвення локального игтиуму в ЙЩ.

В персону параграф! отргаанх рекур^иий зпхввадшпешщ для побудови МНОЯИН ( )| якх сфораульован! у

зигляд1 теорек. ^

Теорема 3. Кошюненти точки X ' знаходяться зг. ре курент-ним сп!ввш1ошонняи

* • и« Г г-*

| гI , I < ),

х , I * гп^С**),

m

- maoc {oc£ |CxJ1, x^,..., , X,,

5 t "'

Teopeua 4. Rexaü Bifloui точка i 4HCJIO

Тод! -5 t

ix.' , С < mtcs)

. 4»(it,Xsnt(i-0),i>mtcsjr

В другому параграф! розглядаеться процедура направленого неявного перебору точок кноииии ^PCjt) •

Встановлен! iaui теореыи. .-

Теорема Ь <пт>авнло в!до1Рвання IV Якщо X ' 6 ^("УО »

, то i,kCS>) точок.що 'опдуить 344г)

за точное , «в налг ать уноешп ф i явноиу перегляду

■о. £4

за точкой Л наленитъ точка Л i де

lxC%) ~ >riMc{i\xl''1* Ii t l- Vi] , SO) »St Iis, itCS)) + 1 .

П1д явниы переглядом точки А розум1еться перегляд uie'i точки при якоыу вимаджтБся обчислешш знаяенка ЕЦХ"),' •

Теорема б (правило в1дс!двання П). Нехай де 1ндекс ¿г($)такий, що вкконуеться система умов

Тод! ,

Теорема У (критеу!й оптимальное1!1!). Нехай на кроц! Ъ алгоритму при посл!довнону перегляд! точок мнояини СРС"^ от~ римана точка Х*'*" 2

Тодх: а) надо

х 'V ©

, то Н - розв"язок задач!; б) яюто X ' » то X ,,|С-розв"язок задач!.

В третьому параграф! побудований покрсковий алгоритм розв"~ язку задач! (10), (II), а такоа обговорена його ефектщшстъ шляхом пор!вняння числа явно ! неявно переглянутях точок.

Четвертий параграф прксвячений побудов! алгоритму знаход-яення локального иШиуип в ЗШ (10), (II), коля П точннй рсзв"язск невежливо знайти за р.рипусткмйй чао.

Трети глава присвячена постанови! обчислсвального оксперя-центу по досл!д£зннв запропонованого алгоритму при розв"язувйп-н! тестових ! ьрактичких задач.

В первому параграф! аргуыентовано обираеться ! розвмязуе?£-ся тестова задача монотонного ц!лочиселышго програмувашш. Задача розв"язуетьсн при рдзних вим!рностях, результати пор!вню~ сться !з розрахунками ц!б! х задач! методом вектора спаду. Зроб-лене пор!вняннй дозволяе зробити висновок, що при виы!риостях, характерних для класу розглядуваних задач (пэтуан!сть мноашш А порядку 103 + Ю5), запрспонований точний алгоритм но пос-тупаеться нав!ть набликеноиу методу вектора спада. Результата експерииенту вказумь такок на значку к!льк!сгь точок ыиожшш-Д , як1 переглянут! неявно. Так, приП^б" (|А\= Ю-*)

всього явно переглянутнх точок виявияооь лиие 683.

В другому параграф! наведен! результати обчнслювального експериненту по роэв"язувавнв практичной задач! м1н!и1э&ц1¥ вартост1 одношпунтового флотбета з ф1ксованим перепадом при эаданих уловах руху грунтових вод.

На зак1нченкя наведено висновки за днсертац!йног> роботов.

0СН0ВН1 РЕЗУЛЬТАТ« РОБОТИ

1. Побудорчн! иатеиатнчн1 иодел1 для задач ц1н1и1зац11 вартост! складних Ндроспоруд при эаданих уиовах руху грунтових вод.

2. Отрииан! задач!'зведен! до задач монотонного ц!лоче-селыюго програиувангч. Показана коректн1сть переходу в1д не-герервно! задач! до задач! !1Щ.

3. Розроблено иетод розв"язувания ЗШЩ, при якому к!ль-к!сть точок, як1 переглядасться на допустии!сть явно, и 1н1м1-зуеться.

4. На основх запропонованого методу розроблено комплекс програи, який дозволяв автоыатизувати розрахунки широкого классу г!дроопоруд, оптинальних за вартгот».

5. Чисельно реал!зо^ана постановка обчнслсвалыюго експе-рименту по досл!дяенн1> розробленого алгоритму при роьв"язуваи-н! тестових ! ванливих прикладних задач.

Основн1 п 0«71 ох б ни я да сертац1йно? роботи опубл1кован! у таких робота*:

1. Ляшко О.В., Третях В.П. Математическая иодель задачи оптимизации разиергв ыногоипунтового флютбета и алгоритм ее решения.// Тезидоп. наук, -техн, коиф; "Зас-тосу^ання обчислЕвальнох техя!ки, иатеыагичних метод!в ! ио-делввания в автоиатизацП експериментальних дослш.ань"

Ки¥в, 1987 . - С. 66-67.

2. Ляшко О.В. Решение одного класса задач минимизации стоимости гидросооружений у/ Тези доп. " таух • •• -техн'. • конф "Застосування обчислпвальнох техн1ки ! математич-них метод1в у наукових та еконоихчних дослиаеннях1;-Ки?в, 1986 . - С.63.

3. Ляшко О.В., Трзтлк В.Д. Роэв'яэувашш одного к ласу задач щлочкслового програмувания// Доц. АН УРСР. Сер. А. От а.-цат. та твхн1чнх науки. - ХУис* . - 1? 7. - С. 7о-7й.

4. Ляшхо О.В. Нахождение локального эхстрвиуиа в задаче об определении оптимальных размеров гидротехнических сооружений // Този доп. наук. техн. кииф. "Застосування обчаславаль-но! яакнгки I иатемлтичних мзгодхв у тукових та еконощчнях доеййд^аинях". Торнопхш», 1969. - С. УЗ.

5о Лтззко О.В. Про зкпзсадкашя локального ыхмцуиа в од-нхй аьдечх цхлочислоаого ирограыуаашш // ^осдаддення операций. - Ш. - № 39. - С. 37.

6. Ляшко О.В., Тротяк В.11. Алгоритм решения одного клас-сь задач целочисленного прогр2-шнров51шс с»ограшченяяш, зй-дьлгаамн б нзяепои виде // Наберкотака и систеюшй акдлиа. - 1993. - № 6. - С. 1о-1б.