{"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\/en\/linear-programming-2\/simplex-method-2\/","title":{"rendered":"Simplex method"},"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\/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-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\/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-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\">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\/simplex-method-2\/#Methode-du-simplexe\" >Simplex 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\/simplex-method-2\/#Methode\" >Method<\/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\/simplex-method-2\/#Exemple-de-resolution\" >Example resolution<\/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\/en\/linear-programming-2\/simplex-method-2\/#Etape-1-Ecriture-sous-forme-standard-et-solution-de-base\" >Step 1: Write in Standard Form and Basic Solution<\/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\/en\/linear-programming-2\/simplex-method-2\/#Aparte-degenerescence-du-simplexe\" >Aside: degeneration of the 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\/en\/linear-programming-2\/simplex-method-2\/#Etape-2-3-election-de-la-variable-entrante-et-sortante-de-la-base\" >Step 2-3: election of the input and output variable of the database<\/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\/en\/linear-programming-2\/simplex-method-2\/#Etape-3-actualisation-du-tableau\" >Step 3: refresh the table<\/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\/en\/linear-programming-2\/simplex-method-2\/#STOP-conditions-darret\" >STOP: stop conditions<\/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\/en\/linear-programming-2\/simplex-method-2\/#Resume\" >Abstract<\/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\/en\/linear-programming-2\/simplex-method-2\/#Cas-particuliers\" >Special cases<\/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\/en\/linear-programming-2\/simplex-method-2\/#Exemple\" >Example<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Methode-du-simplexe\"><\/span>Simplex method<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The method <strong>of the simplex<\/strong> was introduced by <strong>George Danzig<\/strong> from 1946. He is a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> solving linear optimization problems.<\/p>\n\n<p>It consists in minimizing a linear function of <strong>not<\/strong> real variables,<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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=\"dantzig simplex method linear programming incoming variable outgoing variable\" width=\"180\" height=\"24\" title=\"\"><\/figure>\n\n<p>where, on a set defined by means of affine (or linear) constraints of equality and inequality. THE&#039;<em>eligible set<\/em> of the problem is therefore a convex polyhedron.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Methode\"><\/span>Method<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The simplex method is an iterative method that traverses the vertices of the convex polyhedron until the objective function can no longer be improved. The resolution process is as follows:<\/p>\n\n<ol class=\"wp-block-list\">\n<li>The problem is written under <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-canonical-form-and-standard-form\/\">standard form<\/a>.<\/li>\n<li>A solution is found.<\/li>\n<li>Find the pivot column.<\/li>\n<li>Find the line of the pivot and perform the Gauss method<\/li>\n<\/ol>\n\n<ul class=\"wp-block-list\">\n<li>STOP. Optimal solution found or no solution possible.<\/li>\n<\/ul>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-de-resolution\"><\/span>Example resolution<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Consider the following problem to apply the simplex method:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Maximize<\/td>\n<td><em>Z = 3x + 2y<\/em><\/td>\n<\/tr>\n<tr>\n<td>under the constraints:<\/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>Step 1: Write in Standard Form and Basic Solution<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>We transform the inequalities into equations with the addition of <em>variables<\/em>.<\/p>\n\n<p>For this, we introduce a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-origin-unrealizable\/\">slack variable<\/a> (x<sub>3<\/sub>, x<sub>4<\/sub>, x<sub>5<\/sub>) in each of the constraints of the form \u2264, to transform them into equalities (see lesson on the standard form):<\/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 x<sub>1<\/sub> + x<sub>2<\/sub> + x<sub>5<\/sub> = 24<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n\n<p>Then, we adjust the objective function to zero: 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. That is to say that the canonical program variables are at zero, the deviation variables are equal to the element on the right (b). From now on, it is possible to initialize the table of the simplex method.<\/p>\n\n<p>The initial table of the simplex method is made up of all the coefficients of the decision variables of the original problem and the difference variables.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>1st iteration<\/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>Based<\/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>Aside: degeneration of the simplex<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>A feasible basic solution is said to be degenerate if at least one of the basic variables is zero. If during the simplex algorithm, no basis encountered is degenerated, then the algorithm ends in a finite number of iterations. If there exists a degenerate base, then one can meet a possible cycling of the algorithm: one finds a base already met and one loops indefinitely. To treat cases of degeneration, we can apply the rule of Bland (1977) which ensures that the algorithm stops in a finite number of iterations. When several variables are likely to enter or leave the base, we always choose the one with the smallest index.<\/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>Step 2-3: election of the input and output variable of the database<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>First, we establish the variable that comes into the base. For this purpose, we choose the column whose value in the row <strong>Z<\/strong> is the lowest of all the negatives. In this case, that would be the variable x<sub>1<\/sub> of coefficient -3. The column of the variable that enters the base that we call <em>pivot column<\/em> (in green).<\/p>\n\n<p>This variable is chosen because its impact on the value of Z is the greatest (greatest gradient). Entering this variable in the base consists in finding a solution in the space of solutions by following the gradient of this variable. In the following diagram, the ordinate has the greatest gradient compared to the solution Z = 0, we will therefore follow its axis (consider max z = x<sub>B<\/sub>) until you can no longer improve the solution.<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" width=\"259\" height=\"256\" title=\"\"><\/figure>\n\n<p>Once the incoming variable is obtained in the database, we determine which will be the outgoing variable. We make the decision on the basis of a simple calculation: divide each independent term (column b) between the corresponding element of the <em>pivot column<\/em>, provided that both elements are strictly positive (greater than zero).<\/p>\n\n<p>This amounts to considering that our outgoing variable will make a Gaussian pivot with the incoming variable. In other words, the incoming variable will take a non-zero value while the outgoing variable will become zero.<\/p>\n\n<p>We opt for the line whose result is minimal. Indeed, this calculation makes it possible to know up to what value the incoming variable can be increased. the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear program<\/a> having constraints, it is not possible to exceed the most \u201cconstraining\u201d constraint, ie limiting the most the value of the incoming variable.<\/p>\n\n<p><em>In this example: Cb: = 18\/2, 42\/2 and 24\/3.<br \/><\/em>If there would be an element lower than or equal to zero, this quotient is not carried out. When all the elements of the <em>pivot column<\/em> are of this condition we would have fulfilled the stop condition and the problem would have a solution without bounded part.<\/p>\n\n<p>The term of the<em> pivot column<\/em> that had resulted in the smallest non-zero positive quotient in the previous division indicates the row of the gap variable that comes out of base. In this case, it turns out x<sub>5<\/sub>, of coefficient 3. This line is called <em>line<\/em> <em>pivot<\/em> (in red).<\/p>\n\n<p>The intersection of the <em>pivot line<\/em> and the <em>pivot column<\/em> highlights <em>the pivot element<\/em>, in this case the 3.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Etape-3-actualisation-du-tableau\"><\/span>Step 3: refresh the table<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>One calculates the new coefficients of the table in the following way (Gaussian pivot):<\/p>\n\n<ul class=\"wp-block-list\">\n<li>In the pivot element row each new element is calculated as: <em>Pivot line element = Old pivot \/ Pivot line element<\/em><\/li>\n<li>In the pivot column: 0 except the pivot at 1.<\/li>\n<li>In the remaining lines each element is calculated (cross product): <em>New row element = Old row element - (Old pivot line projection * Old pivot column projection \/ Old pivot element).<\/em><\/li>\n<\/ul>\n\n<p>We show the calculations for line x<sub>4 <\/sub>:<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td>Old line 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>projection<\/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>pivot<\/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>bECOMES<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<td>=<\/td>\n<\/tr>\n<tr>\n<td>New line 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>The table corresponding to this second iteration is (note that x<sub>5<\/sub> is out and that x<sub>1<\/sub> has returned to its place, moreover, the objective function is no longer expressed in x<sub>1<\/sub> but in x<sub>5<\/sub>, and its value is 24):<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>Start iteration 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>Based<\/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: stop conditions<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>If the objective is maximization, when in the last line (indicator line) there is no negative value among the costs (there is no variable with a gradient improving the solution), we obtain the stop condition .<\/p>\n\n<p>The value of <strong>Z<\/strong> (column <strong>b<\/strong>) is the optimal solution to the problem.<\/p>\n\n<p>When this condition is not fulfilled, the processes are re-executed iteratively.<\/p>\n\n<figure class=\"wp-block-table\">\n<table>\n<thead>\n<tr>\n<th>4th iteration start<\/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>Based<\/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>We discover that in the last line all the coefficients are positive. The optimal solution is: 33 with the solution vector (12, 3, 0, 0, 3). The solution vector is determined by the value of <strong>b<\/strong> on the rows of basic variables. Note that x<sub>5<\/sub> = 3, i.e. the constraint 3 (containing the difference variable x<sub>5<\/sub>) is not saturated with a 3 margin.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resume\"><\/span>Abstract<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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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>Special cases<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<ul class=\"wp-block-list\">\n<li><strong>Infinite solutions:<\/strong> when the simplex stops and non-base variables have a value of 0 in row Z, it means that there is an infinite solution. To know the limits of the hyperplane (or the segment) of solutions, it suffices to recompute the simplex by entering the variable (s) in the base.<\/li>\n<li><strong>No solution :<\/strong> with the method of <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-method-du-grand-m\/\">big M<\/a>, it is possible that the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-solutions-and-realizable-domain\/\">definition field<\/a> be empty. In this case, during the calculation of the large M certain artificial variables have a non-zero value.<\/li>\n<li><strong>Choice of the input variable:<\/strong> when there is a choice among the incoming variables (same value), a basic variable of the linear program must be chosen as a priority.<\/li>\n<li><strong>Choice of the outgoing variable:<\/strong> when there is a choice among the outgoing variables, the artificial variables are chosen first, then the excess variables, then the difference variables and finally the basic variables.<\/li>\n<li><strong>Degenerate solution:<\/strong> if the optimal solution has zero base variables, then it is said to be degenerate, this is the case when there are more base variables than there are constraints.<\/li>\n<\/ul>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Example<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Note that sometimes the table is written with the value of -Z with the coefficients of c, in this case the optimal solution is obtained when all the coefficients are negative. Consider the following linear program:<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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>First iteration:<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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>Which gives after pivot:<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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>Here is the second iteration before and after pivot:<\/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=\"dantzig simplex method linear programming incoming variable outgoing variable\" 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>All the terms of -Z are negative, so we have an optimal solution (0, 250, 0, 200, 500, 0, 100, 0), first and third constraint are not saturated (deviation variables at 500 and at 100); the objective function is worth 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>Linear Programming Homepage Wiki Simplex method The simplex method was introduced by George Dantzig from 1946. He is a \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\/en\/wp-json\/wp\/v2\/pages\/465","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=465"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/465\/revisions"}],"predecessor-version":[{"id":17907,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/465\/revisions\/17907"}],"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=465"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}