2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: Возникли вопрос по множеству и их оптимизации
Сообщение10.01.2011, 00:10 

(Оффтоп)

Delphist в сообщении #397377 писал(а):
Здравствуйте. ... свою проблему записал в математическом виде


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

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

 
 
 
 Re: Возник вопрос по множеству и их оптимизации
Сообщение10.01.2011, 16:02 
а симплексом нельзя ли как-нить решить?

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

 
 
 
 Re: Возник вопрос по множеству и их оптимизации
Сообщение10.01.2011, 19:17 
Хорошо, спасибо большое

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group