Задача о назначениях
Пусть имеются n работ и n кандидатов для их выполнения. Назначению i-го кандидата (i = 1... n) на j-ю работу (j = 1... n) соответствуют определенная эффективность (прибыль, производительность) или затраты какого-либо ресурса сТре- буется назначить на выполнение всех видов работ таких кандидатов, которые обеспечат наибольшую эффективность, т. е. минимум суммарных затрат или максимум прибыли (производительности). Каждого кандидата можно назначить только на одну должность, и каждая работа может быть выполнена только одним кандидатом.
Математическая постановка задачи имеет вид:
n n n n
mnJ = min? ? Cjxj; ? xij = 1 ? xц = i
j=1 j=1 i=1 j=1
где xij — искомая переменная: х, = 1, если i-й кандидат распределяется на j-ю работу; 0 — в противном случае.
В такой постановке данная задача относится к классу комбинаторных.
Похожие рефераты:
