Эта публикация цитируется в 35 статьях

Новые нижние оценки для задачи размещения с предпочтениями клиентов

И. Л. Васильев^ab, К. Б. Климентова^ab, Ю. А. Кочетов<sup>ba

a</sup> 664033 Иркутск, ул. Лермонтова, 134, Ин-т динамики систем и теории управления СО РАН
^b 630090 Новосибирск, ул. Пирогова, 2, Новосибирский гос. ун-т

Аннотация: Исследуется двухуровневая задача размещения производства, в которой клиенты выбирают поставщиков исходя из собственных предпочтений. Показано, что кооперативная и антикооперативная постановки могут быть сведены к частному случаю, когда каждый клиент имеет линейный порядок предпочтений на множестве открываемых предприятий. Для этого частного случая рассматриваются различные сведения двухуровневой задачи к целочисленному линейному программированию. Предложена новая формулировка задачи, основанная на семействе правильных неравенств, связанных с задачами о паре матриц и упаковки множеств. Показано, что эта формулировка доминирует уже известные с точки зрения линейной релаксации и разрыва целочисленности. Библ. 21.

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

УДК: 519.6:519.866.6

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

 Англоязычная версия: Computational Mathematics and Mathematical Physics, 2009, 49:6, 1010–1020

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

• 
• 
•