УДК 519.8

Монтлевич В.М. Исмаилова А.Н.

ЭМПИРИЧЕСКИЙ АНАЛИЗ ПРИБЛИЖЕННЫХ АЛГОРИТМОВ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ, ОСНОВАННЫХ НА ИДЕЕ ЖАДНОГО ВЫБОРА

Аннотация. В статье приводятся результаты эмпирического изучения эвристических алгоритмов целочисленного программирования, основанных на идее жадного выбора. На основе большого объема вычислительных экспериментов даются оценки средней погрешности приближенного решения.

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

Библиографический список

• 1. Глебов Н.И., Шенмайер В.В. О применимости алгоритма покоординатного подъема к задачам целочисленного программирования // Дискретный анализ и исследование операций. 2000. Сер. 1. Т. 7. № 4. С. 38–47.
• 2. Глебов Н.И. Об условиях разрешимости оптимизационных задач жадным алгоритмом // Дискретный анализ и исследование операций. Июль–декабрь 2002. Сер. 2. Т. 9.№ 2. С. 3–12.
• 3. Шенмайер В.В. Максимизация линейной целевой функции с помощью жадного алгоритма // Дискретный анализ и исследование операций. 1999. Сер. 1. Т. 6. № 4. С. 104–120.