Модификация задачи о назначениях

[DON_VINTON]

Пусть A и B квадратные матрицы размера n$\times$n. Элементы матриц-стоимости работ. Нужно найти такое назначение,которое доставляло бы минимум функции $f=f_a^2+f_b^2$,где $f_a$ и $f_b$ значения стоимости полученные одним и тем же назначением из матриц $A$ и $B$ соответственно .
Может быть есть возможность как-нибудь сделать из двух матриц одну ? У меня никаких идей.

[DON_VINTON]

В силу неотрицательности элементов матриц думаю, что целевую функцию можно заменить суммой $f_a+f_b$. Может быть и матрицы можно сложить: A+B ?

[Евгений Машеров]

Нельзя.

[DON_VINTON]

А что можно сделать ?
Я в данный момент пытаюсь построить алгоритм выдающий не одно решение, а множество решений отстоящих от оптимальных на $\epsilon>0$.Может что и прояснится.
Но все равно интересно узнать и другое мнение.

[venco]

Скорее всего, точное решение можно будет получить только полным перебором.
А приблизительно можно попробовать итерациями:
Найти минимум на $(A+B)$ - $f_{a0}, f_{b0}$, потом минимум на $(f_{a0}A+f_{b0}B)$, потом на $(f_{a1}A+f_{b1}B)$, и т.д.

[Евгений Машеров]

Ну, в качестве задачи квадратичного программирования это можно сформулировать. Но вот сохранится ли свойство "неделимости оптимального решения"? Пока не пойму...