[PDF] Programmation Linéaire en nombres entiers MOD 4.4: Recherche

View - Download Programmation Linéaire en nombres entiers MOD 4.4: Recherche

Previous PDF

Next PDF

Programmation Lineaire en nombres entiers

MOD 4.4: Recherche operationnelle

Nicolas Bousquet

Ecole Centrale de Lyon

1/23

Rappel

Lors des premiers cours, on a vu:

Comment

r esoudre un p rogrammelin eaireen nomb rer eelgr ^aceau

Simplexe.

Comment

d enirle dual d'un PL . Que dans le cas d'un programme lineaire en nombre entier (PLNE), c'etait plus complique. On a vu (en BE), que si la matrice de contraintes est TU alors solutions reelles et entieres etaient \les m^emes".

Aujourd'hui:

Que fait-on dans les autres cas?

2/23

Algorithm \Branch and Bound"

Idee: Si une solution n'est pas entiere alors on va essayer de rendre un coecient \entier".)On prend un coecientxinon entier dans la solution optimale courantextel quexiest non entier. On cree deux PL, un ou on rajoute la contraintexi bxicand l'autrexi dxie. On fait deux appels recursifs et on renvoie la meilleure solution.Structure de l'algorithme:

On veut resoudre un PL en nombre entiers:

On commence par le resoudre en nombre reel.

Si la solution optimale est entiere on renvoie la solution et sa valeur. Sinon on prend une variable non entierex=. On cree deux nouveaux PL avec les anciennes contraintes plusx bcpour l'un etx depour l'autre.

On retourne le maximum des deux resultats.

3/23

Algorithm \Branch and Bound"

Idee: Si une solution n'est pas entiere alors on va essayer de rendre un coecient \entier".)On prend un coecientxinon entier dans la solution optimale courantextel quexiest non entier. On cree deux PL, un ou on rajoute la contraintexi bxicand l'autrexi dxie. On fait deux appels recursifs et on renvoie la meilleure solution.Structure de l'algorithme:

On veut resoudre un PL en nombre entiers:

On commence par le resoudre en nombre reel.

Si la solution optimale est entiere on renvoie la solution et sa valeur. Sinon on prend une variable non entierex=. On cree deux nouveaux PL avec les anciennes contraintes plusx bcpour l'un etx depour l'autre.

On retourne le maximum des deux resultats.

3/23

Algorithm \Branch and Bound"

Idee: Si une solution n'est pas entiere alors on va essayer de rendre un coecient \entier".)On prend un coecientxinon entier dans la solution optimale courantextel quexiest non entier. On cree deux PL, un ou on rajoute la contraintexi bxicand l'autrexi dxie. On fait deux appels recursifs et on renvoie la meilleure solution.Structure de l'algorithme:

On veut resoudre un PL en nombre entiers:

On commence par le resoudre en nombre reel.

Si la solution optimale est entiere on renvoie la solution et sa valeur. Sinon on prend une variable non entierex=. On cree deux nouveaux PL avec les anciennes contraintes plusx bcpour l'un etx depour l'autre.

On retourne le maximum des deux resultats.

3/23

Algorithm \Branch and Bound"

Idee: Si une solution n'est pas entiere alors on va essayer de rendre un coecient \entier".)On prend un coecientxinon entier dans la solution optimale courantextel quexiest non entier. On cree deux PL, un ou on rajoute la contraintexi bxicand l'autrexi dxie. On fait deux appels recursifs et on renvoie la meilleure solution.Structure de l'algorithme:

On veut resoudre un PL en nombre entiers:

On commence par le resoudre en nombre reel.

Si la solution optimale est entiere on renvoie la solution et sa valeur. Sinon on prend une variable non entierex=. On cree deux nouveaux PL avec les anciennes contraintes plusx bcpour l'un etx depour l'autre.

On retourne le maximum des deux resultats.

3/23

Algorithm \Branch and Bound"

Idee: Si une solution n'est pas entiere alors on va essayer de rendre un coecient \entier".)On prend un coecientxinon entier dans la solution optimale courantextel quexiest non entier. On cree deux PL, un ou on rajoute la contraintexi bxicand l'autrexi dxie. On fait deux appels recursifs et on renvoie la meilleure solution.Structure de l'algorithme:

On veut resoudre un PL en nombre entiers:

On commence par le resoudre en nombre reel.

Si la solution optimale est entiere on renvoie la solution et sa valeur. Sinon on prend une variable non entierex=. On cree deux nouveaux PL avec les anciennes contraintes plusx bcpour l'un etx depour l'autre.

On retourne le maximum des deux resultats.

3/23

Illustration

4/23

Illustration

4/23

Illustration

4/23

Illustration

4/23

Illustration

4/23

Formalisation

Soit (P) le programme lineaire en entree.

On calcule une solution optimalexde (P).

Si le PL n'est pas satisable, alors on renvoie1(ou +1pour un probleme de minimisation).

Sixest un vecteur entier, alors on renvoiex.

Sinon soitxiune coordonnee dexnon entiere

Creer deux PL (P') et (P") ou (P')= (P) plus la contrainte x i bxicet (P") = (P) plus la contraintexi dxie. Renvoyer le maximum entre l'optimal entier de (P') et l'optimal entier de (P").

Lemme:L'algorithme termine.

5/23

Ameliorations possibles

Remarque:

On peut se souvenir de la meilleure solution entiere qu'on a trouve jusqu'a present. Si la solution en nombre reel de la composante qu'on considere est inferieure, on peut \couper la branche".Remarque 2: On peut en fait facilement calculer la solution optimale du nouveau

PLsans tout recalculer!

Bien choisir son heuristique pour la variable a modier (vaste sujet)Remarque 3: Si on considere un problemef0;1g(ou toutes les variables prennent des valeurs dans 01), alors les contraintes qu'on rajoute sont du type \je selectionne / je ne selectionne pas" la variable, ce qui est assez peu informatif... 6/23

Ameliorations possibles

Remarque:

On peut se souvenir de la meilleure solution entiere qu'on a trouve jusqu'a present. Si la solution en nombre reel de la composante qu'on considere est inferieure, on peut \couper la branche".Remarque 2: On peut en fait facilement calculer la solution optimale du nouveau

PLsans tout recalculer!

Bien choisir son heuristique pour la variable a modier (vaste sujet)Remarque 3: Si on considere un problemef0;1g(ou toutes les variables prennent des valeurs dans 01), alors les contraintes qu'on rajoute sont du type \je selectionne / je ne selectionne pas" la variable, ce qui est assez peu informatif... 6/23

Ameliorations possibles

Remarque:

On peut se souvenir de la meilleure solution entiere qu'on a trouve jusqu'a present. Si la solution en nombre reel de la composante qu'on considere est inferieure, on peut \couper la branche".Remarque 2: On peut en fait facilement calculer la solution optimale du nouveau

PLsans tout recalculer!

Bien choisir son heuristique pour la variable a modier (vaste sujet)Remarque 3: Si on considere un problemef0;1g(ou toutes les variables prennent des valeurs dans 01), alors les contraintes qu'on rajoute sont du type \je selectionne / je ne selectionne pas" la variable, ce qui est assez peu informatif... 6/23

Methode 2: Cutting planes

Idee:Trouver une nouvelle contrainte qui:

Ne modie pas l'ensemble des contraintes entieres;

Elimine un point non entier de l'emble des solutions du PL en nombre reel. En d'autres termes, on cherche une contrainte qui ne va pas modier les solutions entieres (et donc l'optimale ne va pas changer) mais va couper une partie de l'ensemble faisable en nombre reel. 7/23

Exemple11

8/23

Exemple11

8/23

Exemple11

8/23

Exemple

8/23

Exemple

8/23

Exemple

8/23

Coupes de Gomory

Question:Comment trouver une telle coupe en general?

Soit le Simplexe renvoie un solution entiereX.

Soit il existe au moins un coecient non entier (disonsxi) a la n de l'algorithme. On a donc: x i+X jnon basiquea jxj=bi)xi+X jnon basiquebajcxjbi (vrai pour n'importe quelle solution))xi+X jnon basiquebajcxj bbic (vrai pour n'importe quelle solutionentiere !) 9/23

Coupes de Gomory

Question:Comment trouver une telle coupe en general?

Soit le Simplexe renvoie un solution entiereX.

Soit il existe au moins un coecient non entier (disonsxi) a la n de l'algorithme. On a donc: x i+X jnon basiquea jxj=bi)xi+X jnon basiquebajcxjbi (vrai pour n'importe quelle solution))xi+X jnon basiquebajcxj bbic (vrai pour n'importe quelle solutionentiere !) 9/23

Coupes de Gomory

Question:Comment trouver une telle coupe en general?

Soit le Simplexe renvoie un solution entiereX.

Soit il existe au moins un coecient non entier (disonsxi) a la n de l'algorithme. On a donc: x i+X jnon basiquea jxj=bi)xi+X jnon basiquebajcxjbi (vrai pour n'importe quelle solution))xi+X jnon basiquebajcxj bbic (vrai pour n'importe quelle solutionentiere !) 9/23

Coupes de Gomory

Question:Comment trouver une telle coupe en general?

Soit le Simplexe renvoie un solution entiereX.

Soit il existe au moins un coecient non entier (disonsxi) a la n de l'algorithme. On a donc: x i+X jnon basiquea jxj=bi)xi+X jnon basiquebajcxjbi (vrai pour n'importe quelle solution))xi+X jnon basiquebajcxj bbicquotesdbs_dbs7.pdfusesText_13

[PDF] exercices recherche operationnelle

[PDF] theme astral chinois complet gratuit interpretation

[PDF] cours recherche opérationnelle methode de simplexe

[PDF] recherche opérationnelle simplexe exercices corrigés

[PDF] livre recherche opérationnelle pdf

[PDF] cours et exercices corrigés de recherche opérationnelle+pdf

[PDF] inpes

[PDF] methode boscher pdf download

[PDF] méthode boscher cahier de lecture pdf

[PDF] methode boscher en ligne

[PDF] méthode boscher gratuit

[PDF] méthode boscher cahier des sons pdf

[PDF] adjectif pour acrostiche

[PDF] recherche qualitative définition

[PDF] méthode qualitative et quantitative