{"id":6851,"date":"2019-04-10T13:17:20","date_gmt":"2019-04-10T12:17:20","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=6851"},"modified":"2022-12-03T23:02:05","modified_gmt":"2022-12-03T22:02:05","slug":"ecarts-complementaires","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/complementary-deviations\/","title":{"rendered":"Additional deviations"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"6851\" class=\"elementor elementor-6851\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-866af3c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"866af3c\" 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-d8b5263\" data-id=\"d8b5263\" 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-6486758 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"6486758\" 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-507f543\" data-id=\"507f543\" 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-b1a4a39 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b1a4a39\" 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-3abf559\" data-id=\"3abf559\" 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-05c0bdf elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"05c0bdf\" 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-7441afdc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7441afdc\" 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-40a84bbb\" data-id=\"40a84bbb\" 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-70f786d3 elementor-widget elementor-widget-text-editor\" data-id=\"70f786d3\" 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<p><\/p>\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\/complementary-deviations\/#Ecarts-complementaires\" >Additional deviations<\/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\/complementary-deviations\/#Processus\" >Process<\/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\/complementary-deviations\/#Exemple-1\" >Example 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\/complementary-deviations\/#Exemple-2\" >Example 2<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Ecarts-complementaires\"><\/span>Additional deviations<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The complementary deviations are usable if the primal is realizable and the solution is bounded, the dual is realizable and its solution is also bounded. If the values of the primal and dual solutions are equal, they are optimal for their linear program, we speak of <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/dual-program\/\">strong duality<\/a>. Sometimes it is not possible to find a solution, or not useful to calculate it. The primal and dual program being linked, it is possible to deduce a solution of the reciprocal program using the complementary deviations.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Processus\"><\/span>Process<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>One of the main theorems of the theory of duality in <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear programming<\/a> is the theorem of complementary deviations. This theorem allows us to find the optimal solution of the dual problem when we know the optimal solution of the primal problem (and vice versa) by solving a system of equations formed by the decision variables (primal and dual) and the constraints (primal and dual model).<\/p>\n<p><\/p>\n<p>The importance of this theorem is that it makes it easier to solve linear optimization models, allowing you to find the easiest model to deal with (from the point of view <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithmic<\/a>). The process is as follows:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Find a workable solution on the primal.<\/li>\n<li>If this is the case, note the non-zero variables (this implies that the constraint of the dual is saturated) and the constraints with play (which implies that the variable of the dual is zero).<\/li>\n<li>Solve the system of equations<\/li>\n<li>Check the strong duality, ie the solution of the primal is identical to that of the dual. In this case the feasible solution is an optimum.<\/li>\n<\/ol>\n<p><\/p>\n<p><strong>Version I<\/strong>. Let x * and y * be the solutions of the primal and the dual. These two solutions are optimal if and only if:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>for any j from 1 to n\n<ul>\n<li>either the constraint j of the dual is saturated<\/li>\n<li>or x *<sub>j<\/sub>=0<\/li>\n<li>or both<\/li>\n<\/ul>\n<\/li>\n<li>for all i from 1 to m\n<ul>\n<li>either the constraint i of the primal is saturated<\/li>\n<li>or y *<sub>i<\/sub>=0<\/li>\n<li>or both<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><\/p>\n<p>The second version of the complementary deviations makes it possible to better understand how to find a solution in the reciprocal program. For this it must be assumed that the two conditions of version I are always true.<\/p>\n<p><\/p>\n<p><strong>Version II<\/strong>. A solution x of the primal is optimal if and only if there exists a vector y * such that:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>y * is eligible<\/li>\n<li>if x<sub>j<\/sub>&gt; 0 then the j-th constraint of the dual is saturated<\/li>\n<li>if the i-th constraint of the primal is not saturated then y *<sub>i<\/sub>=0.<\/li>\n<li>and conversely between the dual and the primal.<\/li>\n<\/ul>\n<p><\/p>\n<p>Thus, once a solution is found in the reciprocal program, all that remains is to verify the strong duality of the system.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-1\"><\/span>Example 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Consider the following linear programming model with 2 variables whose optimal solution is X = 14\/5 and Y = 8\/5 with the optimal value V = 20.8.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6791 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision6.png\" alt=\"simplex method complementary slackness complementary gaps\" width=\"123\" height=\"78\" title=\"\"><\/figure>\n<p><\/p>\n<p>The dual model associated with the primal model is:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6792 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision7.png\" alt=\"simplex method complementary slackness complementary gaps\" width=\"129\" height=\"87\" title=\"\"><\/figure>\n<p><\/p>\n<p>Then, the theorem of complementary deviations shows the following relations:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img decoding=\"async\" class=\"alignnone wp-image-6793 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision8.png\" alt=\"simplex method complementary slackness complementary gaps\" width=\"124\" height=\"90\" title=\"\"><\/figure>\n<p><\/p>\n<p>As we know, X = 14\/5 and Y = 8\/5 (primal optimal solution). If we replace these values of X and Y in the third and fourth equations (because both constraints of the primal are saturated and we cannot conclude anything about equations 1 and 2), we generate a system of equations in terms of A and of B whose solution corresponds to A = 6\/5 and B = 2\/5. If we then evaluate the objective function in the dual problem of this solution, we get: V = 12 (6\/5) +16 (2\/5) = 20.8, which is similar to the optimal value of the primal problem ( strong duality).<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple-2\"><\/span>Example 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Consider the following problem:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6794 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision9.png\" alt=\"simplex method complementary slackness complementary gaps\" width=\"418\" height=\"119\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision9.png 418w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision9-300x85.png 300w\" sizes=\"(max-width: 418px) 100vw, 418px\" \/><\/figure>\n<p><\/p>\n<p>The solution to this problem is {42, 0, 10.4, 0, 0.4}. The dual problem is the following:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6795 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision10.png\" alt=\"simplex method complementary slackness complementary gaps\" width=\"359\" height=\"133\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision10.png 359w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/03\/decision10-300x111.png 300w\" sizes=\"(max-width: 359px) 100vw, 359px\" \/><\/figure>\n<p><\/p>\n<p>Feasibility test. The first constraint is saturated, no conclusion for y1. The second constraint is not saturated, so y2 = 0. The third constraint is saturated, nothing on y3.<\/p>\n<p><\/p>\n<p>Positive variables. x1 = 0, nothing to conclude. x2&gt; 0, the second constraint of the dual is saturated. x3 = 0, nothing to conclude. x4&gt; 0, the fourth constraint of the dual is saturated.<\/p>\n<p><\/p>\n<p>So, the solution to dual must satisfy: y2 = 0; y1 + y3 = 4; 4y1 + y3 = 1 with {1, 0, 3} as the solution. The values of the primal and dual are equivalent so we have the optimum.<\/p>\n<p><\/p>\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 Complementary gaps Complementary gaps can be used if the primal is realizable and the solution is bounded, the dual \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-6851","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6851","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=6851"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6851\/revisions"}],"predecessor-version":[{"id":17909,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/6851\/revisions\/17909"}],"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=6851"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}