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

		Экономическая теория
		Решение задачи
		18 февраля 2021
		Выполнен, номер заказа №17599
		Прошла проверку преподавателем МГУ
		245 руб.

Выберем в каждой строке матрицы минимальный элемент и подчеркнем его. Разделим множество всех столбцов матрицы на два подмножества А и А. А назовем «множеством выбранных столбцов», А«невыбранных». В самом начале итерации множество А всегда пустое, Асодержит в нашем случае все 7 столбцов: 

Шаг1. Выберем из А/ столбец, содержащий наибольшее количество подчеркнутых элементов, и переведем его в А. Это столбец 6. Шаг2. Справа от матрицы напротив строк выпишем все подчеркнутые элементы множества А, которое содержит в данном случае 6-й столбец. Такой элемент есть у 3-й, 4-й, 7-й строки. Слева от матрицы только для тех строк, в которых есть подчеркнутые элементы из А, запишем разности: минимальный элемент множества А/ для строки минус подчеркнутый элемент из множества А той же строки. Затем найдем минимальное значение этих разностей. Шаг3. Здесь выделяем столбец из А и ячейку с минимальной разностью, равной 0. Шаг4. Добавим полученную минимальную разность «0» ко всем элементам 6-го столбца (выделенного А). Все подчеркивания в таблице сохраняем. Шаг 5. В новой таблице тот элемент из из которого мы вычитали b3 и получили минимальную разность, отметим 3-мя точками внизу. Столбец, содержащий элемент с тремя точками, обозначим С. Так как в столбце С (в пятом столбце) есть еще подчеркнутый элемент «4», то удаляем три точки, переводим столбец С в множество А (т.е. выделяем его) и возвращаемся к шагу 4 Так как в столбце С (во втором столбце) есть еще подчеркнутый элемент «», то удаляем три точки, переводим столбец С в множество А (т.е. выделяем его) и возвращаемся к шагу 4 Добавим полученную минимальную разность «1» ко всем элементам 2-го, 5- го, 6-го столбца. Выбираем столбец 7, элемент 2 подчеркиваем тремя точками: Шаг6. Столбец №7, содержащий элемент с тремя точками, обозначим С. Столбец С не содержит других подчеркнутых элементов, тогда подчеркнем элемент с тремя точками полностью, уберем при этом другое подчеркивание в одной строке с ним. Шаг7. Видим, не каждый столбец содержит по одному подчеркнутому элементу: в 1-м и 4-м столбцах их нет, в 3-м и 6-м по 2. Следовательно, мы не нашли оптимум. Возвращаемся к шагу 1 и начинаем новую итерацию. Здесь сначала выделили вновь 6-й столбец как содержащий наибольшее количество подчеркиваний. Добавляем «0» к выделенному столбцу и в новой таблице подчеркиваем «4» в 7-м столбце второй строки тремя точками. Так как в столбце С (в 7-м столбце) есть еще подчеркнутый элемент «2», то удаляем три точки, переводим столбец С в множество А (т.е. выделяем его) и возвращаемся к шагу 4: Добавляем «0» к выделенным столбцам и в новой таблице подчеркиваем «4» в 5-м столбце второй строки тремя точками. Так как в столбце С (в 5-м столбце) есть еще подчеркнутый элемент «5», то удаляем три точки, переводим столбец С в множество А и возвращаемся к шагу 4: Добавляем «0» к выделенным столбцам и в новой таблице подчеркиваем «5» во 2-м столбце второй строки тремя точками. Так как в столбце С есть еще подчеркнутый элемент «3», то удаляем три точки, переводим столбец С в множество возвращаемся к шагу 4: Добавляем «0» к выделенным столбцам и в новой таблице подчеркиваем «5» в 3-м столбце второй строки тремя точками. Так как в столбце С есть еще подчеркнутый элемент «4», то удаляем три точки, переводим столбец С в множество возвращаемся к шагу 4: Увеличиваем все выделенные столбцы на 1 и 4 в четвертой строке и четвертом столбце подчеркиваем тремя точками: Подчеркиваем «4» полностью, удаляем подчеркивание «4» в 5-м столбце. Теперь только в 1-м столбце нет подчеркнутого элемента. Считаем А пустым и начинаем новую итерацию: Увеличиваем выделенный столбец на 1 и 6 в пятой строке и первом столбце подчеркиваем тремя точками: Подчеркиваем «6» полностью, удаляем подчеркивание «6» в 3-м столбце и получаем оптимальное решение: Запишем ответ к решенной задаче. Для этого на исходную матрицу наносим в соответствующих местах подчеркивания оптимального расположения элементов: Сложим все подчеркнутые элементы: Т(минимальное время выполнения всех заданий) = 3+4+3+4+6+2+2 = 24