Том 16, номер 2, 2009 г., Стр. 21-41
УДК 519.854.2
И. Л. Васильев, К. Б. Климентова
Метод ветвей и отсечений для задачи размещения с предпочтениями клиентов
Аннотация:
Проводится численное исследование методов решения задачи размещения производства, в которой клиенты выбирают поставщиков исходя из собственных предпочтений. Рассматриваются различные формулировки данной задачи в виде задач целочисленного линейного программирования. Для предложенного ранее семейства правильных неравенств, возникающего из связи с задачей о паре матриц, реализован метод отсечений. Проведён вычислительный эксперимент по его тестированию. Поиск точного решения задач осуществляется двумя вариантами метода ветвей и отсечений с использованием указанного выше метода отсечений. Для поиска верхних оценок оптимального решения в точных методах предложено использовать метод имитации отжига. Вычислительный эксперимент подтверждает эффективность реализованного подхода по сравнению с известными.
Библиогр. 15.
Ключевые слова: задача размещения с предпочтениями клиентов, метод отсечений, локальный поиск, метод ветвей и отсечений.
Васильев Игорь Леонидович 1
Климентова Ксения Борисовна 1
1. Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
е-mail: vil@icc.ru, Xenia.Klimentova@icc.ru
Статья поступила 7 ноября 2008 г.
Исправленный вариант — 4 февраля 2009 г.
