{"id":465,"date":"2016-01-28T15:13:45","date_gmt":"2016-01-28T14:13:45","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=465"},"modified":"2022-12-03T22:57:30","modified_gmt":"2022-12-03T21:57:30","slug":"methode-du-simplexe","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/","title":{"rendered":"M\u00e9todo simplex"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"465\" class=\"elementor elementor-465\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f35a6fa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f35a6fa\" 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-e0322f1\" data-id=\"e0322f1\" 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-eb6ef16 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"eb6ef16\" 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\/programacion-lineal\/\">\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\">Programaci\u00f3n lineal<\/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-aa9f28a\" data-id=\"aa9f28a\" 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-94243ab elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"94243ab\" 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-dc72a83\" data-id=\"dc72a83\" 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-1be4569 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1be4569\" 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_lin%C3%A9aire\" 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-2b4b20e6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2b4b20e6\" 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-130480ae\" data-id=\"130480ae\" 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-aa081ee elementor-widget elementor-widget-text-editor\" data-id=\"aa081ee\" 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\/programacion-lineal\/metodo-simplex\/#Methode-du-simplexe\" >M\u00e9todo simplex<\/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\/programacion-lineal\/metodo-simplex\/#Methode\" >M\u00e9todo<\/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\/programacion-lineal\/metodo-simplex\/#Exemple-de-resolution\" >Resoluci\u00f3n de ejemplo<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Etape-1-Ecriture-sous-forme-standard-et-solution-de-base\" >Paso 1: escriba en forma est\u00e1ndar y soluci\u00f3n b\u00e1sica<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Aparte-degenerescence-du-simplexe\" >Aparte: degeneraci\u00f3n del simplex<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Etape-2-3-election-de-la-variable-entrante-et-sortante-de-la-base\" >Paso 2-3: elecci\u00f3n de la variable de entrada y salida de la base de datos<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Etape-3-actualisation-du-tableau\" >Paso 3: actualiza la tabla<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#STOP-conditions-darret\" >STOP: condiciones de parada<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Resume\" >Abstracto<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Cas-particuliers\" >Casos particulares<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/#Exemple\" >Ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methode-du-simplexe\"><\/span>M\u00e9todo simplex<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>El m\u00e9todo <strong>del simplex<\/strong> fue introducido por <strong>George Danzig<\/strong> de 1946. Es un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algoritmo<\/a> resoluci\u00f3n de problemas de optimizaci\u00f3n lineal.<\/p>\n\n<p>Consiste en minimizar una funci\u00f3n lineal de <strong>no<\/strong> variables reales,<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" class=\"alignnone wp-image-2339 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/simplexe-300x49.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"300\" height=\"49\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/simplexe-300x49.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/simplexe.png 355w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<\/div>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"aligncenter wp-image-2340 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/simplexe2.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"180\" height=\"24\" title=\"\"><\/figure>\n\n<p>donde, en un conjunto definido por medio de restricciones afines (o lineales) de igualdad y desigualdad. LOS&#039;<em>conjunto elegible<\/em> Por tanto, el problema es un poliedro convexo.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Methode\"><\/span>M\u00e9todo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>El m\u00e9todo simplex es un m\u00e9todo iterativo que atraviesa los v\u00e9rtices del poliedro convexo hasta que la funci\u00f3n objetivo ya no se puede mejorar. El proceso de resoluci\u00f3n es el siguiente:<\/p>\n\n<ol class=\"wp-block-list\">\n<li>El problema est\u00e1 escrito debajo <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-forma-canonica-y-forma-estandar-2\/\">forma est\u00e1ndar<\/a>.<\/li>\n<li>Se encuentra una soluci\u00f3n.<\/li>\n<li>Encuentra la columna de pivote.<\/li>\n<li>Encuentre la l\u00ednea del pivote y realice el m\u00e9todo de Gauss<\/li>\n<\/ol>\n\n<ul class=\"wp-block-list\">\n<li>PARADA. Soluci\u00f3n \u00f3ptima encontrada o ninguna soluci\u00f3n posible.<\/li>\n<\/ul>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-de-resolution\"><\/span>Resoluci\u00f3n de ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Considere el siguiente problema para aplicar el m\u00e9todo simplex:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Maximizar<\/td>\n<td><em>Z = 3x + 2y<\/em><\/td>\n<\/tr>\n<tr>\n<td>bajo las limitaciones:<\/td>\n<td><em>2x + y \u2264 18<\/em><\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td><em>2x + 3y \u2264 42<\/em><\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td><em>3x + y \u2264 24<\/em><\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td>x \u2265 0, y \u2265 0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-1-Ecriture-sous-forme-standard-et-solution-de-base\"><\/span>Paso 1: escriba en forma est\u00e1ndar y soluci\u00f3n b\u00e1sica<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>Transformamos las desigualdades en ecuaciones con la suma de <em>variables<\/em>.<\/p>\n\n<p>Para ello, presentamos un <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-origin-irrealizable\/\">variable de holgura<\/a> (X<sub>3<\/sub>, X<sub>4<\/sub>, X<sub>5<\/sub>) en cada una de las restricciones de la forma \u2264, para transformarlas en igualdades (ver lecci\u00f3n sobre la forma est\u00e1ndar):<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>2 x<sub>1<\/sub> + x<sub>2<\/sub> + x<sub>3<\/sub> = 18<\/td>\n<\/tr>\n<tr>\n<td>2 x<sub>1<\/sub> + 3 x<sub>2<\/sub> + x<sub>4<\/sub> = 42<\/td>\n<\/tr>\n<tr>\n<td>3 veces<sub>1<\/sub> + x<sub>2<\/sub> + x<sub>5<\/sub> = 24<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Luego, ajustamos la funci\u00f3n objetivo a cero: Z - 3 x<sub>1<\/sub> - X<sub>2<\/sub> - 0 x<sub>3<\/sub> - 0 x<sub>4<\/sub> - 0 x<sub>5<\/sub> = 0. Es decir que las variables can\u00f3nicas del programa est\u00e1n en cero, las variables de desviaci\u00f3n son iguales al elemento de la derecha (b). A partir de ahora, es posible inicializar la tabla del m\u00e9todo simplex.<\/p>\n\n<p>La tabla inicial del m\u00e9todo s\u00edmplex est\u00e1 formada por todos los coeficientes de las variables de decisi\u00f3n del problema original y las variables de diferencia.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>1ra iteraci\u00f3n<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u00a0vs<\/td>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>3<\/td>\n<td>2<\/td>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<\/tr>\n<tr>\n<td>Basado<\/td>\n<td>Cb<\/td>\n<td>B<\/td>\n<td>X<sub>1<\/sub><\/td>\n<td>X<sub>2<\/sub><\/td>\n<td>X<sub>3<\/sub><\/td>\n<td>X<sub>4<\/sub><\/td>\n<td>X<sub>5<\/sub><\/td>\n<\/tr>\n<tr>\n<td>X<sub>3<\/sub><\/td>\n<td>9<\/td>\n<td>18<\/td>\n<td>2<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>X<sub>4<\/sub><\/td>\n<td>21<\/td>\n<td>42<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>X<sub>5<\/sub><\/td>\n<td>8<\/td>\n<td>24<\/td>\n<td>3<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>Z<\/td>\n<td>\u00a0<\/td>\n<td>0<\/td>\n<td>-3<\/td>\n<td>-2<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Aparte-degenerescence-du-simplexe\"><\/span>Aparte: degeneraci\u00f3n del simplex<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>Se dice que una soluci\u00f3n b\u00e1sica factible es degenerada si al menos una de las variables b\u00e1sicas es cero. Si durante el algoritmo s\u00edmplex no se degenera ninguna base encontrada, entonces el algoritmo termina en un n\u00famero finito de iteraciones. Si existe una base degenerada, entonces se puede encontrar un posible ciclo del algoritmo: se encuentra una base ya encontrada y se repite indefinidamente. Para tratar casos de degeneraci\u00f3n, podemos aplicar la regla de Bland (1977) que asegura que el algoritmo se detiene en un n\u00famero finito de iteraciones. Cuando es probable que varias variables entren o salgan de la base, siempre elegimos la que tiene el \u00edndice m\u00e1s peque\u00f1o.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-2-3-election-de-la-variable-entrante-et-sortante-de-la-base\"><\/span>Paso 2-3: elecci\u00f3n de la variable de entrada y salida de la base de datos<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>Primero, establecemos la variable que entra en la base. Para ello, elegimos la columna cuyo valor en la fila <strong>Z<\/strong> es el m\u00e1s bajo de todos los negativos. En este caso, esa ser\u00eda la variable x<sub>1<\/sub> del coeficiente -3. La columna de la variable que entra en la base que llamamos <em>columna de pivote<\/em> (en verde).<\/p>\n\n<p>Se elige esta variable porque su impacto en el valor de Z es el mayor (mayor gradiente). Introducir esta variable en la base consiste en encontrar una soluci\u00f3n en el espacio de soluciones siguiendo el gradiente de esta variable. En el siguiente diagrama, la ordenada tiene el mayor gradiente en comparaci\u00f3n con la soluci\u00f3n Z = 0, por lo que seguiremos su eje (considere max z = x<sub>B<\/sub>) hasta que ya no pueda mejorar la soluci\u00f3n.<\/p>\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-7281 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire18.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"259\" height=\"256\" title=\"\"><\/figure>\n\n<p>Una vez obtenida la variable entrante en la base de datos, determinamos cu\u00e1l ser\u00e1 la variable saliente. Tomamos la decisi\u00f3n sobre la base de un c\u00e1lculo simple: dividir cada t\u00e9rmino independiente (columna b) entre el elemento correspondiente del <em>columna de pivote<\/em>, siempre que ambos elementos sean estrictamente positivos (mayores que cero).<\/p>\n\n<p>Esto equivale a considerar que nuestra variable saliente har\u00e1 un pivote gaussiano con la variable entrante. En otras palabras, la variable entrante tomar\u00e1 un valor distinto de cero mientras que la variable saliente se convertir\u00e1 en cero.<\/p>\n\n<p>Optamos por la l\u00ednea cuyo resultado es m\u00ednimo. De hecho, este c\u00e1lculo permite saber hasta qu\u00e9 valor se puede aumentar la variable entrante. la <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/\">programa lineal<\/a> teniendo restricciones, no es posible exceder la restricci\u00f3n m\u00e1s \u201crestrictiva\u201d, es decir, limitando al m\u00e1ximo el valor de la variable entrante.<\/p>\n\n<p><em>En este ejemplo: Cb: = 18\/2, 42\/2 y 24\/3.<br \/><\/em>Si hubiera un elemento menor o igual a cero, este cociente no se realiza. Cuando todos los elementos del <em>columna de pivote<\/em> fuera de esta condici\u00f3n habr\u00edamos cumplido la condici\u00f3n de parada y el problema tendr\u00eda soluci\u00f3n sin parte acotada.<\/p>\n\n<p>El t\u00e9rmino de la<em> columna de pivote<\/em> que result\u00f3 en el cociente positivo m\u00e1s peque\u00f1o distinto de cero en la divisi\u00f3n anterior indica la fila de la variable de brecha que sale de la base. En este caso, resulta x<sub>5<\/sub>, de coeficiente 3. Esta l\u00ednea se llama <em>l\u00ednea<\/em> <em>pivote<\/em> (en rojo).<\/p>\n\n<p>La intersecci\u00f3n de la <em>l\u00ednea de pivote<\/em> y la <em>columna de pivote<\/em> Destacar <em>el elemento pivote<\/em>, en este caso el 3.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-3-actualisation-du-tableau\"><\/span>Paso 3: actualiza la tabla<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>Se calculan los nuevos coeficientes de la tabla de la siguiente manera (pivote gaussiano):<\/p>\n\n<ul class=\"wp-block-list\">\n<li>En la fila del elemento pivote, cada nuevo elemento se calcula como: <em>Elemento de l\u00ednea de pivote = Elemento de l\u00ednea de pivote \/ pivote antiguo<\/em><\/li>\n<li>En la columna de pivote: 0 excepto el pivote en 1.<\/li>\n<li>En las l\u00edneas restantes se calcula cada elemento (producto cruzado): <em>Nuevo elemento de fila = Elemento de fila antiguo - (Proyecci\u00f3n de l\u00ednea de pivote antigua * Proyecci\u00f3n de columna de pivote antigua \/ Elemento de pivote antiguo).<\/em><\/li>\n<\/ul>\n\n<p>Mostramos los c\u00e1lculos para la l\u00ednea x<sub>4 <\/sub>:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>L\u00ednea antigua x<sub>4<\/sub><\/td>\n<td>42<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td>\u2013<\/td>\n<td>\u00a0<\/td>\n<td>\u2013<\/td>\n<td>\u2013<\/td>\n<td>\u2013<\/td>\n<td>\u2013<\/td>\n<\/tr>\n<tr>\n<td>proyecci\u00f3n<\/td>\n<td>2*24<\/td>\n<td>\u00a0<\/td>\n<td>2*1<\/td>\n<td>2*0<\/td>\n<td>2*0<\/td>\n<td>2*1<\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td>\/<\/td>\n<td>\u00a0<\/td>\n<td>\/<\/td>\n<td>\/<\/td>\n<td>\/<\/td>\n<td>\/<\/td>\n<\/tr>\n<tr>\n<td>pivote<\/td>\n<td>3<\/td>\n<td>\u00a0<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td>=<\/td>\n<td>se convierte en<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<\/tr>\n<tr>\n<td>Nueva l\u00ednea x<sub>4<\/sub><\/td>\n<td>26<\/td>\n<td>0<\/td>\n<td>7\/3<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>-2\/3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>La tabla correspondiente a esta segunda iteraci\u00f3n es (tenga en cuenta que x<sub>5<\/sub> est\u00e1 fuera y que x<sub>1<\/sub> ha vuelto a su lugar, adem\u00e1s, la funci\u00f3n objetivo ya no se expresa en x<sub>1<\/sub> pero en x<sub>5<\/sub>, y su valor es 24):<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>Iniciar iteraci\u00f3n 2-th<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>3<\/td>\n<td>2<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>Basado<\/td>\n<td>Cb<\/td>\n<td>B<\/td>\n<td>X<sub>1<\/sub><\/td>\n<td>X<sub>2<\/sub><\/td>\n<td>X<sub>3<\/sub><\/td>\n<td>X<sub>4<\/sub><\/td>\n<td>X<sub>5<\/sub><\/td>\n<\/tr>\n<tr>\n<td>X<sub>3<\/sub><\/td>\n<td>\u00a0<\/td>\n<td>2<\/td>\n<td>0<\/td>\n<td>1\/3<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>-2\/3<\/td>\n<\/tr>\n<tr>\n<td>X<sub>4<\/sub><\/td>\n<td>\u00a0<\/td>\n<td>26<\/td>\n<td>0<\/td>\n<td>7\/3<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>-2\/3<\/td>\n<\/tr>\n<tr>\n<td>X<sub>1<\/sub><\/td>\n<td>\u00a0<\/td>\n<td>8<\/td>\n<td>1<\/td>\n<td>1\/3<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>1\/3<\/td>\n<\/tr>\n<tr>\n<td>Z<\/td>\n<td>\u00a0<\/td>\n<td>24<\/td>\n<td>0<\/td>\n<td>-1<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"STOP-conditions-darret\"><\/span>STOP: condiciones de parada<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>Si el objetivo es la maximizaci\u00f3n, cuando en la \u00faltima l\u00ednea (l\u00ednea indicadora) no hay un valor negativo entre los costos (no hay una variable con un gradiente que mejore la soluci\u00f3n), obtenemos la condici\u00f3n de stop.<\/p>\n\n<p>El valor de <strong>Z<\/strong> (columna <strong>B<\/strong>) es la soluci\u00f3n \u00f3ptima al problema.<\/p>\n\n<p>Cuando no se cumple esta condici\u00f3n, los procesos se vuelven a ejecutar de forma iterativa.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>Inicio de la cuarta iteraci\u00f3n<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>\u00a0<\/td>\n<td>3<\/td>\n<td>2<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>Basado<\/td>\n<td>Cb<\/td>\n<td>B<\/td>\n<td>X<sub>1<\/sub><\/td>\n<td>X<sub>2<\/sub><\/td>\n<td>X<sub>3<\/sub><\/td>\n<td>X<sub>4<\/sub><\/td>\n<td>X<sub>5<\/sub><\/td>\n<\/tr>\n<tr>\n<td>X<sub>2<\/sub><\/td>\n<td>0<\/td>\n<td>12<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>-1\/2<\/td>\n<td>1\/2<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>X<sub>5<\/sub><\/td>\n<td>0<\/td>\n<td>3<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>-7\/4<\/td>\n<td>1\/4<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>X<sub>1<\/sub><\/td>\n<td>0<\/td>\n<td>3<\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>3\/4<\/td>\n<td>-1\/4<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td>Z<\/td>\n<td>\u00a0<\/td>\n<td>33<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>5\/4<\/td>\n<td>1\/4<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Descubrimos que en la \u00faltima l\u00ednea todos los coeficientes son positivos. La soluci\u00f3n \u00f3ptima es: 33 con el vector soluci\u00f3n (12, 3, 0, 0, 3). El vector soluci\u00f3n est\u00e1 determinado por el valor de <strong>B<\/strong> en las filas de variables b\u00e1sicas. Tenga en cuenta que x<sub>5<\/sub> = 3, es decir, la restricci\u00f3n 3 (que contiene la variable de diferencia x<sub>5<\/sub>) no est\u00e1 saturado con un margen 3.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resume\"><\/span>Abstracto<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-782 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/simplex.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"682\" height=\"505\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/simplex.png 682w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/simplex-300x222.png 300w\" sizes=\"(max-width: 682px) 100vw, 682px\" \/><\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Cas-particuliers\"><\/span>Casos particulares<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<ul class=\"wp-block-list\">\n<li><strong>Soluciones infinitas:<\/strong> cuando el simplex se detiene y las variables no base tienen un valor de 0 en la fila Z, significa que hay una soluci\u00f3n infinita. Para conocer los l\u00edmites del hiperplano (o del segmento) de soluciones, basta con volver a calcular el simplex ingresando la (s) variable (s) en la base.<\/li>\n<li><strong>Sin soluci\u00f3n :<\/strong> con el metodo de <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-metodo-du-grand-m\/\">gran M<\/a>, es posible que el <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-soluciones-y-dominio-realizable\/\">campo de definici\u00f3n<\/a> estar vac\u00edo En este caso, durante el c\u00e1lculo de la M grande, ciertas variables artificiales tienen un valor distinto de cero.<\/li>\n<li><strong>Elecci\u00f3n de la variable de entrada:<\/strong> cuando hay una elecci\u00f3n entre las variables de entrada (mismo valor), se debe elegir como prioridad una variable b\u00e1sica del programa lineal.<\/li>\n<li><strong>Elecci\u00f3n de la variable saliente:<\/strong> cuando hay una elecci\u00f3n entre las variables salientes, primero se eligen las variables artificiales, luego las variables en exceso, luego las variables diferenciales y finalmente las variables b\u00e1sicas.<\/li>\n<li><strong>Soluci\u00f3n degenerada:<\/strong> si la soluci\u00f3n \u00f3ptima tiene cero variables base, entonces se dice que es degenerada, este es el caso cuando hay m\u00e1s variables base que restricciones.<\/li>\n<\/ul>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>N\u00f3tese que en ocasiones la tabla se escribe con el valor de -Z con los coeficientes de c, en este caso la soluci\u00f3n \u00f3ptima se obtiene cuando todos los coeficientes son negativos. Considere el siguiente programa lineal:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7285 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire19.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"641\" height=\"183\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire19.png 641w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire19-300x86.png 300w\" sizes=\"(max-width: 641px) 100vw, 641px\" \/><\/figure>\n\n<p>Primera iteraci\u00f3n:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7286 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire20.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"753\" height=\"282\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire20.png 753w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire20-300x112.png 300w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/figure>\n\n<p>Lo que da despu\u00e9s de pivote:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7287 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire21.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"605\" height=\"175\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire21.png 605w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire21-300x87.png 300w\" sizes=\"(max-width: 605px) 100vw, 605px\" \/><\/figure>\n\n<p>Aqu\u00ed est\u00e1 la segunda iteraci\u00f3n antes y despu\u00e9s del pivote:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7288 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire22.png\" alt=\"m\u00e9todo dantzig simplex programaci\u00f3n lineal variable entrante variable saliente\" width=\"558\" height=\"353\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire22.png 558w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/10\/lineaire22-300x190.png 300w\" sizes=\"(max-width: 558px) 100vw, 558px\" \/><\/figure>\n\n<p>Todos los t\u00e9rminos de -Z son negativos, por lo que tenemos una soluci\u00f3n \u00f3ptima (0, 250, 0, 200, 500, 0, 100, 0), la primera y la tercera restricci\u00f3n no est\u00e1n saturadas (variables de desviaci\u00f3n en 500 y en 100); la funci\u00f3n objetivo vale 350.000.<\/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>P\u00e1gina principal de programaci\u00f3n lineal Wiki M\u00e9todo simplex El m\u00e9todo simplex fue introducido por George Dantzig en 1946. Es un \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":486,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-465","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/465","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=465"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/465\/revisions"}],"predecessor-version":[{"id":17907,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/465\/revisions\/17907"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/486"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=465"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}