Cours 9 : programmation linéaire (recherche opérationnelle
10
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
10
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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
Voir
- solutions réalisables
- simplification par élimination de variables ¶
- itération ¶
- x3 ≤
- max z
- x3
- x1
- x2
- choix
- variable
- variables
• • • •
•
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 dune 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(linformation 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 x≤24000, x≤2000, x≤6000, p ,p≥0 1 2 3 1 2 Lobjectif(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.44p≤24000 1 2 0.05p + 0.10p≤2000 1 2 0.10p + 0.36p≤6000 1 2 p ,p≥0 1 2
Forme standard(on peut toujours sy ramener) :
max∑c x j=1,n j j sous contraintes∑a x≤b (1≤i≤m) j=1,n ij j i x≥0 (1≤j≤n) 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 lobjectif (pas nécessairement unique) Il nexiste pas forcément de solution optimale (soit il nexiste pas de solution réalisable, soit il nexiste pas de valeur optimale finie) : max x -x 1 2 sous contraintes : -2x + x≤-1 1 2 -x -2x≤-2 1 2 x , x≥0 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 + x≤5 1 2 3 4x + x + 2x≤11 1 2 3 3x + 4x + 2x≤8 1 2 3 x , x , x≥0 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 , x≥0 1 2 3 4 5 6
5
6
3
•
•
•
•
• •
•
Itération
Idée 2 :dune 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 lobjectif (dune 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 Jusquoù augmenter ? – x≥0 => x≤5/2, x≥0 => x≤11/4, x≥0 => x≤8/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 lexpression de z, on voit que lamélioration ne peut être obtenue que par laugmentation de x . x , x≥0 => (x≤5) & (x≤1). 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 x≤b (1≤i≤m) j=1,n ij j i x≥0 (1≤j≤n) j On introduit les variables décarts x , , x : n+1 n+m x = b -∑(1a x ≤i≤m) n+i ijj=1,n ij x≥0 (1≤j≤n+m) j Chaque itération de lalgorithme 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 dun 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 lamélioration de lobjectif 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 dune dictionnaire à un autre (ou encore de passer dune base à une autre)
Exemple
max z = 5x + 5x + 3x s.c. 1 2 3 x + 3x + x≤3 1 2 3 -x + 3x≤2 1 3 2x - x + 2x≤4 1 2 3 2x + 3x - x≤2 1 2 3 x , x , x≥0 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 - x≥0 => x1≤3 4 1 x = 2 + x => x1≥-2 5 1 x = 4 - 2x => x1≤2 6 1 x = 2 - 2x =>x1≤1 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 Lorsquil ny 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 dune base admissible) – 2. Chercher à effectuer un pivotage (itération) : • Si tous les coefficients des variables de la fonction objectif sont positifs alors il ny a pas doptimum fini, STOP • Si tous les coefficients des variables de la fonction objectif sont négatifs, loptimum est atteint, STOP • Sinon, choix de la variable dentrée, choix de la variable de sortie, pivotage
Correction : – Le problème est la terminaison qui nest pas garantie a priori.
–
–
Règle de Bland : lors dun pivotage, la variable qui entre est celle dindice minimal parmi celles qui peuvent rentrer, et la variable qui sort est celle dindice minimal parmi celles qui peuvent sortir. Proposition : le simplexe termine avec la règle de Bland
14
7
•
•
•
• •
•
•
•
•
Problème de linitialisation
Dictionnaire initial: x = b -∑(1a x ≤i≤m) n+i ijj=1,n ij z =∑c x j=1,n j j Il nest 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 (1≤i≤m) j=1,n ij j 0 i x≥0 (0≤j≤n) 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 + 2x≤4 1 2 3 2x - 3x + x≤-5 1 2 3 -x + x - 2x≤-1 1 2 3 x , x , x≥0 1 2 3 Dictionnaire initial non réalisable -> Problème auxilliaire : max z = - x 0 s.c. 2x - x + 2x - x≤4 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 , x≥0 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 lobjectif 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 dentré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 dentrée choisie. Si on ne trouve pas de variable de sortie, lobjectif peut prendre une valeur aussi grande que lon 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 lindice est le plus petit) : max 10x -57x -9x -24x s.c. 1 2 3 4 0.5x - 5.5x -2.5x +9x≤0 1 2 3 4 0.5x - 1.5x -0.5x - x≤0 1 2 3 4 x≤1 1 Ce cyclage apparaît lorsque lon 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 ditérations requis est de lordre de3m/2oùmest le nombre de contraintes (ne dépend pas du nombre de variables) -> CPLEX, OSL, XPRESS, MPSX, – Quelques exemples pathologiques engendrent un nombre ditérations exponentiel : n-j max∑10 x s.c. j=1,n j i-j i-1 2∑10 x + x≤= 1, ,n)100 (i j=1,i-1 j i x≥0 (j = 1, , n) j n-1 2 itérations
19
10
