Решение задачи о назначениях

Задание. Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей cij. Решить задачу методом потенциалов и венгерским методом.

Решение венгерским методом.
Исходная матрица имеет вид:

3

14

5

6

7

1

9

7

4

3

8

7

4

6

3

5

6

9

13

15

19

14

16

8

12

Решение находим с помощью сервиса Задача о назначениях.
Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

0

11

2

3

4

3

0

8

6

3

2

1

5

4

1

3

0

3

0

1

4

8

10

5

11

6

8

0

4

8


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

0

10

1

3

4

0

7

5

3

2

5

3

0

3

0

0

0

3

8

10

11

5

7

0

4

0

1

1

0

0


После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (4; 1)
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

0

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (4; 1)
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-]

10

1

3

4

[0]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

0

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]

10

1

3

4

[0]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 4 (должно быть 5).

[-0-]

10

1

3

4

[0]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 5).
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

0

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 5 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 3).
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[-0-]

3

[0]

[-0-]

0

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[-0-]

3

[0]

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[-0-]

3

[0]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 1 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (2; 1), (4; 2).
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[0]

[-0-]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[0]

[-0-]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 1).
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

0

3

0

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

0

4


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 4 и столбце 5 вычеркиваем.
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

0

3

0

[-0-]

0

3

8

10

11

5

7

[0]

4


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

0

3

8

10

11

5

7

[0]

4


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


В итоге получаем следующую матрицу:

[0]

10

1

3

4

[-0-]

7

5

3

2

5

3

[0]

3

[-0-]

[-0-]

[0]

3

8

10

11

5

7

[0]

4


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

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

0

10

1

3

4

0

7

5

3

2

5

3

0

3

0

0

0

3

8

10

11

5

7

0

4


Минимальный элемент сокращенной матрицы (min(10, 1, 4, 7, 5, 2, 5, 7, 4) = 1) вычитаем из всех ее элементов:

0

9

0

3

3

0

6

4

3

1

5

3

0

3

0

0

0

3

8

10

11

4

6

0

3


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

0

9

0

3

3

0

6

4

3

1

6

3

0

4

0

1

0

3

9

10

11

4

6

0

3

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

0

9

0

3

3

0

0

6

4

3

1

0

6

3

0

4

0

0

1

0

3

9

10

0

11

4

6

0

3

0


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

0

9

0

3

3

0

6

4

3

1

6

3

0

4

0

1

0

3

9

10

11

4

6

0

3

0

0

0

0

0


После вычитания минимальных элементов получаем полностью редуцированную матрицу.

2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (1; 3).
В данной таблице количество нулей равно 2 (должно быть 5).

[0]

9

[-0-]

3

3

[-0-]

6

4

3

1

6

3

[0]

4

[-0-]

1

0

3

9

10

11

4

6

0

3


В данной таблице количество нулей равно 3 (должно быть 5).

[0]

9

[-0-]

3

3

[-0-]

6

4

3

1

6

3

[0]

4

[-0-]

1

[0]

3

9

10

11

4

6

0

3


В данной таблице количество нулей равно 4 (должно быть 5).

[0]

9

[-0-]

3

3

[-0-]

6

4

3

1

6

3

[0]

4

[-0-]

1

[0]

3

9

10

11

4

6

[0]

3


Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 3 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 3), (1; 1).
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

0

1

0

3

9

10

11

4

6

0

3


В данной таблице количество нулей равно 3 (должно быть 5).

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

[0]

1

0

3

9

10

11

4

6

0

3


В данной таблице количество нулей равно 4 (должно быть 5).

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

[0]

1

[0]

3

9

10

11

4

6

0

3


В данной таблице количество нулей равно 5 (должно быть 5).

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

[0]

1

[0]

3

9

10

11

4

6

[0]

3


В итоге получаем следующую матрицу:

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

[0]

1

[0]

3

9

10

11

4

6

[0]

3


Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

0

9

0

3

3

0

6

4

3

1

6

3

0

4

0

1

0

3

9

10

11

4

6

0

3

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

[-0-]

9

[0]

3

3

[0]

6

4

3

1

6

3

[-0-]

4

[0]

1

[0]

3

9

10

11

4

6

[0]

3


Cmin = 5 + 1 + 3 + 6 + 8 = 23

Задача назначения

Пример. Дано m = 5 видов машин и m = 5 видов работ с трудоемкостью aij (маш./ч), представленной в табл. 14.15. Закрепить работы за машинами таким образом, чтобы суммарная трудоемкость работ была бы наименьшей.
Решение. Исходная матрица имеет вид:

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

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

0 1 3 0 2 4
0 0 3 3 3 6
4 0 2 4 6 2
4 0 3 6 4 3
0 3 4 1 5 2

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

0 1 1 0 0
0 0 1 3 1
4 0 0 4 4
4 0 1 6 2
0 3 2 1 3
0 0 2 0 2

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 1), (5; 1), (1; 4), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [0] 1 3 1
4 [-0-] 0 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [0] 1 3 1
4 [-0-] [0] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 4 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[0] [-0-] 1 3 1
4 0 0 4 4
4 0 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[0] [-0-] 1 3 1
4 [0] [-0-] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 5 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (1; 4).
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-] 1 1 [-0-] [0]
[0] [-0-] 1 3 1
4 0 0 4 4
4 0 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-] 1 1 [-0-] [0]
[0] [-0-] 1 3 1
4 [0] [-0-] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 1 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (5; 1), (2; 2).
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[0] [-0-] 1 3 1
4 0 0 4 4
4 0 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[0] [-0-] 1 3 1
4 [0] [-0-] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 2), (4; 2), (2; 1).
В данной таблице количество нулей равно 2 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [0] 1 3 1
4 [-0-] 0 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [0] 1 3 1
4 [-0-] [0] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 2 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (4; 2), (3; 3).
В данной таблице количество нулей равно 2 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [-0-] 1 3 1
4 [0] [-0-] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (3, 3). Другие нули в строке 3 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (3; 2).
В данной таблице количество нулей равно 2 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] 0 1 3 1
4 [-0-] [0] 4 4
4 0 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [0] 1 3 1
4 [-0-] [0] 4 4
4 [-0-] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (4, 2). Другие нули в строке 2 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 2), (3; 2)
В данной таблице количество нулей равно 2 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [-0-] 1 3 1
4 [-0-] 0 4 4
4 [0] 1 6 2
[-0-] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[0] 1 1 [-0-] [-0-]
[-0-] [-0-] 1 3 1
4 [-0-] [0] 4 4
4 [0] 1 6 2
[-0-] 3 2 1 3

Фиксируем нулевое значение в клетке (5, 1). Другие нули в строке 1 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (1; 1), (2; 1)
В данной таблице количество нулей равно 2 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[-0-] 0 1 3 1
4 0 0 4 4
4 0 1 6 2
[0] 3 2 1 3

В данной таблице количество нулей равно 3 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[-0-] [0] 1 3 1
4 [-0-] 0 4 4
4 [-0-] 1 6 2
[0] 3 2 1 3

В данной таблице количество нулей равно 4 (должно быть 5).

[-0-] 1 1 [0] [-0-]
[-0-] [0] 1 3 1
4 [-0-] [0] 4 4
4 [-0-] 1 6 2
[0] 3 2 1 3

В итоге получаем следующую матрицу:

[-0-] 1 1 [0] [-0-]
[-0-] [0] 1 3 1
4 [-0-] [0] 4 4
4 [-0-] 1 6 2
[0] 3 2 1 3

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

0 1 1 0 0
0 0 1 3 1
4 0 0 4 4
4 0 1 6 2
0 3 2 1 3

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

0 1 1 0 0
0 0 1 3 1
4 0 0 4 4
4 0 0 5 1
0 3 1 0 2

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

1 2 1 0 0
1 1 1 3 1
5 1 0 4 4
4 0 0 5 1
0 3 1 0 2

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

1 2 1 0 0 0
0 0 0 2 0 1
5 1 0 4 4 0
4 0 0 5 1 0
0 3 1 0 2 0

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

1 2 1 0 0
0 0 0 2 0
5 1 0 4 4
4 0 0 5 1
0 3 1 0 2
0 0 0 0 0

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 4). Другие нули в строке 4 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (5; 4), (1; 5).
В данной таблице количество нулей равно 2 (должно быть 5).

1 2 1 [0] [-0-]
[0] [-0-] [-0-] 2 [-0-]
5 1 0 4 4
4 0 0 5 1
[-0-] 3 1 [-0-] 2

В данной таблице количество нулей равно 3 (должно быть 5).

1 2 1 [0] [-0-]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 0 [-0-] 5 1
[-0-] 3 1 [-0-] 2

В данной таблице количество нулей равно 4 (должно быть 5).

1 2 1 [0] [-0-]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[-0-] 3 1 [-0-] 2

Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 5 и столбце 1 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (2; 5), (1; 4).
В данной таблице количество нулей равно 2 (должно быть 5).

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 0 4 4
4 0 0 5 1
[-0-] 3 1 0 2

В данной таблице количество нулей равно 3 (должно быть 5).

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 0 [-0-] 5 1
[-0-] 3 1 0 2

В данной таблице количество нулей равно 4 (должно быть 5).

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[-0-] 3 1 0 2

В данной таблице количество нулей равно 5 (должно быть 5).

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[-0-] 3 1 [0] 2

В итоге получаем следующую матрицу:

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[-0-] 3 1 [0] 2

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

1 2 1 0 0
0 0 0 2 0
5 1 0 4 4
4 0 0 5 1
0 3 1 0 2

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

1 2 1 [-0-] [0]
[0] [-0-] [-0-] 2 [-0-]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[-0-] 3 1 [0] 2

Cmin = 6 + 6 + 4 + 3 + 3 = 22
Альтернативный вариант №2.

1 2 1 [0] [-0-]
[-0-] [-0-] [-0-] 2 [0]
5 1 [0] 4 4
4 [0] [-0-] 5 1
[0] 3 1 [-0-] 2

Cmin = 9 + 4 + 4 + 3 + 2 = 22
Скачать решение:xml:xls

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

загрузка...