Задача назначения радиочастот

В системе мобильной телефонной связи коммуникация между парами телефонов достигается за счет беспроводных соединений, использующих частоты из некоторой электромагнитной полосы. Задача назначения частот[2] (ЗНЧ) (The frequency assignment problem (FAP)) является трудной дискретной задачей, тесно связанной с задачей раскраски графа. ЗНЧ формально описывается следующим образом. Необходимо установить множество связей для передачи для того, чтобы сделать возможным связь между множеством станций. Каждой связи должна быть назначена частота из заданного множества допустимых частот (области частот) , такого, что не возникает помех связи между данными подмножествами связей, т.е. такого, что для каждой пары связей частоты и , приписанные этим связям, отличаются по меньшей мере на . Объединение этих областей частот обозначается . Цель состоит в минимизации числа использованных частот.

Введем бинарные решающие переменные :

Модель ДО назначения частот имеет вид:

при ограничениях

(частота выбирается только раз)

(для любой пары связей частоты и , приписанные этим связям, отличаются по крайней мере на )