{"id":7428,"date":"2019-11-15T17:08:58","date_gmt":"2019-11-15T16:08:58","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=7428"},"modified":"2024-02-11T18:52:16","modified_gmt":"2024-02-11T17:52:16","slug":"ecart-complementaire","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/","title":{"rendered":"5 Dual Corrected Exercises and complementary gap"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"7428\" class=\"elementor elementor-7428\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-a8bdbcb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a8bdbcb\" 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-a6fff5d\" data-id=\"a6fff5d\" 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-96972a8 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"96972a8\" 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-9d2e392\" data-id=\"9d2e392\" 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-b568173 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b568173\" 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-9d012eb\" data-id=\"9d012eb\" 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-445d3bd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"445d3bd\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_du_simplexe\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f38f1cb elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f38f1cb\" 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-f69861a\" data-id=\"f69861a\" 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-a7f8e19 elementor-widget elementor-widget-heading\" data-id=\"a7f8e19\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercices-corriges-sur-le-programme-dual-et-ecart-complementaire\" >Corrected exercises on the dual program and complementary gap<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Tutoriel\" >Tutorial<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercice-1\" >Exercise 1<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercice-2\" >Exercise 2<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercice-3\" >Exercise 3<\/a><\/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\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercice-4\" >Exercise 4<\/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\/linear-programming-2\/lp-dual-et-ecart-complementaire-exercises-solutions\/#Exercice-5\" >Exercise 5<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercices-corriges-sur-le-programme-dual-et-ecart-complementaire\"><\/span>Corrected exercises on the dual program and complementary gap<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-ac5d075 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac5d075\" 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-7cc122e\" data-id=\"7cc122e\" 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-d099cc3 elementor-widget elementor-widget-text-editor\" data-id=\"d099cc3\" 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>This tutorial offers various corrected exercises on the dual program and the complementary deviation algorithm. The exercises are followed by corrections.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter wp-image-11096 size-full\" src=\"http:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/cropped-Capture.png\" alt=\"complementary deviation\" width=\"97\" height=\"97\" title=\"\"><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-132dae3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"132dae3\" 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-1245d8f\" data-id=\"1245d8f\" 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-227a1c3 elementor-widget elementor-widget-heading\" data-id=\"227a1c3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Tutoriel\"><\/span>Tutorial<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-99a712d elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"99a712d\" 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-6b9fde4\" data-id=\"6b9fde4\" 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-fefdea4 elementor-widget elementor-widget-text-editor\" data-id=\"fefdea4\" 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>Consider the following linear program:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7325,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-7325 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire31.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"325\" height=\"102\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire31.png 325w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire31-300x94.png 300w\" sizes=\"(max-width: 325px) 100vw, 325px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>Solve the linear program.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:heading {\"level\":4} --><\/p>\n<p><!-- \/wp:heading --><!-- wp:paragraph --><\/p>\n<p>There are four basic variables for two constraints, it is possible that the problem is not bounded and does not have a solution. Since there are two constraints, the dual will have two variables, it is easy to find a graphical solution to this new linear program.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>The dual is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7327,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"alignnone wp-image-7327 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire32.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"212\" height=\"135\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>And here is its graphical representation, with a minimum in (1,1) and for objective function 15.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7330,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7330 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire33.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"421\" height=\"299\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire33.png 421w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire33-300x213.png 300w\" sizes=\"(max-width: 421px) 100vw, 421px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>Let&#039;s look at the complementary deviations to find a solution of the primal.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>The two variables are non-zero, therefore the two constraints of the primal are saturated (the constraints become equality).<\/li>\n<li>In the dual, the constraints 1 and 3 are unsaturated for the solution (1,1), this means that the first variable and the third variable of the primal are zero.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>So we have the following two equations to solve:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>x<sub>2<\/sub> + 2x<sub>4<\/sub> = 8<\/li>\n<li>2x<sub>2<\/sub> + x<sub>4<\/sub> = 7<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>Which gives for solution (0, 2, 0, 3) and for objective function 15. The solutions of the primal and dual are equal, there is strong duality, it is therefore an optimal solution.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c4a38ea elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c4a38ea\" 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-40e947a\" data-id=\"40e947a\" 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-c47c756 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"c47c756\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\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-8b2d13b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8b2d13b\" 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-e1e439f\" data-id=\"e1e439f\" 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-3b7cb38 elementor-widget elementor-widget-heading\" data-id=\"3b7cb38\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-1\"><\/span>Exercise 1<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-786a7ea elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"786a7ea\" 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-97358bf\" data-id=\"97358bf\" 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-c9a2718 elementor-widget elementor-widget-text-editor\" data-id=\"c9a2718\" 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>Solve the following linear program using the dual (graphic resolution + simplex and complementary deviations):<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7332,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7332 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire34.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"270\" height=\"115\" title=\"\"><\/figure>\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-776d3fc elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"776d3fc\" 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-7de4f4a\" data-id=\"7de4f4a\" 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-58d89a7 elementor-widget elementor-widget-toggle\" data-id=\"58d89a7\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-9311\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-9311\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-9311\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-9311\"><p>The linear program is in canonical form, so we can calculate the dual without changing the form of the program. The dual is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7431,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7431 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire71.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"240\" height=\"179\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>with graphic resolution:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7432,\"width\":426,\"height\":319,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7432 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire72.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"884\" height=\"664\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire72.png 884w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire72-300x225.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire72-768x577.png 768w\" sizes=\"(max-width: 884px) 100vw, 884px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The global optimum is unique and is located at the point (6\/5, 7\/5) with the objective function Z = 79\/5.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>For the simplex, the standard form adds a difference variable for each constraint of the linear program. The final table is:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7434,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7434 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire73.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"470\" height=\"222\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire73.png 470w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire73-300x142.png 300w\" sizes=\"(max-width: 470px) 100vw, 470px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The solution vector of the dual is (6\/5, 7\/5, 0, 0, 19\/5, 19\/5) with Z = 79\/5. The additional deviations give the following information:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>The third and fourth constraints of the dual are unsaturated, the third and fourth variables of the primal are zero.<\/li>\n<li>The two basic variables are not zero, the two constraints of the primal are thus saturated.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>We must therefore solve the system of equations:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>x1 + 3 x2 = 5<\/li>\n<li>2 x1 + x2 = 7<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The vector (16\/5, 3\/5, 0, 0) is solution of the system, with Z = 79\/5. There is strong duality so it is about the global optimal of the linear program.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-e52df9e elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e52df9e\" 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-e26b81b\" data-id=\"e26b81b\" 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-001b242 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"001b242\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\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-8d999b8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"8d999b8\" 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-229205c\" data-id=\"229205c\" 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-32dbd90 elementor-widget elementor-widget-heading\" data-id=\"32dbd90\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-2\"><\/span>Exercise 2<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-23df8ab elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"23df8ab\" 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-a58b0b9\" data-id=\"a58b0b9\" 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-9acf234 elementor-widget elementor-widget-text-editor\" data-id=\"9acf234\" 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>Consider the following linear program:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7334,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7334 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire35.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"194\" height=\"139\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>Calculate the optimal solution by graphic resolution. The objective function has for new coefficient (3, 5), to check that the solution found previously is always optimal using the dual and the complementary deviations.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c8417b8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c8417b8\" 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-763b685\" data-id=\"763b685\" 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-a6cfbc9 elementor-widget elementor-widget-toggle\" data-id=\"a6cfbc9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1741\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1741\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1741\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1741\"><p>The domain of definition is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7441,\"width\":464,\"height\":353,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7441 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire74.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"867\" height=\"662\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire74.png 867w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire74-300x229.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire74-768x586.png 768w\" sizes=\"(max-width: 867px) 100vw, 867px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The graphical solution is the vector (5, 3) with Z = 13.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>With coefficients of the objective function at (3, 5), we will have Z = 30. Let us check with the complementary deviations if we have a strong duality. The dual program is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7443,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7443 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire75.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"279\" height=\"140\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The additional differences are as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>the two basic variables of the primal are non-zero, therefore the two constraints of the dual are saturated<\/li>\n<li>the first constraint of the primal is unsaturated, so the first variable of the dual is zero.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>We must therefore solve the following system:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>3 x3 = 3<\/li>\n<li>x2 - x3 = 5<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The vector (0, 6, 1) is solution of the system, with Z = 30. There is strong duality therefore (5, 3) is always the optimal solution of the primal program.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-0e0b352 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0e0b352\" 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-e3644e0\" data-id=\"e3644e0\" 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-97a722d elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"97a722d\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\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-687d401 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"687d401\" 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-e676acf\" data-id=\"e676acf\" 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-8a7b6b9 elementor-widget elementor-widget-heading\" data-id=\"8a7b6b9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-3\"><\/span>Exercise 3<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-893c7ac elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"893c7ac\" 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-d34ab07\" data-id=\"d34ab07\" 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-b315aac elementor-widget elementor-widget-text-editor\" data-id=\"b315aac\" 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>Consider the following linear program:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7337,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7337 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire36.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"268\" height=\"171\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>Test the optimality of the solution (250, 500, 1500) using the dual and complementary deviations.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>The mathematical modeling turns out to be false, and after checking the vector b of the constraints is (950, 550, 1575, 6900). Using the dual, check whether the solution is admissible and whether it is the optimal solution.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>Likewise with the vector (1000, 500, 1500, 9750).<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-3395ed4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"3395ed4\" 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-e399d3e\" data-id=\"e399d3e\" 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-85a6a71 elementor-widget elementor-widget-toggle\" data-id=\"85a6a71\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1401\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1401\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1401\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1401\"><p>The vector (250, 500, 1500) is an admissible solution because no constraint is violated. The optimal solution has the value Z = 11500. Let us check its optimality by the dual and the complementary deviations. The dual is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7446,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7446 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire76.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"392\" height=\"160\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire76.png 392w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire76-300x122.png 300w\" sizes=\"(max-width: 392px) 100vw, 392px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The additional deviations give the following information:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>no base variable of the primal is zero, so the constraints of the dual are saturated<\/li>\n<li>the first constraint of the primal is not saturated, so the first variable of the dual is zero<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>This gives the following system:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>3 X4 = 4<\/li>\n<li>X2 + 6X4 = 12<\/li>\n<li>X3 + 2 X4 = 3<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>With solution vector (0, 4, 1\/3, 4\/3) with Z = 11500. There is strong duality so this is indeed the optimal solution.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>Let us test the optimality again with a primal with the column b = (950, 550, 1575, 6900), only the objective function of the dual changes. The solution is admissible and the additional differences are as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>The three basic variables are non-zero therefore the constraints of the dual are saturated.<\/li>\n<li>No constraint is saturated, therefore the basic variables of the dual are zero.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>No need to solve the dual because the basic variables are all zero (Z = 0), there is no solution to the dual. This means that the solution of the dual is not on an extremum of the domain of definition.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>Likewise with the vector b = (1000, 500, 1500, 9750). The solution is admissible and the additional deviations give the following information:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>The three basic variables are non-zero therefore the constraints of the dual are saturated.<\/li>\n<li>The first and the fourth constraints are unsaturated, therefore the first and the fourth basic variable of the dual are zero.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The system does not admit a solution, therefore the proposed solution is not on an extremum of the domain of definition. Therefore it cannot be the optimum of the linear program.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-a37ab11 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"a37ab11\" 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-365378a\" data-id=\"365378a\" 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-eeea466 elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"eeea466\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\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-4e5a004 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e5a004\" 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-89b9b28\" data-id=\"89b9b28\" 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-75ee24f elementor-widget elementor-widget-heading\" data-id=\"75ee24f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-4\"><\/span>Exercise 4<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-404ef7c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"404ef7c\" 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-6b71eff\" data-id=\"6b71eff\" 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-bf5bb65 elementor-widget elementor-widget-text-editor\" data-id=\"bf5bb65\" 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>When injecting a quantity of electricity into the network, this energy diffuses through the lines offering the least resistance. It is possible to know the lines that will be taken by this energy flow using a linear program.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>To do this, the network and the energy flow must be defined:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>the flow starts from a single source and diffuses by the path with the least resistance towards the consumer<\/li>\n<li>the lines are one-way, the energy flow can only move in the direction of the current already passing through the line<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>A network is represented in the form of a graph as follows: nodes are substations and arcs representing lines, node 1 is the origin of the energy source, node 7 is the destination of the energy flow.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7453,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7453 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire77.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"291\" height=\"127\" title=\"\"><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The variables are:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>for each line, a variable between 0 and 1 gives the percentage of use of the line.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The objective function is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>we try to minimize the total cost, that is to say the sum of the percentages of use of the lines multiplied by the cost of the line.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The constraints are as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>for the original node, the sum of the variables of the outgoing arcs minus the sum of the variables of the incoming arcs is equal to 1<\/li>\n<li>for the arrival node, the sum of the variables of the incoming arcs minus the sum of the variables of the outgoing arcs is equal to 1<\/li>\n<li>for the other nodes, the sum of the variables of the outgoing arcs minus the sum of the variables of the incoming arcs is equal to 0.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>Represent the linear program of the previous graph, calculate the dual program and solve it using Excel. Deduce the result of the Primal program, note that an equation system can be solved in Excel by the command <strong>{= PRODUCTMAT (INVERSEMAT (System); Target vector)}<\/strong> where the coefficients are given in matrix form.<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:paragraph --><\/p>\n<p>For example :<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7457,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7457 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/4-1.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"544\" height=\"234\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/4-1.png 544w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/4-1-300x129.png 300w\" sizes=\"(max-width: 544px) 100vw, 544px\" \/><\/figure>\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-6fdddb4 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6fdddb4\" 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-e858e4b\" data-id=\"e858e4b\" 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-4af44fe elementor-widget elementor-widget-toggle\" data-id=\"4af44fe\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-7851\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-7851\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-7851\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-7851\"><p>The linear program representing the shortest path problem is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7461,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7461 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire79.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"592\" height=\"244\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire79.png 592w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire79-300x124.png 300w\" sizes=\"(max-width: 592px) 100vw, 592px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The following Excel program gives the solutions of the Primal in Green and the solutions of the Dual in Red (the constraints of the Primal are in line while the constraints of the Dual are in column), note that the equality constraints of the Primal make that the variables of the dual are on the set of reals:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7462,\"width\":926,\"height\":337,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7462 size-large\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80-1024x373.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"1024\" height=\"373\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80-1024x373.png 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80-300x109.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80-768x280.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80-1200x438.png 1200w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire80.png 1327w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The constraints 4, 5, 7, 8 of the dual are unsaturated, therefore the variables 4, 5, 7, 8 of the primal are zero. We must therefore solve the following system:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7464,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7464 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire81.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"501\" height=\"140\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire81.png 501w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire81-300x84.png 300w\" sizes=\"(max-width: 501px) 100vw, 501px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>This system can be solved very simply without Excel and the answer is the vector (0, 1, 0, 0, 0, 1, 0, 0, 1, 1) and Z = 22. There is strong duality so it is an optimal solution. By representing the arcs used by the energy flow in red, this gives the following diffusion graph:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7466,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7466 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire82.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"297\" height=\"130\" title=\"\"><\/figure><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-ccf369f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ccf369f\" 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-3dd1b85\" data-id=\"3dd1b85\" 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-4d8785c elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"4d8785c\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\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-bec48f8 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bec48f8\" 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-ea4104c\" data-id=\"ea4104c\" 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-1837e39 elementor-widget elementor-widget-heading\" data-id=\"1837e39\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Exercice-5\"><\/span>Exercise 5<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-279650f elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"279650f\" 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-6f57281\" data-id=\"6f57281\" 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-a0b0ffb elementor-widget elementor-widget-text-editor\" data-id=\"a0b0ffb\" 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>An energy island (local network cut off from the global network) has two energy sources and three consumer villages. Plant 1 produces 550 MWh and plant 2 produces 350 MWh. Village 1 requires 400 MWh, village 2 requires 300 MWh and village 3 requires 200 MWh. For each MWh passing through a network line, the cost in euros is as shown in the graph below:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7343,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7343 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire37.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"486\" height=\"306\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire37.png 486w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire37-300x189.png 300w\" sizes=\"(max-width: 486px) 100vw, 486px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>A solution exists if the quantity available is greater than or equal to the quantity requested<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list {\"ordered\":true} --><\/p>\n<ol>\n<li>Express the problem of minimizing the cost of energy transit from producers to consumers, explain the objective function and the constraints<\/li>\n<li>Express the problem of maximizing the profit of energy transit (point of view of the network manager).<\/li>\n<li>Solve one problem and find a solution for the other using the complementary deviations.<\/li>\n<\/ol>\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-fa49d05 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"fa49d05\" 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-48d71dc\" data-id=\"48d71dc\" 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-bf001c6 elementor-widget elementor-widget-toggle\" data-id=\"bf001c6\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-2001\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-2001\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">Solution<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-2001\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-2001\"><p>There are 900 quantity available and as many requests, so there is a possible solution. The variables are:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>for each row, X represents the quantity passing through the row.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The objective function is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>minimize the total cost of resources passing through all lines.<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The constraints are as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:list --><\/p>\n<ul>\n<li>stock constraints (less than or equal)<\/li>\n<li>demand constraints (greater than or equal).<\/li>\n<\/ul>\n<p><!-- \/wp:list --><!-- wp:paragraph --><\/p>\n<p>The linear program is as follows:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7469,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7469 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire83.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"413\" height=\"198\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire83.png 413w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire83-300x144.png 300w\" sizes=\"(max-width: 413px) 100vw, 413px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>Like the previous exercise, we will solve the primal and the dual on the same Excel sheet:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7470,\"width\":923,\"height\":410,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7470 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire84.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"1022\" height=\"454\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire84.png 1022w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire84-300x133.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire84-768x341.png 768w\" sizes=\"(max-width: 1022px) 100vw, 1022px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>The solution of the dual gives for solution vector (0, 2, 5, 6, 3) with the fifth and sixth unsaturated constraints. It is deduced from this that the first constraint of the primal is not saturated (therefore with a non-zero variation variable) and that the fifth and sixth basic variables are zero. We must therefore solve the following system:<\/p>\n<p><!-- \/wp:paragraph --><!-- wp:image {\"id\":7473,\"sizeSlug\":\"large\"} --><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-7473 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire85.png\" alt=\"linear programming dual form complementary gaps corrected exercises\" width=\"366\" height=\"96\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire85.png 366w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2019\/11\/lineaire85-300x79.png 300w\" sizes=\"(max-width: 366px) 100vw, 366px\" \/><\/figure>\n<p><!-- \/wp:image --><!-- wp:paragraph --><\/p>\n<p>It is possible to find a solution without Excel, this will give the base vector (50, 300, 200, 350, 0, 0) with Z = 3700. By strong duality this is an optimal solution.<\/p><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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 Home page Wiki Corrected exercises on the dual program and complementary deviation This tutorial offers various corrected exercises on the dual program and\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-7428","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7428","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=7428"}],"version-history":[{"count":6,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7428\/revisions"}],"predecessor-version":[{"id":20324,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/7428\/revisions\/20324"}],"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=7428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}