Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Здравствуйте. По роду деятельности я программист и сейчас свою проблему записал в математическом виде 1) Есть множество свойств {ФП} 2) Есть множество компонентов {K} Каждый K обладает свойствами из множества {ФП}, а также каждому К соответствует один элемент P, где P - это положительное число
Задача: Найти набор (подмножество) {k}, которые в результате дадут строго заданное подмножество {фп}, но при этом сумма Р полученных К должна быть минимальна.
Вопрос: Что-то не соображу как решаются подобного рода задачи, симплексом (если да, то как будет выглядеть целевая ф-ция и ограничения) или быть может что-нибудь из теории множеств? Пожалуйста, наведите на мысль.
Заранее спасибо!
GAA
Re: Возникли вопрос по множеству и их оптимизации
11.01.2011, 22:28
Похоже на Задачу о наилучшем покрытии. См., например, Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978 (djvu) Насколько я помню, в этой книге в описании алгоритма поиска решения ЗНР есть опечатка.