Возник вопрос по множеству и их оптимизации

[Delphist]

Здравствуйте. По роду деятельности я программист и сейчас свою проблему записал в математическом виде
1) Есть множество свойств {ФП}
2) Есть множество компонентов {K}
Каждый K обладает свойствами из множества {ФП}, а также каждому К соответствует один элемент P, где P - это положительное число

Задача: Найти набор (подмножество) {k}, которые в результате дадут строго заданное подмножество {фп}, но при этом сумма Р полученных
К должна быть минимальна.

Вопрос: Как решаются подобного рода задачи, симплексом (если да, то как будет выглядеть целевая ф-ция и ограничения) или быть может что-нибудь
из теории множеств?

Заранее спасибо!

[mihailm]

(Оффтоп)

Delphist в сообщении #397377 писал(а):

Здравствуйте. ... свою проблему записал в математическом виде

Это вы так думаете что в математическом виде, математики так не думают (отвечу за всех)

[deep blue]

У каждого компонента задано подмножество свойств и его вес P. Нужно покрыть все множество свойств его допустимыми подмножествами (компонентами), при этом суммарный вес должен быть минимален.
Это известная задача о покрытии, а точнее о разбиении множества на допустимые подмножества, она NP-трудная, но решается достаточно быстро (как правило). Есть много переборных алгоритмов ее решения, для ознакомления с самой задачей можно глянуть “Теория графов: алгоритмический подход. Кристофидес”, а чтобы эффективно ее решать- лучше почитать что-нибудь на английском, но Кристофидеса скорее всего будет достаточно.

[Delphist]

а симплексом нельзя ли как-нить решить?

[deep blue]

Обычным симплексом (без отсекающих плоскостей) нельзя, это задача ЦЛП, а не ЛП. Симплексом можно получить оценку снизу, решая ЛП вместо ЦЛП, а далее использовать ее в переборе. В Кристофидесе похожий алгоритм, но без симплексной оценки, а в статьях на тему set covering problem чего только нет.

[Delphist]

Хорошо, спасибо большое