Правила форума
В этом разделе
нельзя создавать новые темы. Если Вы хотите задать новый вопрос, то
не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть
удалены без предупреждения.Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса
обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть
удалена или перемещена в
Карантин, а Вы так и не узнаете, почему.
Delphist |
Возник вопрос по множеству и их оптимизации 10.01.2011, 00:02 |
|
21/08/07 29
|
Последний раз редактировалось Delphist 10.01.2011, 00:16, всего редактировалось 1 раз.
Здравствуйте. По роду деятельности я программист и сейчас свою проблему записал в математическом виде 1) Есть множество свойств {ФП} 2) Есть множество компонентов {K} Каждый K обладает свойствами из множества {ФП}, а также каждому К соответствует один элемент P, где P - это положительное число
Задача: Найти набор (подмножество) {k}, которые в результате дадут строго заданное подмножество {фп}, но при этом сумма Р полученных К должна быть минимальна.
Вопрос: Как решаются подобного рода задачи, симплексом (если да, то как будет выглядеть целевая ф-ция и ограничения) или быть может что-нибудь из теории множеств?
Заранее спасибо!
|
|
|
|
|
mihailm |
Re: Возникли вопрос по множеству и их оптимизации 10.01.2011, 00:10 |
|
19/05/10 ∞ 3940 Россия
|
(Оффтоп)
Здравствуйте. ... свою проблему записал в математическом виде
Это вы так думаете что в математическом виде, математики так не думают (отвечу за всех)
|
|
|
|
|
deep blue |
Re: Возник вопрос по множеству и их оптимизации 10.01.2011, 01:43 |
|
23/11/09 173
|
У каждого компонента задано подмножество свойств и его вес P. Нужно покрыть все множество свойств его допустимыми подмножествами (компонентами), при этом суммарный вес должен быть минимален. Это известная задача о покрытии, а точнее о разбиении множества на допустимые подмножества, она NP-трудная, но решается достаточно быстро (как правило). Есть много переборных алгоритмов ее решения, для ознакомления с самой задачей можно глянуть “Теория графов: алгоритмический подход. Кристофидес”, а чтобы эффективно ее решать- лучше почитать что-нибудь на английском, но Кристофидеса скорее всего будет достаточно.
|
|
|
|
|
Delphist |
Re: Возник вопрос по множеству и их оптимизации 10.01.2011, 16:02 |
|
21/08/07 29
|
а симплексом нельзя ли как-нить решить?
|
|
|
|
|
deep blue |
Re: Возник вопрос по множеству и их оптимизации 10.01.2011, 17:57 |
|
23/11/09 173
|
Обычным симплексом (без отсекающих плоскостей) нельзя, это задача ЦЛП, а не ЛП. Симплексом можно получить оценку снизу, решая ЛП вместо ЦЛП, а далее использовать ее в переборе. В Кристофидесе похожий алгоритм, но без симплексной оценки, а в статьях на тему set covering problem чего только нет.
|
|
|
|
|
Delphist |
Re: Возник вопрос по множеству и их оптимизации 10.01.2011, 19:17 |
|
21/08/07 29
|
|
|
|
|
|
Страница 1 из 1
|
[ Сообщений: 6 ] |
|
Модераторы: Модераторы Математики, Супермодераторы