Обчислювальна схема алгоритмів послідовної оптимізації, що мінімізує пошуки в дереві варіантів. Повідомлення 1

Abstract

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

Предлагается алгоритм решения задачи дискретного программирования. В ходе решения анализируемая задача заменяется последовательностью задач поиска точек, которые принадлежат некоторым подмножествам множества планов начальной задачи. Описан рекуррентный способ построения последовательности решений вспомогательных задач. Доказано, что эта конечная последовательность сходится к решению начальной задачи.

Propose an improving of algorithms solving tasks of discrete programming, which are based on computing scheme of branches and limits, which are seem to be algorithms of sorting tree of variants union of algorithms elimination invalid and nonoptimal variants, also algorithms partitioning discrete sets, determinated in Euclidean space. Showed, that is possible computing scheme, which is does not need any searching in the tree of variants and computing limits.