Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем
Запропонована методика оптимізації розвитку складної транспортної системи на прикладі залізничного транспорту за допомогою методу послідовного аналізу варіантів....
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України
2008
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/11467 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем / О.А. Шумейко // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 192-198. — Бібліогр.: 4 назв. — укp. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-11467 |
|---|---|
| record_format |
dspace |
| spelling |
Шумейко, О.А. 2010-08-19T15:41:23Z 2010-08-19T15:41:23Z 2008 Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем / О.А. Шумейко // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 192-198. — Бібліогр.: 4 назв. — укp. XXXX-0009 https://nasplib.isofts.kiev.ua/handle/123456789/11467 330.4:519.8:658.12 Запропонована методика оптимізації розвитку складної транспортної системи на прикладі залізничного транспорту за допомогою методу послідовного аналізу варіантів. uk Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| spellingShingle |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем Шумейко, О.А. |
| title_short |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| title_full |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| title_fullStr |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| title_full_unstemmed |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| title_sort |
послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем |
| author |
Шумейко, О.А. |
| author_facet |
Шумейко, О.А. |
| publishDate |
2008 |
| language |
Ukrainian |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України |
| format |
Article |
| description |
Запропонована методика оптимізації розвитку складної транспортної системи на прикладі залізничного транспорту за допомогою методу послідовного аналізу варіантів.
|
| issn |
XXXX-0009 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/11467 |
| citation_txt |
Послідовний аналіз варіантів, як метод оптимізації розвитку транспортних систем / О.А. Шумейко // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 192-198. — Бібліогр.: 4 назв. — укp. |
| work_keys_str_mv |
AT šumeikooa poslídovniianalízvaríantívâkmetodoptimízacíírozvitkutransportnihsistem |
| first_indexed |
2025-11-26T08:10:56Z |
| last_indexed |
2025-11-26T08:10:56Z |
| _version_ |
1850615253175369728 |
| fulltext |
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
192
192
УДК 330.4:519.8:658.12 О.А. Шумейко
ПОСЛІДОВНИЙ АНАЛІЗ ВАРІАНТІВ, ЯК МЕТОД
ОПТИМІЗАЦІЇ РОЗВИТКУ ТРАНСПОРТНИХ СИСТЕМ
Запропонована методика оптимізації розвитку
складної транспортної системи на прикладі залізничного
транспорту за допомогою методу послідовного аналізу
варіантів.
Вступ. У статті розглядається можливість використання
методу послідовного аналізу варіантів (ПАВ) для чисельного рішення
задач оптимізації розвитку складної транспортної системи.
Аналіз досліджень. При розробці алгоритмів чисельного
рішення ряду екстремальних техніко-економічних задач було звернено
увагу на доцільність використання ідей теорії послідовних
статистичних рішень для вивчення достатньо широких класів
багатоваріантних задач оптимізації та побудови алгоритмів їх
розв’язання. Математичний метод, заснований на цьому підході, був
вперше сформульований В.С. Михалевічем та Н.Є.Шором [ 1-3].
В основі методу ПАВ покладена ідея представлення процесу
рішення у вигляді багатоступінчатої структури, аналогічної структурі
складного випробування. Кожна ступінь пов’язана з перевіркою
наявності тих чи інших властивостей у множини варіантів або у
окремих варіантів та приводить к безпосередньому скороченню
початкової кількості варіантів, або готує можливість такого
скорочення у майбутньому.
В багатьох задачах для організації випробувань з метою
зменшення множини можливих варіантів до використовуються
загальні властивості оптимальних варіантів, які є узагальненням
«принципу оптимальності» Р.Беллмана у динамічному програмуванні
[4]. При рішенні варіаційних задач використання методу ПАВ
базується на «принципі оптимальності» Р. Беллмана.
Проблема. Процеси оптимізації по методу ПАВ складаються з
послідовності операцій, в яких результат попередньої операції
можливо використати для управляння ходом майбутніх операцій. У
всіх процесах, що розглядаються, здійснюється послідовність вибору.
Таку послідовність назвемо стратегією або поведінкою системи. Для
задач оптимізації розвитку технічного оснащення залізничних
транспортних систем здійснюємо пошук найбільш бажаних, за
заданим критерієм, оптимальних стратегій. Досліджуються процеси
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
193
193
пошуку оптимальних стратегій у випадку, коли критерієм
оптимальності є показник ефективності капіталовкладень.
Такі задачі слід розглядати у рамках загальної схеми
послідовного пошуку рішень для випадку, коли результат будь-якого
припустимого випробування є детермінованим. Властивість
монотонної рекурсивної функції-критерію дозволяє використовувати
для рішення таких задач деяку особисту схему методу послідовного
пошуку рішення.
Метод ПАВ є досить універсальним і може бути використаний
для рішення широкого колу багатоваріантних задач. Однак,
використання будь-якого математичного методу, включаючи й метод
ПАВ для рішення реальних задач завжди обмежене. Тому
використання методу ПАВ для розв’язання задач оптимізації розвитку
технічного та технологічного оснащення транспортних систем
повинне бути додатково обґрунтоване.
Обґрунтуємо використання методу ПАВ для рішення задач
розвитку транспортних систем. Поставлена задач розвитку складної
транспортної ситсеми може інтерпретуватися як Т-кроковий процес
прийняття рішень, в якому рішення на кроці К ( TK ,1= ), полягає у
виборі одного чи декількох значень керуючих змінних. Далі, задача
визначена для будь-якого числа кроків та має структуру, що не
залежить від числа кроків. При розгляді задачі, що складається з К-
кроків, може бути завдана деяка множина параметрів, що описує стан
системи, тобто параметрів, від яких залежать значення керуючих
змінних.
Множина параметрів може бути вибрано таким чином, що таж
сама множина параметрів буде описувати стан системи незалежно від
кількості кроків. Вибір керування на К-м кроці в К-кроковому процесі,
таким чином, не буде залежить від попередніх кроків. Якщо наведені
умови виконуються, значить задача може бути вирішена по схемі
ПАВ.
Метод ПАВ є тим методом, що долає множину об’єктивних
труднощів, пов’язаних з застосуванням методів класичного
математичного аналізу розвитку техніко-технологічного оснащення
транспортних систем залізничного транспорту. Опишемо, переваги
методу ПАВ.
При дослідженні розвитку систем суттєвою є структура
поведінки. Це ствердження означає, що бажано знати характеристики
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
194
194
системи, що визначають рішення, яке слід приймати на кожному
конкретному кроці процесу рішення.
У більшості випадків при досліджені фізичної системи ми не
задовольняємось визначенням оптимальної поведінки системи для
якоїсь однієї множини значень параметрів, а дозволяємо параметрам
змінюватись у деякій критичній зоні значень, а потім досліджуємо,
наскільки оптимальна поведінка зачіпається цими змінами. Тобто
здійснюємо аналіз чутливості критерію. Такий аналіз структурної лінії
поведінки дає найбільш суттєву інформацію.
Зрозуміло, що можна протабувати всі значення функції і
навіть досить велику кінцеву множину значень. Відповідно
залишається можливість використання будь-якої інтерполяційної
схеми, яка дозволить встановити значення, виходячи з не багатьох
обраних значень.
Щоб у задати у інтервалі ],0[ T всю множину значень
)(
~
tfN скористаємось значеннями, що приймаються у конечному
числі точок Tt ,...,2,,0 ∆∆= . Потім заявимо, що кожний елемент
послідовності { })(
~
tfN обчислюється та табулюється в кожній з цих
точок і тільки в цих точках. Таким чином, отримаємо деяку решітку,
вершини якої визначаються перетином відповідних прямих для
кожного стану системи і кожного кроку t.
Функція-критерій, що розглядається має ту особливу
структуру, яка може бути використана для полегшення пошуку.
Властивість монотонно-рекурсивних функціоналів критерію дозволяє
розробити зручні прийоми для чисельного рішення задач оптимізації
розвитку систем. Властивість монотонної рекурсії функції-критерію
дозволяє порівнювати відрізки траєкторії, що сходяться в одну й ту
саму вершину решітки. Рішення t -крокової задачі отримаємо з
рішення )1( −t -крокової задачі шляхом додавання t -го кроку й
використання результату отриманого для )1( −t -го кроку.
Використання такого методу не тільки дозволяє розв’язати задачу для
T,1 кроків, але й для кожного Tt < дає оптимальне рішення.
Описаний математичний метод дає можливість отримати таку
інформацію о динаміці розвитку системи, яку не дає ніякий інший
метод.
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
195
195
Особо слід відмітити точність методу. Метод дає абсолютне
значення екстремуму, а не відносне. Це дозволяє, наприклад,
використати чисельні результати реалізації методу, у якості еталону
для наближених результатів, що можуть бути отримані іншими, менш
точними, методами.
Можливі випадки, коли рішення має декілька оптимальних
траєкторій, що виключають одна одну. В деяких випадках дослідження
достатньо знати лише одну з оптимальних траєкторій, в інших потрібні
всі оптимальні траєкторії, причому останній результат розцінюється
більш високо, ніж безпосередньо визначення екстремуму функції
критерію.
Крім того можлива необхідність отримати не тільки значення
екстремуму функції-критерію, але й наближених її значень. Вони
можуть бути досить важливими у випадку, якщо потрібні прості
наближення в складних ситуаціях. Ці наближені траєкторії можливо
отримати, якщо при розрахунках фіксувати такі траєкторії. Така
процедура може бути легко реалізована у програмі обчислення на
комп’ютері.
Декілька слів скажемо об обсягах обчислень. Якщо до деякої
вершини решітки веде 10 різних відрізків траєкторій, тоді процес
оптимізації з N змінними призведе до 10N різних множин виборів, при
умові простого перебору варіантів. Але в цьому процесі загальна
кількість можливостей в дійсності значно менша, так як вибір деякої
вершини решітки обмежує можливі зміни у подальшій траєкторій,
відрізки яких сходяться у обраній вершині решітки. Але при всьому
цьому об’єми обчислень можуть бути дуже масштабні.
Використання методу ПАВ є більш ефективним, ніж просте
дослідження всіх випадків. Це пояснюється принципом оптимальності.
Згідно цього принципу, після вибору деякого початкового стану
0b ,
ми відмовляємось надалі від обстеження всіх траєкторій, що
включають цей стан, а розглядаємо лише ті траєкторії, які оптимальні
для )1( −t -крокового процесу. Цей принцип є дійсним для кожного
кроку. Таким чином, процес рішення, оснований на цьому принципі,
дозволяє зберегти адитивність, а не мультиплікативність числа
операцій (тобто обсяг розрахунків для 20=N приблизно стає в
двічі більшим ніж для 10=N ). Ефективність такого підходу
порівняно з повним перебором стає все більш суттєвою у порівнянні з
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
196
196
збільшенням числа кроків. Причина цього полягає у виключені на
кожному кроці неспритних комбінацій з подальшого розрахунку.
Якщо прийняти що N – кількість точок по вертикалі решітки, а
Т – відповідно по її горизонталі, то загальне число обчислень функції
критерію складе не більше ніж TN2
. Форма задачі інваріантна
відносно Т.
Додаткові умови, які визначаються таблицями можливих
переходів для задачі, скоріш спрощують її розв’язання, сприяючи
процесу відсіювання небажаних варіантів.
Особливу складність при практичному застосуванні методу
ПАВ для рішення задач оптимізації розвитку залізничних
транспортних систем полягає у створенні таблиці можливих переходів.
Існують такі задачі оптимізації розвитку техніко-
технологічного стану транспортних систем у яких кінцевий стан в
процесі оптимізації не фіксується. Такий підхід дозволяє відшукати
одночасно всі оптимальні рішення, у результаті яких система
переходить з початкового стану
00 ~
Bb ∈ в кожне з кінцевих станів,
що забезпечують відповідність техніко-економічним вимогам на
кінець періоду, що досліджується. При цьому, починаючи з обраного ,
можливо отримати деревовидну структуру, на який значення величин
tb на наступних гілках будуть відповідати частково-оптимальним
рішенням. Вся процедура повинна бути повторена для всіх множин
значень
0~
B , які дають задачу, що розпадається.
Метод ПАВ, що використовується для рішення задачі
оптимізації техніко-технологічного розвитку транспортних систем,
може бути використаний для рішення широкого кола багатоваріантних
задач з метою аналізу впливу багатьох факторів на вибір оптимальної
траєкторії дослідження системи.
Це дозволяє наприклад провести аналіз чутливості критерію
ефективності капіталовкладень та дослідити вплив різних факторів на
цей показник.
У зв’язку з масштабністю та складністю відповідних
обчислень метод ПАВ доцільно реалізувати виключно за допомогою
обчислювальній техніки (комп’ютерів).
Метод дозволяє досліджувати теоретично необмежену
кількість станів систем. Таким чином, задача об’єктивного та науково-
обґрунтованого вибору економічно-раціональної траєкторії розвитку
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
197
197
залізничних транспортних систем повинна отримати принципово нове
рішення.
Універсальність методу ПАВ полягає у тому, що незважаючи
на специфічні особливості всіх можливих систем, для оптимізації
розвитку яких він використовується, він може враховувати
особливості кожної з них. Специфічні особливості кожної з систем
враховуються завдяки індивідуальній таблиці можливих переходів.
Розглянемо побудову алгоритму оптимізації розвитку
транспортної системи.
Для отримання чисельного розв’язку задачі оптимізації
розвитку транспортної системи необхідно мати математичну модель.
Така модель, основана на методі ПАВ є достатньо наочним і точним
відображенням реального розвитку системи в плані її техніко-
технологічного оснащення.
Чисельна схема методу ПАВ є таким достатньо
стандартизованим апаратом, який використовується для вирішення
багатьох класів задач. В дисертаційній роботі пропонується
застосувати цю схему ще для одного важливого класу задач – задач
оптимізації розвитку транспортних систем на залізничному транспорті.
Передумови до побудови моделі. Припустимо:
система, що досліджується, може знаходитися у N різних станів,
що визначаються відповідними параметрами. Ці стани
занумеруємо в деякому порядку, порядок нумерації не має
значення, але він повинен зберігатися на протязі всього процесу
оптимізації, приймаємо порядок нумерації 1,2,…,N;
заданий набор правил або таблиця можливих переходів, згідно
якої система може переходити з одного стану в іншій. Зміна станів
системи викликані капіталовкладеннями, значення яких
обчислюється як сума всіх капіталовкладень у відповідні
елементи технічного оснащення та технологічні заходи.
заданий критерій оптимальності розвитку, яким виступає показник
ефективності капіталовкладень (тобто коефіцієнт відношення
ефекту від переходу в новий стан до капіталовкладень, що
викликали цей стан, для спрощення розрахунків величини ефектів,
повинні бути представлені у грошовому виді).
Опишемо процес оптимізації (ідея послідовного перебору
варіантів):
послідовно будуються відрізки траєкторій;
Економіко-математичне моделювання соціально-економічних
систем
Збірник наукових праць МННЦ ІТіС
Київ – 2008, випуск 13
198
198
із множини побудованих відрізків виключаються ті, що не
задовольняють техніко-технологічним вимогам періоду (року)
розрахунку;
серед допустимих обираються групи порівняних, потім в кожній
групі визначається найкращій за заданим критерієм (ефективність
капіталовкладень), що залишається для подальшого аналізу;
розглядається продовження відрізків траєкторій найкращих
представників кожної з груп, на наступній стадії знову обираються
найкращі відрізки вже більшої довжини і т.д. до отримання
повного рішення.
З кожним кроком оптимізації розмірність області допустимих
значень скорочується у результаті відсіву станів, що не відповідають
плановим техніко-технологічним вимогам. На останньому кроці маємо
оптимальну за заданим критерієм (ефективність капіталовкладень)
схему розвитку системи.
По попереднім станам, параметри яких фіксуються під час
дослідження, відтворюємо всю траєкторію розвитку системи та
значення заданого критерію для кожного етапу розвитку системи. У
результаті отримуємо траєкторію, що задовольняють техніко-
технологічним вимогам та оптимальні за заданим критерієм серед всіх
можливих траєкторій, що приводять систему з деякого початкового
стану до визначеного кінцевого стану.
Висновок. Методика оптимізації розвитку техніко-
технологічного оснащення залізничних транспортних систем, що
заснована на методі ПАВ, дає об’єктивне рішення поставленої задачі
та є придатною для машинної реалізації. Особливий алгоритм
відсіювання нежиттєздатних варіантів розвитку дозволяє значно
скоротити обсяги обчислень. Це, у свою чергу, призводить до
можливості розгляду масштабних задач розвитку з багатьма
параметрами та значним горизонтом планування.
Література.
Михалевич В.С. Последовательные алгоритмы оптимизации и их
применение. // Кибернетика. – 1965. – №1. – С.45-56.
Михалевич В.С. последовательные алгоритмы оптимизации и их
применение. // Кибернетика. – 1965. – №2. С.85-88.
Михалевич В.С., Шор Н.З. Численное решение многовариантных
задач по методу последовательного анализа вариантов. – М.:
ЛЭММ АН СССР, 1962.
Беллман Р. Динамическое программирование. М.: Физматгиз,
1960.
|