ЗАДАЧІ СТОХАСТИЧНОЇ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ: ОГЛЯД ОСТАННІХ РЕЗУЛЬТАТІВ

Анотація

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