КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Этап второй
|
|
|
|
Этап 2 следует за первым этапом, если для какой-то строки 
. Этап 2 заключается в построении цепочки в матрице 
и построении матрицы 
.
1. В матрице строится цепочка, первый элемент которой 
, расположенный в строке, для которой . Второй элемент - 
, расположенный в том же столбце, что и . Третий элемент -, расположенный в той же строке, что и и т.д. Последний элемент цепочки всегда .
2. После того, как построена цепочка, определяется элемент 
: 
, 
, для всех 
, входящих в цепочку. Элемент - это минимальный элемент среди совокупности невязки по строке, где начинается цепочка, невязки по столбцу, где заканчивается цепочка и элементов матрицы 
, находящихся на тех же позициях, что и , входящие в цепочку в матрице . Здесь строится матрица 
, элементы которой определяются следующим образом:
Далее для 
вычисляется суммарная невязка. Если 
, то конец алгоритма, иначе – следующая итерация.
ЭТАП ТРЕТИЙ
На этом этапе осуществляется переход от матрицы к 
, в которой появляется один или более невыделенных нулей.
1. Среди невыделенных элементов матрицы ищется минимальный: 
.
2. Значение h добавляется ко всем элементам выделенных знаком <+> столбцов и вычитается из всех элементов невыделенных строк матрицы . В результате получаем и переходим к этапу 1.
Лекция 14. Задача назначения.
Постановка задачи назначения: имеется n исполнителей и имеется n работ
Которые необходимо выполнить. Заданы эффективности выполнение каждым из исполнителей каждой работы.
 |
Необходимо распределить исполнителей по работам таким образом, чтобы суммарная эффективность была максимальной. При этом каждый исполнитель исполняет только одну работу. Эта задача относится к классу комбинаторных задач. Общее количество вариантов n!
Математическая постановка:
 |
Введем переменные:
Матрица состоит из 0 и 1.Строки-исполнители, столбцы-работы. В каждой строчке и в каждом столбце будет одна единица.
Критерий суммарной эффективности:
Ограничения:
Каждая работа выполняется
 |  |
одним исполнителем.
Каждый исполнитель выполняет
одну работу.
Эта задача линейного программирования. Будем решать эту задачу венгерским методом.
Определение1: Нулевые элементы матрицы называются независимыми, если в строках и столбцах где они находятся, не содержится других.
|
|
|
|
|
Дата добавления: 2014-01-07; Просмотров: 228; Нарушение авторских прав?; Мы поможем в написании вашей работы!