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

Нац!снгль:-»а ахадем-1я каук УкраТни 1нститут тбернетики ¡мен1 В. М. Глушкова

ОД

На правах рукопису Б1ЛЕЦЬКИЙ Василь 1ванович

УДК 519.853 + 681.3.06

ДОСЛ1ДЖЕННЯ ТА РОЗРОБКА ЕФЕКТИВНИХ АЛГОРИТМ1В ТА ПРОГРАМНИХ ЗАСОБ1В ПРИЙНЯТТЯ Р1ШЕНЬ В ДЕЯКИХ ЗАДАЧАХ ОПТИМАЛЬНОГО ПРОЕКТУВАННЯ ТА БУД1ВНИЦТВА ЗАЛ 13 НИ ЦБ

05.13.02 — математпчне моделювання в наукових досл1*дженнях

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

К"Ув 1996

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

Робота виконана в 1нституп юбернетики ¡меш В. М. Глушко-ва HAH Украши.

Науковий KepiBHUK: член-кореспоыдент HAH Украши, доктор ({мзико-математичних наук ШОР Наум Зуселевич.

ОфЫйш опоненти: доктор техшчних наук

КОЗЛИК ГригорШ Олександрович,

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

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

Захист в1дбудеться « ^ » fe^/^S/t-^ —_ 199<^f р.

Qlr/. Ду0д на засщанш спещал1зовано! вчено! ради Д 01.39.06 при 1нститут1 юбернетики ¡меш В. М. Глушкова HAH Укра!-ни за адресою:

252022 КиТв 22, проспект Академжа Глушкова, 40.

3 дисертащею можна ознайомнтися в науково-техшчному apxißi шституту.

Автореферат роз^ланий «—» —£- 199'f>.

Учений секретар Ji/fT^

спещал!зованоГ вчено! ради РЕВЕНКО В. Л.

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

¿ктуальн1стг. уобот. Одною з важливих галузей застосування ефективних математичних метод1з в зал1зничне буд1вщцтво.

УкраХна - держава, яка характеризуеться р1зноман1тн1стю при-родних умов те природних Сагатств. Це позяачаеться на сво«р1днос-т1 промислового, с1льськогосподарсь»ого виробництва та транспорт-но1 системи.

В тепер1шн1й час в1д0уваеться переОудова економ1ки в умовах коротко! енергетично! кризи. Сал1зничкому транспорту на;чоI краХни належить пров1дна роль з транспортному обслуговуванн1 промноловос--т1. с1льського господарства та населения. Питома ваге зал1зниць УкраХни в вактзжооб1гу вс1х вид1в транспорту збер1гаеться ста-сЯльною 1 складав Олизько 46Ж. Тому подальший розвиток економ1ка УкраХни, IX стаб1л1зац1я багато в чему залежать в1д нэд!йного функц1онування транспсртноХ системк, зокрема - в1д зал1зничного транспорту, як духе вахливо! XX складовоХ частини.

Протв 1снуючкй матер1ально-техя1чний стан залХзничного транспорту, жалюгХдаий стан зал1зниць (приблизно на 20 тис. юл кол'й потрЮна повне замХна рейск), низьк1 евидкост1 руху по!зд1в не дозволяють розв'язувати проОлеми трансиортннх перевезень з ураху-ванням вимог, як1 ставляться перед зал1зничним транспортом сучас-ними умовами.

Одним 1з спосо01в досягнення ефективност! роботк ззл1зничного транспорту в суттевв п1движения швидкост1 руху.

В 1985 - 1990 рр. кафедрою пошуку, проектувзння та буд1вниц-тва зал1зниць Дн1цропетровського 1нституту 1нженер1в зал1зничиого транспорту Оув проведений анал1з деяких д1лянок зал1зничних л1н!й УкраХни, на основ1 якого зро0лен1 висновки, що п1двищення швлдкос-т1 руху пасажирських по!зд1в нав1ть до 120 км/г не доц1лъно через складний план та проф1ль, хвороби та деформацП земляного полотна. Для орган1зац1Х високошвидк1сного руху пасахирсышх по!од1в у сучасних умовах стае важливим модэрн1зац1я 1снуючкх зал1зяичяих л1н1й, а також буд1вництво новях зал1зниць, як1 в1дпов1дали о м1жнародним нормам, що, звичайно, потреоуе розв'яз&кня складних практичних задач по проектуванню та Оуд1вкицтву поздовхньогэ про-ф1лю зал!зниць. До проектних л1н!й високошвидк1сних маг!стрелой

судуть вистэвляться б1льа корстк! вимогл но допусках у ф1зичних та геометричних параметрах. Буд1вництзо еисокошвкдк1сних л1н!й потре-Оуе в!д проекта:!- та СудХвельнкх орган1зац1й заетосування сучасних технологий, ефективних сбчислювальних засо<31в для знгходжешя оп-тпмальних розв' язк1в. Без таких за'соС1й не о01йтися 1 при реконст-рукцИ 1снуючнх зал1знкць. Тому розробка ефективних оочислывальних ззсо01в, як1 б позволял:! оперативно та на перспективу приймати оп-тшальн1 р1шенил при реконструкцП, проектуванн1 та буд!вництв1 зал1зничлих маПстралей, е актуальном.

Метэ робот;;. Бэгато практкчких задач тхланування та проектування, як1 впникають у залХзшгаому будШ:ицтв1. маюгь велику розм!рн!сть. Характерною особлив!стю 1х в наявнХсть велико! к1ль-кост! р1зкоман!шо1 та спещ1ф1чно1 ЬК^рмеаП, а також' ус1ляких фактор1в, що не завжди повн!стю форшл1зую?ься. При оперативному розв*язуванн1 таких задач нер1дко достатньо набл:даного, а не точ-ього розв'язху. який вимагае значно (Яльше затрат у час1 та ще й-не заведи усп1шно зак1нчуеться. В таких умовах ваяливима е виб1р мотод1в та розробка ка 1х оснэв1 прикладных програмшх засоб1в, як1 забезяечували б потрЮну точн1сть р^з'язку за долустимий час.

Метою робота е досл1джеяня та розробка ефективних алгоритм1в та программах засоб!в пр'.йнлття р!щонь у процзс1 розв'язування оп-тим1зац1йких задач проектування та оуд1вництва нових зал1зниць, реконструкцП старих зал1з:птчних л1н1й.

Метолт досл!гуень.-При розробц1 та досл1даенн1 алгоритм1в ви-ксристовувався мьтематичн:^ апарат метод!в, котр! до^ре гарекомен-дувзлл себе на прэктт;1 при розв'язуванн1 бэгатьох задач плануван-ня тс проектування. Таки?л1 е розроблен! в 1нститут1 кМернетики 1м. В.М.Глушкова Нац1ональыс1 АкадемП наук Укра!ки (1К НАНУ) Н.З.Шором метода узагалькеного град1ентного спуску з розтягуванням простору (УГСРП), а такозс розреблений В.С.Михалевцчем та Н.З.Шором метод посл1довного анал!зу вар1ант1в (ПАЗ).

Одним 1з засоб1Б дос."1дження ефективнсст1 розробленях алго-ритм1в е перев1рка 1х працездатност! в комплексах прикладник та серв1сних програм (пакетах прикладнкх програм), розроблених на основ! сучасних метод1в побудози прихяадних програмних систем та ре-ал1зацП 1де! В.М.Глушкова про системну оптш1зац1ю.

Науковз новизна. На основ1 досл1джень те еистемагизацП нако-пиченого доевхду виявлен! новх задач!, цо маыть важливе практична

значения в процес1 проектування та оуд1вництвз зал1знздь, розроб-лен1 1х математичн! модел1.

Запроггонозан1 та реал1зован1 нов! п1дходи до розв'язування цих задач, цо урахогують 1х особливоот!, надають. спец1ал1сту за-л!зничного буд1вництва можлкЫсть оперативно розз'язувати задач1, дозволяють йому активно Срати участь у формуванн! приЯкягаях р1-шень, отримати кращ! людлно-машинн! вар1а,нти»

Для розв'язувашя задач розроблен! нов! ефзктизн! алгоритма. прост1 та зручн1 в користуванн! 1 .так1, то добре реал!зую?ься в д!алоговому реким1 з користувачем.

Розроблено проблемно~ор5.едтованйй пакет прикладаих поограм Д1СПАВ, який дозволяв в пакетному та д1алоговому режимах сг:ец1д-л1отам (непрограм!стш) розв'я'рубэти низку "опт$цл1зацШ|ИХ" задач проектування та буд1вництьа зал1знкць, а також задач по Шдгстоз-ц1, контролю вх1днс! 1нфсрмац11 та видач1 в зруч.н1й да: користува-ча форм1 результатов розв'язувантш."

Практична ц!кя!сть. Описан! в дииертацП спта;!зац!йк! алго-ритми та розроблен1 на Хх основ1 програмн1 засоби каьть вааслизэ практично застосуваннл для розв'язувашя основных з^дач в галуз! зал1зничного буд!внщтза. Пакет Д1С1ЪШ чи його аналог можне ззсто-совувати на р1зних стад1ях склацання та експертизи просктних вар!-ант!в, у процес1 проектування, буц!вккцтва та роконструкц!! зал1з-ничних л1н1й з урахувэкням динам!кк розьитку об'вкта та р!зких фактор1в, як1 вимагають вчасного коректування осяовних парет,-.етр!в проектных розв'язк1в. В1н моке використовуваться у в1дпов!дних системах автоматизованого проектування та кзрування буд1внп.дтвом, у рамках яких мокэ бути значно прискорениЯ пошук кращах цроектнил. та керуючих р1шень шляхом проведения посл1довних оптимзльних ко-ректувань попередн1х вар1ант1в на р!зша еталах "жкттевого" циклу об'екта, п1двищена роль спец!ал1сха ъри оперативному пошуку краалх людино-мапяшних розв'язк1в..

Апробац1я результата роботи. Результата розробок пройзлп ап-робац!ю на багатьох рэальних об'ектах. ЕксперимемальШ досл1джен-ня виконувались за матер!алами техн!чного проекту при проектуванн! складних д1лътщь БайкалотАмурсько! маг!страл1 (Чуро - йнчукан, Чара - Леприндо, Сльокма - Вельбеткан та 1н.) на стадИ розробки робочих креслень. Результата розь'язувань впровадаен! при споруд-женн! друго! колИ зал1зшино1 в!тки Абакан - Тайшет й ново! за-

л1зниц! Обська - Бованенкоьо.

OchobhI результати розробок допов1дались та обговорюзались на четверт'й школ1-сем1нар1 (м.Сухум1, Ю - 19 траЕня 1982 р.), на сем1нарах Республ1канського будинку економ1чно1 й науково-техн'чно! пропаганд:! по досвхду викеристчкня, перспектив розвитку та застосувакня пакет1з прикладных програм (m.KiiIb, 13-14 жовтня 1937 р., 23-24 жовтня 19Э0 р.), на сем1нэрах науково1 ради HAH Укра1ни з проблема "Кибернетика".

рубл1каШ1. OchobhI резух.ътати за темой дисертацИ опубл1ко-ваыо в семи статтях, список яких наведено в к1нц1 автореферату.

На захист впносяться математичн! модел1 тг алгоритма розв'я-зувакня основних оптим1заи1йних задач, що виникають у npouecl про-ектування та буд1внидтЕа зал1знипь, а також програмн! засоби прий-няття р1шень при оперативному розв'язуванн1 цих задач та ЕИбор! кращи людашо-мажннюс вар1ант1в.

Структура та обсяг гисертацЦ. Дисертац1я складаеться з всту-пу. трьох розд1л1в, зак1нчення, списку л1тератури та додатку. Робота викладена (без додатку) на 102 стор1нках машинописного тексту. Список л1тератури нараховуе 67 нацмену нь.

3MICT ДИСЕРТЛШ

У бсшугЛ обгрунтовуеться ?.ктуальн1сть досл1дкень, про як! йде мова в дгсертацП, с£юрмульован1 мета досл1джень, наукова новизна та лрактичне значения роботи, наводиться короткий зм1ст розд1л1в дисертацИ.

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

Зазначаеться, виходячи з практики буд1вництва, цо зал1зшщя -це складний об'ект 1з сво!«и специф1чними особливостями, зимогами економ1чного характеру. Бона тЮко пов'язана з районами, як! при-лягають до не!, з1 своерШжм керуванкяч природними та виробничи-ми процесами. Буд1вництво зал1зшщ1, як правило, ведеться по типо-вих проектах, однак спорудження кожного сб'екта зд1Ясшзеться в не-

- ь -

однакових 1нзсенерно-г&олог1чних та прирсдно-кл1«ьтичних умовах оу-д1вництва. Розрив у час1 м!зк завершениям розробки робсчого проекту та його реал1зац1ею, чяст1 непаредбачен! та неспод1аан1 зм1ни си-туац1й на об;вкт1 буд1вництва стають основою для коректув&яня ра-н1шв прийнятих вар!ант1в (як безпосередньо перед початком буд1вни-цтва, так 1 в процес1 його)_ та, прибняття таких р1шень, як! б у б1лып повн1й м1р1- в1добрежп.ли реельн1 ситуацП, зменшил" витрати вкладуваних ресурс!з та не призвали, -до непоправних насл1дк!я.

Досл1дження, як1 проведен1 1нститутом к1бернетики 1м. В.М.Глушкова НАН УкраХшт спХльно з трестом "Бамстроймехан^зацчя" та СКВ ГолозбамОуду з проектування та. 5уд1зництза д1лоюк зал1з-ниць, що находились у складких умовах буд1вництва, показали, що задач! пошуку оптимальних розв'язххв щодо проф!л» дорХг.вимагають розробки таких метод1в, моделей та злгори'л'Лв, як1 бу.та б досить ефоктивнкми та забезпечкли мокливЮть участ! снец1ал1ста в пошуку кращого лвдияо-мащнного вар1внта. розробка уфективного м&тематич-ного забезпечекня, як показуе.акал1з та уззгальнення накопиченого матер1алу щодо розв'зування деяких оптим1зац1Дних задач проектування та буд1вництва залХзниць. мозклгва на основ1 реал1зац1Х 1де1 В.М.Глушкова про системну оптим1зац1ю. Пояснюзться це там, що задач! вибору опттаальних проектпих парам?тр!в щодо профХлю зал1з-ниць потр!бно розв'язувати в комплекс! "зал1зниця - навколганв середовище". Зал1зницю та райони, як! прилягаать до не!, нэоохХдно розглядати як складну систему з урзхуванням особливого 1х взземо-зв'язку, вимог та впливу Хх на проектн1 розв'язки загалом та го-крема.

За складнях'умов 0уд1вництва вшшкають багатокритерХальн! та багатоекстремальнХ задач1 з негладкими цХльовими функц1яии. При Хх розв'язуванн1 потр1бно зраховувати багато р!зномак!тних фактор1в, серед яких е так!, що ванко формал1зуються або взагал1 ке формел1-зуються, оц1нювати вар1анти-в умовах визначеяост1 та невизначено-ст1, реал1зовувати формальн1 й неформальн! процэдури. Реальн1 умо-ви буд1вництва часто залекать 1 з!д витадкових Фактор1з, як1 наяэ-ред н!як немояливо передбачити. За таких уков кращоь е схема розв'язування, що дозволяе спец1ал!сту зал1зничного будХвництва активно брати участь в обчислювальному процес1. А для цього потр!-бн1 алгоритми, як1 мокуть надати спец1ал1сту, залекно в1д поставлено! задач!. моалив1сть керувати процесом розв'азувакяя, оц1яша-

- в -

ти варХанти, приймати остаточна р1шбнпя в'^одячи з конкретно! точки зору спец!ал1ста на основ1 цШсного Сачення проекту.

Задач1 проектування та 0уд1вництза зал'зющь е задачами нел1-н1йного програмувакня с обмеженнями типу р1вностей та нер1вностей 1, загалом, недиферешЦйовними ц1льэбимп функц1ящ. Для 12 розв'язування ефективними е широко в1дом1 у практи'щому застосуванн1 метода узагальненого град1ентного спуску з розгягуванням простору та посл1доркого анал1зу вар1ант1в. Алгоритми, заснован1 на цих методах, дюзволяють ефективно розв'язувати задач1, як1 виникають в процес!. проектування та Оуд1вництва поздсвкнього проф1лю зал!з-нгаь, у найб1льш!й м1р1 1м1тують процес пошуку розв'язку, який прийнятий на прек^щ! в зал1зничшжу буд1вництв!, використовують традац1йн1 вида та склад вх1дно! 1нформац11, надаэть можлив1сть ефективного д1алога "спец1ал1ст - ЕОМ" при розв'язуванн1 задач, оц1нц1 та анал!з1 вар!ант1в.

В розд1л1 наводяться обчислювальна схема алгоритму УГСРП в напрямку р1зшш1 двох посл1довних град1ент1в, а також загальна схема методу ПАВ стосовно до задач проектування залХзниць.

у другому роэОил описуються д^як! ттим!зац1йн1 задач!, до виникають ь процес-1 проектування та 0уд1вшщтва посдовжыього про-ф1лю зал1зниць 1 мають ва&ливе практична застосування, математичн1 модел1 цих задач та алгоритми 1х розв'язування.

Зокрема, описуеться' задача вябору оптимального вар1анта про-ектно1 л1яП з урахуванням плену розпод1.1у земляних мае та проведения земляних роб1т. Така сп1льна задача виниказ у випадку, коли при споруджбнн1 поздсвкнього проф1лг велика значения мае урахуван-ня поздовкнього перем!щення земляних мае 1з ви!мок у насипи. Затрата на спорудаення земляного полотна залэжать 1 в1д висотних поз-начок проекшо1 л1н11, 1 в1д способу проведения земляних роб1т. Оптимальней вар!ант проектно1 л1н11 визначаеться в результат! роз-в'язання задач1

(га1л /(у,г) / у € У. <р((у,г) < 0. I = 1,т),

де у - вектор висотних позначок проектнс1 л1н11 1з множили допустима розв'язк1в У; г - параметра плану проведения земляних роб1т; Ф{(у.2) - технолог1чн1 обмьження.

Для розв'язувакпя такс! сп!льно! задач1 пропонуеться 1тера-ц1йшй декомпозиц!йний алгоритм, в якому, починаючи з деякого по-

чатковсго наближення у0 е У, на кожному кроц1 спочатку розв'>;зу-вться задача визначекня плану та способу проведения земляных роб1т '(а також - штомих вартостей розробки вч!мок та споруджоння на-сип1в), а пот1м - задача оптимального коректування проектно! л1н11 (основнкх параметр1в) для того, щоб отримати наступне, краще наб-лиження у{ € У, ( = 1,2,...

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

Потр1бно знайти _ _ _

хиь > 1 9 1 = к = 1,г> (1)

як1 0 задовольняли умовак

Е Е х... < а,. I = 17р. (2)

./>=1 *** 1

А А *чъхиъ > V ' я ^ (3)

та м1н1м1зували функц1онал проведения ашляних роб 1т

р ч г

Е Е Е о,,^,. (5)

да к1льк1сть грунту, цо перевозиться з ¿-го постачальника

(ви!мки, кар'еру ) /-му спокизачу (насетт. кавальер тощо) й-м способом; - варт1сть перевезення одишдЦ грунту з £-го поста-чальника ¿-му споживачу к-и способом; а{ - проф1льний обсяг ьиХмки Ь^ - проф1льний обсяг насту J: - коеф1ц1енти ущ!льнедня грунту; - час на доставку оашиц! грунту з 1-го постачальна-

ка му споживачу й-м способом за пер1од часу I; Тг~ обмекэння на час перевезення грунту в Z-.lt пер1од.

Розв'язування задач1 (1) - (5) засновало на застосуваннЗ. методу УГСРП у напрямку р1зниц1 двох посл!довяих град1ент!в до зада-ч1, дво!стоГ до (1) - (5) у в1дпов1дност1 з1 схемою декоштозицН. Нехай - дво!ст1 зм1нн1, як1 в1дпов1дають обмежен-

ням (3), (4). Позначимо X, V, П_в!дпов1дно вектори зм1нних

хиъ' 1 ~ ^ ~ й ~ *'г> 1 = 1»э" 1 складемо функ-

Шю Лагранха.такого виду:

KX.V.F) - Z £ Z +

+ Z Vj(bj - Z Z blJhxtJk) ~

-ZwAT - Z a1,,,* ). i 1 1 и.люеij

Задача назначения део!стих зм1нних магиме вигляд:

mas mln X(J7,7.ff).

У.ЮО XSD

дeD - область, визначена обмежекнями (3), (4).

Одночасно з дво1стою задачею розз'чзуеться так звана згладжв-на, яка рипливев з прямо! ыляхом введения в ц1льову функц1ю (5) додаткових е-квадратичних доданк1в "оГ^л, • Так1 доданки слабо

вп.чивають на розв'язок задач1 визначення плану проведения земляних роб1т, але габезпечують його однозначнЮть.

По дво!стих гм1нних визягчаються одини<т?1 вартост1 розробки ви1мок та споруджэння насш1в, як1 використсвуються при визначекн1 нового положения проектно! л1н!1.

В багатьох зипадках грунт ]з ви!мок непридатний для споруд-ження насип1в. Тод1 для насип1в викоркстовучться 1кш1 джерела грунт1в - кар*ери, як! розташовуються вздовж траси зал1зниц1 на деяк1й в1ддал1 в1д не!. Для таких випацк1в велике значения мае задача розпод1лення земляних мае кэр*ер1в (РЗМК).

В робот1 наведен1 постаьорка задач1 РЗМК, алгоритм II роз-в'язування. Звертаеться увага на те, що задача РЗМ2:, в загальному випадку, нел1н1йна. Вэрт1сть перевезення грунту залежить не т1ль-ки е!д транспортних витрат, а й в1д к1лькост1 постачальни1в грунту, 1х тип1вг часу буд1в:нцтва проф1лю дороги тощо. Кр1м того, постачальнчки грунт1в, як правило, розташпван1 ездозж траси дороги й строго упорядковак1 за в1дстаяню в1дносно початку буд1вництва зал1зниц1.

Враховулчи особлизост1 задэч1 РЗМК, для II розв'язування роз-роблений ефектквний алгоритм на осяов1 методу ПАВ.

Дал1 в роздШ описуеться загальна постановка вашгаво! 1 та-ко1.шо мае самост1йне практична застосування задач1 коректування основних парэмвтр1в проектно! л1н11 - эбсцио А"0 ^ (г®,

та ординат У0 = • (у°, у®.....ур И то чох перелому. В загальному

вигляд! задачу оптимального корэктувьтшя основних пара;летр!в про-

ектно1 л1н11 мокна сформулювати таким чином. •

У деяк1й област1 вар1ювання основних параметр1в *

С = G0 X G2 Х-- -X GH , (6)

да G{ = (lxt - x^l < Д> U {|y( - y°l < 0). i «= Ö~N. TOTplöHO знай-

ти так1 _

Г = (xp. У* = (yp. i = ОД. (7)

як1 ö м1н1м1зували функц1онал буд1вельних витрат

Р(Х\Г) = min P(X,Y) (8)

а,Г)©3

та задовольняли множин1 обмекень

Q = lQj{X,Y,B) <0). J = 1Л. (9)

де В = (b,,b2.....bp) - нормативн1 коеф1ц1енти 1з норм та правил

буд1вництва зал1зниць (НПБ); А - область вар1ювання параметра X; О - те х саме для параметра У; К - к1льк!сть точок перелому про-ектно1 л1н11, що визначаеться в результат1 розв'язання задач1.

У 01лшост1 випадк1в вкмагаеться . цоб початок та к!нець проектно! л1н11 на д1лянц1 коректування були заф1ксованими, тобто

*S - х0- «о - г'к - 4- У'к =

Для розв'язування alel задач1 описувться р1зн1 алгоритма, як1 розроблен! на ochobI загально! схеми методу ПАВ 1 в1др1зняються один в1д одного ■"тособом побудови пор1внянних та в1дбору персдак-тивних вар1ант1в.

Кехай X = - деяка упорядкована ляожина (абсцлс харак-

терных точок поверхн1 земл1 вздовж траси, абсцие точок перелому початкового вар1анта 1 т.1н.). Кожне значения х1 зв'язаке з попо-редн1м сп1вв1дношенням х( ~'xt_t + Ах{. де ¿г{ - деяка додатня величина.

Кояному елементу х{ е X ставиться у в1дпов!дн1сть мнояина елемент1в (в1дм1ток) У( = iy(). J = 1.2,....п, 1з облает! Baglio-вання IУ - У°| < ö таким чином, що = у\ + Ду, i = О.п,

J = 1,я.

.Многсшз V = U

{°=0,П

тШшм кроком по вертикал! Ду та кроком по горкзонтал! Д.г£ для генерацИ мнокини вэр1ант'в.

С!тка, що аизначаеться мнозжною V, називаеться короткою,

у{). J = 1.« ]■ визначас с1тку з пос-

якщо розв'язок задач1 (6) - (9) У* Суде визначатисяна деяк1й anplopl в1дом1й множив! X* = dp с ï. У випадку, коли У* визна-чаетюя на деяк1й anplopl нев1дом1й мнокин! X* с X (вона Суде ви-значена лише в резулыаИ розв'язання задач!), множила 7 Суде за-давати некорстку с1тку.

Позначимо через J множину 1ндекс1в (1.2. ...,т}. Посл1довн1сть

t„ 1Ь -

в1дм1ток Yh* ж (у ', у^..... Ук ). ir е J, г <= O.k. визначае ча-

стковий й-кроковий вар1ант у точц1 укк. е J. ОЩнкою (критер1-

&

ем) Л-крокового варианта s формула FIY.) = Е f{y. ,, у.), де

j. варт1сть буд!вельшх витрат на в1др1зку (yt_1. i/t>-

Для в1дбору перспективних й-крокових вар1ант1в використову-ються дискретн1 аналоги функц1ональних р1внянь - рекурентн1 сп1в-в1дкошення.

В алгоритм1 7 перспективний fc-кроковий вар1внт в1дбираеться серед множини вс1х допустимых вар1ант1в, що зак1нчуються в точц1

yh, !j € J. В алгоритм1 2 - серед множини вс1х допустимих, що ма-

ють -сп1льний в1др1зок j1, укк). t^j. е »7.

У розд1л1 наводиться анал!з та пор1вняльн! оц!нки цих алгоритм^. Алгоритм 1 б!лыц простий, • ьимагае для запам'ятовування перспективних вар1ант1в зна1шо менше пам'ят1, н1к алгоритм 2. Це мае суттеве значения при розв'язузанн1 задач велико! розм1рност1 (ца об'ектах велико! протяхност!). Але алгоритм 2 не призводать до втрати часткових перспективних вар1ант1в (що ц1лком можливо в алгоритм! 1), тому що в1дб1р перспективних вар!ант1в зд1йснюеться з урахуванням 1х продовкекь.

У результат1 анал1зу та у зв'язку з необх1дн1стю розв'язувати задач1 зелико! розм!рност1 був розроблэний алгоритм 3, який за ефективнЮтю в!дбору перспективних вар1ант1з практично не поступа-вться алгоритму 2, а для запам'ятовування !х потребуе пам'ят1 ст1-льки. ск1льки 1 алгоритм 1.

Характерною особлив1стю цього алгоритму в те. що для кожно1 точки (в1дм!тки) множила перспективних вар1ант1в конструюеться з урахуванням розвитку (умовного продовження з точки ¡/¿) початко-вого вар1анта 1 будв м1стити не б1льшв Hlat один вар1ант. В 1ншому (способ! побудови покрокових допустимих та множини пор1внянних ва-

- И -

р1ант1в) в1н не в1др1знявтъся в1д алгоритму 1. '

На кожному кроц1 й, й = 1,2.....Н, конструюеться мнозг^а до-

<ь

пустимих вар1ант1в Z>(y ), яка у випадку коротко! с1тки оудв

Ч 1 {ь

складатися 1з елемент1в yk ). f£k е J\ у випадку

нежорстко1 с1тки - 1з елемент1в (уJ, ук*) VJ € [й^ й21,

0 < йх < й^ < й-1, lj,lh € .т. Для кожно1 точки ул*. tA € J, буду-вться множина пор1вняяних вар1ант1в S{yh*).

У випадку »орстко1 ClTKK ДЛЯ- кожно! точки у.*, i. € J, 13

множини Sty^*) в1дбиразться один перспективная вар1ант УА*. t <= J", використовуючи рекурентне сп!вв1дношення

такий, що задовольняз умов1

'"¿-1 " < ьз + е- (Ш

у1к* - fjLt 0 - —

де uj_j в- . -- . J => 1 ,m, € J.

Ъ3 - 8лгебра1чна р1зниця-уклон1в сум1жаих елемент1в проектно! л1-

Hll, е - достатньо мала додатня величина. 't

У випадку незюрстко1 с1тки для кокно! точки у I. € J, с. ih

1з множини S(yk ) в1дбирееться .один перспективная вар1ант УА .

1 € J, використовуючи рекурентне сп1вв1дношення

= ^mln {?(У{ ) + /(у{ , у/)}.

такий, що задовольняз умов1

¡Uj - u°l < ъз + е.

. у1** - w

де ц --- , < I < й^ О < Aj < ^ < й-1,

u°, &3, е - так!, як 1 в формул1 (11).

На останньсму кроц1 наЗкращий вар'ант Y* в1дбираеться 1з мнокини вс1х допустимих Еар1ант1в О(У^). j = 1.2.....и. за м!н!му-

мом вартост1 буд1вельних витрат.

Наводиться доведения, цо алгоритм 3 в будь-як1й облает1 коректування дае розв'язок задач! (7) - (9) за учови (Х°.У°) е Q.

Описуються такок частков1 задач1 коректування основных пара-метр1в проектно! л1н11 та алгоритми 1х розв'язування. Такими в: коректування проектно! л1н1! за .одним параметром (або К, або Л. за двома параметрах (X та У), коректування з зм1ною к1лькост1 пря-мих д1лянок проектно! л1н11, з збереженням I! конф1гурац1!.

В роздШ описуеться.також алгоритм розв'язування задач1 вводу початкового вар!анта проектно! л1н11 в допустиму область. Суть задач1 полягае в такому.

Нехай уР = У°)- вар1ант розв'язку, заданий cneula-

лютом (проектувальником). Лрицустимо, що в1н не задовольняв вимо-гам 1ШБ, тобто if е Q, Q - тошна обмежень (9).

Потр1бно знайти такий вар1ант проектно!■ л1н11

х* = х° ± Дг£, у J = у° ± Vy . t = Q,N, який задовольняв би обме-женням (9) та в найб1льш1й Mlpl збер1гав задум спец1ал1ста,' тобто щоб сума в1дхилень

N N

Е \Dx.\ + £ IDy.l t-i t-i

в1д вар1анта ff0 була найменшою.

Описуеться також схема розв'язування задач1 оптимального проектування поздовкнього проф1лю (одержания оптимального розв'язку у випадку, кож не заданий початковий вар1ант).

У третъолу роз01л1 описуються особлизост1 процесу проектування та буд1вництва зал1зниць. Суть !х полягае в тому.що на практи-ul, як правило, спец1ал1ст транспортного буд1вництва на ochobI досв1ду та 1нту1ц1! назначав допустим1 вар1анти розв'язк!в, як! пот1м оц1нюються за загальноприйнятою методикою 1 як1 можуть при необх1дност1 потребувати коректування. Пошук допустимих розв'язк1в зд1йсныеться на ochobI анал1гу та резбивки траси на пор1вняно од-нор1дн1 д1лянки, як1 можуть знаходитись в ун1кальних умовах 1з сво!ми специф1чними особливостями, наявн1стю р1зних 1 не завжди формал1зованих факторов. В1д спец1ал1ста в такому випадку вимага-еться ум1ти розв'язувати 0агатокритер1альн1 задач! в ситуац1ях, яким притаманн! (з р1зних причин) недостатн! знания про об'вкт.

Мета може бути досягнута за рахунок розробхи ефёктивних алгорктм1в. та програмних засоб!в, як1 повинн1 задовольняти певн;гм ьимог~м для реал1зац11 можливостГ активно! участ1 спец1ал1ста в посуку розв'я-зку.

Про так1 еимоги, а тако» про вимоги, що висовуються до роботи з даними при систешПй оптям1зац11. про режим д1алога та його особливост1 йдэ мова в розд1л1.

Дал! в розд1л1 опиоуються розроблений у в!дпоз1дност1 з пос-тановою Держком1тету з науки та техн!ки в1д 30.10.1935 р. Л 555 й розпорядженням ПрезидП HAH Укра1ни в1д 25.12.1985 р. * 2794 11ПП Д1СПАВ, його особливост1 та функц1ональн1 можливост1, арх1текту-ра, 1нформац1йно-дов1дксза пШсистема, подсистема розв'язання задач 1 роботи з даними, вх1дна мова пакета.

Системна частина пакета е подэльшим розвитком математичного забезпечення пакет1в ПТЛ, Д1СПРО 1 дозволяв в д1алоговому рехкм! спец1ал!сту (коркстувачу-непрограм!сту) самост1?чо вибирати схему рсзв'язування задач1, брати активну участь у npouecl прийняття pl-шення, коригувати вх1дн1 та вих1дн1 дан!.

Арх1тектура пакета обновлена зимогами, як1 були Еисунут! до пакета при його проектуванн1. Пакет язляз собою кс?.'ллекс приклад-них та системних програч. В1я складаеться з двох незалекних одна в1д одно! п1дсистем.

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

Шдсистема розв'язування задач та роботи з дакми забезпечуе та п1дтримуе обчислввальний пронес, м1стить усяку 1нформац1а, яка Ееобх1дна для його орган!зац11.

Вх1дна мова пакета складаеться з набору оператор1в 1 служить' для сп!лкування користувача з пакетом.

У розд1л1 наводяться результата експвриментальких досл1джень на реальних об'ектах, як! вкконувались за матер1алами техн!чного проекту та робочих креслень 1 були впровадженз1 при проектузанн1 та буд1вництв1 окремих д1лянок Еайкало-Амурсько! маг!страл!, що знаходились у складних 1н:..-;-нерно-геолог1чких та природно-кл!матич-них умовах.

В зак(нченн,1 п!Д5'«'-аыться п1дсумки за результатами взконаяо1 роботи. Акал!з досл1джень показав високу ефективн!сть розроблених

програмяих засоб1в. Пакет Д1СПАВ ке мае аналог1в.. В1н розрахований на застосування його -в npoueci проектування та буд!вництва яових залХсниць, реконструкцИ старих, при, експертиз1 проект1в, в учбо-вкх Щлях 1 рекомендований. спец1ал!стами зал1зничного буд1вництва для широкого використання.

Однак на сьогодн1кш1й день■програмне забезпечення пакета зи-магав адаптацИ та рсзробки нових програмних засоб1в, в т.ч. 1 та-!-.:х, !до забезпечили б певною м1рою граф1чну наочн1сть проектних ро?а'язк1в. Це могло б принести пакету чи його аналогов1 б1льш ши-роке 'застосування. для розв'язування одтим1зац1йних задач проекту-, вання та буд1вництва зал1зниць. '

В Довожу наводягься фрагмент роботи пакета Д1СПАВ в дХало-говому режниХ та деяк1 документа. про впровадження результат1в ви-конано! робота.'

Робота виконзна п1д кер1вництвом член-кореспондента HAH Укра-1ш, професора Н.З.Шора. ■

Основн! результата роботи.'

1. Проведен1 дослХдиення в галуз] зал1зничяого будХвнвдтва по розв'язуванкю оптим1зац1йних задач проектування та буд1вництва за-л1зниць.

2. Виявлэний ряд важливих оптим1зац1йних задач, що виникають у процес! реконструкцП, проектування та буд1вництва зал1зшщь, розроблен1 математичн1 модел1 цих задач.

3. Виконан! досл1дження по розробц1 алгоритм1в, запропонован1 та розроблен! нов1 алгоритш 1 програмк1 засобк розв*язування оп-тим1зйц1йп!х задач проектування та буд1вництва зал1зшщь.

4. Проведено ек'ч.ориментальне досл1де.ення розроблених програм на багатьох реальна об'ектах у складних природних умовах буд1в-ництва.

5. Розроблений пакет прикладних програм для розв*язування ос-новних задач проектування та буд1вництва зал1зниць, який рекомендований спеЩалЮтами до застосування його в орган1зац1ях. причет-них до проектування та буд1вництва зал1зниць, в учбових ц1лях.

о. Щодо програмно! реалХзацИ, то автором програмно реал1зо-ван! алгоритш розв*язування задач коректування основних парамет-

plB проектно! л1н11, вводу початкозого вар1анта в допустиму область, проектування поздовжнього проф1лю зал1зниц1. чзсткоео - де-кошозиц1йни& алгоритм, а також написаний ряд програм, що дозволяв спец1ал1сту активно брати участь в обчиелювальному. процес! при системней оптим1ззц11.

Осноен! результата дасертапи опубл1кован1 в таких роботах:

1. Беляева Л.В., Билецкий В.И., Шор Н.Э. О декомпозиционном алгоритме выбора оптимального профиля железной дороги // Кибернетика - 1983 - >6 3 - С. 76-79.

2. Зайцев Р.В., С'/.Скрко А.Е., БилецкиС В.И. Некоторые аспекта ре-лизации интерактивного режима в САПР // Тез. докл. IV ск.-семинара "Интерактивные системы",- Тбилиси - 1982 - ч.1 - С. 250.

3. К вопросу автоматизированного проектирования профиля / Р.В. Зайцев, В.И.БилецкиЯ, А.Н.Сибирко и др.// Транспортное строительство - 1984 - Л 10 - С. 9-11.

4. О комплексе задач оптимизации проектных решений по профили сложных участков дорог {на примере БАМ) / В.С.Михалевич, В.И. Билецкий, Р.В.Зайцев и др. - Киоз. 1980.- 46 с. - (Препр./ ИК АН УССР. Ин-т кибернетики; 80-29).

5. Пакет прикладных программ для реления задач проектирования и строительств- келезных дорог / В.И.БилецкиЯ, Р.3.Зайцев, Г.И. Горбач и др. - К., 1992. - 21 с. - (Препр. / Академия наук Ук-рааш, Ин-т кибернетики им.В.М.Бажова; 92-33).

6. Проектирование оптимального продольного профиля новых железных дорог на ЭЦВМ / В.С.Мкхалевич, Н.З'.Шор, А.Н.Сибирко, В.И.БилецкиЯ и др. - Киев: РФАП ИК АН УССР. 1970. - 244 с.

7. СиСирко A.B., Зайцев Р.В., Билецкий В.И. О применения метода последовательного анализа вариантов при автоматизированном решения задач железнодорожного строительства // Програмно-техни-ческие средства АСУ.- Киев: ИК AI УССР. 1983 - С. 76-84.

Билецкий В.И. Исследование и разработка эффективных алгоритмов и программных средств принятия решений в некоторых задачах оптимального проектирования и строительства железных дорог.

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

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

• Blletsky V.I.Analysis and development of efficient algorithms and software tools for decision making in some problems of optimal design and construction of railroads.

Candidate of Techn. Scl thesis, speciality 05.13.02 -mathematical modelling in scientific research. V.M.Glushcov Institute of Cybernetic NAS Ukraine, Kiev,1996.

The work is devoted to the application of known methods of consequetlve analysis of variants and generalized gradient descent with space dilation to solving of Important practical problems arising in design and construction of railroads. Based on these methods efficient numeric algorithms have been developed which are easy to apply and implement in the user interaction mode. A package of application programs has been developed which allows specialists to solve problems in dialog mode thereby getting the best human-mashlne solutions. Practical testing of the software tools has been conducted applied to many real-life objects which has confirmed efficiency of the developed algorithms.

Кл»чов1 слова: алгоритм, проектна л1н1я, вар1ант, програмн1 засоби, д!алоговий режим, црийияття р1шень, зал!зниця.