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

Claude Jard

Description

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

Sujets

• Variable
• Solution
• Élimination
• Problème
• cours

Informations

• Publié par: aproe
• Nombre de lectures: 1 415
• Langue: Français

Extrait

• • • •

•

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 x≤24000, x≤2000, x≤6000, p ,p≥0 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.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 sy 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 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 , 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 :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 ? – 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 lexpression de z, on voit que lamélioration ne peut être obtenue que par laugmentation 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 i jj=1,n ij x≥0 (1≤j≤n+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 + 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 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 ≤i≤m) n+i i jj=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 (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 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 +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 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/2oùmest 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 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