Задача о назначениях: новый класс

[a-xenon]

Напомню, что в классической форме, необходимо n сотрудников распределить на m должностей, так чтобы была минимальна/максимальна суммарная стоимость.
Столкнулся с необычной задачей о назначениях: имеется берег в виде прямой линии, прибрежное пространство разделено на прямоугольные зоны. И есть локаторы, область видения которых тоже прямоугольной формы. В месте пересечения зон и локаторов получаем стоимость (как в классической формулировке), зависящую от произведения площади пересечения, параметра зоны и параметра локатора. Необходимо расставить локаторы так,чтобы стоимость наблюдения ими была минимальна.

-- Вс мар 07, 2010 21:48:09 --

Получается непрерывная задача о назначениях. Пробовал решать жадным алгоритмом: глобального оптимума не получается найти, только субоптимальность. Помогите разобраться, может что-то уже есть решенное наподобие.

[mserg]

Привели бы конкретные данные, а то непонятно, куда ставится радар (на береговую линию?), должен ли радар покрывать всю зону или два радара могут покрывать по пол-зоны, как формируется стоимость, что за параметры локатора и как они учитываются, каковы ориентировочные объемы данных (зон, радаров) и т.д. Замечено, что на этом форуме с телепатией очень плохо...