задача назначения с затратами

у меня есть проблема, с которой я застрял, и не могу найти, с чего начать, поэтому я безнадежно обращаюсь к stackoverflow.

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

проблема в следующем:

произведение существует из n модулей. есть две компании, которые могут построить каждый модуль с некоторой стоимостью (c_ij, i: номер модуля, j: номер компании). если модули a и b производятся разными компаниями, они также имеют дополнительную стоимость (p_ab). модули a и b не обязательно должны быть последовательными, такие же дополнительные расходы применяются и для a и c. как и ожидалось, задача хочет, чтобы мы нашли назначение модулей компаниям так, чтобы общая стоимость была минимальной.

Любые идеи ?


variable-assignment graph-algorithm np-complete
person fizboz    schedule 22.11.2010    source источник
comment
Там только две компании или по две на каждый модуль?   -  person jpalecek    schedule 06.12.2010
comment
всего две компании.   -  person fizboz    schedule 12.12.2010

Ответы (1)


arrow_upward
1
arrow_downward

Ее можно свести к задаче о минимальном разрезе, которую можно найти с помощью любого алгоритма максимального потока. Так что за сеть? Модули будут вершинами нашего графа, а также мы добавим 2 новые вершины источник и сток. Из источника мы добавляем ребро к каждому модулю i с емкостью Ci1. Аналогично из каждого модуля i прибавляем ребро к стоку емкостью Ci2. Также для любых модулей i и j добавим ребро с пропускной способностью pij (граф, ориентированный таким образом, будет два ребра (i j) и (j i)). Нетрудно видеть, что значение минимального разреза является решением задачи (модули в части разреза с исходником отнесены ко второй компании, а остальные модули к первой компании)

person MikleB    schedule 29.11.2010
comment
спасибо mikleb, это был точный ответ, который я нашел через 2 дня после того, как опубликовал вопрос. я должен был быть более ответственным, чтобы опубликовать ответ, но он вылетел из головы. но в любом случае, ваше решение должно помочь другим людям в будущем. - person fizboz; 12.12.2010