|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Метод решения задачи о назначениях ⇐ ПредыдущаяСтр 7 из 7
В практических задачах часто возникает необходимость так распределить ресурсы между потребителями, чтобы каждому потребителю досталось не более единицы ресурса и суммарный эффект от распределения был бы наибольшим. Рассмотрим пример. Пример В распоряжении менеджера проекта имеется пять разнотипных различных исполнителей. нужно произвести 5 различных работ. Вероятности выполнения i‑ й работы j‑ м исполнителем - Pij, известны. Необходимо на каждую работу назначить одного исполнителя таким образом, чтобы ожидаемое количество выполненных работ было максимальным. Исходные данные для решения задачи отображены в таблице. Приведем формальную постановку задачи. Пусть
Специфический вид ограничений позволяет выделить данную задачу в особый класс задач, называемых задачами о назначениях. Задача о назначении в общем случае описывается следующим образом. Необходимо распределить n исходных объектов на n конечных. Распределение должно быть таким, чтобы каждый исходный объект был назначен на один и только один конечный. На каждый конечный объект должен быть назначен ровно один исходный объект. Назначение i‑ го исходного объекта на j‑ й конечный связано с затратами Отличительной чертой задачи о назначениях является то, что количество продукции в исходном пункте всегда равно ее количеству, требуемому в конечном пункте и равно 1. Поскольку количество исходных и конечных пунктов всегда можно сделать одинаковыми путем добавления фиктивных исходных (конечных) пунктов, то математически задача о назначениях формулируется в виде
где Задача о назначениях не требует специальных методов построения начального опорного плана. Однако методы нахождения оптимального плана этой задачи являются достаточно специфическими. Рассмотрим один из наиболее известных методов решения задачи о назначениях, иногда называемый венгерским методом, решив с его помощью задачу из примера. Поскольку задача, является задачей минимизации, преобразуем целевую функцию примера следующим образом. Введем величины gij такие, что
Оптимальное решение задачи о назначениях не изменится, если из любой строки или столбца матрицы стоимостей
Так как величины
Из доказанного выше утверждения следует, что, если в ходе преобразований исходной матрицы Найдем в каждой строке и столбце таблицы минимальную gij и вычтем ее из всех остальных величин gij данной строки (столбца). Операцию выполним в два этапа. На первом этапе по строкам, и результат занесем в таблицу, на втором этапе по столбцам, используя результаты вычитания по строкам. Получим матрицу. Эта матрица не дает допустимого решения состоящего из нулей, т. е. такого решения, при котором для каждой строки (и столбца) имелся бы один нуль и каждому нулю (из множества входящих в базис) соответствовала бы одна строка и один столбец. В этом случае рассматриваемый метод предлагает провести минимальное число прямых через некоторые столбцы и строки таблицы так, чтобы вычеркнуть все нули. В нашем случае зачеркнутыми оказались 3 столбец, 3 и 4 строки таблицы. Далее выбирается минимальный не вычеркнутый элемент gij (у нас это будет g51=0.01), который вычитается из всех не вычеркнутых элементов и прибавляется к каждому элементу, стоящему на пересечении прямых, т.е. к элементам g33 и g43. В результате получается таблица.
Таблица также не дает допустимого решения состоящего из нулей. Проведем над ней операцию аналогичную той, которая была проведена ранее. Результаты этой операции отражены в таблице, которая содержит допустимое решение, состоящее из нулей. Это решение отмечено в таблице звездочками.
Таким образом, необходимо 1 исполнителя назначить на 5 работу, 2 – на 3-ю, 3 – на 2-ю, 4 – на 1-ю и 5 – на 1-ю. В этом случае математическое ожидание числа невыполненных работ окажется равным 1, 86. Пример.Имеется четыре исполнителей работ и 4 вида работ. В матрице указано время, расходуемое при выполнении
Вычтем минимальные числа из каждой строки. Получим
Так как минимальное назначение не получено (второй, третий и четвертый столбцы). Вычитая из каждого столбца минимальное значение, получим
Ни одно из назначений не получено (должно быть в каждой строке и столбце по одному нулю). Проводим минимальное число прямых через строки и столбцы так, чтобы удалить все нули. Получим
Минимальный элемент матрицы равен 2. Вычеркиваем его из всех невычеркнутых элементов и складываем со значениями элементов, стоящими на пересечении вычеркиваемых строк и столбцов. Получим
Выбираем элементы так, чтобы нулевые элементы были во всех сроках и во всех столбцах. Получим
Суммарное время выполнения работ равно
Популярное:
|
Последнее изменение этой страницы: 2016-07-13; Просмотров: 916; Нарушение авторского права страницы
переменные, такие что 
, если i-е исполнитель назначен на j-ю работу и 
во всех других случаях. Тогда математическое ожидание числа выполненных работ определяется по формуле 
. На величины переменных 
, i =1, …, 5. 
, j =1, …, 5.
. Необходимо найти такой план распределения, который соответствует минимуму суммарных затрат.
, 
, 
, i, j =1, 2, …, n, 
,. Величина gij есть вероятность того, что j‑ я работа после назначения на нее i‑ го исполнителя окажется невыполненной. Тогда целевая функция 
достигает минимума на том же опорном плане, на котором исходная целевая функция достигает максимума. Следовательно, исходная задача равносильна задаче
, i, j = 1, 2, …, 5.
(в данном случае из матрицы 
) вычесть постоянную величину. Действительно пусть 
константы. Тогда: 
с нулевыми элементами, и эти нулевые элементы или их подмножество образуют допустимое решение, то это решение будет оптимальным, так как число непораженных объектов не может быть отрицательным.
1
3
4
1
3
4
5
-м исполнителем 
-й работы. Необходимо минимизировать время.
.
.
.
.
.
