Многим многим «Обобщенному назначению« Проблема »

Question

У меня возникли проблемы с конкретной проблемой. Я должен запланировать 5 сотрудников для работы более 14 дней. каждый сотрудник может работать только 9 из 14 дней, и каждый день должно быть запланировано 3 сотрудника. Ключевая часть заключается в том, что каждый сотрудник имеет определенный штраф за работу в определенный день. Так что, если они не могут работать в этот день, его штраф в размере 10, если они могут это сделать, и не возражают против его штрафа в ноль и, наконец, если они могут, но не хотят его штрафа в размере 5.

I имеют матрицу значений штрафа для каждого сотрудника за каждый день. Я пытаюсь найти способ написать свои противопоказания.

Я подумал о матрице A (матрице штрафа) и матрице B (матрице расписания) и матрице C, где C (i, j) = A (i, j) * B (i, j). с учетом этой настройки, если A (i, j) равно 0 (сотрудник не работает), тогда штраф не будет приниматься во внимание и наоборот.

Так тогда я мог бы сказать, как мои ограничения:

А (1,1) + A (1, M) + A (1, п) < = 9

и

A (1,1) + A (m, 1) + A (n, 1) = 3

и я минимизирую: C (1,1) + C (m, m) + C (n, n)

Моя проблема в том, чтобы рассматривать это как это, пытается использовать это в алгоритме оптимизации. Предполагается, что симплекс-алгоритм может решить любую проблему с LP, но он может быть самым медленным. Я застрял, и теперь я уверен, что рассматриваю это неправильно. Если кто-то может дать мне свежий взгляд и, возможно, объяснить, почему я смотрю на это неправильно, я бы это оценил.

Answer 1

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

Почему вы моделируете «способный и желательный», «способный, но не желающий», и «неспособный» использовать функцию штрафа? Разве вы не хотите минимизировать количество случаев, когда работнику назначается временной интервал, который работник способен, но не хочет работать? (Без, конечно, назначения рабочих слотов, которые они не могут работать?)

Если вы измените проблему, как я предложил выше, ее можно смоделировать как прямую проблему с минимальными затратами. У вас есть один набор узлов для сотрудников и один набор узлов для временных интервалов. Подключите сотрудника к временному интервалу с краем емкости 1, если сотрудник сможет работать с этим временным интервалом. Дайте ему стоимость 0, если работник готов работать тогда и стоит 1, если работник не желает работать тогда. Добавьте источник и раковину; источник должен иметь преимущество перед каждым сотрудником с емкостью 9 (количество дней, в течение которых они могут работать) и нулевую стоимость, тогда как каждый временной интервал должен иметь край к раковине с емкостью 3 и нулевой стоимостью.

Сравнительно простой код с минимальным расходом потока с нуля.

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