08:13 Задача о назначениях | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
2. Найти значения, минимизирующие целевую функцию для следующей матрицы
Решение проводим с помощью сервиса Задача о назначениях Шаг №1. 1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
После вычитания минимальных элементов получаем полностью редуцированную матрицу. 2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость. Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем. Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем. Фиксируем нулевое значение в клетке (4, 4). Другие нули в строке 4 и столбце 4 вычеркиваем. В итоге получаем следующую матрицу:
Количество найденных нулей равно k = 4. В результате получаем эквивалентную матрицу Сэ:
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить минимальную стоимость назначения.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Всего комментариев: 0 | |