Постановка задачи

 

Задача заключается в выборе такого распределения ре­сурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс.

Возможные применения задачи о назначениях представле­ны в табл. 26.1.

 

 

Матрица стоимостей С имеет вид

 

 

где c_ij — затраты, связанные с назначением i-го ресурса на j-й объект, i = j = , где п — число объектов или ресурсов.

Обозначим:

 

 

Таким образом, решение задачи может быть записано в ви­де Х = (x_ij).

Допустимое решение называется назначением. Оно строит­ся путем выбора ровно одного элемента в каждой строке мат­рицы X = (x_ij) и ровно одного элемента в каждом столбце этой матрицы.

Элементы c_ij матрицы С, соответствующие элементам x_ij = 1 матрицы X, будем отмечать кружками:

 

 

Математическая постановка задачи:

 

 

при ограничениях: