Recherche opérationnelle - Programmation linéaire : polyèdre des contraintes, approche de résolution analytique, etc.

Thèmes abordés

Cours de recherche opérationnelle, programmation linéaire, polyèdre des contraintes, contraintes linéaires, optimisation d'une fonction linéaire, algorithme simplexe, exercices, exemples

Résumé du document

Un problème de programmation linéaire peut être défini comme le problème d'optimisation (maximisation ou minimisation) d'une fonction linéaire soumise à des contraintes linéaires.
Les contraintes peuvent être d'égalités ou d'inégalités. Partons d'un exemple simple...

Dans ce problème, il existe deux inconnues, et cinq contraintes. Toutes les contraintes sont des inégalités et elles sont toutes linéaires dans le sens qui implique chacun une inégalité dans une fonction linéaire des variables.

Extraits

[...] am j . cj . Pn Produits de l'entreprise i P an 2 an . i an . m an cn b1 b bi . bm Achat a ij . [...]

[...] Rappelons que sous l'hypothèse de rang plein, le système A.x b admet une infinité de solutions qui construisent un ensemble D : x n / A.x b ou A.x b ou A.x b appelé domaine des solutions acceptables. II.1. Standardisation Un programme linéaire est mis sous forme standard lorsque toutes ses contraintes sont des égalités et toutes ses variables sont non-négatives. Page 1 Cours de Recherche Opérationnelle z x sc : A.x b 0 Cycle Ingénieurs (I.1) II.2. Forme canonique Un programme linéaire est sous forme canonique pure lorsque toutes ses contraintes sont des inégalités et toutes ses variables sont non-négatives : z x sc : A. [...]

[...] Variables hors-base 1 xH Fob 11 yH . s xB s yH m xB Variables de base 1 xB m yH 1 e xH 1e yH . se yH . me yH . Secondmembres Variables de base Critère choix VS n xH m 1 xB . s xB . [...]

[...] On réexamine les signes des nouveaux coefficients de la FO (dernière ligne du tableau) et on poursuit l'itération ou on arrête l'algorithme et on retient les valeurs optimales trouvées. Dans le cas particulier d'un problème déjà écrit sous forme canonique Ax b avec b les variables d'écart constituent une solution acceptable de base évidente xB . Ainsi : xH x T cB 0 T c T H b et z * 0 j c j * A (aij ) Alors, le tableau simplexe se simplifie : Page 32 Cours de Recherche Opérationnelle Cycle Ingénieurs Variables hors-base . x1 xe . [...]

[...] Cherchons les volumes d'optimisation : Soit x i le volume du mélange Mi. La fonction objectif à maximiser s'écrit z 5x1 4 x et les contraintes sont exprimées par: x1 4 x2 24 x 2x 1 x2 2 x 1 x1 ; x2 0 Alors, il suffit de considérer le polyèdre des contraintes obtenu par l'intersection des droites d'équations : : x1 D2 : x2 0 : x 1.5 x : x2 0.5 x1 3 : x 2 : x2 x1 1 Page 12 Cours de Recherche Opérationnelle Cycle Ingénieurs Partant de z on peut connaitre la pente de la droite de la fonction objectif à maximiser ( x2 1.25 x1 0.25 z Ainsi, si on déplace cette droite dans le sens d'augmentation de z (pour maximiser le critère), son intersection avec le polyèdre des contraintes nous fournira la solution optimale qui correspond dans ce cas au sommet S5. [...]