La Programmation Linéaire Mixte (PLM)

Thèmes abordés

Programmation Linéaire Mixte, PLM, algorithme de coupe, optimisation linéaire, variables entières binaires, variables réelles et binaires, variables entières et réelles

Résumé du document

La PLM désigne les problèmes d'optimisation linéaire faisant intervenir plusieurs types de variables.

Applications:
- théorie de jeux
- Optimisation des réseaux
- le problème de localisation du transport
- fabrication par lot
…….

Extraits

[...] la borne globale inferieure, est la valeur de la meilleur solution entière trouvée. est la valeur objective de la solution optimale du programme linéaire définit par le nœud V. Méthode des coupes de Gomory Principe des méthodes de coupes Introduire de nouvelles contraintes linéaires au problème pour réduire le domaine réalisable du problème relaxé sans pour autant éliminer de points du domaine réalisable du problème avec les contraintes de nombre entier sur les variables. La procédure consiste à résoudre une suite de problèmes relaxés jusqu'à ce qu'une solution optimale en nombres entiers soit obtenue. [...]

[...] I Soit fi le cout fixe d'avoir un dépôt a i . J clients . ; j ; . ; J Soit cij le cout de satisfaire la demande du client j du dépôt i Pour simplifier les modèles, nous ne considérons pas les capacités. Formulation min ∑i fi yi +∑i ∑j cijxij soumis a ∑i xij = 1 quelque soit j xij yi quelque soit i , j yj appartient à quelque soit j xij appartient à quelque soit i , j Résolution graphique Exemple x1,x2 deux entiers Résolution graphique (suite) Résolution graphique Exemple x1 entier ,x2 réel Notez bien que la solution optimale est ( ) avec objectif 5.05 Algorithmes de résolution des PLMs Pour la résolution des problèmes de la PLM il existe plusieurs algorithmes d'où on peut citer: Branch and bound Méthode des coupes de Gomory Algorithme de Branch and bound On crée un arbre de recherche et d‘énumération. [...]

[...] A chaque nœud, on résout un programme linéaire. Ce qu'on fait dépend sur les valeurs des variables qui doivent prendre des valeurs entières. Deux choix principales: 1 Couper le nœud(a cause des bornes; borne = "bound"). Il y a trois raisons pour lesquelles on peut couper un nœud : La relaxation linéaire n'est pas de solution réalisable. La valeur objective de la relaxation linéaire n'est pas meilleurs que la valeur objective de la meilleure solution entière déjà trouvée. La solution optimale de la relaxation linéaire est déjà entière Diviser le nœud ("branch"). [...]