Задача о назначении

Задача о назначении

Имеется n работ и n исполнителей. Назначение i-ого работника на j-ую работу связано с затратами c_­ij­, требуется найти назначение кандидатов на все работы, дающие минимальные суммарные затраты. При этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом.

Постановка задачи и выбор оптимизации
Пусть для монтажа четырех объектов требуется 4 крана. Каждый кран A_­i­ для монтажа объекта B_­j­. Нужно так распределить краны по объектам, чтобы суммарное время для монтажа было минимальным. C­_ij­ - затраты времени i-ого крана на монтаж j-ого объекта. Исходные данные приведены в таблице 1.
Таблица 1.

	B1	B2	B3	B4	ai	di
A1
A2
A3
A4
bj

x_ij­=1, если A­_i­ → B_­j­;
в противном случае x_ij­=0
Т.к. каждый кран можно распределить только на один объект и на каждом объекте может работать только один кран, то введенные переменные x_ij­ должны подчиняться двум условиям (ограничениям).

Критерий оптимизации (целевая функция):

Для решения задачи о назначении существует несколько методов, наиболее известный - «венгерский». Принцип метода (основная идея метода): оптимальность решения задачи о назначении не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину d­_i­ (d­_j). Решения считается оптимальным, если измененные искусственно затраты c_ij*≥0 и можно отыскать такой набор переменных x_­ij­, что: