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

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

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



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






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


ПДМ, 2013, номер 2(20), страницы 91–100 (Mi pdm411)  

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

Модификация метода Лагариаса–Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках

Д. М. Мурин

Ярославский государственный университет им. П. Г. Демидова, г. Ярославль, Россия

Аннотация: В работе 1985 г. Дж. Лагариас и А. Одлыжко предложили метод решения вычислительной задачи о рюкзаке, основанный на её сведении к задаче поиска короткого вектора в решётке специального вида. Метод Лагариаса–Одлыжко позволяет решать “практически все” задачи о рюкзаках, обладающие малой плотностью. В настоящей работе метод Лагариаса–Одлыжко решения задачи о рюкзаке модифицируется применительно к случаям обобщённой задачи о рюкзаке и систем задач о рюкзаках. Система задач о рюкзаках вводится в настоящей работе как конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Определяются множества значений плотности обобщённых задач о рюкзаках и систем задач о рюкзаках, такие, что модифицированные методы позволяют решать “практически все” обобщённые задачи о рюкзаках и системы задач о рюкзаках, обладающие плотностью из этих множеств.

Ключевые слова: метод Лагариаса–Одлыжко, задача о рюкзаке, обобщённая задача о рюкзаке, системы задач о рюкзаках.

Полный текст: PDF файл (581 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 511

Образец цитирования: Д. М. Мурин, “Модификация метода Лагариаса–Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках”, ПДМ, 2013, № 2(20), 91–100

Цитирование в формате AMSBIB
\RBibitem{Mur13}
\by Д.~М.~Мурин
\paper Модификация метода Лагариаса--Одлыжко для решения обобщённой задачи о~рюкзаке и~систем задач о~рюкзаках
\jour ПДМ
\yr 2013
\issue 2(20)
\pages 91--100
\mathnet{http://mi.mathnet.ru/pdm411}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm411
  • http://mi.mathnet.ru/rus/pdm/y2013/i2/p91

    ОТПРАВИТЬ: 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
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:296
    Полный текст:109
    Литература:29
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021