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

В задачах данного раздела найти решение задачи по критерию стоимости любым из известных методов.

Исходная матрица имеет вид:

8

6

0

8

4

3

4

0

7

8

2

2

2

9

9

3

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

1

3

9

1

5

6

5

9

2

1

7

7

7

0

0

6

Далее решаем с помощью калькулятора.

Шаг №1.

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

0

2

8

0

1

0

1

0

4

5

1

0

6

6

1

7

0

0

6

0

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

0

2

8

0

0

1

0

4

1

0

6

6

7

0

0

6

0

0

0

0


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

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

[0]

2

8

[-0-]

[-0-]

1

[0]

4

1

0

6

6

7

0

[-0-]

6


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

[0]

2

8

[-0-]

[-0-]

1

[0]

4

1

[0]

6

6

7

[-0-]

[-0-]

6

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

[-0-]

2

8

[0]

[0]

1

[-0-]

4

1

0

6

6

7

0

0

6


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

[-0-]

2

8

[0]

[0]

1

[-0-]

4

1

[0]

6

6

7

[-0-]

0

6


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

[-0-]

2

8

[0]

[0]

1

[-0-]

4

1

[0]

6

6

7

[-0-]

[0]

6


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

[-0-]

2

8

[0]

[0]

1

[-0-]

4

1

[0]

6

6

7

[-0-]

[0]

6


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

0

2

8

0

0

1

0

4

1

0

6

6

7

0

0

6


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

[-0-]

2

8

[0]

[0]

1

[-0-]

4

1

[0]

6

6

7

[-0-]

[0]

6


Cmax = 8 + 4 + 8 + 9 = 29

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

загрузка...