{"id":3045,"date":"2016-09-06T12:34:25","date_gmt":"2016-09-06T11:34:25","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3045"},"modified":"2022-12-03T22:59:01","modified_gmt":"2022-12-03T21:59:01","slug":"generation-de-colonnes","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/generacion-de-columnas\/","title":{"rendered":"Generaci\u00f3n de columnas"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3045\" class=\"elementor elementor-3045\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-902ec7b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"902ec7b\" 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-170734f\" data-id=\"170734f\" 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-1abb46c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1abb46c\" 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-5648710\" data-id=\"5648710\" 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-50176df elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"50176df\" 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-e72a08d\" data-id=\"e72a08d\" 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-58524a7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"58524a7\" 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\/G%C3%A9n%C3%A9ration_de_colonnes\" 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-4e8c9e60 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e8c9e60\" 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-4bd99c3e\" data-id=\"4bd99c3e\" 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-33701a01 elementor-widget elementor-widget-text-editor\" data-id=\"33701a01\" 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\/optimizacion-combinatoria\/generacion-de-columnas\/#Generation-de-colonnes\" >Generaci\u00f3n de columnas<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Generation-de-colonnes\"><\/span>Generaci\u00f3n de columnas<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Cuando una <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/\">programa lineal<\/a> tiene muchas variables, no es posible resolverlo por un <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/\">s\u00edmplex<\/a>. La generaci\u00f3n de columnas permite generar las variables \u00fatiles de forma progresiva hasta obtener una soluci\u00f3n \u00f3ptima. El objetivo de este m\u00e9todo es resolver un problema reducido con un conjunto limitado de variables.<\/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;\">El problema inicial de una generaci\u00f3n de columnas se denomina problema principal y el problema reducido se denomina problema restringido.<\/div>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">El problema restringido de una generaci\u00f3n de columnas es m\u00e1s sencillo de resolver, pero si el conjunto de sus variables no contiene las que dan la soluci\u00f3n \u00f3ptima al problema maestro, para llegar a la soluci\u00f3n \u00f3ptima del problema maestro, es necesario sumar el problema se limita a las variables que se pueden utilizar para mejorar la soluci\u00f3n.<\/div>\n\n<p>El problema que consiste en encontrar la mejor variable para agregar en el problema restringido se denomina subproblema asociado al problema maestro (u or\u00e1culo). Su objetivo es encontrar la variable (o columna) de m\u00ednimo coste reducido (es decir, la m\u00e1s prometedora para mejorar la soluci\u00f3n).<\/p>\n\n<p>El costo reducido de las variables se calcula utilizando las variables duales obtenidas despu\u00e9s de resolver el problema restringido. El punto del dual as\u00ed utilizado en el subproblema se llama punto de separaci\u00f3n. A menudo, esta es una soluci\u00f3n \u00f3ptima del problema dual del restringido.<\/p>\n\n<p>Consideramos el siguiente programa lineal continuo (LP):<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4736 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne1.png\" alt=\"Generaci\u00f3n de columnas\" width=\"301\" height=\"75\" title=\"\"><\/figure>\n<\/div>\n\n<p>Suponemos que el n\u00famero de variables en T es demasiado grande para que el problema (LP) se resuelva en un tiempo razonable y que queremos resolverlo generando columnas. Por lo tanto, buscamos resolver el problema restringido asociado con el problema maestro con un conjunto restringido de variables denotadas por R<sub>los<\/sub>. El problema restringido debe ser factible. Es posible utilizar columnas simples, por ejemplo columnas aleatorias, o incluso las que resultan de una soluci\u00f3n factible obtenida de un <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/\">heur\u00edstico<\/a>.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4744 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne2.png\" alt=\"Generaci\u00f3n de columnas\" width=\"301\" height=\"80\" title=\"\"><\/figure>\n<\/div>\n\n<p>El problema (RLP) ahora es peque\u00f1o y ser\u00e1 m\u00e1s f\u00e1cil de resolver con un solucionador. Esta resoluci\u00f3n nos proporcionar\u00e1 los valores \u00f3ptimos de las variables duales v<sub>j<\/sub> asociado con restricciones. Estos valores se pasan al subproblema que nos permite obtener la (s) columna (s) para sumar al conjunto R<sub>los<\/sub>.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4750 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne3.png\" alt=\"Generaci\u00f3n de columnas\" width=\"160\" height=\"75\" title=\"\"><\/figure>\n<\/div>\n\n<p>El c\u00e1lculo del coste reducido nos permite saber si una columna disminuy\u00f3 el valor del objetivo (y por tanto lo mejor\u00f3).<\/p>\n\n<p>Como (LP) es un problema de <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-del-lenguaje\/minimizacion-dun-afd\/\">minimizaci\u00f3n<\/a>, el subproblema tambi\u00e9n busca minimizar este costo reducido. Si el costo m\u00ednimo reducido es positivo, entonces no se pueden agregar columnas al problema restringido (RPL) para mejorar el objetivo. La soluci\u00f3n \u00f3ptima del problema restringido es, por tanto, una soluci\u00f3n \u00f3ptima del problema maestro (PL). De lo contrario, agregamos una o m\u00e1s columnas entre las que tienen un costo reducido negativo al actualizar el conjunto R<sub>los<\/sub> y solucionamos despu\u00e9s del nuevo problema restringido (RLP).<\/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>Optimizaci\u00f3n combinatoria P\u00e1gina de inicio Wiki Generaci\u00f3n de columnas Cuando un programa lineal tiene muchas variables, no es posible resolverlo por s\u00edmplex. \u2026 <\/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-3045","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3045","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=3045"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3045\/revisions"}],"predecessor-version":[{"id":17901,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/3045\/revisions\/17901"}],"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=3045"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}