Вычислительные методы в дискретной математике

Применение пороговых приближений для решения систем нелинейных уравнений в методе разделяющих плоскостей

В. Г. Никонов^a, А. Н. Шурупов<sup>b

a</sup> РАЕН, г. Москва
^b МИРЭА, г. Москва

Аннотация: В методе разделяющих плоскостей предлагается перейти от системы линейных неравенств, эквивалентной нелинейному булеву уравнению, к системе линейных неравенств, являющейся следствием исходного уравнения. Вводится понятие импликативного $k$-приближения в пороговом базисе, которое характеризуется, с одной стороны, числом $k$ линейных неравенств, а с другой стороны, дефицитом — мерой близости импликативного приближения к исходной системе неравенств. Предельный случай — 1-приближение, как и остальные, не является однозначным. Отказ от свойства импликативности позволяет ввести понятие статистического порогового приближения для булевой функции. Введённые понятия могут быть использованы для сокращения числа линейных неравенств в системе, порождённой исходным нелинейным уравнением, с сохранением возможности её решения.

Ключевые слова: метод разделяющих плоскостей, нелинейные булевы уравнения, пороговые функции, пороговые приближения.

УДК: 512.55

DOI: 10.17223/2226308X/10/64