- •1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
- •2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
- •3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
- •1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
- •2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
- •3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
- •1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
- •2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
- •4. Методом проб и ошибок определяем матрицу назначения х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
Получаем сокращенную матрицу (элементы выделены):
8 |
0 |
0 |
4 |
1 |
2 |
0 |
4 |
0 |
2 |
8 |
1 |
4 |
2 |
6 |
4 |
4 |
7 |
1 |
0 |
0 |
1 |
6 |
1 |
4 |
2 |
5 |
1 |
3 |
1 |
6 |
0 |
3 |
2 |
5 |
4 |
0 |
5 |
2 |
0 |
7 |
4 |
0 |
2 |
2 |
4 |
0 |
6 |
5 |
1 |
4 |
0 |
4 |
1 |
2 |
6 |
3 |
6 |
4 |
3 |
5 |
0 |
4 |
3 |
Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
9 |
0 |
0 |
5 |
2 |
3 |
0 |
4 |
0 |
1 |
7 |
1 |
4 |
2 |
5 |
3 |
4 |
6 |
0 |
0 |
0 |
1 |
5 |
0 |
5 |
2 |
5 |
2 |
4 |
2 |
6 |
0 |
4 |
2 |
5 |
5 |
1 |
6 |
2 |
0 |
8 |
4 |
0 |
3 |
3 |
5 |
0 |
6 |
5 |
0 |
3 |
0 |
4 |
1 |
1 |
5 |
3 |
5 |
3 |
3 |
5 |
0 |
3 |
2 |
Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
9 |
0 |
0 |
5 |
2 |
3 |
0 |
4 |
0 |
0 |
1 |
7 |
1 |
4 |
2 |
5 |
3 |
0 |
4 |
6 |
0 |
0 |
0 |
1 |
5 |
0 |
0 |
5 |
2 |
5 |
2 |
4 |
2 |
6 |
0 |
0 |
4 |
2 |
5 |
5 |
1 |
6 |
2 |
0 |
0 |
8 |
4 |
0 |
3 |
3 |
5 |
0 |
6 |
0 |
5 |
0 |
3 |
0 |
4 |
1 |
1 |
5 |
0 |
3 |
5 |
3 |
3 |
5 |
0 |
3 |
2 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
9 |
0 |
0 |
5 |
2 |
3 |
0 |
4 |
0 |
1 |
7 |
1 |
4 |
2 |
5 |
3 |
4 |
6 |
0 |
0 |
0 |
1 |
5 |
0 |
5 |
2 |
5 |
2 |
4 |
2 |
6 |
0 |
4 |
2 |
5 |
5 |
1 |
6 |
2 |
0 |
8 |
4 |
0 |
3 |
3 |
5 |
0 |
6 |
5 |
0 |
3 |
0 |
4 |
1 |
1 |
5 |
3 |
5 |
3 |
3 |
5 |
0 |
3 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.