Cours 9 : programmation linéaire (recherche opérationnelle

De
Publié par

11 Cours 9 : programmation linéaire(recherche opérationnelle) • 1. Exemple introductif• 2. La méthode du simplexe• 3. Dictionnaires• 4. Algorithme C. JARDCours ALGO1MMI+MIT2007-2008 2 • Production optimale d'une raffinerie produisant 4 produitsfinis (essence, kérosène, mazout et résidu) à partir de deuxtypes de pétrole brut (brut1 et brut2), avec les paramètressuivants : 1. Introduction : la raffinerie 36242110 EssenceKérosèneMazoutRésidu Vente 2415Brut1Brut2Achat $/barilProduit 0.5, 1Cout deproduction($/baril) 2400020006000 80, 445, 1010, 365, 10 EssenceKérosèneMazoutRésidu Productionmaximale(baril/jour)Rendement(%)Brut1, Brut2
  • solutions réalisables
  • simplification par élimination de variables ¶
  • itération ¶
  • x3 ≤
  • max z
  • x3
  • x1
  • x2
  • choix
  • variable
  • variables
Publié le : mercredi 28 mars 2012
Lecture(s) : 1 082
Source : dit.bretagne.ens-cachan.fr
Nombre de pages : 10
Voir plus Voir moins
Cours 9 : programmation linéaire C. JARD (recherche opérationnelle) Cours ALGO1 MMI+MIT 2007-2008
1. Exemple introductif
2. La méthode du simplexe
3. Dictionnaires
4. Algorithme
1. Introduction : la raffinerie
1
Production optimale dune raffinerie produisant 4 produits finis (essence, kérosène, mazout et résidu) à partir de deux types de pétrole brut (brut1 et brut2), avec les paramètres suivants : Rendement(%) Production maximale Produit $/baril Brut1, Brut2 (baril/jour)
Achat
Vente
Brut1 Brut2
Essence Kérosène Mazout Résidu
24 15
36 24 21 10
Essence Kérosène Mazout Résidu
Cout de production ($/baril)
80, 44 5, 10 10, 36 5, 10
0.5, 1
24000 2000 6000
2
1
Le modèle mathématique
Les variables de décision(linformation recherchée) : p , p : nombre de barils/jour de Brut1 et 2 raffinés 1 2 x , , x : nombre de barils/jour obtenus pour chaque produit 1 4 Les contraintes sur ces variables: 0.80p +0.44p =x 1 2 1 0.05p +0.10p =x 1 2 2 0.10p +0.36p =x 1 2 3 0.05p +0.10p =x 1 2 4 x24000, x2000, x6000, p ,p0 1 2 3 1 2 Lobjectif(maximisation sous contraintes du profit = vente - achat -coût de production) : max (36x +24x +21x +10x -24p -15p -0.5p -1p ) 1 2 3 4 1 2 1 2
Simplification par élimination de variables
max (8.1p1 + 10.8p2) sous contraintes : 0.80p + 0.44p24000 1 2 0.05p + 0.10p2000 1 2 0.10p + 0.36p6000 1 2 p ,p0 1 2
Forme standard(on peut toujours sy ramener) :
maxc x j=1,n j j sous contraintesa xb (1im) j=1,n ij j i  x0 (1jn) j
3
4
2
Une solution (x ,,x ) estréalisablesi elle satisfait à toutes les 1 n contraintes Elle estoptimalesi elle est réalisable et si elle maximise lobjectif (pas nécessairement unique) Il nexiste pas forcément de solution optimale (soit il nexiste pas de solution réalisable, soit il nexiste pas de valeur optimale finie) : max x -x 1 2 sous contraintes : -2x + x-1 1 2 -x -2x-2 1 2 x , x0 1 2 (il existe des solutions réalisables : 1,1 ; 5,0 mais on peut toujours trouver une solution meilleure)
2. La méthode du simplexe (Dantzig 1955) -> points intérieurs
Idée 1: rajouter des variables décarts pour se ramener à des équations linéaires.
Exemple : max z = 5x + 4x + 3x s.c. 1 2 3 2x + 3x + x5 1 2 3 4x + x + 2x11 1 2 3 3x + 4x + 2x8 1 2 3 x , x , x0 1 2 3
max z = 5x + 4x + 3x s.c. 1 2 3 x = 5 - 2x - 3x - x 4 1 2 3 x = 11 - 4x - x - 2x 5 1 2 3 x = 8 - 3x - 4x - 2x 6 1 2 3 x , x , x , x , x , x0 1 2 3 4 5 6
5
6
3
Itération
Idée 2 :dune solution réalisable (x , , x ) trouver une autre 1 6 réalisable (x ,  x ) meilleure, i.e. 1 6 5x + 4x + 3x < 5x + 4x + 3x 1 2 3 1 2 3 Première solution réalisable : x = x = x = 0, x = 5, x = 11, x = 8, objectif z = 0 1 2 3 4 5 6 Amélioration par augmentation de lobjectif (dune variable de décision x , x ou x ). Choisissons x par exemple (z = 5x ) : 1 2 3 1 1 – x = 1 => x = 3, x = 7, x = 5, z = 5 1 4 5 6 – x = 2 => x = 1, x = 3, x = 2, z = 10 1 4 5 6 – x = 3 => x = -1, x = -1, x = -1 non réalisable 1 4 5 6 Jusquoù augmenter ? – x0 => x5/2, x0 => x11/4, x0 => x8/3 4 1 5 1 6 1 – On prend la plus contraignante (x = 5/2) 1
7
x = 5/2, x = 0, x = 0 => x = 0, x = 1, x = 1/2, z = 25/2 1 2 3 4 5 6 On exprime les variables positives (x , x , x ) en fonction des 1 5 6 variables nulles (x , x , x ) : 2 3 4 x = 5/2 - 3/2 x - 1/2 x -1/2 x 1 2 3 4 x = 1 + 5x + 2x 5 2 4 x = 1/2 + 1/2 x -1/2 x + 3/2 x 6 2 3 4 z = 25/2 - 7/2 x + 1/2 x - 5/2 x 2 3 4 Solution courante z = 25/2. De lexpression de z, on voit que lamélioration ne peut être obtenue que par laugmentation de x . x , x0 => (x5) & (x1). On prend donc x = 1 (x 3 1 6 3 3 3 6 prend la valeur 0).
8
4
Les nouvelles variables non nulles sont x , x et x . On obtient 1 5 3 le nouveau système : x = 2 - 2x - 2x + x 1 2 4 6 x = 1 + 5x + 2x 5 2 4 x = 1 + x + 3x - 2x 3 2 4 6 z = 13 - 3x - x - x 2 4 6 Solution courante : x = 2, x = 1, x = 1, x = 0, x = 0, x = 0, z = 13 1 3 5 2 4 6 Quelle variable peut-on augmenter ? Aucune car une augmentation de x , x ou x fait diminuer z. Cette solution est 2 4 6 optimale.
3. Dictionnaires
9
Soit un PL sous forme standard : max z =c x j=1,n j j s.c.a xb (1im) j=1,n ij j i  x0 (1jn) j On introduit les variables décarts x , , x : n+1 n+m x = b -(1a x im) n+i ijj=1,n ij x0 (1jn+m) j Chaque itération de lalgorithme du simplexe produit un système déquations linéaires, appelédictionnaire; les équations exprimentmvariables et la variablezen fonction desnautres variables. Un dictionnaire estréalisablesi en posant à 0 les variables droites, on obtient une solution réalisable
10
5
Attention, il existe des solutions réalisables qui ne correspondent pas à un dictionnaire. Exemple : x = 1, x = 0, x = 1, x = 2, x = 5, x = 3 ; 1 2 3 4 5 6 le simplexe ignore toutes les autres Les variables gauches dun dictionnaire sont lesvariables de base Les variables droites sont lesvariables hors-base A chaque itération, une variable entre dans la base et une variable sort de la base Le choix de la variable à entrer est dicté par lamélioration de lobjectif z Le choix de la variable à sortir est dicté par le désir de conserver toutes les variables non négatives On appellepivotagele processus permettant de passer dune dictionnaire à un autre (ou encore de passer dune base à une autre)
Exemple
max z = 5x + 5x + 3x s.c. 1 2 3 x + 3x + x3 1 2 3 -x + 3x2 1 3 2x - x + 2x4 1 2 3 2x + 3x - x2 1 2 3 x , x , x0 1 2 3 Dictionnaire initial: x = 3 - x - 3x - x 4 1 2 3 x = 2 + x - 3x 5 1 3 x = 4 - 2x + x - 2x 6 1 2 3 x = 2 - 2x - 3x + x 7 1 2 3 z = 5x + 5x + 3x  1 2 3 Choix entrée x 1
11
12
6
Choix entrée x (x et x sont considérés à 0) 1 2 3 x = 3 - x0 => x13 4 1 x = 2 + x => x1-2 5 1 x = 4 - 2x => x12 6 1 x = 2 - 2x =>x11 7 1 Choix sortie x (pivot : utiliser sa ligne) : x = 1 - 3/2 x + 1/2 x -1/2 x 7 1 2 3 7 Nouveau dictionnaire: x = 2 - 3/2 x - 3/2 x + 1/2 x 4 2 3 7 x = 3 - 3/2 x - 5/2 x - 1/2 x 5 2 3 7 x = 2 + 4x - 3x +x 6 2 3 7 x = 1 - 3/2 x + 1/2 x -1/2 x 1 2 3 7 z = 5 - 5/2 x + 11/2 x - 5/2 x 2 3 7 Choix entrée x etc 3 Lorsquil ny a plus avantage à entrer une variable dans la base, on obtient une solution optimale : x = 32/29, x = 8/29, x = 30/29, pour z = 10 1 2 3
4. Algorithme du simplexe
13
Résumé: – 1. Initialisation : former le dictionnaire (partir dune base admissible) – 2. Chercher à effectuer un pivotage (itération) : • Si tous les coefficients des variables de la fonction objectif sont positifs alors il ny a pas doptimum fini, STOP • Si tous les coefficients des variables de la fonction objectif sont négatifs, loptimum est atteint, STOP • Sinon, choix de la variable dentrée, choix de la variable de sortie, pivotage
Correction : – Le problème est la terminaison qui nest pas garantie a priori.
Règle de Bland : lors dun pivotage, la variable qui entre est celle dindice minimal parmi celles qui peuvent rentrer, et la variable qui sort est celle dindice minimal parmi celles qui peuvent sortir. Proposition : le simplexe termine avec la règle de Bland
14
7
Problème de linitialisation
Dictionnaire initial: x = b -(1a x im) n+i ijj=1,n ij z =c x j=1,n j j Il nest réalisable que si les b sont non négatifs (le vecteur 0 est une solution i initiale) Sinon, on construit le programme auxilliaire suivant : min x 0 s.c.xa x - b (1im) j=1,n ij j 0 i  x0 (0jn) j Une solution réalisable est facile à obtenir pour ce problème Le programme initial a une solution réalisable ssi ce problème a pour valeur optimale 0
Exemple
15
Problème initial : max z = x - x + x s.c. 1 2 3 2x - x + 2x4 1 2 3 2x - 3x + x-5 1 2 3 -x + x - 2x-1 1 2 3 x , x , x0 1 2 3 Dictionnaire initial non réalisable -> Problème auxilliaire : max z = - x 0 s.c. 2x - x + 2x - x4 1 2 3 0 2x - 3x + x - x-5 1 2 3 0 -x + x - 2x - x-1 1 2 3 0 x , x , x , x0 0 1 2 3 Son dictionnaire initial : x = 4 - 2x + x - 2x + x 4 1 2 3 0 x = -5 - 2x + 3x - x + x 5 1 2 3 0 x = -1 + x - x + 2x + x 6 1 2 3 0 z = - x 0 On rentre x dans la base et sort la variable la plus négative x 0 5 16
8
On obtient alors le dictionnaire : x = 5 + 2x - 3x + x + x 0 1 2 3 5 x = 9 - 2x - x + x 4 2 3 5 x = 4 + 3x - 4x + 3x + x 6 1 2 3 5 z = -5 - 2x + 3x - x - x 1 2 3 5
En 2 itérations du simplexe, on obtient : x = 8/5 - 1/5x + 1/5x + 3/5x - 4/5x 3 1 5 6 0 x = 11/5 + 3/5x + 2/5x +1/5x - 3/5x 2 1 5 6 0 x = 3 - x - x + 2x 4 1 6 0 z = - x 0 Valeur optimale 0 => il existe une solution réalisable au problème initial => on obtient un dictionnaire réalisable au problème initial en éliminant la colonne de x et en écrivant lobjectif en fonction des variables hors-0 base : x = 8/5 - 1/5x + 1/5x + 3/5x 3 1 5 6 x = 11/5 + 3/5x + 2/5x + 1/5x 2 1 5 6 x = 3 - x - x 4 1 6 z = -3/5 + 1/5x - 1/5x + 2/5x (z = x - x + x ) 1 5 6 1 2 3
Itération
17
La variable dentrée est une variable hors-base dont le coefficient dans la dernière ligne du dictionnaire courant est positif La variable de sortie est une variable de base dont la non-négativité impose la contrainte la plus forte sur la borne supérieure de la variable dentrée choisie. Si on ne trouve pas de variable de sortie, lobjectif peut prendre une valeur aussi grande que lon veut et le problème est donc non borné Peut-on générer un nombre infini de dictionnaires ? Oui Exemple (on choisit en entrée la variable dont le coefficient est le plus grand dans la ligne z, et en sortie, celle dont lindice est le plus petit) :  max 10x -57x -9x -24x s.c. 1 2 3 4 0.5x - 5.5x -2.5x +9x0 1 2 3 4 0.5x - 1.5x -0.5x - x0 1 2 3 4 x1 1 Ce cyclage apparaît lorsque lon retombe sur un même dictionnaire
18
9
Théorèmes
La seule façon de ne pas terminer est le cyclage. Il existe des méthodes pour lever le cyclage Preuve : il y a un nombre fini de façons de choisirmvariables de base parmi lesn+mvariables. Il suffit de montrer que deux dictionnaires ayant la même base sont identiques Vitesse : – En pratique, on observe que le nombre ditérations requis est de lordre de3m/2mest le nombre de contraintes (ne dépend pas du nombre de variables) -> CPLEX, OSL, XPRESS, MPSX,  – Quelques exemples pathologiques engendrent un nombre ditérations exponentiel : n-j max10 x s.c. j=1,n j i-j i-1 210 x + x= 1, ,n)100 (i j=1,i-1 j i x0 (j = 1, , n) j n-1 2 itérations
19
10
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.