2014 dxdy logo

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

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




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

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

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

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

 
 
 
 Re: Возникли вопрос по множеству и их оптимизации
Сообщение11.01.2011, 22:28 
Похоже на Задачу о наилучшем покрытии. См., например,
Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978 (djvu)
Насколько я помню, в этой книге в описании алгоритма поиска решения ЗНР есть опечатка.

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


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