{"id":1319,"date":"2016-02-02T17:26:34","date_gmt":"2016-02-02T16:26:34","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1319"},"modified":"2022-12-03T22:58:51","modified_gmt":"2022-12-03T21:58:51","slug":"algorithme-hongrois","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/","title":{"rendered":"Algoritmo h\u00fangaro"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1319\" class=\"elementor elementor-1319\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c0343d1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c0343d1\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-000d4ba\" data-id=\"000d4ba\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5ff45da elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5ff45da\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\"> Problema de planificaci\u00f3n<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-884f774\" data-id=\"884f774\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-73ada20 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"73ada20\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/es\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Pagina de inicio<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-b4f726e\" data-id=\"b4f726e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-4750b98 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"4750b98\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_hongrois\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-efffc50 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"efffc50\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-72724cc2\" data-id=\"72724cc2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5efa6b99 elementor-widget elementor-widget-text-editor\" data-id=\"5efa6b99\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenido<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/#Algorithme-hongrois\" >Algoritmo h\u00fangaro<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/#Etape-1-algorithme-hongrois-reduction-du-tableau-initial\" >Paso 1 algoritmo h\u00fangaro: reducci\u00f3n de la tabla inicial<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/#Etape-2-algorithme-hongrois-rechercher-une-solution-realisable\" >Algoritmo h\u00fangaro, paso 2: encuentre una soluci\u00f3n viable<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/#Etape-3-algorithme-hongrois-creation-des-pivots\" >Paso 3 algoritmo h\u00fangaro: creaci\u00f3n de los pivotes<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-planificacion\/algoritmo-hungaro\/#Etape-4-algorithme-hongrois-modification-du-tableau\" >Paso 4 algoritmo h\u00fangaro: modificaci\u00f3n de la tabla<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-hongrois\"><\/span>Algoritmo h\u00fangaro<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Tambi\u00e9n llamado <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> de K\u00fchn, el algoritmo h\u00fangaro o m\u00e9todo h\u00fangaro resuelve problemas de asignaci\u00f3n del tipo tabla de costes. Considere un n\u00famero de m\u00e1quinas y tantas tareas. Cada m\u00e1quina realiza una tarea a un costo determinado. El objetivo es determinar la m\u00e1quina en la que se ejecutar\u00e1 cada tarea, en paralelo.<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Siendo este problema similar a un problema de acoplamiento en un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a>, cumple el criterio de K\u00f6nig de cobertura nodal de peso m\u00ednimo. Por lo tanto, el objetivo es encontrar un elemento por fila y columna en la tabla de modo que la suma de los costos sea m\u00ednima. Si partimos de un problema de maximizaci\u00f3n, ser\u00e1 necesario invertir los costes para volver a un problema de <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/\">minimizaci\u00f3n<\/a>.<\/div>\n\n<p>Tomemos un ejemplo simple para mostrar el proceso del algoritmo. Deje que 5 m\u00e1quinas (fila) y 5 tareas (columna) den la siguiente tabla de costos:<\/p>\n\n<div class=\"standard\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-1-algorithme-hongrois-reduction-du-tableau-initial\"><\/span>Paso 1 algoritmo h\u00fangaro: reducci\u00f3n de la tabla inicial<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Restamos de cada l\u00ednea el elemento m\u00e1s peque\u00f1o de la l\u00ednea. Cuanto m\u00e1s restamos de cada columna, menor es el elemento de la columna.<\/div>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Esta estandarizaci\u00f3n de los costos de las m\u00e1quinas y las tareas hace posible tener al menos un cero por fila y por columna.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-2-algorithme-hongrois-rechercher-une-solution-realisable\"><\/span>Algoritmo h\u00fangaro, paso 2: encuentre una soluci\u00f3n viable<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Buscamos la l\u00ednea con la menor cantidad de ceros no cruzados. En caso de empate, tomaremos la l\u00ednea m\u00e1s alta.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Rodeamos uno de los ceros de esta l\u00ednea (arbitrariamente el que est\u00e1 m\u00e1s a la izquierda).<\/li>\n<li>Todos los ceros de la misma fila y columna que la seleccionada est\u00e1n tachados.<\/li>\n<li>Comenzamos de nuevo hasta que todos los ceros est\u00e9n encasillados o tachados.<\/li>\n<\/ol>\n<\/div>\n\n<p>Si hemos enmarcado un cero por fila y por columna, tenemos una soluci\u00f3n \u00f3ptima. De lo contrario, vamos al paso 3.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">13<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-3-algorithme-hongrois-creation-des-pivots\"><\/span>Paso 3 algoritmo h\u00fangaro: creaci\u00f3n de los pivotes<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>La subtabla permite por sustracci\u00f3n tener una configuraci\u00f3n que permita encontrar una soluci\u00f3n \u00f3ptima. La construcci\u00f3n de los pivotes se realiza de la siguiente manera:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Marcamos cualquier l\u00ednea que no contenga ning\u00fan cero enmarcado.<\/li>\n<li>Cualquier columna con un cero tachado se marca en una fila marcada.<\/li>\n<li>Marcamos cualquier fila que tenga un cero enmarcado en una columna marcada.<\/li>\n<li>Repita 2 y 3 hasta que no haya m\u00e1s cambios.<\/li>\n<\/ol>\n<\/div>\n\n<p>Luego se dibuja una l\u00ednea en cualquier l\u00ednea no marcada y en cualquier columna marcada. En nuestro ejemplo, las filas 1 y 2 est\u00e1n marcadas, as\u00ed como la columna 4. Los elementos marcados con doble marca est\u00e1n marcados con una estrella.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>5<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-7-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-6-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #000000;\">-0-<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-3-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-10-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-13-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">-5-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-0-<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">*-4-*<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">-9-<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-4-algorithme-hongrois-modification-du-tableau\"><\/span>Paso 4 algoritmo h\u00fangaro: modificaci\u00f3n de la tabla<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Las celdas no cruzadas por una l\u00ednea constituyen una tabla parcial.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<ol>\n<li>Restamos de todas las casillas de esta tabla el elemento m\u00e1s peque\u00f1o de la misma.<\/li>\n<li>Este elemento se suma a todas las casillas de la tabla tachadas en ambas direcciones (acompa\u00f1adas de una estrella).<\/li>\n<\/ol>\n<\/div>\n\n<p>Los pasos 2 a 4 se repiten hasta que se obtiene un resultado \u00f3ptimo. En nuestro ejemplo, obtenemos un resultado \u00f3ptimo despu\u00e9s de la primera iteraci\u00f3n.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td>1<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\"><span style=\"color: #ff0000;\">0<\/span><\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td>\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>La asignaci\u00f3n m\u00ednima se calcula a partir de la tabla inicial: 9 + 5 + 5 + 4 + 9 = 32.<\/p>\n<p>La siguiente figura muestra los cambios en el gr\u00e1fico bipartito con el algoritmo h\u00fangaro.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-9818 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1.png\" alt=\"Algoritmo h\u00fangaro Algoritmo de K\u00fchn Problemas de asignaci\u00f3n de m\u00e9todos h\u00fangaros Criterio de K\u00f6nig\" width=\"874\" height=\"746\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1.png 874w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1-300x256.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/16-Figure7-1-768x656.png 768w\" sizes=\"(max-width: 874px) 100vw, 874px\" \/><\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Problema de programaci\u00f3n P\u00e1gina de inicio Wiki Algoritmo h\u00fangaro Tambi\u00e9n llamado algoritmo de K\u00fchn, el algoritmo h\u00fangaro o m\u00e9todo h\u00fangaro resuelve problemas de asignaci\u00f3n tipo tabla... <\/p>","protected":false},"author":1,"featured_media":0,"parent":868,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1319","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1319","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=1319"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1319\/revisions"}],"predecessor-version":[{"id":17917,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1319\/revisions\/17917"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/868"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=1319"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}