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

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

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

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

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

Обозначим:

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

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

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

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

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

Дата добавления: 2014-10-15