ZAD804 (Лабораторные работы)
Описание файла
Файл "ZAD804" внутри архива находится в папке "Лабораторные работы". Документ из архива "Лабораторные работы", который расположен в категории "". Всё это находится в предмете "военная кафедра" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "ZAD804"
Текст из документа "ZAD804"
ЗАДАЧА 804
Постановка задачи.
Найти хij = {0,1},
максимизирующие функцию
при
Алгоритм решения
Задана матрица Р, состоящая из n строк и m столбцов.
-
В каждом столбце матрицы выбирается максимальный элемент, именуемый основой. Строка, содержащая основу, называется занятой.
-
Если в m строках есть основа, то набор оптимален: решение найдено.
-
Отмечается любая строка, содержащая более одной основы.
-
Элементы всех отмеченных строк делятся на минимальное отношение какой-либо основы отмеченных строк к элементу в данном столбце, но в неотмеченных строках. Такая строка (где найден элемент) отмечается, элемент именуется основой, а бывшая основа – обычным элементом.
-
Если последняя сформированная основа содержится в занятой строке, то осуществляется переход к пункту 4), иначе все строки считаются неотмеченными и осуществляется переход к пункту 2).
Пример для отладки
n=5; m=4;
Пример для счета: n=9; m=7;
Результаты счета:
Выдать на печать xij оптимального набора (i и j), значение Z.