{"id":3910,"date":"2016-08-24T09:21:40","date_gmt":"2016-08-24T08:21:40","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3910"},"modified":"2022-12-03T22:59:07","modified_gmt":"2022-12-03T21:59:07","slug":"algorithme-out-of-kilter","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/algoritmo-fuera-de-lugar\/","title":{"rendered":"Algoritmo fuera de kil\u00f3metro"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3910\" class=\"elementor elementor-3910\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-efb2af4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"efb2af4\" 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-862500c\" data-id=\"862500c\" 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-2411965 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2411965\" 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-flujo-maximo\/\">\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 flujo m\u00e1ximo<\/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-1090814\" data-id=\"1090814\" 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-8ecd9f4 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8ecd9f4\" 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-f7f1f43\" data-id=\"f7f1f43\" 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-bdd8712 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"bdd8712\" 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:\/\/www.rand.org\/content\/dam\/rand\/pubs\/research_memoranda\/2008\/RM5472.pdf\" 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-284489a1 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"284489a1\" 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-58e9a757\" data-id=\"58e9a757\" 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-5667251a elementor-widget elementor-widget-text-editor\" data-id=\"5667251a\" 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-flujo-maximo\/algoritmo-fuera-de-lugar\/#Algorithme-out-of-kilter\" >Algoritmo fuera de lugar<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-out-of-kilter\"><\/span>Algoritmo fuera de lugar<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Tambi\u00e9n llamado <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> de Fulkerson-Ford (que no debe confundirse con el algoritmo de <a href=\"https:\/\/complex-systems-ai.com\/es\/problema-de-flujo-maximo\/\">flujo maximo<\/a>), el algoritmo descentrado calcula un flujo m\u00e1ximo a un costo m\u00ednimo con l\u00edmites m\u00ednimos y m\u00e1ximos en los bordes.<\/p>\n\n<p>Diremos que una arista est\u00e1 In-Kilter si satisface el <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/desviaciones-complementarias\/\">desviaciones adicionales<\/a>, de lo contrario, diremos que est\u00e1 fuera de orden (kilter significa &quot;en buenas condiciones&quot;).<\/p>\n\n<p>Las siguientes explicaciones no se traducir\u00e1n en aras de la comprensi\u00f3n de la l\u00f3gica subyacente en el sentido de &quot;kilter&quot;.<\/p>\n\n<p><b>Teorema: <\/b>Una soluci\u00f3n factible x * es una soluci\u00f3n \u00f3ptima del problema MCF si y solo si para alg\u00fan conjunto de potenciales de nodo \u03c0, los costos reducidos y los valores de flujo satisfacen las siguientes condiciones de holgura complementaria para cada borde (u, v) en el <b>la red<\/b><b>:<\/b><\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-4437\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1.png\" alt=\"algoritmo fuera de lugar\" width=\"417\" height=\"166\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1.png 417w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter1-300x119.png 300w\" sizes=\"(max-width: 417px) 100vw, 417px\" \/><\/figure>\n<\/div>\n\n<p>Lo que da el siguiente diagrama de eficiencia:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4446 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2.png\" alt=\"algoritmo fuera de lugar\" width=\"869\" height=\"356\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2.png 869w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2-300x123.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter2-768x315.png 768w\" sizes=\"(max-width: 869px) 100vw, 869px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4452 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4.png\" alt=\"algoritmo fuera de lugar\" width=\"897\" height=\"386\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4.png 897w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4-300x129.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter4-768x330.png 768w\" sizes=\"(max-width: 897px) 100vw, 897px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4455 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5.png\" alt=\"algoritmo fuera de lugar\" width=\"867\" height=\"397\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5.png 867w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5-300x137.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter5-768x352.png 768w\" sizes=\"(max-width: 867px) 100vw, 867px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-4458 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6.png\" alt=\"algoritmo fuera de lugar\" width=\"840\" height=\"427\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6.png 840w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6-300x153.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/08\/kilter6-768x390.png 768w\" sizes=\"(max-width: 840px) 100vw, 840px\" \/><\/figure>\n<\/div>\n\n<p>Exactitud:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>Los n\u00fameros de kil\u00f3metros de los bordes no aumentan\n<ul>\n<li>Dos operaciones en el algoritmo afectan el n\u00famero total de arcos:\n<ul>\n<li>actualizar los potenciales de los nodos<\/li>\n<li>aumentar el flujo a lo largo del ciclo <i>W<\/i><\/li>\n<\/ul>\n<\/li>\n<li>En cada iteraci\u00f3n, el algoritmo selecciona un borde (p, q)\n<ul>\n<li>Lo vuelve in-kilter durante una posible actualizaci\u00f3n<\/li>\n<li>Disminuirlo en al menos 1 por el aumento de flujo.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n<p>El algoritmo termina dentro de O (mU) iteraciones, el tiempo de ejecuci\u00f3n total es: O (m ^ 2 U + mUn log n)<\/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 flujo m\u00e1ximo P\u00e1gina de inicio Wiki Algoritmo fuera de lo normal Tambi\u00e9n llamado algoritmo Fulkerson-Ford (que no debe confundirse con el algoritmo de flujo m\u00e1ximo), el algoritmo fuera de lo normal... <\/p>","protected":false},"author":1,"featured_media":0,"parent":3587,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3910","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3910","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=3910"}],"version-history":[{"count":5,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3910\/revisions"}],"predecessor-version":[{"id":18459,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3910\/revisions\/18459"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3587"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=3910"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}