ZAD802 (Лабораторные работы)
Описание файла
Файл "ZAD802" внутри архива находится в папке "Лабораторные работы". Документ из архива "Лабораторные работы", который расположен в категории "". Всё это находится в предмете "военная кафедра" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "ZAD802"
Текст из документа "ZAD802"
Задача 802.
Применение метода линейного программирования для решения задачи о назначении.
Постановка задачи
Найти числа = 0 или 1, максимизирующие функцию :
при ограничениях :
( j = 1, ..., m );
Последовательность вычислений :
-
Если n > m, то производится транспонирование матрицы P ( n - число строк, m - число столбцов ).
-
При решении задачи используется Бредфордский метод, который состоит в следующем. В каждой строке матрицы выбирается максимальный элемент, именуемый «основной». Столбец, содержащий основу, называется занятым.
-
Если в n столбцах из m есть основа, то набор оптимален, печатается ответ, иначе переходим к п.4.
-
Отмечается любой столбец, занятый более, чем одной основой.
-
Все элементы всех отмеченных столбцов (сначала - один столбец ) уменьшаются на минимальную величину, необходимую, чтобы какая-то из основ этого столбца стала равной хотя бы одному элементу в данной строке, но принадлежащему неотмеченному столбцу. Теперь этот столбец отмечается, элемент именуется «основой», а бывшая основа - обычным элементом.
-
Если последняя сформированная основа находится в занятом столбце, то осуществляется переход к пункту 5, иначе все столбцы считаются неотмеченными и осуществляется переход к пункту 3.
Пример
( m = 5, n = 7 )
Исходные данные
n = m = 10