оспорва решението за назначаване на унгарския метод. Пример.
Цел: Определяне на назначенията на максимум.
няма да даде всякаква вербална състояние, те могат да бъдат различни, като например "На работното място се провеждат 6 кандидати за 6 позиции, а те са получили съответната оценка в интервю за всяко свободно работно място, за извършване на набор от кандидати за шестте позиции, така че цялостната оценка на кандидатите е минимизиран" или "шест машини изпълняват шест творби в рамките на срока, посочен в таблицата, да направи план за производство на ...". Предполагаме, че това е една матрица (кредит, време и т.н.), както и необходимостта да се реши проблема на унгарската метод за определяне на максималната, т.е. избере една клетка в ред и колона, така че сумата от максимум.
решение:
Етап 1:
Забележка: Първата стъпка е необходима само за решаването на проблема на максимума, ако искате да го решим в най-малкото, а след това да го пропуснете.
Transform матрица чрез заместване на всеки елемент на елемент матрица на максималната разлика и ред на елемента.
Вие искате да получите нулите на всеки ред и всяка колона. В третата, петата и шестата колони от нули не се изважда от елементите на тези колони минимален елемент на съответната колона.
Ние получи матрица, в която всеки ред и всяка колона е нула. Нашата цел е да се отбележи, от една клетка във всеки ред и всяка колона, така че те са нула. В тази матрица, само първите четири реда и колоната, отговарят на това изискване. Забележка съответната клетка рамка.
Имайте предвид, като "недоволен линия», петия, в която ние имаме нула марка се провали, а във втората колона, тя се състои от нула в петия ред. Но втората колона съдържа също и нула в първия ред, а трябва да се отбележи като "недоволен". Първият низ от нули вече не се съдържа, т.е. процес отбележат линиите на недоволни свърши, и ние имаме ситуация, наречена "фактор".
В таблицата ще чества недоволни редове и колони със звездички, а числото до звездичката означим поръчката ще означава (за по-добро разбиране на процеса).
Ние избираме минималния елемент на маркираните линии е маркирана с линии. Този 3 стоящи в петата колона и петата колона.
Изваждане този елемент на избрани редове и колони в получения добавят.
Извършване на действие, имайте предвид, че сега е възможно да се отбележи, нула в петия ред и петата колона.
Не е достатъчно дори нула във втория ред. Трябва да отбележим, че както недоволни, тя има нула в първата колона, трябва да се отбележи колко недоволен, той от своя страна съдържа нула във втория ред, трябва да се отбележи, но тя не съдържа повече нули, маркирайте законен процес.
Ние избираме минималния елемент на маркираните линии е белязана от колони. Този елемент 2 в шестия ред и шестата колона. Deuce изважда от втория и шестия изтичане, и се добавя към първата колона.
Следвайте стъпките. Имайте предвид, че сега можете да се отбележи още един нула.
Получени матрица с шест нули, един във всеки ред и колона, следователно, е възможно да се проведе дестинацията (разпределението на работа и т.н.) от матрицата:
А цената (рационалност, работно време и т.н.), като назначаване ще бъде:
Свързани статии