Основні теореми для розв’язання задачі про призначення

Теорема 1: Якщо xij=Xij мінімізує зі всіх xij, таких, що xij³0 і , то xij=Xij мінімізує також функціонал , де при всіх i і j= 1,…,n...

Теорема 2 (Фробеніуса): Мінімальне число ліній, що покривають усі нулі матриці, дорівнює максимальному числу незалежних нулів у ній.

Незалежним нулем будемо називати єдиний вибраний нуль у рядку та стовпці, на перетині яких він знаходиться. Якщо, крім вибраного незалежного нуля, в рядку або стовпці присутні ще нулі, то їх далі необхідно вважати залежними. Незалежний нуль на місці (i, j) є призначенням і – го завдання на виконання j-м ресурсом.

Фактично наведений метод розв`язку зводиться до перетворень рядків і стовпців за допомогою деяких констант доти, поки достатнє число коефіцієнтів Cij не обернеться на нуль, що дасть шуканий результат.