Распределить машины между постами с максимальным доходом для авто­сервиса.

Решение

Определим максимальный элемент в каждом столбце.

Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.

Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.

В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это вторая строка и второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.

	Ауди	Пежо	ВАЗ
Пост 1
Пост 2
Пост 3

В оставшейся матрице в каждой строке и в каждом столбце остались только нулевые значения. Это означает, что данная задача имеет два варианта решения.

1 вариант.

Выделенные нули определяют оптимальное решение: на посту 1 моются машины Ауди, на втором посту– Пежо, на третьем – ВАЗ.

Суммарный доход 3 + 7 + 8 = 18 у.е.

2 вариант.

Выделенные нули определяют оптимальное решение: на посту 1 моются машины ВАЗ, на втором посту– Пежо, на третьем – Ауди.

Суммарный доход 6 + 7 + 5 = 18 у.е.

Задача 2

Время опоздания трех сотрудников на работу (в минутах) в зависимости от коллективов представлено в таблице. Распределить работников в коллективы таким образом, чтобы суммарное время опозданий было минимальным.

Решение

Определим минимальный элемент в каждом столбце.

Вычтем из элементов столбца минимальный элемент столбца. Определим минимальные элементы по строкам.

Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.

В полученной матрице в каждой строке и в каждом столбце имеется хотя бы один нуль. Найдем строку или столбец, содержащий один нуль. В данной задаче это первая, третья строка и первый, второй столбец. Выберем элемент (2,2) и вычеркнем вторую строку и второй столбец. Элемент (2,2) выделим.

	Сотрудник 1	Сотрудник 2	Сотрудник 3
Коллектив 1
Коллектив 2
Коллектив 3

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

Выделенные нули определяют оптимальное решение: в первом коллективе должен работать первый сотрудник, во втором – второй, в третьем коллективе третий сотрудник.

Суммарное время опоздания: 4 + 2 + 3 = 9 минут.

Задача 3

Производительность (тыс. шт.) работников предприятия на соответствующих работах представлена в виде матрицы.

Распределить работы среди претендентов с максимальной суммарной производительностью для предприятия.

Решение

Определим максимальный элемент в каждом столбце.

Вычтем из максимального элемента другие элементы столбца. Определим минимальные элементы по строкам.

Так как в полученной матрице имеется ненулевая строка, то из элементов строки вычтем соответствующий минимальный элемент.

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

	Работа 1	Работа 2	Работа 3	Работа 4
Работник 1
Работник 2
Работник 3
Работник 4

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

	Работа 1	Работа 2	Работа 3	Работа 4
Работник 1
Работник 2
Работник 3
Работник 4

В оставшейся матрице минимальное значение равно единице. К элементам, лежащим, на пересечении вертикальных и горизонтальных прямых, прибавим минимальное значение, а из невычеркнутых вычтем.

В полученной матрице третья строка и четвертый столбец содержат один нуль. Выберем элемент (4,4) и вычеркнем четвертую строку и четвертый столбец. Элемент (4,4) выделим.

	Работа 1	Работа 2	Работа 3	Работа 4
Работник 1
Работник 2
Работник 3
Работник 4

В оставшейся матрице в третьей строке и втором столбце имеется один нуль. Выберем ячейку (3,3) и вычеркнем третью строку и третий столбец. Элемент (3,3) выделим.

	Работа 1	Работа 2	Работа 3	Работа 4
Работник 1
Работник 2
Работник 3
Работник 4

В полученной матрице первая строка имеет два нулевых значения, вторая только один, поэтому данная задача имеет только одно решение.

Выделенные нули определяют оптимальное решение: первого работника необходимо назначить на вторую работу, второго – на первую, третьего – на третью, четвертого – на четвертую работу.

Суммарная производительность: 7 + 6 + 7 + 8 = 28 тыс. шт.

Не нашли, что искали? Воспользуйтесь поиском: