МЕТОД ГІЛОК І МЕЖ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ОПТИМІЗАЦІЇ ЛІНІЙНОЇ ЦІЛЬОВОЇ ФУНКЦІЇ НА РОЗМІЩЕННЯХ З ІМОВІРНІСНОЮ НЕВИЗНАЧЕНІСТЮ

Анотація

Актуальним напрямом сучасної теорії оптимізації є дослідження задач комбінаторної природи за різних видів невизначеності. Один із підходів до формулювання оптимізаційних задач з імовірнісною невизначеністю ґрунтується на введенні відношення порядку на фактор–множині, що утворюється при розбитті заданої множини незалежних випадкових величин на основі порівняння їх числових характеристик. Ця стаття присвячена обґрунтуванню методу гілок і меж для розв’язування оптимізаційних задач на розміщеннях, постановка яких здійснена на основі такого підходу. Зокрема, обґрунтовано алгоритм методу гілок і меж для розв’язування задач оптимізації на розміщеннях з лінійною цільовою функцією, у якій коефіцієнти є детермінованими величинами, тоді як елементи мультимножини є класами еквівалентності за згаданою еквівалентністю (H–задач). Пропонується проводити галуження загальної множини розміщень, надаючи певні можливі значення частині змінних. Коли отримується одноелементна множина, здійснюється перевірка, чи належить одержане розміщення множині, що визначена додатковими (некомбінаторними) обмеженнями. Запропоновано й обґрунтовано спосіб оцінювання підмножин, у якому використовуються властивості екстремалі в лінійній безумовній задачі стохастичної комбінаторної оптимізації на розміщеннях, сформульовано алгоритм методу гілок і меж. Роботу алгоритму проілюстровано прикладом. Для лінійної безумовної задачі оптимізації на розміщеннях, у якій коефіцієнти цільової функції є класами еквівалентності, а елементи мультимножини – детермінованими величинами (Hd–задач), встановлено зв’язок із H–задачами. Спираючись на цей взаємозв’язок та властивості розв’язку H–задачі, встановлено властивості мінімалі у розв’язку Hd–задачі. Розглянуто особливості застосування методу гілок і меж для розв’язування Hd–задач: як і для H–задачі пропонується використовувати галуження «вглиб», також обґрунтовано спосіб оцінювання підмножин.