{"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\/en\/linear-programming-2\/lp-method-du-grand-m\/","title":{"rendered":"LP: large M method"},"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\/en\/linear-programming-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\">Linear programming<\/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\/en\/\">\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\">Home page<\/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\">Contents<\/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=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/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\/en\/linear-programming-2\/lp-method-du-grand-m\/#Methode-du-grand-M\" >Big M method<\/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\/en\/linear-programming-2\/lp-method-du-grand-m\/#Pourquoi-une-variable-artificielle\" >Why an artificial variable?<\/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\/en\/linear-programming-2\/lp-method-du-grand-m\/#Construction-de-la-Phase-1\" >Construction of Phase 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\/en\/linear-programming-2\/lp-method-du-grand-m\/#Phase-2\" >Phase 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\/en\/linear-programming-2\/lp-method-du-grand-m\/#Algorithme-du-simplexe\" >Simplex algorithm<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methode-du-grand-M\"><\/span>Big M method<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>When the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">simplex<\/a> has artificial variables, it is possible not to find an obvious starting solution (test if the origin is in the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-solutions-and-realizable-domain\/\">definition field<\/a>). In this case, a starting solution must be found using the big M method.<\/p>\n\n<p>This method computes an auxiliary problem before solving the simplex of the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear program<\/a>, which is why it is called a two-phase simplex.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Pourquoi-une-variable-artificielle\"><\/span>Why an artificial variable?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Before explaining how to obtain a solution to start the simplex, it is important to understand why it is necessary to add an artificial variable in addition to the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-origin-unrealizable\/\">slack variable<\/a>.<\/p>\n\n<p>Take as an example the following linear program:<\/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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"175\" height=\"80\" title=\"\"><\/figure>\n\n<p>Let&#039;s add the variance variables:<\/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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"250\" height=\"80\" title=\"\"><\/figure>\n\n<p>The simplex starts by taking the base variables at zero, so with the following vector (0, 0, -19, 32). This is impossible because X3 cannot take a negative value. This is why a new variable must be added, which will therefore be 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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"276\" height=\"83\" title=\"\"><\/figure>\n\n<p>Here the vector (0, 0, 0, 19, 32) is a feasible solution. But since it is an artificial variable, it must be possible to remove it from the Simplex in order to be able to find a global solution. It is therefore necessary that X5 = 0. To check if this is possible, we are looking to minimize X5.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Construction-de-la-Phase-1\"><\/span>Construction of Phase 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>We prepare in a similar way to the initial table of the Simplex method, but with some differences. By taking the previous example, we try to solve the following problem:<\/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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"270\" height=\"80\" title=\"\"><\/figure>\n\n<p>We know that only X4 and X5 are in the base, so the first step is to express the objective function with the non-base variables (here X1, X2, X3). In the example, this is possible thanks to the first constraint.<\/p>\n\n<p>The first step is to solve the following linear program:<\/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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"237\" height=\"72\" title=\"\"><\/figure>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Phase-2\"><\/span>Phase 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The second phase of the Two-Phase method is developed exactly like the Simplex method, except that before starting the iterations it is necessary to remove the columns corresponding to the artificial variables, and to reconstruct the original table.<\/p>\n\n<ul class=\"wp-block-list\">\n<li><strong>Delete the columns of artificial variables:<\/strong> If we have come to the conclusion that the initial problem has a solution, we need to prepare our table for the second phase. This step is very simple, you just have to delete the columns corresponding to the artificial variables.<\/li>\n<li><strong>Reconstruction of the initial table:<\/strong> The initial array, in this case, remains roughly equal to the last array of the first phase. The line of the objective function should be modified only by that of the initial problem and recalculate the line Z (in the same way as in the first table of phase 1).<\/li>\n<\/ul>\n\n<p>The stopping condition is the same as in the Simplex method. In other words, when in the indicator line none of the values of the reduced costs is negative (because we are in the case of a maximization).<\/p>\n\n<p>The previous simplex gives for optimal solution Z = 0 with the vector (0, 19\/3, 0, 20\/3, 0). That means that it is possible to do without the artificial variable and that the solution found is in the space of definition of the initial problem (since X5 does not intervene and that it is out of base). The final solution gives the following 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=\"non-feasible origin degenerate simplex big M method artificial variable\" width=\"253\" height=\"86\" title=\"\"><\/figure>\n\n<p>The last step of phase 1 consists of taking the initial objective function (here -2X1 - X2) and replacing all the base variables with non-base variables (here X2 and X4 are in the base, X1 and X3 are outside the bases ).<\/p>\n\n<p>We have for the first constraint X2 = 19\/3 - 2 \/ 3X1 + 1 \/ 3X3, we can therefore rewrite the objective function by: Z = - 4 \/ 3X1 - 1 \/ 3X2 -19\/3.<\/p>\n\n<p>From this point, all the iterations, until reaching the optimal solution of the problem, show no difference with the Simplex method.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-du-simplexe\"><\/span>Simplex algorithm<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Here is the revisited simplex algorithm:<\/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=\"non-feasible origin degenerate simplex big M method artificial variable two-phase simplex\" 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>Linear programming Wiki home page Big M method When the simplex has artificial variables, it is possible not to find a solution \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\/en\/wp-json\/wp\/v2\/pages\/6827","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=6827"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6827\/revisions"}],"predecessor-version":[{"id":17912,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6827\/revisions\/17912"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/486"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=6827"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}