Составить математическую модель и найти оптимальный план назначений в задаче о назначениях

Перепишем условие задачи в виде матрицы тарифов:
3 7 5
2 4 4
4 7 2
Математическая модель задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = n, i = 1,2,…, m, (2)
∑xij = m, j = 1,2,…, n, (3)
xij ≥ 0, целые
Запишем экономико-математическую модель для нашей задачи. Переменные xij принимают значения 1, если i-й кандидат занимает j-ю вакансию. Если данное условие не выполняется, то xij=0.
Ограничения по кандидатам:
x11 + x12 + x13 = 1
x21 + x22 + x23 = 1
x31 + x32 + x33 = 1
Ограничения по вакансиям:
x11 + x21 + x31 = 1
x12 + x22 + x32 = 1
x13 + x23 + x33 = 1
Целевая функция:
3x11 + 7x12 + 5x13 + 2x21 + 4x22 + 4x23 + 4x31 + 7x32 + 2x33 → min
Шаг №1 .
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0 4 2 3
0 2 2 2
2 5 0 2
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
0 2 2
0 0 2
2 3 0
0 2 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу