La programmation linéaire en nombres entiers

Résumé du document

Pour résoudre les problèmes d'optimisation combinatoire nous pouvons être tentés par la méthode d'énumération explicite de toutes les solutions réalisables, mais ceci deviendra très difficile sinon impossible dès que l'on a un problème de taille moyenne.

Extraits

[...] < number > 05/11/19 < number > 2.2 Procédure Générale Etape La liste des candidats contient le problème Poser zs = +. Etape Terminer si la liste est vide: Si au moins une solution réalisable de a été rencontrée alors le point "incumbent" est une solution optimale de Sinon, le problème est non réalisable. Etape Choisir un problème dans la liste qui devient le (PC). Eliminer ce de la liste. Etape Identifier une relaxation (PCR) de (PC). 05/11/19 < number > Procédure Générale Etape Traiter (PCR). [...]

[...] Stérilisation: Si le (PCR) n'est pas réalisable alors retourner en 2. Sinon, si zi  zs alors retourner en 2. Sinon, si zi est atteinte en un point entier réalisable (zi [...]

[...] En effet, Le (PCR) est réalisable. zi [...]

[...] Leur principe est très simple comme on le verra dans ce cours. L'efficacité pratique des algorithmes basés sur ces méthodes dépend beaucoup de la manière utilisée pour effectuer la séparation et surtout l'évaluation. 05/11/19 < number > Min CT x (PNE) s. à Ax = b x 0 xj entier , avec x xn)T Programmation Linéaire Continue : PLC pas de contraintes d'intégrité Programmation Linéaire Mixte : PLM certaines variables peuvent ne pas être entières Programmation Linéaire en nombres Entiers: PLE contraintes d'intégrité Programmation Linéaire Binaire : PLB xj = 0 ou 1 05/11/19 < number > Méthodes Naïves : 1°) Méthode d'Arrondi : Min z = -x1 - x2 s. [...]

[...] Alors, pourquoi ne pas arrondir la solution optimale du problème continu ? Mais là aussi, nous pouvons avoir des surprises. Ainsi, lorsqu'il s'agit de remplacer un plan de production optimal consistant à fabriquer 3426,5 verres par la solution arrondie de 3426 verres, tout utilisateur averti n'hésitera pas à le faire, d'autant plus lorsqu'on sait que le fait d'arrondir aura de très faibles chances de rendre le plan de production non réalisable. 05/11/19 < number > Par contre, si un plan de production consiste à construire 3,75 bateaux, alors le choix de construire 3 ou 4 bateaux peut avoir des répercussions importantes sur la politique de l'entreprise. [...]