{"id":1392,"date":"2016-02-04T16:12:57","date_gmt":"2016-02-04T15:12:57","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1392"},"modified":"2022-12-03T22:58:51","modified_gmt":"2022-12-03T21:58:51","slug":"stepping-stone","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/","title":{"rendered":"Stepping stone"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1392\" class=\"elementor elementor-1392\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-9f582aa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"9f582aa\" 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-16d7596\" data-id=\"16d7596\" 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-3f861ec elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"3f861ec\" 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\/planning-problem\/\">\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\"> Planning problem<\/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-05327a5\" data-id=\"05327a5\" 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-8e4ddf1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"8e4ddf1\" 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-4a94bce\" data-id=\"4a94bce\" 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-ea43ea1 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ea43ea1\" 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:\/\/businessjargons.com\/stepping-stone-method.html\" 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-523203c4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"523203c4\" 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-a148bb2\" data-id=\"a148bb2\" 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-19969ff7 elementor-widget elementor-widget-text-editor\" data-id=\"19969ff7\" 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\/planning-problem\/stepping-stone\/#Stepping-Stone\" >Stepping Stone<\/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\/planning-problem\/stepping-stone\/#Stepping-stone-%E2%80%93-Etape-1-obtention-dune-solution-de-base\" >Stepping stone - Step 1: obtaining a base solution<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Par-coin-Nord-Ouest\" >By Northwest corner<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Par-la-methode-des-minimums\" >By the minimum method<\/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\/planning-problem\/stepping-stone\/#Par-la-methode-de-Vogel-ou-Balas-Hammer\" >By the Vogel (or Balas-Hammer) method<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Stepping-stone-%E2%80%93-Etape-2-calcul-des-potentiels\" >Stepping stone - Step 2: calculating the potentials<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Stepping-stone-%E2%80%93-Etape-3-calcul-de-la-variation-de-cout-unitaire\" >Stepping stone - Step 3: calculation of the unit cost variation<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Stepping-stone-%E2%80%93-Etape-4-calcul-de-la-quantite-maximale-du-flot\" >Stepping stone - Step 4: calculating the maximum amount of the flow<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/complex-systems-ai.com\/en\/planning-problem\/stepping-stone\/#Stepping-stone-%E2%80%93-Etape-5-mise-a-jour-du-tableau\" >Stepping stone - Step 5: update the table<\/a><\/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\/planning-problem\/stepping-stone\/#Aparte\" >Aside<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Stepping-Stone\"><\/span>Stepping Stone<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The problem solved by the Stepping Stone algorithm is as follows:<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Are different origins, proposing a certain quantifiable offer; and destinations requiring a certain quantity; a transport cost is assigned for each origin-destination combination; how to best meet demand at the lowest cost?<\/div>\n\n<p>Let&#039;s take an example to show how the algorithm works. Consider four origins and five applicants with costs and quantity according to the table:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">vs<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">6<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">16<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\u00a0The idea of stepping stone is to start from a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">basic fix<\/a> feasible (non-optimal) in order to iteratively improve it until a non-optimizable solution is obtained. There is no better solution, so it is optimal. It is important to check that the supply and the demand are equal, if this is not the case it is necessary to add a fictitious demand of significant cost for each offer.<\/div>\n\n<p>It is possible to perform the algorithm using two tables (one for the costs, one for the flows). It is also possible to display the two values in the same box since only the flow will vary.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Stepping-stone-%E2%80%93-Etape-1-obtention-dune-solution-de-base\"><\/span>Stepping stone - Step 1: obtaining a base solution<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Par-coin-Nord-Ouest\"><\/span>By Northwest corner<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>The principle is simple:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">1. Select the northwest corner cell and assign as many units as possible (minimum requirements) available for supply and demand.<br \/>2. Adjust the supply and demand values in the allocation of the respective rows and columns<br \/>3. If the supply of the first row is exhausted, go down to the first cell of the next row.<br \/>4. If the demand for the first cell is satisfied, move horizontally to the next cell.<br \/>5. If for a cell supply equals demand, the next allocation can be made in the cell either in the next row or column.<br \/>6. Continue the procedure until the total amount available is fully allocated to cells, as needed.<\/div>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">13<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<p>The total cost of the basic solution is: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395.<\/p>\n\n<p>In many cases it is not possible to meet the demand, this method although fast only gives an unrealistic feasible solution. Here we do not represent the costs but the flows f<sub>ij<\/sub> of the offer <strong>i<\/strong> to the request <strong>j<\/strong>.<\/p>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Par-la-methode-des-minimums\"><\/span>By the minimum method<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">1. Identify the box with the minimum unit transport cost c<sub>ij<\/sub>.<br \/>2. If the minimum cost is not unique, you are free to choose any cell.<br \/>3. Choose the value of x as much as possible<sub>ij<\/sub> corresponding, depending on capacity and requirement constraints.<br \/>4. Repeat steps 1 to 3 until all restrictions are satisfied.<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6333 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/transport3.png\" alt=\"algorithm stepping stone planning problem balas-hammer vogel\" width=\"583\" height=\"181\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/transport3.png 583w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/transport3-300x93.png 300w\" sizes=\"(max-width: 583px) 100vw, 583px\" \/><\/figure>\n<\/div>\n\n<h3 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Par-la-methode-de-Vogel-ou-Balas-Hammer\"><\/span>By the Vogel (or Balas-Hammer) method<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n<p>This method makes use of the transport difference between the two best choices for supply and demand. The basic solution is often very close to the optimal solution.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>1. Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the lowest unit cell cost in the same row (column).<\/p>\n<div>2. Identify the row or column with the greatest penalty cost. Break ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, cross out only one of the two and allocate a supply or demand of zero to the remaining one.<\/div>\n<div>\u00a0<\/div>\n<p>3.<\/p>\n<ul>\n<li>If there is exactly one row or column left with zero supply or demand, stop.<\/li>\n<li>If there is a row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the minimums method. Stop.<\/li>\n<li>If all the rows and columns that have not been crossed out have a supply or demand (remaining) of zero, use the minimum method. Stop.<\/li>\n<\/ul>\n<p>In all other cases, go to step 1.<\/p>\n<\/div>\n\n<p>The first iteration of the method gives: D<sub>O1<\/sub> = 4, D<sub>O2<\/sub> = 3, D<sub>O3<\/sub> = 1, D<sub>O4<\/sub> = 3, D<sub>D1<\/sub> = 1, D<sub>D2<\/sub> = 5, D<sub>D3<\/sub> = 9, D<sub>D4<\/sub> = 1, D<sub>D5<\/sub> = 2. Column D<sub>3<\/sub> has the largest cost difference, the smallest cost is 1, so we saturate the intersection O<sub>1<\/sub> with<sub>3<\/sub> with the min flow (12, 15). The O offer<sub>1<\/sub> is therefore saturated.<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">X<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">X<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">X<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">X<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<p>For the new cost difference calculation, we will no longer take into account the values in row O<sub>1<\/sub>. We get after 5 iterations to the following configuration:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">10<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Stepping-stone-%E2%80%93-Etape-2-calcul-des-potentiels\"><\/span>Stepping stone - Step 2: calculating the potentials<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Once you have a basic solution, the idea is to modify the solution to make it better. That is to say, it is necessary to modify the flows. For this, we will choose a flow that lowers the total cost of transport the most. The first step in determining this flow is to calculate the potentials. The potentials are calculated ONLY on the cells with a non-zero flow!<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Let us set a potential of 0 to the line with the cell with the highest cost flow. Here we will take the basic solution provided by the Northwest corner method: p<sub>O1<\/sub> = 0.<\/div>\n\n<p>We can then calculate other potentials. The potentials are calculated step by step. In our case, we have calculated the potential of row 1 from c<sub>12<\/sub>, it is therefore possible to calculate the potential of column 1 or column 2.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\u00a0To calculate the potentials we apply the following rule: p<sub>D<\/sub> + p<sub>O<\/sub> = c<sub>ij\u00a0<\/sub>which gives N equations with N unknowns.<\/div>\n\n<p>Let&#039;s take the example again: for column 1, p<sub>D1<\/sub> = c<sub>11<\/sub> + P<sub>O1<\/sub> = 7. For row 2, p<sub>D2<\/sub> = c<sub>12<\/sub> + P<sub>O1<\/sub> = 12. The same for the other rows and columns: p<sub>O2<\/sub>\u00a0 = p<sub>D2<\/sub> - vs<sub>22<\/sub> = 12 -3 = 9; p<sub>D3<\/sub> = 21; p<sub>03<\/sub> = 11; P<sub>D4<\/sub> = 23: P<sub>O4<\/sub> = 12; P<sub>D5<\/sub> = 28.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Stepping-stone-%E2%80%93-Etape-3-calcul-de-la-variation-de-cout-unitaire\"><\/span>Stepping stone - Step 3: calculation of the unit cost variation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">For each cell with zero flow, we calculate v<sub>ij<\/sub> by adding the potential of the associated origin to the unit cost of the box and subtracting the potential of the corresponding destination: v<sub>ij<\/sub> = c<sub>ij<\/sub> - p<sub>Oi<\/sub> - p<sub>Dj<\/sub>.<\/div>\n\n<p>We get the following table:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">v<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">p<sub>O<\/sub><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-20<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-18<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-19<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">17<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">12<\/td>\n<td align=\"center\" valign=\"top\">15<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">-10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">23<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">p<sub>D<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">21<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">23<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">28<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Stepping-stone-%E2%80%93-Etape-4-calcul-de-la-quantite-maximale-du-flot\"><\/span>Stepping stone - Step 4: calculating the maximum amount of the flow<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">We now know the variation in the cost of a unit depending on the origin and destination compared to the initial solution. We must now determine the flow circuits allowing to reduce the total cost. This calculation is done only for the v<sub>ij<\/sub> negative.<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\u00a0To fill an empty cell, you must empty a full cell. When looking for a circuit (a \u201cloop\u201d), we must make sure that a cell with a flow always succeeds the last cell chosen in the circuit. Thus, the circuit is made up of an empty box and full boxes. The maximum flow that can be moved to fill the empty cell is the minimum of the flows of the non-zero cells.<\/div>\n\n<p>For example for box 0<sub>1<\/sub>-D<sub>3<\/sub>, we take the following circuit f<sub>13<\/sub> -&gt; f<sub>12<\/sub> -&gt; f<sub>22<\/sub> -&gt; f<sub>23<\/sub> -&gt; f<sub>13<\/sub> with the minimum flow of 2. We obtain the following table:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">p<sub>O<\/sub><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">2<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">0<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">9<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">p<sub>D<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">7<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">21<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">23<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">28<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<p>By multiplying f<sub>ij<\/sub>* v<sub>ij<\/sub>, we know the variation of the total cost by the modification by the flow f<sub>ij<\/sub>. We choose the box with the greatest f<sub>ij<\/sub>* v<sub>ij<\/sub>, here the O box<sub>1<\/sub>-D<sub>3<\/sub><\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Stepping-stone-%E2%80%93-Etape-5-mise-a-jour-du-tableau\"><\/span>Stepping stone - Step 5: update the table<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The flow update calculation is done by the \u201c+ -\u201d rule without counting the return to the original box. So in the circuit: f<sub>13<\/sub> + = 2, f<sub>12<\/sub> - = 2, f<sub>22<\/sub> + = 2 and f<sub>23<\/sub> - = 2. The table is as follows:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2-2 = \u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">0+2 = 2<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">9+2 = 11<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">2-2 = \u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">13<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">4<\/td>\n<td align=\"center\" valign=\"top\">4<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<p>The total cost of the basic solution is: 10 * 7 + 2 * 12 + 9 * 3 + 2 * 12 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 395. The cost of this solution is: 10 * 7 + 11 * 3 + 2 * 1 + 13 * 10 + 12 + 4 * 11 + 4 * 16 = 355. Let the basic solution minus f<sub>13<\/sub>* v<sub>13<\/sub> = 2*20 = 40.<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">We repeat steps 2 to 5 until no more v<sub>ij<\/sub> negative. We know then that there is no circuit to reduce the total cost, so we have an optimal solution.<\/div>\n\n<p>In our example, we finally have the following table:<\/p>\n\n<div class=\"standard\" style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">f<sub>ij<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">D<sub>5<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">offer<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>1<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">12<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">12<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>2<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">11<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>3<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">10<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">14<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">O<sub>4<\/sub><\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">\u2013<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">5<\/td>\n<td align=\"center\" valign=\"top\">\u2013<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">8<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">demand<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">10<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">11<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">15<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">5<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div class=\"plain_layout\">4<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n\n<p>With a total cost of: 10 * 8 + 11 * 3 + 12 * 1 + 3 * 17 + 5 * 11 + 4 * 7 = 259.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Aparte\"><\/span>Aside<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>We talk about flow because the problem is solved as a min cost flow problem (<a href=\"https:\/\/complex-systems-ai.com\/en\/maximum-flow-problem\/\">maximum flow<\/a> at minimum cost) in a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> complete bipartite \u2013 a set of sources connected to a set of sinks (hence the \u201c+ \u2013\u201d rule since we go once in the direction of the flow then in the opposite direction in the chosen circuit).<\/p>\n<p><img decoding=\"async\" class=\"alignnone wp-image-9824 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Stepping-Stone-Method-Flowchart72.png\" alt=\"algorithm stepping stone planning problem balas-hammer vogel\" width=\"850\" height=\"673\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Stepping-Stone-Method-Flowchart72.png 850w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Stepping-Stone-Method-Flowchart72-300x238.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Stepping-Stone-Method-Flowchart72-768x608.png 768w\" sizes=\"(max-width: 850px) 100vw, 850px\" \/><\/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>Planning problem Home page Wiki Stepping Stone The problem solved by the Stepping stone algorithm is the following: Given different origins, proposing a \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":868,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1392","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1392","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=1392"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1392\/revisions"}],"predecessor-version":[{"id":17919,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1392\/revisions\/17919"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/868"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1392"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}