RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ., 2017, номер 2, страницы 48–61 (Mi vagtu478)  

КОМПЬЮТЕРНОЕ ОБЕСПЕЧЕНИЕ И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций

Г. А. Попов

Астраханский государственный технический университет

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

Ключевые слова: квадратичное программирование, бинарные переменные, оптимальное решение, формула Кардано, эвристический алгоритм.

DOI: https://doi.org/10.24143/2072-9502-2017-2-48-61

Полный текст: PDF файл (374 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 004.056.5
Поступила в редакцию: 21.03.2017

Образец цитирования: Г. А. Попов, “Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций”, Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ., 2017, № 2, 48–61

Цитирование в формате AMSBIB
\RBibitem{Pop17}
\by Г.~А.~Попов
\paper Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций
\jour Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ.
\yr 2017
\issue 2
\pages 48--61
\mathnet{http://mi.mathnet.ru/vagtu478}
\crossref{https://doi.org/10.24143/2072-9502-2017-2-48-61}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/vagtu478
  • http://mi.mathnet.ru/rus/vagtu/y2017/i2/p48

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика
    Просмотров:
    Эта страница:87
    Полный текст:29
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020