Дослідження з дискретної оптимізації

Методи локальної оптимізації
Cпеціальні задачі дискретної оптимізації
Задачі дискретної оптимізації за умов невизначеності вихідних даних
Застосування моделей і методів дискретної оптимізації для розв'язання економічних задач
Література

Розвиток і активне використання при дослідженні важливих народногосподарських проблем різних модифікацій методу послідовного аналізу варіантів сприяли виникненню й інших загальних і спеціалізованих схем розв'язування багатоваріантних задач. Для задач математичного дискретного програмування І.В.Сергієнко в 1964р. запропонував загальну схему методу вектора спаду [5], що надалі розроблялась як в Інституті кібернетики, так і в інших наукових закладах країни для наближеного розв'язування багатьох типів задач дискретної оптимізації. Вже в 60-ті роки стало зрозуміло, що точних методів розв'язання багатоваріантних задач недостатньо для різноманітної практики, оскільки переважна більшість цих задач характеризується винятково великою складністю і для знаходження їх точного розв'язку може знадобиться надто багато невиправданих затрат різних ресурсів (машинного часу, пам'яті тощо). Понад те, нерідко знайдені точні розв'язки не становлять великої цінності, оскільки взагалі початкові дані для задач можуть бути лише наближеними, а моделі, що використовуються, у більшості випадків лише приблизно відбивають реальні ситуації. Цим і пояснюється, що в останні десятиріччя для розв'язання дискретних задач розроблено різні наближені методи, в тому числі методи локальної оптимізації [5-9].
Були розроблені та впроваджені математичні моделі та методи, а також відповідні програмні засоби для розв'язування слабкоструктурованих задач вибору (тобто таких, формальна постановка яких не задається повністю апріорно, а має уточнюватись у процесі їх розв'язування), які звичайно виникають при прийнятті відповідальних рішень. Для розв'язання та дослідження подібних задач В.М.Глушковим було запропоновано системний підхід, який був еволюційним кроком в розвитку методології досліджень в області оптимізації, в тому числі дискретної. В.М.Глушков вважав, що постановка задачі оптимізації, яка полягає в знаходженні в наперед заданій незмінній допустимій області точки (чи множини точок), в якій деяка скалярна цільова функція приймає екстремальне значення, є незадовільною для великої кількості планово-управлінських та проектно-конструкторських задач якнайменше в двох відношеннях. По-перше, в таких задачах цільова функція не є скалярною, а векторною, а по-друге, допустима область може змінюватись в процесі оптимізації, і саме в її цілеспрямованій зміні і заключається основна змістовна сутність процесу оптимізації [10]. Системна оптимізація склала ту основу, на якій було здійснено подальший розвиток та розробку нових методів розв'язання складних задач дискретної оптимізації з керованими даними за умов дії факторів невизначеності, а також вирішення питань розв'язуваності і стійкості, без чого не може бути коректно поставлена і розв'язана будь-яка оптимізаційна задача [5,9,11].

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

Наверх

1. Методи локальної оптимізації

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

Перспективним напрямком у створенні методів дискретної оптимізації (в тому числі методів локального пошуку) є використання в їх обчислювальних схемах певних ймовірнісних механізмів. До цього напрямку належить відомий метод відпалу, для теоретичного обгрунтування якого використані ланцюги Маркова, що надало можливість довести при достатньо загальних припущеннях його збіжність до глобального розв'язку з ймовірністю, яка прямує до одиниці. Однак проведені чисельні експерименти показали, що для багатьох прикладних задач цим методом не можна досягти глобального екстремуму при прийнятному об'ємі обчислень. У зв'язку з цим були запропоновані наближені алгоритми розв'язування комбінаторних задач оптимізації, загальна обчислювальна схема яких може бути інтерпретована як певне розширення схеми методу вектора спаду [5,9] за рахунок включення в неї на кожній ітерації можливостей випадкового переходу не тільки до ІкращихІ (за значенням цільової функції), але й до ІгіршихІ розв'язків, що властиве методу відпалу. Це дозволяє уникати ІпоганихІ локальних оптимумів і знаходити розв'язки, близькі до глобального оптимуму. Проведені обчислювальні експерименти продемонстрували достатньо високу ефективність нових алгоритмів для задач комівояжера, квадратичних задач про призначення, ряду задач оптимального проектування, що виникають у САПР, та інших прикладних задачах. Слід особливо відзначити можливість створення на їх основі паралельних алгоритмів, призначених для багатопроцесорних ЕОМ, в яких досягається суттєве зменшення часу розв'язування із збільшенням кількості процесорів.

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

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

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

Спільною проблемою методів локального типу є вибір стратегії пошуку, тобто правильного поєднання процесів розширення та звуження області пошуку з метою знаходження глобального оптимуму. Задача полягає в тому, щоб після одержання деякого локального оптимуму перейти в область тяжіння іншого локального оптимуму, тобто вийти з області знайденого локального оптимуму і таким чином розширити район пошуку (так звана диверсифікація пошуку). З іншого боку, для знаходження покращеного розв'язку логічно дослідити точки, близькі до одержаного локального оптимуму, тобто звузити область пошуку (інтенсифікація пошуку). Вирішенню вказаної проблеми сприяв запропонований В.П.Шилом з метою більш ефективного використання інформації, що накопичується в процесі розв'язання дискретної оптимізаційної задачі, метод глобального рівноважного пошуку (ГРП). Він є розвитком методу вектора спаду та базується на ідеях методу відпалу. Аналіз проведених обчислювальних експериментів показав перевагу методу ГРП над відомими методами при розв'язанні складних задач [9]. На основі методу ГРП розроблено і досліджено точні та наближені алгоритми розв'язання задач на графах, що виникають при побудові кодів, які коригують помилки. Отримано нові оцінки зниження максимального об'єму кодів для Z-каналу. Побудовано нові змістовні та математичні моделі задач пошуку логічних структур надійних комунікаційних мереж, запропоновано шляхи розв'язання таких задач.

Введені нові поняття РЕСТАРТ розподілу та РЕСТАРТ критерію зупину алгоритму та розроблено РЕСТАРТ технологію, яка дозволяє досягти значного зменшення середнього часу розв'язання задач дискретної оптимізації.
Створено методи формалізації та розв'язування комбінаторних оптимізаційних задач [5,7], зокрема задач розмитого програмування на множині розмитих комбінаторних об'єктів, утворених з елементів деякої скінченної множини та елементів розмитих множин, визначених на цій множині. Розроблено підхід до розв'язування задач такого типу методами локальної оптимізації. Проведені дослідження показують, що запропонований підхід доцільно застосовувати до формалізації та розв'язування задач, для постановки яких використовуються експериментальні дані або такі, що визначені статистично. Це, зокрема, прикладні задачі формування колективу виконавців деякого обсягу робіт, парку машин, вибору обладнання, виготовлення сумішей із заданих складників, що відповідають наперед визначеним вимогам, розмита задача про ранець, задача класифікації біологічних об'єктів, складання програми обробітку сільськогосподарських угідь, оцінка відповідності реальних технічних характеристик декларованим і багато інших задач. Використання метрики на розмитих комбінаторних просторах дало змогу розробити алгоритми локальної оптимізації для розв'язування так званих задач домінування.

Широке використання методів локальної оптимізації стимулювало дослідження в області опуклого аналізу, пов'язані з побудовою моделей опуклості на дискретних множинах [5]. У деяких розділах дискретної оптимізації постають питання про виділення класів задач, цільові функції яких не мають локальних екстремумів, відмінних від глобальних. Відомим прикладом є оптимізація на дискретних метричних просторах, графах, частково впорядкованих множинах. Розроблена єдина схема, яка дає змогу певною мірою узагальнити моделі опуклості, запропоновані різними авторами для дослідження тих чи інших задач дискретної оптимізації. Для дискретних множин досить загальної структури були визначені поняття, аналогічні загальновідомим поняттям опуклих (квазіопуклих) множин і функцій. Запропоновано розширення цих понять, яке залишає в силі відоме твердження про збіг локального і глобального мінімумів для задач опуклої оптимізації. Досліджене питання про умови збігу різних моделей опуклості.

Ряд робіт, проведених в Інституті кібернетики, присвячено проблемі використання переваг методів лінійного програмування для наближеного розв'язування задач частково цілочислового, а також цілочислового лінійного програмування. Один з таких підходів [5] полягає у видаленні з вихідної задачі умов цілочисельності, побудові на її основі деякої допоміжної задачі лінійного програмування, а потім - в застосуванні достатньо простої процедури для отримання розв'язку вихідної задачі.

В Інституті кібернетики було розроблено пакети прикладних програм (ППП) серії ДИСПРО для розв'язання різних типів задач дискретної оптимізації. В цих пакетах реалізовано широкий спектр оптимізаційних методів, що можуть використовуватись для дослідження багатьох питань розміщення і реконструкції виробництва, проектування технічних пристроїв та машин, складання розкладів виконання робіт при обмежених ресурсах та ін. Вони мають ефективне системне забезпечення, в тому числі засоби, що дають можливість користувачу активно брати участь в обчислювальному процесі (досліджувати математичні моделі і методи, які розглядаються, здійснювати пошук розв'язків в режимі діалогу) [5,8,12,13].

Наверх

2. Деякі спеціальні задачі дискретної оптимізації

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

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

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

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

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

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

Наверх

3. Задачі дискретної оптимізації за умов невизначеності вихідних даних

Сучасний етап розвитку теорiї та застосувань математичного, в тому числi дискретного, програмування характеризується необхiднiстю врахування в математичних моделях значного числа невизначених та тих, що погано формалiзуються, факторів, а також неоднозначностi задання вихiдної інформацiї про параметри моделi. Існують рiзнi способи врахування невизначеностi, зокрема за допомогою аналiзу задачi на чутливiсть розв'язків, отриманих для детермiнованих моделей, або шляхом побудови моделей, що містять фактор невизначеностi в явному виглядi. Вихiдні данi таких моделей можуть розглядатися як неточно задані, випадкові, керовані та ін. Розвиваючи та об'єднуючи відомі підходи неточного та узагальненого програмування, були досліджені різні класи задач цілочислової оптимізації з неоднозначно заданою iнформацiєю, для яких встановлено критерії допустимості та оптимальності розв'язків. На основі цих критеріїв розроблено декомпозиційний підхід до розв'язування задач з керованими та неточно заданими початковими даними, який поєднує пошук оптимальних або наближених розв'язків з вирішенням проблеми знаходження невизначених даних моделi [5,8].

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

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

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

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

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

Наверх

4. Застосування моделей і методів дискретної оптимізації для розв'язання економічних задач

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

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

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

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

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

Алгоритмічні засоби, створені для розв'язування на практиці слабкоструктурованих задач вибору, було покладено в основу системи підтримки прийняття рішень (СППР) Альтернатива і ще цілого комплексу спеціалізованих СППР, програмна реалізація яких здійснена на персональних ЕОМ класу IBM PCAT. Ця система орієнтована на розв'язування проблем оптимального вибору, що важко формалізуються, і призначена для безпосереднього використання особами, що приймають рішення, з метою систематизації та інформаційно-аналітичної підтримки діяльності цих осіб. Система дає можливість підвищувати ступінь обгрунтованості рішень в ситуаціях, коли необхідно із заданої скінченної множини можливих альтернатив виділити одну чи кілька кращих з урахуванням переваг та результатів аналізу оцінок, поданих кількома експертами за критеріями, які мають якісний характер. Вибір здійснюється за допомогою спеціальної задачі нелінійного програмування, яка формується шляхом відображення думки кожного експерта в точку простору допустимих оцінок, а підсумковий результат визначається на основі розв'язування задачі оптимізації, що є одним із підкласів відомої задачі Вебера. Структура СППР ІАльтернативаІ дала змогу в низці спеціальних застосувань адаптувати її до конкретних проблемних та програмно-технічних середовищ (за рахунок включення в інтегровані програмні системи, які реалізують комплексні інформаційні технології, зв'язок з СУБД, роботу в локальних мережах).

Одним із плідних напрямків розширення сфери використання розробленої інформаційної технології стали моделі середньострокового прогнозування основних макроекономічних показників України. На початку 1995р. в Інституті кібернетики було розроблено прогноз валового внутрішнього продукту - головного показника України на 1996-2000рр. За час, що минув, підтвердилась висока точність прогнозу, яка перевершила відомі короткострокові (річні) прогнози. Це пояснюється істотним використанням більшого обсягу даних для прогнозу, системним підходом до їх обробки і адекватним відображенням ситуації в застосованих моделях.

Однією з важливих сфер використання економіко-математичних методів і моделей, комп'ютерних і комп'ютерно-мережевих засобів є наукові дослідження і відповідні аналітичні, модельні та прогнозні розрахунки, що стосуються економічної безпеки держави. Такі роботи було започатковано Інститутом кібернетики в співдружності з Державним науково-дослідним інститутом інформатизації та моделювання економіки для Ради Національної безпеки та оборони (РНБО) України [14].

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

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

І.В.Сергієнко, Т.Т. Лебєдєва, В.П. Шило

Наверх

Література

1. Вычислительные методы выбора оптимальных проектных решений / Под ред. В.С. Михалевича. - К.: Наук. думка, 1977. - 178 с.
2. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования. - М.: Наука, 1986.- 264 с.
3. Михалевич В.С., Кукса А.И. Методы последовательной оптимизации. - М.: Наука, 1983. - 208 с.
4. Михалевич В.С., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. - М.: Наука, 1982. - 286 с.
5. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. - К.: Наук. думка, 1985. - 382 с.; 2-е изд., доп. и перераб., 1988.- 472 с.
6. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближеные методы решения дискретных задач оптимизации. - К.: Наук. думка, 1980. - 276 с.
7. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. - К.: Наук. думка, 1981. - 288 с.
8. Сергієнко І.В. Становлення і розвиток досліджень з інформатики. - К.: Наук. думка, 1998. - 206 с.
9. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследование. - К.: Наук. думка, 2003. - 270 с.
10. Глушков В.М. О системной оптимизации // Кибернетика. - 1980. - №5. - С.3-5.
11. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач.- К.: Наук. думка, 1995. - 170 с.
12. Сергиенко И.В. Методы организации вычислительного процесса на вычислительных машинах. - К.: Ин-т кибернетики АН УССР, 1971. - 163 с.
13. Парасюк И.Н., Сергиенко И.В. Пакеты программ анализа данных. Технология разработки. - М.: Финансы и статистика, 1988. - 159с.
14. Великий А.П., Горбулін В.П., Сергієнко І.В. Про підходи та принципи дослідження економічної безпеки та деякі результати їх практичного застосування // УСиМ. - 1997. - №4/5. - С. 5-16.

Наверх