Розробка навчального програмного забезпечення з теми «Метод гілок та меж» для задач оптимізації на переставленнях

Abstract

Об'єктом розробки є процес вивчення та застосування методу гілок та меж до задач оптимізації на переставленнях у курсі «Елементи комбінаторної оптимізації». Предметом розробки є програмна реалізація навчального вебзастосунку, який дозволяє формулювати задачі комбінаторної оптимізації, точно розв'язувати їх методом гілок та меж, покроково візуалізувати дерево галуження та відпрацьовувати алгоритм у тренажері з власноручною побудовою дерева. Метою роботи є створення навчального програмного засобу, що допомагає студентам зрозуміти ідею напрямленого перебору, формули оцінок ν та ξ і правила відсікання для задач на переставленнях. Результатом роботи стало розроблення навчального вебзастосунку «Permutex» на базі Next.js 16 та TypeScript. Реалізовано ключові модулі: • обчислювальне ядро методу гілок та меж для безумовної лінійної задачі, лінійної задачі з обмеженнями, комбінаторної транспортної задачі та задачі про найкоротший маршрут у графі; • модуль обчислення оцінок ν і ξ з підтримкою режимів мінімізації та максимізації; • модуль повного перебору для порівняння ефективності методу гілок та меж із наївним підходом; • інтерактивна візуалізація дерева галуження на бібліотеці React Flow з покроковою навігацією та автозапуском; • редактори вхідних даних з валідацією, генератор випадкових задач та готові приклади задач; • чотири інтерактивні тренажери - для безумовної задачі, для задачі з обмеженнями, для комбінаторної транспортної задачі та для задачі про маршрут - у яких студент сам обирає бруньку, фіксує значення з G, обчислює ν та ξ, ухвалює рішення про відсікання, а програма перевіряє кожен крок з підрахунком правильних і помилкових відповідей; • режим самоперевірки (Quiz) у демонстраційному розв'язувачі, у якому студент вводить очікувані ν та ξ, а програма ставить ✓ або ✗; • довідковий розділ із формулюваннями теорем, означеннями та прикладами на основі KaTeX.