Методы оптимизации

Выпуклые матрицы и линейные целочисленные оптимизационные задачи

В. В. Григорьев^a, А. П. Тизик^b, Ю. П. Тресков<sup>b

a</sup> Московский государственный институт международных отношений МИД России, г. Москва
^b Учреждение Российской академии наук Вычислительный центр им. А.А. Дородницына РАН, г. Москва

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

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

УДК: 519.863

Поступила в редакцию: 23.07.2009
Исправленный вариант: 10.09.2009

Реферативные базы данных:

•