Recherche opérationnelle : programmation linéaire exercices et solutions

Thèmes abordés

Recherche opérationnelle, programmation linéaire, modélisation, résolution, exercices, solutions, mathématiques

Résumé du document

La formulation du modèle mathématique est l'étape la plus délicate de la résolution d'un problème. Il nécessite un effort de conception qui doit aboutir à la détermination des trois éléments suivants :
Formalisation : en 4 étapes
· Compréhension du problème
· Identification des variables de décision (qui sont les inconnus du problème)
· Fixation des objectifs à atteindre => la fonction objective
· Précision des contraintes du problème, contraintes exprimées sous forme linéaire par rapport aux variables de décision => les sous contraintes

Extraits

[...] Les formes d'un programme linéaire On distingue trois formes : La forme standard La forme canonique L'écriture Matricielle 1. La forme canonique Tout programme linéaire peut s'écrire sous forme d'un système avec un ensemble d'inégalités (contraintes) et une fonction à optimiser, qu'on appelle la forme canonique. La fonction économique : Max = Sous contraintes : bi m : nombre de contraintes n : nombre de variables pour 1 i m pour 1 j n contraintes propres contraintes impropres de positivité Exemple : Max Z = 5x1+8x2 Sous contraintes : : 5x1+8x2 x1+5x2 x1 x2 1000 200 300 500 x1 0 ; x2 0 2. [...]

[...] - La valeur de la fonction économique Z pour chaque programme admissible est l'opposé du nombre sur la ligne de Z dans la colonne second membre d. Exemples d'application Max 5x1+7x2 S.C : x1+ 2x2 12 3x1+ 2x2 18 x1 + x2 7 x1 0 ; x 2 0 Le PL sous forme standard : Max 5x1+3x2+0*x3+0*x4+0*x5 S.C : x1+ 2x2 + x3 3x1+ 2x2 x1 + x2 = 12 + x4 = 18 +x5 = 7 x1 0 ; x 2 0 ; x 3 0 ; x 4 0 ; x 5 0 Sous forme tableau : Le pivot Variable de décision Variables d'écart Le plus petit Second membre x1 x3 Variables dans la base x x x x bi coef x4 x5 Fonction économique Z 7 Plus grand x1 x2 x4 x5 Z 1/2 x x3 1/2 x x bi coef L'1= / 2 L'2 = L2 - 2L'1 L'3= L3- L'1 L'4 = L4-7L' - 3/2 x1 x2 x4 x1 Z x x x x5 - bi -45 coef L''1 = L'1-1/2* L''3 L''2= L'2 - 2L''3 L''3=(L'3)/(1/2) L''4 = L'4 - 3/2 L''2 Tous les coefficients sur la ligne de la fonction économique sont négatifs ou nuls, le maximum est donc atteint. [...]

[...] Correspondance Dual - Primal À chaque problème de programmation linéaire est associé un autre problème de programmation linéaire appelé le dual. La première forme d'optimisation s'appelle le Primal sa transformative s'appelle le Dual : Primal Max S/C : B Min S/C : At Dual Tableau des correspondances : Primal Fonction Objectif (max) Second membre C A = matrice des contraintes Contrainte i : Contrainte i : = Variable xj 0 Variable xj 0 At : Transposée de la matrice A Remarque : le dual du dual c'est le primal. [...]

[...] Ces exemples portent sur des problèmes pour lesquels la modélisation en programme linéaire est bien adaptée et clairement explicitée. Exemple 1 : Programme de production d'une usine Une usine fabrique deux produits A et B à partir des matières premières M1, M2 et M3 qui sont limités. Le profit réalisé à la vente du produit est 4 Dh pour le produit A Dh pour le produit B. Le tableau suivant explique la nomenclature de chaque produit, ainsi que le stock disponible pour chaque matière. [...]

[...] 2 valeur optimale de la fonction économique du primal est égale à la valeur optimale de la fonction économique du dual. 3 contrainte du primal à l'optimum n'est pas saturée la variable correspondante est nulle. c. Exemples d'application: Résoudre le programme linéaire suivant : Min Z = 12y1+ 7y2 + 18y3 : y1+ y2 + 3y3 5 2y1+ y2 + 2y3 7 y1 0 ; y2 0 ; y3 0 Dual : Max 5x1+7x2 : x1+ 2x2 12 7 x1 + x 2 3x1+ 2x2 18 x1 0 ; x 2 0 x1+ 2x2 = 12 d'où, les points appartenant à x1+ x2 = 7 d'où, les points appartenant à 3x1+ 2x2 = 18 d'où, les points appartenant à A(0 42 B(2 45 C 41 D - et (12 et ( 7 et ( 6 y B(2 C(4 D(6 x Les points A(0 , B(2 C et D sont les solutions possibles On remplace ces points dans la fonction objective on trouve : A(0 42 B(2 45 C 41 D 30 La solution optimale est donc : x1= 2 ; x2 et Z = 45 D'après le Th1 : le primal admet une solution D'après le Th2 : ZD =45 ZP= 45 D'après le Th3 : 1ère Contrainte : 2 + 5 = 12 Contrainte saturée ème 2 Contrainte : 2 + 5 = 7 Contrainte saturée ème 3 Contrainte : 3*2 + 2*5 =16 18 Contrainte non-saturée y1+ y2 = 5 y1 = 2 2y1+ y2 = 7 y2 = 3 D'où la solution est ; 3 ; y3=0 d. [...]