Алгоритм спрощення розв’язку в задачах дискретної оптимізаціі

Анотація

Зазвичай пошук розв’язку в задачах дискретної оптимізації пов'язаний з принциповими обчислюваними труднощами. Відомі методи точного або наближеного розв’язку таких задач вивчаються з урахуванням належності їх до, так званих, задач з класу P та NP (алгоритми поліноміальної та експоненціальної реалізації розв’язку). Сучасні комбінаторні методи для практичного розв’язку задач дискретної оптимізації потребують розробки алгоритмів, які дозволяють отримувати наближений розв'язок з гарантованою оцінкою відхилення від оптимуму. Алгоритми спрощення є ефективним прийомом пошуку розв’язку оптимізаційної задачі. Якщо виконати проектування багатовимірного процесу на двовимірну площину, то такий прийом дозволить наочно відобразити у графічній формі множини розв’язків задачі. В рамках даного дослідження запропоновано спосіб спрощення комбінаторного розв’язку задачі дискретної оптимізації. Він заснований на тому, що виконується декомпозиція системи, яка відображає систему обмежень п’ятивимірної вихідної задачі на двовимірну координатну площину. Такий спосіб дозволяє отримати просту систему графічних розв’язувань складної задачі лінійної дискретної оптимізації. З практичної точки зору запропонований метод дозволяє спростити обчислювальну складність оптимізаційних задач такого класу. Прикладним аспектом запропонованого підходу є використання отриманого наукового результату для забезпечення можливості вдосконалення типових технологічних процесів, що описуються системами лінійних рівнянь з наявністю системами лінійних обмежень. Це складає передумови для подальшого розвитку та удосконалення подібних систем. В даному дослідженні запропоновано методику декомпозиції дискретної оптимізаційної системи шляхом проекції вихідної задачі на двовимірні координатні площини. За такого прийому вихідна задача трансформується в комбінаторне сімейство підсистем, що дозволяє отримати систему графічних розв’язувань складної задачі лінійної дискретної оптимізації