{"id":1770,"date":"2016-10-27T17:01:28","date_gmt":"2016-10-27T16:01:28","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1770"},"modified":"2024-02-11T19:49:16","modified_gmt":"2024-02-11T18:49:16","slug":"optimisation-combinatoire","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/","title":{"rendered":"Optimizaci\u00f3n combinatoria 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1770\" class=\"elementor elementor-1770\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-af7b5e0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"af7b5e0\" 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-aef2227\" data-id=\"aef2227\" 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-a9aa898 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a9aa898\" 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\/2020\/04\/03\/teorias-y-algoritmos-2\/\">\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\">Teor\u00edas<\/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-240d7c7\" data-id=\"240d7c7\" 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-46b18bf elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"46b18bf\" 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-fa1b870\" data-id=\"fa1b870\" 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-673dfcd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"673dfcd\" 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\/Optimisation_combinatoire\" 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-5fd9688 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5fd9688\" 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-d3b2db5\" data-id=\"d3b2db5\" 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-9724ce3 elementor-widget elementor-widget-toggle\" data-id=\"9724ce3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1581\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1581\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. M\u00e9todos exactos (optimizaci\u00f3n combinatoria)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1581\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1581\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/plano-de-corte\/\">Plano de corte<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/ramificar-y-enlazar\/\">Rama y encuadernado<\/a><\/li>\n<li>Rama y corte<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/\">Programaci\u00f3n din\u00e1mica<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones\/\">Programaci\u00f3n de restricciones<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/programacion-de-restricciones-2\/\">Programaci\u00f3n de restricciones, m\u00e9todos de resoluci\u00f3n<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/generacion-de-columnas\/\">Generaci\u00f3n de columnas<\/a><\/li>\n<li>Sucursal y precio<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1582\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-1582\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Criterios de exactitud<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1582\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-1582\"><ul>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/No_free_lunch_in_search_and_optimization\" target=\"_blank\" rel=\"noopener\">Teorema de no-almuerzo gratis<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/evaluacion-heuristica\/\">Evaluaci\u00f3n heur\u00edstica<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1583\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-1583\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Heur\u00edsticas y metaheur\u00edsticas<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1583\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-1583\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-estocasticos\/\" target=\"_blank\" rel=\"noreferrer noopener\">Algoritmos estoc\u00e1sticos<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-devolucion\/\" target=\"_blank\" rel=\"noreferrer noopener\">Algoritmos de evoluci\u00f3n<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-basados-en-la-fisica\/\">Algoritmos f\u00edsicos<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-probabilisticos\/\">Algoritmos probabil\u00edsticos<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-desaims\/\">Algoritmos de enjambre<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmo-inmunologico\/\">Algoritmos inmunes<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmos-neuronales\/\">Algoritmos neuronales<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1584\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-1584\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Optimizaci\u00f3n no lineal sin restricciones<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1584\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-1584\"><ul>\n<li><a title=\"B\u00fasqueda de secci\u00f3n dorada\" href=\"https:\/\/en.wikipedia.org\/wiki\/Golden-section_search\" target=\"_blank\" rel=\"noopener\">B\u00fasqueda de secci\u00f3n dorada<\/a><\/li>\n<li><a title=\"m\u00e9todo de Powell\" href=\"https:\/\/en.wikipedia.org\/wiki\/Powell%27s_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todos de interpolaci\u00f3n<\/a><\/li>\n<li><a title=\"b\u00fasqueda de l\u00ednea\" href=\"https:\/\/en.wikipedia.org\/wiki\/Line_search\" target=\"_blank\" rel=\"noopener\">b\u00fasqueda de l\u00ednea<\/a><\/li>\n<li><a title=\"M\u00e9todo Nelder-Mead\" href=\"https:\/\/en.wikipedia.org\/wiki\/Nelder%E2%80%93Mead_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todo Nelder-Mead<\/a><\/li>\n<li><a title=\"Interpolaci\u00f3n parab\u00f3lica sucesiva\" href=\"https:\/\/en.wikipedia.org\/wiki\/Successive_parabolic_interpolation\" target=\"_blank\" rel=\"noopener\">Interpolaci\u00f3n parab\u00f3lica sucesiva<\/a><\/li>\n<li><a title=\"Regi\u00f3n de confianza\" href=\"https:\/\/en.wikipedia.org\/wiki\/Trust_region\" target=\"_blank\" rel=\"noopener\">Regi\u00f3n de confianza<\/a><\/li>\n<li><a title=\"T\u00e9rminos y condiciones\" href=\"https:\/\/en.wikipedia.org\/wiki\/Wolfe_conditions\" target=\"_blank\" rel=\"noopener\">T\u00e9rminos y condiciones<\/a><\/li>\n<li><a title=\"Algoritmo de Berndt-Hall-Hall-Hausman\" href=\"https:\/\/en.wikipedia.org\/wiki\/Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm\" target=\"_blank\" rel=\"noopener\">Berndt-Hall-Hall-Hausman<\/a><\/li>\n<li><a title=\"Algoritmo de Broyden-Fletcher-Goldfarb-Shanno\" href=\"https:\/\/en.wikipedia.org\/wiki\/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm\" target=\"_blank\" rel=\"noopener\">Broyden\u2013Fletcher\u2013Goldfarb\u2013Shanno<\/a>\u00a0y\u00a0<a title=\"BFGS de memoria limitada\" href=\"https:\/\/en.wikipedia.org\/wiki\/Limited-memory_BFGS\" target=\"_blank\" rel=\"noopener\">L-BFGS<\/a><\/li>\n<li><a title=\"F\u00f3rmula de Davidon-Fletcher-Powell\" href=\"https:\/\/en.wikipedia.org\/wiki\/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula\" target=\"_blank\" rel=\"noopener\">Davidon-Fletcher-Powell<\/a><\/li>\n<li><a title=\"Rango uno sim\u00e9trico\" href=\"https:\/\/en.wikipedia.org\/wiki\/Symmetric_rank-one\" target=\"_blank\" rel=\"noopener\">Rango uno sim\u00e9trico (SR1)<\/a><\/li>\n<li><a title=\"M\u00e9todo de gradiente conjugado no lineal\" href=\"https:\/\/en.wikipedia.org\/wiki\/Nonlinear_conjugate_gradient_method\" target=\"_blank\" rel=\"noopener\">Conjugado de gradiente<\/a><\/li>\n<li><a title=\"Algoritmo de Gauss-Newton\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gauss%E2%80%93Newton_algorithm\" target=\"_blank\" rel=\"noopener\">Gauss-Newton<\/a><\/li>\n<li><a title=\"Descenso de gradiente\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gradient_descent\" target=\"_blank\" rel=\"noopener\">degradado<\/a><\/li>\n<li><a title=\"descenso del espejo\" href=\"https:\/\/en.wikipedia.org\/wiki\/Mirror_descent\" target=\"_blank\" rel=\"noopener\">Espejo<\/a><\/li>\n<li><a title=\"Algoritmo de Levenberg-Marquardt\" href=\"https:\/\/en.wikipedia.org\/wiki\/Levenberg%E2%80%93Marquardt_algorithm\" target=\"_blank\" rel=\"noopener\">Levenberg\u2013Marquardt<\/a><\/li>\n<li><a title=\"M\u00e9todo de la pata de perro de Powell\" href=\"https:\/\/en.wikipedia.org\/wiki\/Powell%27s_dog_leg_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todo de la pata de perro de Powell<\/a><\/li>\n<li><a title=\"M\u00e9todo de Newton truncado\" href=\"https:\/\/en.wikipedia.org\/wiki\/Truncated_Newton_method\" target=\"_blank\" rel=\"noopener\">Newton truncado<\/a><\/li>\n<li><a title=\"El m\u00e9todo de Newton en optimizaci\u00f3n.\" href=\"https:\/\/en.wikipedia.org\/wiki\/Newton%27s_method_in_optimization\" target=\"_blank\" rel=\"noopener\">m\u00e9todo de newton<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1585\" class=\"elementor-tab-title\" data-tab=\"5\" role=\"button\" aria-controls=\"elementor-tab-content-1585\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">V. Optimizaci\u00f3n no lineal con restricciones<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1585\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"5\" role=\"region\" aria-labelledby=\"elementor-tab-title-1585\"><ul>\n<li><a title=\"Funci\u00f3n de barrera\" href=\"https:\/\/en.wikipedia.org\/wiki\/Barrier_function\" target=\"_blank\" rel=\"noopener\">M\u00e9todos de barrera<\/a><\/li>\n<li><a title=\"m\u00e9todo de penalizaci\u00f3n\" href=\"https:\/\/en.wikipedia.org\/wiki\/Penalty_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todos de penalizaci\u00f3n<\/a><\/li>\n<li><a title=\"M\u00e9todo Lagrangiano Aumentado\" href=\"https:\/\/en.wikipedia.org\/wiki\/Augmented_Lagrangian_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todos Lagrangianos Aumentados<\/a><\/li>\n<li><a title=\"Programaci\u00f3n cuadr\u00e1tica secuencial\" href=\"https:\/\/en.wikipedia.org\/wiki\/Sequential_quadratic_programming\" target=\"_blank\" rel=\"noopener\">Programaci\u00f3n cuadr\u00e1tica secuencial<\/a><\/li>\n<li><a title=\"Programaci\u00f3n lineal sucesiva\" href=\"https:\/\/en.wikipedia.org\/wiki\/Successive_linear_programming\" target=\"_blank\" rel=\"noopener\">Programaci\u00f3n lineal sucesiva<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1586\" class=\"elementor-tab-title\" data-tab=\"6\" role=\"button\" aria-controls=\"elementor-tab-content-1586\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">VI. Optimizacion convexa<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1586\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"6\" role=\"region\" aria-labelledby=\"elementor-tab-title-1586\"><ul>\n<li><a title=\"M\u00e9todo del plano de corte\" href=\"https:\/\/en.wikipedia.org\/wiki\/Cutting-plane_method\" target=\"_blank\" rel=\"noopener\">M\u00e9todo del plano de corte<\/a><\/li>\n<li><a title=\"Algoritmo de Frank-Wolfe\" href=\"https:\/\/en.wikipedia.org\/wiki\/Frank%E2%80%93Wolfe_algorithm\" target=\"_blank\" rel=\"noopener\">Gradiente reducido (Frank-Wolfe)<\/a><\/li>\n<li><a title=\"m\u00e9todo subgradiente\" href=\"https:\/\/en.wikipedia.org\/wiki\/Subgradient_method\" target=\"_blank\" rel=\"noopener\">m\u00e9todo subgradiente<\/a><\/li>\n<li><a title=\"Escalado af\u00edn\" href=\"https:\/\/en.wikipedia.org\/wiki\/Affine_scaling\" target=\"_blank\" rel=\"noopener\">Escalado af\u00edn<\/a><\/li>\n<li><a title=\"m\u00e9todo elipsoide\" href=\"https:\/\/en.wikipedia.org\/wiki\/Ellipsoid_method\" target=\"_blank\" rel=\"noopener\">Algoritmo elipsoide de Khachiyan<\/a><\/li>\n<li><a title=\"Algoritmo de Karmarkar\" href=\"https:\/\/en.wikipedia.org\/wiki\/Karmarkar%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Algoritmo proyectivo de Karmarkar<\/a><\/li>\n<li><a title=\"Algoritmo s\u00edmplex\" href=\"https:\/\/en.wikipedia.org\/wiki\/Simplex_algorithm\" target=\"_blank\" rel=\"noopener\">Algoritmo simplex de Danzig<\/a><\/li>\n<li><a title=\"M\u00e9todo simplex revisado\" href=\"https:\/\/en.wikipedia.org\/wiki\/Revised_simplex_method\" target=\"_blank\" rel=\"noopener\">Algoritmo simplex revisado<\/a><\/li>\n<li><a title=\"Algoritmo entrecruzado\" href=\"https:\/\/en.wikipedia.org\/wiki\/Criss-cross_algorithm\" target=\"_blank\" rel=\"noopener\">Algoritmo entrecruzado<\/a><\/li>\n<li><a title=\"algoritmo de Lemke\" href=\"https:\/\/en.wikipedia.org\/wiki\/Lemke%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Algoritmo pivotante principal de Lemke<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-58fc4764 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"58fc4764\" 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-2f81a4fa\" data-id=\"2f81a4fa\" 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-43400546 elementor-widget elementor-widget-text-editor\" data-id=\"43400546\" 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' ><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/#Optimisation-combinatoire\" >Optimizaci\u00f3n combinatoria<\/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\/#Arbre-des-solutions\" >\u00c1rbol de soluciones<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/#Techniques-de-resolution\" >T\u00e9cnicas de resoluci\u00f3n<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/#Exacte\" >Exacto<\/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\/optimizacion-combinatoria\/#Heuristique\" >Heur\u00edstico<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/#Meta-heuristique\" >Metaheur\u00edstico<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Optimisation-combinatoire\"><\/span>Optimizaci\u00f3n combinatoria<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>LOS&#039;<b>optimizaci\u00f3n combinatoria<\/b>, tambi\u00e9n llamado <b>optimizaci\u00f3n discreta<\/b>, es una rama de la optimizaci\u00f3n en matem\u00e1ticas aplicadas e inform\u00e1tica, tambi\u00e9n relacionada con la investigaci\u00f3n de operaciones, los algoritmos y la teor\u00eda de la complejidad. La optimizaci\u00f3n combinatoria consiste en encontrar en un conjunto un subconjunto que contenga las \u201cmejores soluciones\u201d.<\/p>\n<p><\/p>\n<p>Encontrar una soluci\u00f3n \u00f3ptima en un conjunto discreto y finito es un problema f\u00e1cil en teor\u00eda: solo tienes que probar todas las soluciones y comparar sus cualidades para ver la mejor. Sin embargo, la explosi\u00f3n combinatoria de posibles soluciones de ciertos problemas matem\u00e1ticos no permite obtener una soluci\u00f3n en un tiempo &quot;humano&quot;.<\/p>\n<p><\/p>\n<p>Algunos problemas de optimizaci\u00f3n combinatoria se pueden resolver (exactamente) en tiempo polinomial, por ejemplo mediante un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> programaci\u00f3n din\u00e1mica o demostrando que el problema puede formularse como un problema de optimizaci\u00f3n lineal en variables reales. En la mayor\u00eda de los casos, el problema es Np-dif\u00edcil y, para solucionarlo, se deben utilizar algoritmos adecuados.<\/p>\n<p><\/p>\n<p>En la pr\u00e1ctica, la complejidad f\u00edsicamente aceptable es a menudo solo polinomial. Entonces estamos satisfechos con tener una soluci\u00f3n aproximada en el mejor de los casos, obtenida por una heur\u00edstica o una metaheur\u00edstica. Es importante se\u00f1alar que algunos de estos m\u00e9todos proporcionan \u00f3ptimos globales, la diferencia con los m\u00e9todos exactos es el hecho de no tener una prueba formal (prueba matem\u00e1tica o de finalidad) de su optimalidad global.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-1812 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi.png\" alt=\"t\u00e9cnica de optimizaci\u00f3n combinatoria\" width=\"618\" height=\"301\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi.png 618w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi-300x146.png 300w\" sizes=\"(max-width: 618px) 100vw, 618px\" \/><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-des-solutions\"><\/span>\u00c1rbol de soluciones<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Es decir <strong>mi<\/strong> todas las soluciones a los problemas. Se supone que es discreto y finito. La enumeraci\u00f3n de soluciones est\u00e1 representada por <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a>. todos los elementos de <strong>mi<\/strong> est\u00e1n separados en <strong>no<\/strong> subconjunto no vac\u00edo disjunto, cada uno de los cuales contiene una parte del conjunto de soluciones. Por ejemplo, el conjunto se puede dividir en dos en el problema de la mochila, tomemos o no un elemento x<sub>k<\/sub> en el bolso.<\/p>\n<p><\/p>\n<p>La operaci\u00f3n se puede repetir para cada subconjunto hasta que cada conjunto contenga solo un elemento. En el ejemplo de la mochila, cada subconjunto se separa hasta que se toma una decisi\u00f3n sobre el \u00faltimo elemento.<\/p>\n<p><\/p>\n<p>La ra\u00edz del \u00e1rbol es <strong>mi<\/strong>, los cables son los subconjuntos, etc. como se muestra en el siguiente diagrama:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"aligncenter wp-image-2095 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration.png\" alt=\"optimizaci\u00f3n de enumeraci\u00f3n\" width=\"785\" height=\"230\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration.png 785w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration-300x88.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration-768x225.png 768w\" sizes=\"(max-width: 785px) 100vw, 785px\" \/><\/figure>\n<p><\/p>\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Techniques-de-resolution\"><\/span>T\u00e9cnicas de resoluci\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exacte\"><\/span>Exacto<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Estos m\u00e9todos dan una garant\u00eda para encontrar la soluci\u00f3n \u00f3ptima para una instancia de tama\u00f1o finito en un tiempo limitado y para demostrar su optimalidad.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Heuristique\"><\/span>Heur\u00edstico<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Cuando la complejidad de un problema es exponencial o presenta una explosi\u00f3n combinatoria, se recomienda el uso de heur\u00edsticas. Este es un m\u00e9todo que proporciona r\u00e1pidamente una &quot;buena&quot; soluci\u00f3n al problema. Esta soluci\u00f3n aproximada puede proporcionar un punto de partida para utilizar un m\u00e9todo exacto (como la esquina noroeste para el problema del transporte). Todos los algoritmos codiciosos e ingenuos son heur\u00edsticos.<\/p>\n<p><\/p>\n<p>Cabe se\u00f1alar que las heur\u00edsticas est\u00e1n dise\u00f1adas para resolver un problema dado y no pueden usarse en otras condiciones a diferencia de las metaheur\u00edsticas. Las heur\u00edsticas se eval\u00faan seg\u00fan tres criterios:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Calidad del resultado: la heur\u00edstica se enfrenta a los resultados \u00f3ptimos para un conjunto de valores del problema dado (hablamos de benchmark). La calidad de la soluci\u00f3n puede ser una distancia a la soluci\u00f3n \u00f3ptima o una probabilidad de alcanzarla.<\/li>\n<li>Costo de la heur\u00edstica: complejidad en el tiempo y el espacio.<\/li>\n<li>Campo de aplicaci\u00f3n: el campo de admisibilidad de todas las variables.<\/li>\n<\/ol>\n<p><\/p>\n<p>Las heur\u00edsticas para un problema dado son numerosas, por lo que es importante proporcionar una r\u00e1pida y proporcionar &quot;buenos&quot; resultados.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Meta-heuristique\"><\/span>Metaheur\u00edstico<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Las metaheur\u00edsticas tienen un mayor nivel de abstracci\u00f3n que las heur\u00edsticas, ya que es un m\u00e9todo que puede adaptarse a un problema dado. As\u00ed, los m\u00e9todos se pueden aplicar a diversos problemas (en forma de caja negra) sin modificar su funcionamiento. Tambi\u00e9n hablamos de heur\u00edstica generalista.<\/p>\n<p><\/p>\n<p>Hay dos tipos de metaheur\u00edsticas: poblaci\u00f3n <em>(Para)<\/em> o curso <em>(B)<\/em>. La mayor\u00eda de los algoritmos no tienen una poblaci\u00f3n determinada, por lo que es posible utilizar el algoritmo para una ruta o una poblaci\u00f3n.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"aligncenter wp-image-1856 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population.png\" alt=\"metaheur\u00edstica de ruta de poblaci\u00f3n\" width=\"640\" height=\"480\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population.png 640w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population-300x225.png 300w\" sizes=\"(max-width: 640px) 100vw, 640px\" \/><\/figure>\n<p><\/p>\n<p>Ambos tipos funcionan con el mismo proceso de cuatro pasos:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li><em>Vecindario <\/em>: la vecindad de una soluci\u00f3n es un subconjunto de soluciones que pueden alcanzarse mediante una transformaci\u00f3n de la soluci\u00f3n inicial (por permutaci\u00f3n, por extensi\u00f3n, por mutaci\u00f3n, por eyecci\u00f3n, etc.).<\/li>\n<li><em>Exploraci\u00f3n<\/em> : la exploraci\u00f3n consiste en recopilar datos de todo el barrio.<\/li>\n<li><em>Operaci\u00f3n<\/em> : la operaci\u00f3n utiliza la informaci\u00f3n recolectada para definir las \u00e1reas de \u201cinter\u00e9s\u201d del \u00e1rea de investigaci\u00f3n que forma el barrio.<\/li>\n<li><em>Memoria<\/em> : la memoria tiene en cuenta el aprendizaje y permite determinar las zonas susceptibles de tener un \u00f3ptimo global. Si las nuevas soluciones o los criterios de parada ya no permiten mejorar la soluci\u00f3n, el algoritmo se detiene. De lo contrario, regrese al paso 1. Ciertos algoritmos solo funcionan con criterios de detenci\u00f3n, por lo que estamos hablando de metaheur\u00edsticas sin memoria.<\/li>\n<\/ol>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1836 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta.png\" alt=\"algoritmo de optimizaci\u00f3n\" width=\"649\" height=\"591\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta.png 649w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta-300x273.png 300w\" sizes=\"(max-width: 649px) 100vw, 649px\" \/><\/figure>\n<p><\/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>Teor\u00edas P\u00e1gina de inicio Wiki I. M\u00e9todos exactos (optimizaci\u00f3n combinatoria) Plano de corte Rama y l\u00edmite Rama y corte Programaci\u00f3n din\u00e1mica Programaci\u00f3n con restricciones Programaci\u00f3n con restricciones, M\u00e9todos \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1770","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770","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=1770"}],"version-history":[{"count":32,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770\/revisions"}],"predecessor-version":[{"id":20400,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/1770\/revisions\/20400"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=1770"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}