{"id":486,"date":"2016-01-27T17:51:48","date_gmt":"2016-01-27T16:51:48","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=486"},"modified":"2024-02-11T19:47:51","modified_gmt":"2024-02-11T18:47:51","slug":"programmation-lineaire","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/","title":{"rendered":"Linear Programming 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"486\" class=\"elementor elementor-486\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-6ca8283 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"6ca8283\" 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-7af6528\" data-id=\"7af6528\" 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-34f9550 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"34f9550\" 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\/2020\/04\/03\/theories-and-algorithms-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\">Theories<\/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-2e5f67f\" data-id=\"2e5f67f\" 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-220c790 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"220c790\" 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-ef00321\" data-id=\"ef00321\" 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-675b9f9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"675b9f9\" 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-0c90880 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0c90880\" 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-6b91111\" data-id=\"6b91111\" 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-5fc33db elementor-widget elementor-widget-toggle\" data-id=\"5fc33db\" 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-1001\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1001\" 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\">I. Linear programming methods<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1001\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1001\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/aide-a-la-decision\/methode-scientifique\/\" target=\"_blank\" rel=\"noreferrer noopener\">The scientific method<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/mathematical-modeling\/\">Mathematical modeling<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/linear-modeling\/\" target=\"_blank\" rel=\"noreferrer noopener\">Linear modeling<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-solutions-and-realizable-domain\/\" target=\"_blank\" rel=\"noreferrer noopener\">Solutions and feasible area<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-canonical-form-and-standard-form\/\" target=\"_blank\" rel=\"noreferrer noopener\">Canonical form and standard form<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/resolution-graphics\/\">Graphic resolution (2 variables)<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">Simplex<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/dual-program\/\">Dual<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/complementary-deviations\/\">Additional deviations<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/post-optimal-sensitivity-analysis\/\">Sensitivity analysis<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/post-optimal-dual-sensitivity-analysis\/\">Sensitivity analysis (dual)<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-origin-unrealizable\/\">Origin not feasible<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-method-du-grand-m\/\">Big M method<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1002\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-1002\" 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\">II. Solvers<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1002\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-1002\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/resolution-lp-with-excel\/\">Enter a LP in Excel<\/a><\/li>\n<\/ul><\/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-73f58d74 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"73f58d74\" 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-183cdfd3\" data-id=\"183cdfd3\" 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-3760d811 elementor-widget elementor-widget-text-editor\" data-id=\"3760d811\" 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\/#Programmation-lineaire\" >Linear programming<\/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\/#Solutions-possibles\" >Possible solutions<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Programmation-lineaire\"><\/span>Linear programming<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>In Operational Research (OR) such as linear programming, modeling a problem consists in identifying:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>intrinsic variables (unknowns)<\/li>\n<li>the various constraints to which these variables are subject<\/li>\n<li>the target objective (<a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">optimization<\/a>) called the Goal function.<\/li>\n<\/ul>\n<p><\/p>\n<p>In a linear programming (LP) problem the constraints and the objective are linear functions of the variables. Also referred to as a linear program. They are denoted as follows (<a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-canonical-form-and-standard-form\/\">canonic form<\/a> sheer):<\/p>\n<p><\/p>\n<figure class=\"wp-block-table\">\n<table>\n<tbody>\n<tr>\n<td><strong>Maximize\u00a0\u00a0 <\/strong><\/td>\n<td><strong>vs<sup>T<\/sup> x<br \/><\/strong><\/td>\n<\/tr>\n<tr>\n<td><strong>Subject to <\/strong><\/td>\n<td><strong>Ax \u2264 b<\/strong><\/td>\n<\/tr>\n<tr>\n<td>\u00a0<\/td>\n<td><strong>x \u2265 0<\/strong><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/figure>\n<p><\/p>\n<p>where x is the vector of variables <strong>(x<sub>1<\/sub>,\u2026, X<sub>not<\/sub>)<\/strong>, <strong>vs<\/strong> and <strong>b<\/strong> are vectors of coefficients, <strong>TO<\/strong> a size coefficient matrix <strong>m * n<\/strong>, and <strong><sup>T<\/sup><\/strong> the transpose (column vector instead of row vector for example). Inequalities <strong>Ax \u2264 b<\/strong> and <strong>x \u2265 0<\/strong> (positivity of the variables) are constraints. the <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-solutions-and-realizable-domain\/\">definition field<\/a> formed is a convex polytope. The linear program is said to be in standard form if it involves equality constraints.<\/p>\n<p><\/p>\n<p><strong>Positivity of variables<\/strong>. If in the context, we have a non-zero lower bound <strong>x \u2265 k<\/strong>, just ask<strong> y = xk<\/strong> and <strong>y \u2265 0<\/strong>. If there is no lower bound, we can always set <strong>x = yz<\/strong> with <strong>y \u2265 0<\/strong> and <strong>z \u2265 0<\/strong>.<\/p>\n<p><\/p>\n<p>Any standard problem can be written canonically and vice versa. The equality constraint breaks down into two inequality constraints. An inequality constraint is written in the form of equality by adding an <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/lp-origin-unrealizable\/\">slack variable<\/a>.<\/p>\n<p><\/p>\n<p>A solution x &#039;is said to be feasible if it satisfies all the constraints.<\/p>\n<p><\/p>\n<p>To sum up, linear programming is made up of four elements:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>decision variables;<\/li>\n<li>an objective function;<\/li>\n<li>resource constraints;<\/li>\n<li>&quot;type&quot; constraints.<\/li>\n<\/ol>\n<p><\/p>\n<p>To formulate a problem from a specification, follow the four previous points in order.<\/p>\n<p><\/p>\n<p><strong>Example. <\/strong>Consider a factory that produces two types of keyboard earning \u00a3 50 and \u00a3 70 each. To manufacture a type 1 unit, it takes 40 min of labor and 20 min of machining. To manufacture a type 2 unit, it takes 30 minutes of labor and 30 minutes of machining. The workforce works 6 hours a day while the machine is available 8 hours a day. How many units of each type must be produced to maximize profits?<\/p>\n<p><\/p>\n<p><strong>Linear program. <\/strong>This problem is modeled according to the following PL:<\/p>\n<p><\/p>\n<p><em>maximum 50x + 70y<\/em><br \/><em>SC 40x + 30y \u2264 360<\/em><br \/><em>20x + 30y \u2264 480<\/em><br \/><em>x, y\u2265 0<\/em><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solutions-possibles\"><\/span>Possible solutions<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p>Only four cases can arise:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>If the domain of definition is null, the problem is not feasible;<\/li>\n<li>otherwise: the optimum does not exist, the problem is unbounded;<\/li>\n<li>or: the problem has a unique optimal solution coinciding with an extreme point (a vertex) of the domain of definition;<\/li>\n<li>or: the problem has an infinity of solutions forming a face or an edge of the domain of definition.<\/li>\n<\/ol>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-9778 size-large\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Steps-to-solve-linear-programming-problems-by-using-the-simplex-method-839x1024.jpg\" alt=\"linear programming\" width=\"839\" height=\"1024\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Steps-to-solve-linear-programming-problems-by-using-the-simplex-method-839x1024.jpg 839w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Steps-to-solve-linear-programming-problems-by-using-the-simplex-method-246x300.jpg 246w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Steps-to-solve-linear-programming-problems-by-using-the-simplex-method-768x938.jpg 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/09\/Steps-to-solve-linear-programming-problems-by-using-the-simplex-method.jpg 850w\" sizes=\"(max-width: 839px) 100vw, 839px\" \/><\/p>\n<p><\/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>Theories Wiki Home Page I. Linear Programming Methods The Scientific Method Mathematical Modeling Linear Modeling Solutions and Feasible Domain Canonical Form and Standard Form \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-486","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/486","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=486"}],"version-history":[{"count":45,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/486\/revisions"}],"predecessor-version":[{"id":20397,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/486\/revisions\/20397"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=486"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}