Задача о назначениях

Введение
1. Формулировка транспортной задачи и задачи о назначениях
1.1. Формирование математической модели задач
1.2. Алгоритм решения транспортной задачи и задачи о назначениях
2. Практическая реализация алгоритма решения задачи о назначениях
Заключение
Список использованной литературы

Задача о назначениях

Таким образом, математическую модель задачи можно записать так:,(1), i = 1,…,m ,(2), j = 1,…, n,(3), i = 1,…,m, j = 1,…,n(4)Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).Задача о назначении в общем виде формулируется так.Пусть имеется n работ и n кандидатов для выполнения этих работ, назначение кандидата на работу связано с затратами .Требуется найти назначения кандидатов на все работы, дающие минимальные суммарные затраты: при этом каждого кандидата можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом.Это типичная экстремальная задача комбинаторного вида, ее решение путем прямого перебора практически невозможно при сколько-нибудь больших , так как число перестановок !1.2. Алгоритм решения транспортной задачи и задачи о назначенияхАлгоритм решения транспортной задачи состоит из четырех этапов:Этап I. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения ресурсов. Допустимым называется такое распределение ресурсов, которое позволяет удовлетворить весь спрос в пунктах назначения и вывести весь запас продуктов из пунктов производства. Этап 2. Проверка полученного распределения ресурсов на оптимальность Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки. Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.Данный итеративный процесс повторяется до тех пор: пока не будет получено оптимальное решение. Т.к. задача о назначениях является частным случаем транспортной задачи, то любая задача о назначениях может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм. получивший название Венгерского метода. Этот алгоритм состоит из трех этапов. Этап 1: 1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи. 2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки. 3. Повторить ту же самую процедуру для столбцов. Теперь в каждой строке и в каждом столбце таблицы есть по крайней мере один нулевой элемент. Представленная в полученной с помощью описанного выше приема “приведенной” транспортной таблице задача о назначениях эквивалентна исходной задаче, и оптимальное решение для обеих задач будет одним и тем же. Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным. Этап 2:Если некоторое решение является допустимым, то каждой строке и каждому столбцу соответствует только один элемент. Если процесс распределения элементов осуществляется только в клетки с нулевой стоимостью, он приведет к получению минимального значения целевой функции. 1. Найти строку, содержащую только одно нулевое значение стоимости. и в клетку, соответствующую данному значению, поместить один элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости. 2. Зачеркнуть оставшиеся нулевые значения данного столбца 3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным. Если на данном этапе окажется. что есть несколько нулей, которым не соответствуют назначения и которые являются незачеркнутыми, то необходимо: 4. Найти столбец, содержащий только одно нулевое значение: и в соответствующую клетку поместить один элемент. 5. Зачеркнуть оставшиеся нули в данной строке. 6. Повторять пункты 4 и 5 до тех пор: пока дальнейшая их реализация окажется невозможной. Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3. Этап 3:1. Провести минимальное число прямых через строки и столбцы матрицы (но не по диагоналям) таким образом, чтобы они проходили через все нули, содержащиеся в таблице. 2. Найти наименьший среди элементов через которые не проходит ни одна из проведенных прямых 3. Вычесть его из всех элементов, через которые не проходят прямые. 4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых 5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения. В результате применения данной процедуры в таблице появляется по крайней мере один новый ноль. Необходимо возвратиться к этапу 2 и повторять алгоритм до тех пор: пока не будет получено оптимальное решение. 2. Практическая реализация алгоритма решения задачи о назначенияхПостановка задачи и выбор критерия: Пусть для монтажа четырех объектов требуется четыре крана . Из отчетных данных известно, какое время необходимо каждому крану для монтажа объекта .Нужно так распределить краны по объектам чтобы суммарное время на монтаж этих объектов было минимально. В нашем случае – затраты времени-го крана при монтаже объектов .Т а б л и ц а 1 – Исходные числовые данныеАiВ1В2В3В4А1375813А2244512А3472812А4973813Вi1111––Примечание: – минимальный элемент строки.Введем переменные Так как каждый кран можно распределить (назначить) только на один объект и на каждом объекте может работать только один кран, то введенные переменные должны подчиняться двум условиям:(2.2)(2.1)Построение математической модели: критерий оптимизации – суммарное время монтажа четырех объектовматематически можно записать:.(2.3)Нужно найти , удовлетворяющие двум вышеприведенным условиям.Исследование математической модели. Для решения задачи о назначении имеется насколько методов.