Задача о назначениях. Нахождение максимальной прибыли

Типичное задание:
Компании нужно направить коммивояжеров в новые рынки сбыта. Имеется три вакансии и четыре кандидата. Результат назначения кандидата на определенное место определяется ожидаемым увеличением прибыли. Прибыль, которую может дать кандидат, работая на той или иной территории, показана в таблице.
Исходная матрица имеет вид:

5 5 M 2 2
7 4 2 3 1
9 3 5 M 2
7 2 6 7 8

Решение получаем через калькулятор.
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (9) так, чтобы матрица не содержала бы отрицательных элементов:

4 4 M 7 7
2 5 7 6 8
0 6 4 M 7
2 7 3 2 1

Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
0 0 M 3 3 4
0 3 5 4 6 2
0 6 4 M 7 0
1 6 2 1 0 1
0 0 0 0 0 0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
0 0 M 3 3
0 3 5 4 6
0 6 4 M 7
1 6 2 1 0
0 0 0 0 0
0 0 0 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

[0]

[-0-]

M

3

3

[-0-]

3

5

4

6

[-0-]

6

4

M

7

1

6

2

1

[-0-]

[-0-]

[-0-]

[-0-]

[-0-]

[0]

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое .
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 1, строку 1, столбец 5.
Получаем сокращенную матрицу (элементы выделены):

0

0

M

3

3

0

3

5

4

6

0

6

4

M

7

1

6

2

1

0

0

0

0

0

0

Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:

0

0

M

3

3

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

0

0

0

0

0

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

1

0

M

3

4

0

0

2

4

3

6

0

0

5

3

M

7

0

1

5

1

0

0

0

1

0

0

0

1

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

1

[0]

M

3

4

[0]

2

4

3

6

[-0-]

5

3

M

7

1

5

1

[-0-]

[0]

1

[-0-]

[-0-]

[0]

1

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 4), то решение недопустимое .
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 1, строку 4, столбец 2.
Получаем сокращенную матрицу (элементы выделены):

1

0

M

3

4

0

2

4

3

6

0

5

3

M

7

1

5

1

0

0

1

0

0

0

1

Минимальный элемент сокращенной матрицы (3) вычитаем из всех ее элементов:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

1

5

1

0

0

1

0

0

0

1

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

1

0

M

0

1

0

0

2

1

0

3

0

0

5

0

M

4

0

4

8

1

0

0

0

4

3

0

0

1

0

Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

0

0

0

0

0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

1

[0]

M

[-0-]

1

[-0-]

2

1

[0]

3

[0]

5

[-0-]

M

4

4

8

1

[-0-]

[0]

4

3

[0]

[-0-]

1

В результате получаем эквивалентную матрицу Сэ:

1

0

M

0

1

0

2

1

0

3

0

5

0

M

4

4

8

1

0

0

4

3

0

0

1

4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить максимальное значение прибыли.

1

[0]

M

[-0-]

1

[-0-]

2

1

[0]

3

[0]

5

[-0-]

M

4

4

8

1

[-0-]

[0]

4

3

[0]

[-0-]

1

Cmax = 3 + 5 + 9 + 8 + 0 = 25
Альтернативный вариант №2.

1

[0]

M

[-0-]

1

[0]

2

1

[-0-]

3

[-0-]

5

[0]

M

4

4

8

1

[-0-]

[0]

4

3

[-0-]

[0]

1


 Cmax = 8 + 5 + 7 + 5 + 0 = 25

Перейти к онлайн решению своей задачи

загрузка...