Задача о назначении
Задача о назначении Имеется n работ и n исполнителей. Назначение i-ого работника на j-ую работу связано с затратами cij, требуется найти назначение кандидатов на все работы, дающие минимальные суммарные затраты. При этом каждого кандидата можно назначать только на одну работу и каждая работа может быть занята только одним кандидатом. Постановка задачи и выбор оптимизации
xij=1, если Ai → Bj; в противном случае xij=0 Т.к. каждый кран можно распределить только на один объект и на каждом объекте может работать только один кран, то введенные переменные xij должны подчиняться двум условиям (ограничениям). 
Критерий оптимизации (целевая функция):
Для решения задачи о назначении существует несколько методов, наиболее известный - «венгерский». Принцип метода (основная идея метода): оптимальность решения задачи о назначении не нарушается при уменьшении (увеличении) элементов строки (столбца) на одну и ту же величину di (dj). Решения считается оптимальным, если измененные искусственно затраты cij*≥0 и можно отыскать такой набор переменных xij, что:
|
