{"id":15674,"date":"2022-04-21T17:06:21","date_gmt":"2022-04-21T16:06:21","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=15674"},"modified":"2024-02-11T16:01:53","modified_gmt":"2024-02-11T15:01:53","slug":"exbranch-and-cut","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/ejercicios-de-rama-y-corte-corregidos\/","title":{"rendered":"1 Ejercicio Corregido de Rama y corte"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"15674\" class=\"elementor elementor-15674\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-70c302f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"70c302f\" 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-76583a3\" data-id=\"76583a3\" 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-21189fe elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"21189fe\" 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\/optimizacion-combinatoria\/\">\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\">Optimizaci\u00f3n Combinatoria<\/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-79728ef\" data-id=\"79728ef\" 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-da9269b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"da9269b\" 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-9c08292\" data-id=\"9c08292\" 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-6decbe2 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6decbe2\" 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\/M%C3%A9thode_des_plans_s%C3%A9cants\" 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-d63fe0c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d63fe0c\" 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-de5a524\" data-id=\"de5a524\" 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-72e682f elementor-widget elementor-widget-text-editor\" data-id=\"72e682f\" 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<p>Esta p\u00e1gina presenta un ejercicio corregido detallado resuelto por el algoritmo de rama y corte (tambi\u00e9n conocido como plano de corte de Gomory).<\/p><p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"ramificar y cortar el plano de corte de Gomory\" width=\"97\" height=\"97\" title=\"\"><\/p>\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-4a9f2d5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4a9f2d5\" 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-c68bc85\" data-id=\"c68bc85\" 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-35207f7 elementor-widget elementor-widget-heading\" data-id=\"35207f7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<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\/optimizacion-combinatoria\/ejercicios-de-rama-y-corte-corregidos\/#Branch-and-cut-Gomory-cutting-plane\" >Rama y corte \/ plano de corte de Gomory<\/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\/optimizacion-combinatoria\/ejercicios-de-rama-y-corte-corregidos\/#Exercice-1\" >Ejercicio 1<\/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\/optimizacion-combinatoria\/ejercicios-de-rama-y-corte-corregidos\/#Solution\" >Soluci\u00f3n<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Branch-and-cut-Gomory-cutting-plane\"><\/span>Rama y corte \/ plano de corte de Gomory<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-e4d812e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e4d812e\" 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-77fcaa6\" data-id=\"77fcaa6\" 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-0af31b3 elementor-widget elementor-widget-text-editor\" data-id=\"0af31b3\" 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<h2><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Ejercicio 1<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Consider\u00e9moslo <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/\">programa lineal<\/a> Pr\u00f3ximo :<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-15680 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl1.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"214\" height=\"115\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl1.png 214w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl1-18x10.png 18w\" sizes=\"(max-width: 214px) 100vw, 214px\" \/><\/p><p>Resuelva por el m\u00e9todo de Gomory el problema (los dos primeros cortes).<\/p><h2><span class=\"ez-toc-section\" id=\"Solution\"><\/span>Soluci\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h2><p>Resolvamos el problema relajado en n\u00fameros reales. La solucion es:<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-15681 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl2.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"243\" height=\"147\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl2.png 243w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl2-18x12.png 18w\" sizes=\"(max-width: 243px) 100vw, 243px\" \/><\/p><p>El algoritmo del plano de corte de Gomory toma la variable con la parte no entera m\u00e1s grande, aqu\u00ed x_1. Formularemos una nueva restricci\u00f3n considerando solo los restos fraccionarios de cada coeficiente:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15682 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl3.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"224\" height=\"153\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl3.png 224w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl3-18x12.png 18w\" sizes=\"(max-width: 224px) 100vw, 224px\" \/><\/p><p>Estamos creando un nuevo <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-origin-irrealizable\/\">variable de holgura<\/a> para esta nueva restricci\u00f3n que da el siguiente diccionario:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15683 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl4.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"256\" height=\"198\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl4.png 256w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl4-16x12.png 16w\" sizes=\"(max-width: 256px) 100vw, 256px\" \/><\/p><p>Este programa no es realizable, por lo tanto es necesario hacer el <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/\">s\u00edmplex<\/a> doble. En otras palabras, forzamos la salida de x_5 (aqu\u00ed entra x_4), esto da como resultado el siguiente diccionario:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15684 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl5.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"234\" height=\"174\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl5.png 234w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl5-16x12.png 16w\" sizes=\"(max-width: 234px) 100vw, 234px\" \/><\/p><p>La soluci\u00f3n a\u00fan no es satisfactoria, tomamos la restricci\u00f3n con la mayor parte fraccionaria por lo tanto x_2 que da el siguiente corte (en resto fraccionario):<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15686 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl6-1.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"205\" height=\"155\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl6-1.png 205w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl6-1-16x12.png 16w\" sizes=\"(max-width: 205px) 100vw, 205px\" \/><\/p><p>Lo que da una nueva variable de brecha x_6:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15687 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl7.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"254\" height=\"219\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl7.png 254w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl7-14x12.png 14w\" sizes=\"(max-width: 254px) 100vw, 254px\" \/><\/p><p>Despu\u00e9s de aplicar el s\u00edmplex dual (x_6 es forzado a salir y x_5 adentro) obtenemos el siguiente resultado:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-15688 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl8.png\" alt=\"Rama y corte Gomory plano de corte\" width=\"253\" height=\"241\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl8.png 253w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2022\/04\/pl8-13x12.png 13w\" sizes=\"(max-width: 253px) 100vw, 253px\" \/><\/p><p>\u00a1Tenga en cuenta que esto todav\u00eda no resuelve nuestro problema!<\/p>\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>P\u00e1gina de inicio de Wiki de Optimizaci\u00f3n Combinatoria Esta p\u00e1gina presenta un ejercicio corregido detallado resuelto por el algoritmo de ramificaci\u00f3n y corte (tambi\u00e9n conocido como... <\/p>","protected":false},"author":1,"featured_media":0,"parent":1770,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-15674","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15674","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=15674"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15674\/revisions"}],"predecessor-version":[{"id":20255,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/15674\/revisions\/20255"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=15674"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}