Поиск оптимума

stasyun

есть группа рабочих из n человек
они могут работать группами по 3/2/1 человеку. по каждой такой группе известна их производительность труда (причём для 3х человек она в большинстве случаев больше, чем лучшая для одного, умноженная на 3)
необходимо выбрать группы так, чтобы каждый работник входил только в одну группу, и при этом суммарная производительность была бы наибольшей
----------------
сам придумал себе задачку и уже 2 дня спать не могу :mad:

stasyun

а, ну и при том не обязаны быть все группы по 3 рабочих (их вполне может вообще не быть)

griz_a

Так сколько таки в задаче параметров?
Рабочие все одинаковые и у нас три параметра - производительность в одиночку, производительность вдвоем, производительность втроем?
Тогда чего тут. Берем производительность троих, делим на три, производительность двоих пополам и производительность одного, a/3,b/2,c
Если a/3>b/2>c, то забиваем все тройками, остаток двойками, остаток одиночками. Единственное, может быть выгоднее тройки + 2 двойки, если 2b>a+c
Если a/3>c>b/2, то тройки плюс единицы.
Еcли c больше всех, то забиваем все единицами.
Если b/2>a/3>c, то если n четное число, то забиваем все двойками, если нечетное - то либо все двойки, одна единица, либо двойки, тройка смотря что больше - b+c или a.
Ну и если b/2>c>a/3, то все двойки, остаток (если есть) единицами.
Или рабочие все разные и параметров [math]$n+C^2_n+C^3_n$[/math], то у меня нет никаких ожиданий, что у задачи будет осмысленное решение.
Параметров много - дерьмовый ответ

stasyun

конечно, рабочие разные

griz_a

Тогда спите спокойно, ваша задача никакого осмысленного короткого решения не имеет.
Де факто вам все равно в том или ином виде придется перебирать всевозможные наборы.

Niklz

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

BSCurt

с учетом структуры задачи может и какой-то более эффективный алгоритм поиска минимума можно записать.
Какая структура - нет там никакой структур, сиди перебирай элементы множества подмножеств, задача не осмысленная просто

Niklz

>> Какая структура
— могут работать группами по 3/2/1 человеку
— ля 3х человек производительность в большинстве случаев больше, чем лучшая для одного, умноженная на 3
--- каждый работник входил только в одну группу
>> задача не осмысленная просто
ну так можно сказать, что все задачи дискретной оптимизации не осмысленны - сиди себе перебирай варианты. о чем я и говорю, для мехматянина, если решение нельзя записать формулой, задача смысла не имеет

BSCurt

ну так можно сказать, что все задачи дискретной оптимизации не осмысленны. о чем я и говорю, для мехматянина, если решение нельзя записать формулой, задача смысла не имеет
Ты мне кажется тупишьнедопонимаешь, там у произвольной группы рабочих может быть любая производительность, т.е. рабочие и группы не однородные, и всё на этом решение задачи заканчивается.
Из ничего не выйдет ничего - один из принципов математики, можно сказать.

BSCurt

Хотя, возможно есть какой-нибудь рациональный алгоритм поиска разбивки всего множества рабочих на группы, если принять, что нам известно значение функции производительности на каждой 1/2/3 рабочих и нас совершенно не смущает, что таких 1/2/3 рабочих очень даже до черта.

griz_a

если решение не записывается короткой формулой (желательно в гладких функциях) - решение не осмысленно?

Если человек хотел увидеть длинный переборный алгоритм, то он бы так и написал, наверное?
Ответ формулой я написать могу, нет проблем :) Только от нее проку нет.
Могу даже предложить алгоритм покороче чем полный перебор. Суть отбросить заведомо неудачные сочетания. Но по сложности он будем сравним с полным перебором и особенно далеко отсюда не уйдешь.
Если бы перед ним стояла эта задача с практической точки зрения, то можно было бы говорить о громоздких уродливых алгоритмах.
Но если человек для себя поставил задачу, которая его заинтересовала, то вряд ли он ожидает, что ему предложат стену лбом прошибать.

Niklz

>> Если человек хотел увидеть длинный переборный алгоритм, то он бы так и написал, наверное?
ну почему длинный, обычно алгоритмы в дискретной оптимизации записываются строк в 10 :)
>>Могу даже предложить алгоритм покороче чем полный перебор. Суть отбросить заведомо неудачные сочетания.
>>Но по сложности он будем сравним с полным перебором и особенно далеко отсюда не уйдешь.
Во, в этом и задача. И "отбросить заведомо неудачные" это одно из соображений, есть еще "не решать одну подзадачу дважды" в динамическом программировании, есть еще всякие релаксации, которые находят приближенное решение, а затем в его окрестности точное и т.п.
Если искать приближенное решение, то можно вполне эффективный алгоритм дать. Те же приближенные методы решения задачи булева программирования.
>> Если бы перед ним стояла эта задача с практической точки зрения, то можно было бы говорить о громоздких уродливых алгоритмах.
>> Но если человек для себя поставил задачу, которая его заинтересовала, то вряд ли он ожидает, что ему предложат стену лбом прошибать.
Ну почему сразу громоздких и уродливых :) Алгоритмы бывают чертовски изящные!
На интересе к выдуманной задаче может он разберется с дискретной оптимизацией, запрогает что-нибудь - будет польза.

Vlad128

Напиши, пожалуйста, этот алгоритм, зачем разводить тут демагогию? :)

Niklz

ссылки на то, что пришло в голову, я вроде дал: записываешь эту задачу как задачу булева программирования, используешь один из стандартных методов ее решения.

griz_a

Во, в этом и задача.

Я сомневаюсь, что в этом и задача.
В любом случае, любознательность такова сорта несколько нездорова.
Неподъемных аналитически и громоздких вычислительно задач пруд пруди, если бросаться грудью на каждую амбразуру дота, то жизнь так и пройдет в таких бессмысленных метаниях.
Задача должна исходить либо из жизни, etc, либо иметь обозримые подходы к решению.
Подход "а вот интересно, что будет, если поставить такую вот задачу" довольно тухлый. Задач триллионы, решаются из них тысячи.

Vlad128

это все хорошо, но иногда все равно хочется решить :grin:

blackout

Производительность любой группы из 1-го, 2-ух и 3-х рабочих произвольна и никак не зависит от производительности любой другой группы (в частности, группа из 2-ух может быть даже менее производительна, чем каждый ее рабочий по отдельности).
Вывод: задача решается только перебором всех возможных разбиений на группы по 1/2/3 рабочих.

BSCurt

Вывод: задача решается только перебором всех возможных разбиений на группы по 1/2/3 рабочих.
Не совсем общая функция производительности всё таки сумма частных функций производительности, т.е. после того как мы перебрали все подмножества из 1,2,3 элементов и вычислили на каждом из них частную функцию производительности уже можно пытаться что-то думать, что не будет прямым перебором, но всё равно наверное что-то жуткое будет.

iri3955

Смело, с учётом, что ты еще не показал, как свести задачу к NP-полной, а также не доказал соответствующую гипотезу.
Вообще, я поражаюсь, какие здесь выводу понаделали некоторые отметившиеся.
И да, мне тоже кажется, что хорошего решения тут не будет, но обосновать пока не получилось
Оставить комментарий
Имя или ник:
Комментарий: