HJ
Там даже COBOL местами актуален.
жеск
Size: a a a
2020 December 01
I
Там даже COBOL местами актуален.
ВВ
Reuters reported in 2017 that 43% of banking systems still used COBOL with over 200 million lines of COBOL code in use.
ВВ
Впрочем, это оффтопик.
CD
А как просто сделать чтобы каждый работник хотя бы одну работу выполнял?
Я не умею, и очень долго буду вспоминать как сложно
BV
А там досели на вба пишут? Ээээ😱
Угу, из примечательных мест где я лично видел использование vba - boeing
p
Ребят дана задача:
В прикрепленном файле содержится матрица стоимостей выполнения задач. Всего 20 задач (T1, T2... T20) и 10 работников (W1, W2... W10). Необходимо распределить задачи между работниками так, чтобы суммарная стоимость была минимальная и должны быть выполнены следующие условия:
• Каждая задача должна быть назначена
• Все работники должны иметь хотя бы одну задачу, но, не более 3х.
В качестве ответа приведите суммарную стоимость и вектор длины 10, каждый элемент которого соответствует количеству работ, назначенных соответствующему работнику.
подскажите куда копать. Алгоритм какой нибудь
В прикрепленном файле содержится матрица стоимостей выполнения задач. Всего 20 задач (T1, T2... T20) и 10 работников (W1, W2... W10). Необходимо распределить задачи между работниками так, чтобы суммарная стоимость была минимальная и должны быть выполнены следующие условия:
• Каждая задача должна быть назначена
• Все работники должны иметь хотя бы одну задачу, но, не более 3х.
В качестве ответа приведите суммарную стоимость и вектор длины 10, каждый элемент которого соответствует количеству работ, назначенных соответствующему работнику.
подскажите куда копать. Алгоритм какой нибудь
Кроме венгерского алгоритма также можно использовать более общий метод и (лично для меня) более простой - min cost k flow. Это решение уже совсем просто изменить под доп. условия, немного изменив граф.
K
Да спасибо посмотрю. У венгерского требование что матница должна быть квадратной. У меня с этим проблема
ВВ
Да спасибо посмотрю. У венгерского требование что матница должна быть квадратной. У меня с этим проблема
Для неквадратных матриц добавляют фиктивных работников/работы.
K
0 вместо значений ?
K
Ок а как быть со 2 условием где каждый работник должен иметь минимум 1 и максимум 3 работы. У нас 20 заданий а работников всего 10. И нужно всех задачи раскидать оптимально
p
0 вместо значений ?
Бесконечность
ВВ
Там выше уже предложили утроить каждого работника.
Но вот для случая, когда три клона ушли на фиктивную работу, так как остальные демпингуют, нужно подумать.
Наверное, в самом деле проще решить через поток. Или вообще не заморачиваться, а взять lp-solver. :)
Но вот для случая, когда три клона ушли на фиктивную работу, так как остальные демпингуют, нужно подумать.
Наверное, в самом деле проще решить через поток. Или вообще не заморачиваться, а взять lp-solver. :)
ВВ
0 вместо значений ?
Да всё равно. Мы ж выбросим эти задачи.
p
Да всё равно. Мы ж выбросим эти задачи.
Не все равно
K
Там выше уже предложили утроить каждого работника.
Но вот для случая, когда три клона ушли на фиктивную работу, так как остальные демпингуют, нужно подумать.
Наверное, в самом деле проще решить через поток. Или вообще не заморачиваться, а взять lp-solver. :)
Но вот для случая, когда три клона ушли на фиктивную работу, так как остальные демпингуют, нужно подумать.
Наверное, в самом деле проще решить через поток. Или вообще не заморачиваться, а взять lp-solver. :)
Я радостью но нужно самому. Пойду снова думать.
p
Может повлиять на ответ, если 0
CD
Я радостью но нужно самому. Пойду снова думать.
Ну ищите как ограничение снизу в min-cost-max-flow делается
ВВ
Не все равно
Так все работы всё равно будут распределены. Если у фиктивных работ для разных работников одинаковая стоимость, то и их назначение не повлияет на результат.
В венгерском алгоритме идея как раз в том, что вычитание одного и того же числа из любой строчки или столбика не меняет оптимальное решение, только суммарную стоимость.
Так что какое бы значение для фиктивного столбика мы ни выбрали, если одно одинаковое, мы можем его вычесть и получить ноль. Или что-то ещё.
Или я ошибаюсь?
В венгерском алгоритме идея как раз в том, что вычитание одного и того же числа из любой строчки или столбика не меняет оптимальное решение, только суммарную стоимость.
Так что какое бы значение для фиктивного столбика мы ни выбрали, если одно одинаковое, мы можем его вычесть и получить ноль. Или что-то ещё.
Или я ошибаюсь?
ИС
Если не хочется искать про ограничение снизу, можно одному из трёх работников запретить выполнять фиктивные задачи, выставив стоимость в бесконечность, а двум другим экземплярам разрешить, выставив в 0.