M09 programmation lineaire ensea fès -Programmation linaire

Télécharger PDF

Introduction Générale

Pour le grand public, la recherche opérationnelle est une technique récente, datant tout au plus de la seconde guerre mondiale. Et, en fait, c'est bien à son application aux opérations militaires qu'elle doit son nom. En réalité, elle est bien plus ancienne, car, dès le dix-septième siècle, Pascal et Fermat, inventeurs de la notion de l'espérance mathématique en 1654, cherchaient, suivis de peu par Jacques Bernoulli et Waldegrave, à résoudre des problèmes de décision dans l'incertain. Avant la fin de l'ancien régime, Mongue s'était proposé et avait résolu analytiquement un problème économique de nature combinatoire : celui des déblais et remblais en 1776. Sous la monarchie de Juillet, Augustin Cournot s'était attaqué à la théorie mathématique des richesses en 1838, devenant ainsi le précurseur de l'économétrie. Plus récemment, Emile Borel introduisait la théorie mathématique des jeux, sous sa forme moderne, à l'Académie des Sciences durant la période 1921-25 tandis qu'Erlang fondait celle des files d'attente, qu'il utilisait à la conception des réseaux téléphoniques en 1917. Enfin, à la veille de la guerre mondiale (1939-45), Kantorovitch concevait et appliquait la programmation linéaire à la planification peu après que König se fut intéressé aux graphes en 1936.

La Recherche Opérationnelle est donc une discipline qui vise à résoudre par une démarche scientifique des problèmes de décision complexes issus du monde réel. Sa vocation est de construire des modèles pour des problèmes généraux d'aide à la décision (en particulier les problèmes d'optimisation), et de proposer des méthodes de résolution efficace pour ces modèles. Généralement, ces méthodes sont employées sur des problèmes tels que leur utilisation "manuelle" devient impossible. C'est pourquoi, les démarches proposées par la recherche opérationnelle peuvent être traduites en programmes informatiques.

La programmation linéaire est certainement l'un des plus beaux succès de la recherche opérationnelle. Elle provient d'une part, de la puissance de modélisation qu'elle offre et ce malgré la limite inhérente imposée par la linéarité des fonctions impliquées, et d'autre part, de la richesse de la théorie qu'elle a initiée et qui a permis le développement d'algorithmes extrêmement efficaces pour sa résolution. Depuis sa formulation et le développement de la méthode du simplexe pour sa résolution vers la fin des années 40, la programmation linéaire demeure le modèle d'optimisation le plus utilisé par les décideurs grâce certainement à la robustesse des algorithmes disponibles. Le schéma général suivi par ces méthodes est :

Exemples et Applications de la Recherche Opérationnelle

Limité au départ aux problèmes industriels et militaires, de nos jours plusieurs problèmes de divers domaines sont représentés ou approximés par des modèles de PL. L'utilisation de ces techniques de modélisation s'est renforcée encore après avoir construit des algorithmes et des logiciels capables de résoudre de plus larges problèmes avec autant de variables de décision que de contraintes. La tâche de formulation demande généralement une certaine expertise et connaissance du problème pour pouvoir relever facilement les différentes composantes du problème et ainsi donner un programme qui modélise au mieux la situation réelle. Dans ce qui suit, on présentera quelques exemples de formulation de différents problèmes de décision :

Planifier une production

Nous sommes à la tête d'une armée, en guerre contre une nation. Nous prévoyons de produire 20 avions divisés en deux modèles. Selon le modèle, un avion est armé de b bombes et m missiles et il cause des dégâts estimés par d. On résume tout cela dans le tableau suivant :

	modèle A	modèle B
bombes	3	15
missiles	5	10
dégâts	5	11

On dispose au total de 225 bombes et 160 missiles. La question est la suivante : combien d'avions de chaque modèle doit-on produire pour maximiser les dégâts infligés à l'ennemi ?

On appelle xA et xB les quantités d'avions à produire, respectivement du modèle A et du modèle B. Les dégâts totaux peuvent s'écrire comme 5xA +11xB, et l'on cherche donc à maximiser f (xA, xB) = 5xA + 11xB. La première contrainte est évidemment l'ensemble des 20 avions que l'on peut produire. Ainsi xA + xB ≤ 20. De même, nous disposons de contraintes sur le nombre total de bombes et de missiles ce qui conduit à deux contraintes supplémentaires : 3xA +15xB ≤ 225 et 5xA +10xB ≤ 160. Enfin, il faut rajouter des contraintes logiques : les quantités d'avions à produire ne peuvent être que positives et donc xA et xB sont positifs.

Matriciellement, nous aurions c = Ã 5 11 ! , A =  1 1 3 15 5 10   et b =  20 225 160  .

Sous forme compacte le problème se modélise comme suit

  max ctx Ax ≤ b x ∈ N (1.1)

Maximiser le bénéfice d'une usine

Une usine produit deux ciments, rapportant 500Dh et 700Dh par tonne. Une tonne du ciment N°1 nécessite 40 min de calcination dans un four à chaux et 20 min de broyage. Une tonne du ciment N°2 nécessite 30 min de calcination dans un four à chaux et 30 min de broyage. Le four et l'atelier de broyage sont disponibles 6h et 8h par jour. Combien de ciment de chaque type peut-on produire par jour pour maximiser le bénéfice ?

Ce problème se modélise comme suit :

max 500x1 + 700x2 (1.2)

40x1 + 30x2 ≤ 360 (1.3)

20x1 + 30x2 ≤ 480 (1.4)

x1 ≥ 0 , x2 ≥ 0 (1.5)

(1.2) est le profit total qui est à optimiser, appelé fonction objective.

(1.3) et (1.4) sont des contraintes. (1.3) est la disponibilité du four et (1.4) est la disponibilité du broyeur. (1.5) est le domaine des variables.

Problème de médecine

Un spécialiste en médecine a fabriqué un médicament (des pilules) pour guérir les sujets atteints d'un rhume. Ces pilules sont fabriquées selon deux formats :

Petite taille : elle contient 2 grains d'aspirine, 5 grains de bicarbonate et 1 grain de codéine.
Grande taille : elle contient 1 grain d'aspirine, 8 grains de bicarbonate et 6 grains de codéine.

Pour guérir la maladie, le sujet a besoin de 12 grains d'aspirine, 74 grains de bicarbonate et 24 grains de codéine. Déterminer le nombre de pilules minimales à prescrire au sujet pour qu'il soit guéri.

Les variables de décision qui représentent des valeurs inconnues par le décideur qui est dans ce cas le spécialiste en médecine sont :

x1 : le nombre de pilules de petite taille à prescrire.
x2 : le nombre de pilules de grande taille à prescrire.

On vérifie bien que les variables de décision x1 et x2 sont positives : x1 ≥ 0, x2 ≥ 0. Les contraintes imposées par le problème sur les valeurs possibles de x1 et x2 sont :

La prescription doit contenir des pilules avec au moins 12 grains d'aspirine. Sachant qu'une petite pilule contient 2 grains d'aspirine et qu'une grande pilule contient un seul grain d'aspirine, on obtient la contrainte suivante : 2x1 + x2 ≥ 12.
De la même façon que pour l'aspirine, la prescription du spécialiste en médecine doit contenir au moins 74 grains de bicarbonate. Ainsi la contrainte suivante doit être satisfaite : 5x1+8x2 ≥ 74.

Finalement la contrainte imposée par le fait que la prescription doit contenir au moins 24 grains de codéine est x1 +6x2 ≥ 24.

Étape 3 : Identification de la fonction objectif. On remarque qu'il y a plusieurs couples de solutions (x1, x2) qui peuvent satisfaire les contraintes spécifiées à l'étape 2. La prescription doit contenir le minimum possible de pilules. Donc le critère de sélection de la quantité de pilules à prescrire est celle qui minimise le nombre total des pilules z = x1 + x2 . Le programme qui modélise ce problème médical est donc le suivant :

  min x1 + x2 s.t. 2x1 + x2 ≥ 12 5x1 +8x2 ≥ 74 x1 +6x2 ≥ 24 x1 ∈ N, x2 ∈ N (1.6)

Problème de production

Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de ressources : équipement, main d'œuvre, matières premières. Ces besoins sont indiqués dans le tableau ci-dessous. Par ailleurs, chaque ressource est disponible en quantité limitée.

	P1	P2	disponibilité
équipement	3	9	81
main d'œuvre	4	5	55
matière première	2	1	20

Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 6 euros et 4 euros par unité. Quelles quantités de produits P1 et P2 (valeurs non-nécessairement entières) doit produire l'usine afin de maximiser le bénéfice total venant de la vente des 2 produits ?

Choix des variables (les inconnues) : x1 et x2 sont respectivement les quantités des produits P1 et P2 fabriqués (x1, x2 ∈ R).
Choix de la fonction objectif à maximiser : La fonction objectif f correspond au bénéfice total. Elle vaut f (x1, x2) = 6x1 +4x2. Le problème se traduit donc par max (x1,x2)[f (x1, x2) = 6x1 +4x2].
Détermination des contraintes. La disponibilité de chacune des ressources s'écrit : 3x1 +9x2 ≤ 81 4x1 +5x2 ≤ 55 2x1 + x2 ≤ 20 Positivité des variables : x1, x2 ≥ 0.

En résumé, le problème de production se modélise sous la forme

 (1.7)  max (x1,x2)[f (x1, x2) = 6x1 +4x2] s.t. 3x1 +9x2 ≤ 81 4x1 +5x2 ≤ 55 2x1 + x2 ≤ 20 x1, x2 ≥ 0

Formalisation

Tous les problèmes mentionnés ci-dessus et présentés dans ce cours peuvent se formaliser de la façon suivante. On cherche à maximiser une fonction f sur un ensemble K donné : max{f (x), x ∈ K}.

f : K → R est la fonction objectif. f peut être linéaire, quadratique, non linéaire...
K est l'ensemble des solutions possibles dites réalisables (les contraintes). L'ensemble K est fini mais en général de très grande taille.

On peut envisager de façon équivalente un problème de minimisation grâce à la relation min f = −max(−f ).

Programmation Linéaire

Introduction à la Programmation Linéaire

La programmation linéaire est une technique mathématique permettant de déterminer la meilleure solution d'un problème dont les données et les inconnues satisfont à une série d'équations et d'inéquations linéaires. La programmation linéaire a été formulée par Dantzig en 1947 et connaît un développement rapide par suite de son application directe à la gestion scientifique des entreprises. Le facteur expliquant l'essor de la PL est la construction d'ordinateurs puissants qui ont permis de traiter les problèmes concrets de taille très grande. On l'applique surtout en gestion et en économie appliquée. On peut citer les domaines d'application de la programmation linéaire qui sont : les transports, les banques, les industries lourdes et légères, l'agriculture, les chaînes commerciales, la sidérurgie, et même le domaine des applications militaires. Les méthodes de résolution sont la méthode du simplexe, méthode duale du simplexe, méthodes des potentiels, méthode lexicographique et des méthodes récentes appelées méthodes des points intérieurs. Un programme linéaire se définit par ses composantes, une fonction, dite économique ou objective, à maximiser ou à minimiser, les contraintes du problème qui s'expriment par égalités ou inégalités, et les contraintes de non-négativité c'est-à-dire les variables ne peuvent être que positives ou nulles (presque toujours ces variables prennent le sens de quantités). La résolution d'un problème de la programmation linéaire ne pose incontestablement aucune difficulté car il y a des méthodes pratiques pour le résoudre, de plus on peut utiliser des logiciels très efficaces pour la résolution. Mais le problème capital est celui de formuler un problème, si possible, comme un programme linéaire. La problématique que nous tentons de poser est : Est-ce que l'on peut recourir à une classification méthodique pour rendre la modélisation sous forme de programme linéaire très aisée ?

Formes Générales d'un Programme Linéaire

Forme canonique mixte

Il s'agit d'un problème de programmation linéaire (encore appelé programme linéaire) écrit sous la forme suivante.

(x1,...,xn)f (x1,..., xn) = c1x1 + c2x2 + c3x3 +....+ cnxn =Xnj=1c jxj max

 contraintes d'inégalités : ∀i ∈ I1,Xn ai jxj = ai1x1 + ai2x2 +....+ ainxn ≤ bi j=1 contraintes d'égalités : ∀i ∈ I2,Xn ai jxj = bi  j=1 contraintes de signes : ∀j ∈ J1, xj ≥ 0 ∀j ∈ J2, xj de signe quelconque.

(2.1)

L'ensemble I = I1∪ I2 est l'ensemble des indices de contraintes avec card(I) = m. Autrement dit, il y a m contraintes. L'ensemble J = J1∪J2 est l'ensemble des indices des variables avec card(J) = n. Il y a n variables.

Forme canonique pure

Sous cette forme, il n'y a pas de contraintes d'égalité c'est-à-dire I2 = ; et J2 = ;. On note x = (x1,..., xn)t∈ Rn c = (c1,..., cn)t∈ Rn b = (b1,...,bm)t∈ Rn et la matrice A de taille m× n :

A =  a11 a12 ··· a1n ...... am1 am2 ··· amn  

Un programme linéaire (PL) est dit sous forme canonique pure s'il s'écrit :

£¤ xf (x1,..., xn) = ctx = c1x1 + c2x2 + c3x3 +....+ cnxn max ( s.t. Ax ≤ b, x ≥ 0. (2.2)

Forme standard

Sous cette forme, I1 = ; et J2 = ;. Un programme linéaire (PL) est dit sous forme standard s'il s'écrit :

£¤ xf (x1,..., xn) = ctx = c1x1 + c2x2 + c3x3 +....+ cnxn max ( s.t. Ax = b, x ≥ 0. (2.3)

On dit de plus que le PL est sous forme standard simpliciale si A de taille m× n avec m ≤ n, se décompose en : A = (Im|H) où Im désigne la matrice identité de taille m× m et H est une matrice de taille m×(n− m).

Résolution Graphique

Dans le cas d'un (PL) à deux variables, on peut envisager une résolution graphique. Les contraintes où apparaissent des inégalités correspondent géométriquement à des demi-plans. L'intersection de ces demi-plans forme l'ensemble des variables satisfaisant à toutes les contraintes. Dans cette section, nous allons étudier deux types de problèmes :

Résolution graphique d'un problème de maximisation

Reprenons l'exemple de production.

 max (x1,x2)[f (x1, x2) = 6x1 +4x2 ] s.t. 3x1 +9x2 ≤ 81 4x1 +5x2 ≤ 55  2x1 + x2 ≤ 20 x1, x2 ≥ 0

À la fonction objectif f correspond une droite f (x1, x2) = 6x1 +4x2 = constante, de coefficient directeur (−1,6/4). La constante précédente qui définit la droite doit être la plus grande possible (maximisation) et rencontrer l'ensemble des variables qui satisfont les contraintes. Pour déterminer cette valeur maximale, on fait donc "glisser" la droite (translation parallèle à la direction de la droite) du haut vers le bas jusqu'à rencontrer l'ensemble des variables satisfaisant les contraintes. Le maximum de f sur cet ensemble des contraintes est alors atteint. On obtient ainsi la solution optimale (x1, x2) = (15/2,5) et ce qui donne une valeur maximale max(f ) = 65. On remarque que l'ensemble des contraintes (la partie hachurée) est un polygone convexe et que le maximum de f est atteint en un sommet de ce polygone. Cette observation est, en fait, un résultat général que l'on établira dans les sections suivantes.

Résolution graphique d'un problème de minimisation

Pour résoudre le problème linéaire dans le cas d'une minimisation, nous allons appliquer une démarche équivalente, mais dans ce cas, nous cherchons la droite (représentant la fonction économique) la plus rapprochée de l'origine. Résoudre le problème linéaire suivant :

  min 6x1 +9x2 s.t 3x1 +2x2 ≥ 18 x1 +3x2 ≥ 12 x1 + x2 ≥ 8 x ≥ 0

Représentons graphiquement l'ensemble-solution puis représentons la famille de droites correspondante à : 6x1 +9x2 = p ⇐⇒ x2 = −23x1 +p9 ⇐⇒ droite de pente −23

Résoudre graphiquement le problème suivant

  min −50x1 −30x2 s.t 10x1 +6x2 ≤ 45 4x1 +6x2 ≤ 36 2x1 +6x2 ≤ 27 x ≥ 0

Résolution Algébrique

Pour résoudre des problèmes de programmation linéaire ayant un nombre de variables (principales) supérieur à trois, nous devons obligatoirement faire appel à une autre méthode de résolution que celle déjà étudiée. Toutefois, avant d'aborder la méthode du simplexe comme technique de résolution d'un problème de programmation linéaire, nous allons découvrir une version modifiée "la méthode algébrique" qui permettra d'étudier les différentes étapes à franchir pour arriver à une solution optimale.

Variables d'Écart

La méthode de résolution que nous étudions dans ce chapitre nécessite que les contraintes du modèle soient exprimées sous forme d'équations linéaires au lieu d'inéquations. On peut facilement transformer une inéquation linéaire ayant un signe ≤ en une équation linéaire en additionnant une variable non négative dite variable d'écart. Proposition 2.1 Tout PL sous forme standard s'écrit de façon équivalente en un PL sous forme canonique pure et inversement. Démonstration

1. Soit un PL sous forme canonique pure. On a Ax ≤ b ⇐⇒ Xn j=1 ai jxj + ei = bi, ∀i = 1,..,m ai jxj ≥ 0 Ainsi, où ei = bi −Xn j=1 (  (A|Im) Ã x ! = b, ( Ax ≤ b, x ≥ 0.⇐⇒  Ã e x e ! ≥ 0. ⇐⇒ A˜ x˜ = b, x˜ ≥ 0. où e = (e1,..., em)tsont appelées variables d'écart et A˜ est une matrice de taille m× n+ m .

2. Soit un PL sous forme standard. On a Ax = b ⇐⇒ ( Ax ≤ b, Ax ≥ b.⇐⇒ ( Ax ≤ b, −Ax ≤ −b.⇐⇒ Ã A −A ! x ≤ Ã b −b ! ⇐⇒ ˜Ax˜ ≤˜b˜. où ˜A˜ est une matrice de taille 2m× n et ˜b˜ ∈ R2m.

Solutions de Base Réalisables

On considère désormais (sauf mention contraire) un PL toujours sous forme standard. Définition 2.1 On appelle solution réalisable tout vecteur x qui satisfait les contraintes du PL i.e. tel que Ax = b et x ≥ 0. Hypothèse : On suppose désormais que la matrice A est de taille m× n avec rang(A) = m ≤ n. On rappelle que le rang de A est le nombre maximal de lignes de A linéairement indépendantes. C'est aussi le nombre de colonnes de A linéairement indépendantes. L'hypothèse de rang plein n'est pas restrictive car :

si rang(A) < m le système Ax = b n'a pas de solution en général.
Si rang(A) < m et b ∈ Im(A), il y a des équations redondantes dans le système Ax = b, qu'on peut donc supprimer pour obtenir un nouveau système de rang plein.

Sous l'hypothèse de rang plein, le système Ax = b admet toujours des solutions.

Si m < n, il y en a une infinité.
Si m = n, la solution est unique et vaut x = A−1b, dans ce cas, il n'y a rien à maximiser...

Remarque 2.1 Pour la forme canonique pure avec Ax ≤ b, l'hypothèse de rang plein n'est pas non plus restrictive car si rang(A) < m, il y a des contraintes d'inégalités redondantes qu'on peut supprimer pour obtenir un système de rang plein.

Définition 2.2 Soit B ⊆ {1,...,n} un ensemble d'indices avec card(B) = m tel que les colonnes A j, j ∈ B, de A sont linéairement indépendantes. Autrement dit, la sous-matrice A_B formée par ces colonnes est inversible.

FAQ sur la Programmation Linéaire

Qu'est-ce que la Programmation Linéaire (PL) ?

La Programmation Linéaire est une technique mathématique d'optimisation utilisée pour trouver la meilleure solution (maximiser un profit, minimiser un coût) à un problème, sous un ensemble de contraintes exprimées par des équations ou inéquations linéaires. C'est une branche fondamentale de la Recherche Opérationnelle.

Dans quels domaines la PL est-elle appliquée ?

La Programmation Linéaire est appliquée dans une multitude de domaines, notamment en gestion et en économie appliquée. On la retrouve dans les transports, la banque, l'industrie (lourde et légère), l'agriculture, les chaînes commerciales, la sidérurgie, et même dans les applications militaires pour la planification et l'optimisation des ressources.

Quelle est l'importance de la formulation d'un problème en PL ?

La formulation est l'étape cruciale où un problème du monde réel est traduit en un modèle mathématique linéaire. Une formulation correcte et précise est essentielle car elle détermine si le problème peut être résolu efficacement par les algorithmes de PL. Bien que la résolution par ordinateur soit facilitée par des logiciels puissants, identifier les variables de décision, la fonction objectif et les contraintes est le défi principal et le fondement du succès de l'optimisation.