26.1. Задача о назначениях. Постановка задачи

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

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

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

Где Cij — затраты, связанные с назначением I-го ресурса на J-й объект, I = J = , где П — число объектов или ресурсов.

Обозначим:

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

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

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

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

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

< Предыдущая		Следующая >