{"id":2132,"date":"2016-02-10T17:08:38","date_gmt":"2016-02-10T16:08:38","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2132"},"modified":"2022-12-03T22:58:55","modified_gmt":"2022-12-03T21:58:55","slug":"programme-dual","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/dual-program\/","title":{"rendered":"Dual program"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2132\" class=\"elementor elementor-2132\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3e16269 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3e16269\" 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-429f330\" data-id=\"429f330\" 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-54c579e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"54c579e\" 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-768458a\" data-id=\"768458a\" 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-e01ec8d elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"e01ec8d\" 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-37e44bd\" data-id=\"37e44bd\" 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-99e86cb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"99e86cb\" 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-64925884 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"64925884\" 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-713d76e8\" data-id=\"713d76e8\" 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-5ace2e03 elementor-widget elementor-widget-text-editor\" data-id=\"5ace2e03\" 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\/dual-program\/#Programme-dual\" >Dual program<\/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\/dual-program\/#Construction-du-programme-dual\" >Construction of the dual program<\/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\/dual-program\/#Dualite-faible-et-dualite-forte\" >Weak duality and strong duality<\/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\/dual-program\/#Interpretation-du-programme-dual\" >Interpretation of the dual program<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Programme-dual\"><\/span>Dual program<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Although the primal program offers a solution by the method of <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">simplex<\/a>, we are only guaranteed not to be able to improve the solution. In order to prove that it is an optimal solution, we must also solve its dual program. This dual program, in addition to guaranteeing whether or not optimality, will also make it possible to analyze the sensitivity of the variables to change.<\/p>\n\n<p>When the primal program has more variables than constraints, then there is no guaranteed solution (as for a system of equations). In this case, it is preferable to go through the dual in order to find a solution.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Construction-du-programme-dual\"><\/span>Construction of the dual program<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>The dual program is a symmetry of the primal program: There is a constraint for each variable of the primal program; and a dual variable for each constraint of the primal program; the coefficients of the primal objective function are elements <strong>b<\/strong> of the dual and vice versa. It should be noted that the dual of the dual is the primal.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img fetchpriority=\"high\" decoding=\"async\" class=\"wp-image-2185 size-full aligncenter\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/primdual.png\" alt=\"dantzig simplex method linear programming duality dual program\" width=\"321\" height=\"231\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/primdual.png 321w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/primdual-300x216.png 300w\" sizes=\"(max-width: 321px) 100vw, 321px\" \/><\/figure>\n<\/div>\n\n<p>For the following special transformation rules, the primal is considered to be under the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-canonical-form-and-standard-form\/\">canonic form<\/a> :<\/p>\n\n<ul class=\"wp-block-list\">\n<li>If the variable i of the primal is positive or zero, then the constraint i of the dual is in its canonical form<\/li>\n<li>If the variable i of the primal is a real number, then the constraint i of the dual is an equality (logical if we consider equality as a combination of \u201cless than or equal\u201d and \u201cgreater or equal\u201d)<\/li>\n<li>If the constraint j of the primal is in canonical form, then the variable j of the dual is positive or zero<\/li>\n<li>If the constraint j of the primal is an equality, then the variable j of the dual is a real number (logical if we consider equality as a combination of \u201cless than or equal\u201d and \u201cgreater or equal\u201d)<\/li>\n<\/ul>\n\n<p>Considering the transformation of a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear program<\/a> in canonical form, the second point and the fourth point are normally not applied during the transformation into dual for the calculation of the Simplex!<\/p>\n\n<p>Here is a summary of the transformation into Dual by the canonical form.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" class=\"alignnone wp-image-2140 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual.png\" alt=\"dantzig simplex method linear programming duality dual program\" width=\"563\" height=\"414\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual.png 563w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual-300x221.png 300w\" sizes=\"(max-width: 563px) 100vw, 563px\" \/><\/figure>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Dualite-faible-et-dualite-forte\"><\/span>Weak duality and strong duality<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p><strong>Low duality<\/strong> : for any solution of the dual and for any solution of the primal, the objective value of the dual z = cx * is greater than or equal to that of the primal w = by *.<\/p>\n\n<p><strong>Strong duality<\/strong> : if the primal has an optimal solution x * then the dual has an optimal solution y * and the objective value of the primal is equal to that of the dual.<\/p>\n\n<p>Since the dual of the dual is the primal, the primal has an optimal solution if and only if the dual has an optimal solution.<\/p>\n\n<p>There is a relation in the solutions of the primal and the dual:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>if a problem has feasible solutions and a bounded domain for the objective function, then so does its dual.<\/li>\n<li>if a problem has feasible solutions and an unbounded domain for the objective function, then its dual has no feasible solution.<\/li>\n<li>if a problem has no feasible solutions, the dual either has an unbounded domain for the objective function, or has no feasible solutions.<\/li>\n<\/ul>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Interpretation-du-programme-dual\"><\/span>Interpretation of the dual program<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-2175 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual4.png\" alt=\"dantzig simplex method linear programming duality dual program\" width=\"496\" height=\"368\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual4.png 496w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/dual4-300x223.png 300w\" sizes=\"(max-width: 496px) 100vw, 496px\" \/><\/figure>\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 Dual program Although the primal program offers a solution by the simplex method, we only have the guarantee \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-2132","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2132","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=2132"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2132\/revisions"}],"predecessor-version":[{"id":17908,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2132\/revisions\/17908"}],"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=2132"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}