|
Вычислительные методы в дискретной математике
Сравнительный анализ эффективности решения псевдобулевых систем линейных неравенств алгоритмами имитации отжига, Балаша и внутренней точки
Г. О. Маняев, А. Н. Шурупов ФУМО ВО «Информационная безопасность», г. Москва
Аннотация:
Целью работы является разработка и исследование надёжности релаксационного алгоритма решения псевдобулевых систем линейных неравенств, построенного на основе алгоритма внутренней точки. Экспериментальный анализ показал высокую (86 %) среднюю надёжность алгоритма, превосходящую аналогичные результаты некоторых эвристических алгоритмов локального поиска при решении случайно выбираемых псевдобулевых систем линейных неравенств. Выявлены классы систем неравенств, на которых сравниваемые эвристические алгоритмы существенно различаются в эффективности решения.
Ключевые слова:
псевдобулевы линейные неравенства, алгоритм внутренней точки, релаксация, линейное программирование.
Образец цитирования:
Г. О. Маняев, А. Н. Шурупов, “Сравнительный анализ эффективности решения псевдобулевых систем линейных неравенств алгоритмами имитации отжига, Балаша и внутренней точки”, ПДМ. Приложение, 2019, № 12, 218–227
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma476 https://www.mathnet.ru/rus/pdma/y2019/i12/p218
|
|