{"id":6827,"date":"2019-04-08T14:15:31","date_gmt":"2019-04-08T13:15:31","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6827"},"modified":"2022-12-03T23:02:05","modified_gmt":"2022-12-03T22:02:05","slug":"lp-methode-du-grand-m","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-metodo-du-grand-m\/","title":{"rendered":"LP: m\u00e9todo M grande"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6827\" class=\"elementor elementor-6827\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-399f828 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"399f828\" 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-53ed3e7\" data-id=\"53ed3e7\" 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-874e56e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"874e56e\" 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-4536f9a\" data-id=\"4536f9a\" 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-70c24bd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"70c24bd\" 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-57eab6f\" data-id=\"57eab6f\" 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-56be261 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"56be261\" 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\/Algorithme_du_simplexe\" 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-f643c45 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f643c45\" 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-1196d397\" data-id=\"1196d397\" 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-103ce255 elementor-widget elementor-widget-text-editor\" data-id=\"103ce255\" 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\/lp-metodo-du-grand-m\/#Methode-du-grand-M\" >M\u00e9todo Big M<\/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\/lp-metodo-du-grand-m\/#Pourquoi-une-variable-artificielle\" >\u00bfPor qu\u00e9 una variable artificial?<\/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\/lp-metodo-du-grand-m\/#Construction-de-la-Phase-1\" >Construcci\u00f3n de la Fase 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-metodo-du-grand-m\/#Phase-2\" >Fase 2<\/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\/programacion-lineal\/lp-metodo-du-grand-m\/#Algorithme-du-simplexe\" >Algoritmo simplex<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methode-du-grand-M\"><\/span>M\u00e9todo Big M<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Cuando el <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/\">s\u00edmplex<\/a> tiene variables artificiales, es posible no encontrar una soluci\u00f3n de partida obvia (pruebe si el origen est\u00e1 en el <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-soluciones-y-dominio-realizable\/\">campo de definici\u00f3n<\/a>). En este caso, se debe encontrar una soluci\u00f3n inicial utilizando el m\u00e9todo de la gran M.<\/p>\n\n<p>Este m\u00e9todo calcula un problema auxiliar antes de resolver el s\u00edmplex del <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/\">programa lineal<\/a>, por lo que se denomina s\u00edmplex de dos fases.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Pourquoi-une-variable-artificielle\"><\/span>\u00bfPor qu\u00e9 una variable artificial?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Antes de explicar c\u00f3mo obtener una soluci\u00f3n para iniciar el simplex, es importante entender por qu\u00e9 es necesario agregar una variable artificial adem\u00e1s de la <a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/lp-origin-irrealizable\/\">variable de holgura<\/a>.<\/p>\n\n<p>Tomemos como ejemplo el siguiente programa lineal:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-7519 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire99.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"175\" height=\"80\" title=\"\"><\/figure>\n\n<p>Agreguemos las variables de varianza:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-7520 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire100.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"250\" height=\"80\" title=\"\"><\/figure>\n\n<p>El s\u00edmplex comienza tomando las variables base en cero, por lo que con el siguiente vector (0, 0, -19, 32). Esto es imposible porque X3 no puede tomar un valor negativo. Por eso hay que a\u00f1adir una nueva variable que, por tanto, ser\u00e1 artificial.<\/p>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-7521 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire101.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"276\" height=\"83\" title=\"\"><\/figure>\n\n<p>Aqu\u00ed el vector (0, 0, 0, 19, 32) es una soluci\u00f3n factible. Pero como es una variable artificial, debe ser posible eliminarla del Simplex para poder encontrar una soluci\u00f3n global. Por tanto, es necesario que X5 = 0. Para comprobar si esto es posible, buscamos minimizar X5.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Construction-de-la-Phase-1\"><\/span>Construcci\u00f3n de la Fase 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Lo preparamos de forma similar a la tabla inicial del m\u00e9todo Simplex, pero con algunas diferencias. Tomando el ejemplo anterior, intentamos resolver el siguiente problema:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7522 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire102.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"270\" height=\"80\" title=\"\"><\/figure>\n\n<p>Sabemos que solo X4 y X5 est\u00e1n en la base, por lo que el primer paso es expresar la funci\u00f3n objetivo con las variables no base (aqu\u00ed X1, X2, X3). En el ejemplo, esto es posible gracias a la primera restricci\u00f3n.<\/p>\n\n<p>El primer paso es resolver el siguiente programa lineal:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7525 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire103.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"237\" height=\"72\" title=\"\"><\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Phase-2\"><\/span>Fase 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>La segunda fase del m\u00e9todo Two-Phase se desarrolla exactamente igual que el m\u00e9todo Simplex, excepto que antes de iniciar las iteraciones es necesario eliminar las columnas correspondientes a las variables artificiales y reconstruir la tabla original.<\/p>\n\n<ul class=\"wp-block-list\">\n<li><strong>Elimine las columnas de variables artificiales:<\/strong> Si llegamos a la conclusi\u00f3n de que el problema inicial tiene soluci\u00f3n, debemos preparar nuestra tabla para la segunda fase. Este paso es muy sencillo, solo debes borrar las columnas correspondientes a las variables artificiales.<\/li>\n<li><strong>Reconstrucci\u00f3n de la mesa inicial:<\/strong> La matriz inicial, en este caso, permanece aproximadamente igual a la \u00faltima matriz de la primera fase. La l\u00ednea de la funci\u00f3n objetivo debe ser modificada solo por la del problema inicial y recalcular la l\u00ednea Z (de la misma manera que en la primera tabla de la fase 1).<\/li>\n<\/ul>\n\n<p>La condici\u00f3n de parada es la misma que en el m\u00e9todo Simplex. Es decir, cuando en la l\u00ednea del indicador ninguno de los valores de los costos reducidos es negativo (porque estamos en el caso de una maximizaci\u00f3n).<\/p>\n\n<p>El simplex anterior da para la soluci\u00f3n \u00f3ptima Z = 0 con el vector (0, 19\/3, 0, 20\/3, 0). Eso quiere decir que se puede prescindir de la variable artificial y que la soluci\u00f3n encontrada est\u00e1 en el espacio de definici\u00f3n del problema inicial (ya que X5 no interviene y que est\u00e1 fuera de base). La soluci\u00f3n final da el siguiente simplex:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7526 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/12\/lineaire104.png\" alt=\"origen no factible degenerado simplex m\u00e9todo big M variable artificial\" width=\"253\" height=\"86\" title=\"\"><\/figure>\n\n<p>El \u00faltimo paso de la fase 1 consiste en tomar la funci\u00f3n objetivo inicial (aqu\u00ed -2X1 - X2) y reemplazar todas las variables base con variables no base (aqu\u00ed X2 y X4 est\u00e1n en la base, X1 y X3 est\u00e1n fuera de las bases).<\/p>\n\n<p>Tenemos para la primera restricci\u00f3n X2 = 19\/3 - 2 \/ 3X1 + 1 \/ 3X3, por lo tanto, podemos reescribir la funci\u00f3n objetivo por: Z = - 4 \/ 3X1 - 1 \/ 3X2 -19\/3.<\/p>\n\n<p>A partir de este punto, todas las iteraciones, hasta llegar a la soluci\u00f3n \u00f3ptima del problema, no muestran diferencia con el m\u00e9todo Simplex.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-du-simplexe\"><\/span>Algoritmo simplex<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Aqu\u00ed est\u00e1 el algoritmo simplex revisado:<\/p>\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7386 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/algorithme.png\" alt=\"origen no factible simplex degenerado m\u00e9todo big M artificial variable simplex bif\u00e1sico\" width=\"643\" height=\"910\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/algorithme.png 643w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/algorithme-212x300.png 212w\" sizes=\"(max-width: 643px) 100vw, 643px\" \/><\/figure>\n\n<p>\u00a0<\/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>Programaci\u00f3n Lineal P\u00e1gina principal Wiki M\u00e9todo Big M Cuando el s\u00edmplex tiene variables artificiales, es posible que no encuentre soluci\u00f3n\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-6827","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6827","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=6827"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6827\/revisions"}],"predecessor-version":[{"id":17912,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/6827\/revisions\/17912"}],"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=6827"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}