Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Correction de devoir maison n  1 : Exercice 11 : Les données de l’exercice : P

Correction de devoir maison n  1 : Exercice 11 : Les données de l’exercice : PV1 PV1 OFFRES R1 3 4 100 R2 1 3 20 Demandes 40 80 a) Formulation mathèmatique: Puisque l’entreprise veut savoir comment acheminer la marchandise, donc les variables de dècision sont : Xij : ”quantitè de carburant à acheminer de la raffinerie i vers le point de vent j” , avec : i = 1,2 et j = 1 , 2 ; où : -raffinerie 1 : RA -raffinerie 2 : RB -point de vente 1 : PV1 -pointdevente2:PV2 . Xij ≥ 0  i=1,2 , j=1,2. Contraintes de l’offre : une raffinerie ne peut vendre plus que sa production max : X11 + X12 ≤ 100 X21 + X22 ≤ 20 Contraintes de la demande : la quantitè à acheminer vers un point de vente est au moins sa demande min : X11 + X21 ≥ 40 X12 + X22 ≥ 80 La fonction objectif : l’objectif vise à minimiser le coût total de transport, dont l’expression mathèmatique est : Min(Z) = 3X11 + 4X12 + X21 + 3X22. Si on somme les deux premiéres contraintes, on obtient : X11 +X12 +X21 +X22 ≤ 120 Aussi,si on somme les deux derniéres contraintes, on obtient : X11 + X21 + X12 + X22 ≥ 120 Donc, X11 + X12 + X21 + X22 = 120 car l’offre = demande. Toutes les contraintes peuvent alors être mise sous forme d’ ́egalitès. Ainsi le PL (P). X11 + X12 = 100 X21 + X22 = 20 X11 + X21 = 40 X12 + X22 = 80 Xij ≥0,i=1,2etj=1,2 min Z = 3X11 + 4X12 + X21 + X22. b) Le programme linéaire dual : On fait correspondre aux contraintes de l’offre les variables ui et aux contraintes de demande les variables vj, i = 1,2 et j = 1,2. u1 + v1 ≤ 3 u1 + v2 ≤ 4 u2 + v1 ≤ 1 u2 + v2 ≤ 3 ui ∈R,vj ∈R,i=1,2etj=1,2. MaxW = 100u1 + 20u2 + 40v1 + 80v2. c) Interprètation économique du dual: Le problème dual exprime le point de vue du transporteur qui veut maximiser son profit. Ses variables sont les prix d’achat à la raffinerie 1 (u1) et à la raffinerie 2 (u1) et ses prix de vente à PV1 (v1) et à PV2 (v1). d)Résoudre le (PL) par l’algorithme du simplexe : (Pour appliquer l’algorithme du simplexe j’ai changé les notations des variables comme suite X1,1 = X1 , X1,2 = X2 , X2,1 = X3 , X2,2 = X4). Parceque le problème d'optimisation n'a pas une solution base valide pour commencer l'algorithme du simplexe on utilise a méthode de deux phases. D'abord on ajouter les variables d’écart et les variables artificielles et puis on applique l’algorithme du simplexe avec une nouvelle fonction objectif . Et on obtient le PL auxiliaire suivant : X1 + X2 + X5 = 100. X3 + X4 + X6 = 20. X1 + X3 - X7 + V1 =40…………. (1) + X2 + X4. – X8 + V2 =80…………. (2) V1 + V2 = min W……… (*) De (1) et (2) on a : V1 = 40 - X1 -X3 +X7 et V2 = 80 - X2 – X4 + X8 Alors (*) devient : - X1 - X2 - X3 – X4 +X7 + X8 = min W – 120. (On commence avec X5, X6, V1, V2 comme variables de base) Phase 1 : X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b X5 1 1 0 0 1 0 0 0 0 0 100 X6 0 0 1 1 0 1 0 0 0 0 20 V1 1 0 1 0 0 0 -1 0 1 0 40 V2 0 1 0 1 0 0 0 -1 0 1 80 -W -1 -1 -1 -1 0 0 1 1 0 0 -120 C1 = -1 <0 alors S= 1 I= {i: A1 i >0} = {1} L= {l: bl\ A1 l = min { bi\ A1 i} } = {40} ❑ ⇒ r= 3 ; col(r)= V1. X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b X5 0 1 -1 0 1 0 1 0 -1 0 60 X6 0 0 1 1 0 1 0 0 0 0 20 X1 1 0 1 0 0 0 -1 0 1 0 40 V2 0 1 0 1 0 0 0 -1 0 1 80 -W 0 -1 0 -1 0 0 0 1 1 0 -80 C2= -1 <0 alors S= 2 I= {i: A2 i >0} = {1} L= {l: bl\ A2 l = min { bi\ A2 i} } = {60} ❑ ⇒ r= 1 ; col(r)= X5. X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b X2 0 1 -1 0 1 0 1 0 -1 0 60 X6 0 0 1 1 0 1 0 0 0 0 20 X1 1 0 1 0 0 0 -1 0 1 0 40 V2 0 0 1 1 -1 0 -1 -1 1 1 20 -W 0 0 -1 -1 1 0 1 1 0 0 -20 C3= -1 <0 alors S= 3 I= {i: A3 i >0} = {1} L= {l: bl\ A3 l = min { bi\ A2 i} } = {20} ❑ ⇒r= 2 ; col(r)= X6. X1 X2 X3 X4 X5 X6 X7 X8 V1 V2 b X2 0 1 0 1 0 1 1 0 -1 0 80 X3 0 0 1 1 0 1 0 0 0 0 20 X1 1 0 0 -1 0 -1 -1 0 1 0 20 V2 0 0 0 0 -1 -1 -1 -1 1 1 00 -W 0 0 0 0 1 1 1 1 0 0 00 W=0 alors on s’arrête là. On a donc terminé la phase 1 et maintenant on a une solution réalisable pour le PL initiale il nous reste donc qu’à vérifier Si cette solution est optimale. Pour cela on peut procéder en appliquant le simplexe encore une fois mais cette fois avec les coefficients qu’on a eu à la fin du phase 1 en remplaçant la fonction objectif W avec celle du PL initiale Z et en supprimant la 4éme contrainte contenant la variable artificielle V2 (i.e on applique la Phase 2 de simplexe). Sinon on a qu’à écrire le PL sous forme canonique dans la base réalisable qu’on a eu J= (X2, X3, X1). Posant A la matrice associée au PL dans la base canonique en supprimant la contrainte (2) avec la variable artificielle V2). Aj = 1 0 1 0 1 0 0 1 1 le det |AJ|=1#0 alors Aj est inversible. On utilisant la méthode de gausse on chercher l’inverse de Aj , (Aj)-1 : Aj = 1 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 −1 1 1 0 0 0 1 0 0 0 1 1 1 −1 0 1 0 0 −1 1 Alors : (Ai)-1 = 1 1 −1 0 1 0 0 −1 1 Maintenant cherchons la matrice associé au (PL) dans la base J , ^ A : ^ A = (Ai)-1 * A = 1 1 −1 0 1 0 0 −1 1 * 1 1 0 0 0 1 1 0 1 0 1 0 = 0 1 0 0 0 1 1 0 0 1 1 −1 Le second membre dans la base J,~ b : ~ b = (Ai)-1 * b = 80 20 20 Et enfin le cout de transport dans la base J, ~ C : ~ C = C- Ci *^ A = ( 3 41 3) – (4 1 3) * 0 1 0 0 0 1 1 0 0 1 1 −1 = ( 0 0 0 1 ). Puisqu’il s’agit d’un problème de minimisation et ~ C >= 0 ❑ ⇒ alors la base J est une une base optimale pour le (PL) et donc la solution X* est une solution optimale du (PL) avec : X* = (20,80,20,00) i.e. : (X1,1=20 , X2,1 =80, X2,1=20 ,X2,2=00) Cela veut dire que pour satisfaire les demandes des clients en minimisant les couts de transport et en respectant les quantités du production max des raffineries l’entreprise doit transporter : - 20 unités du Raffinerie A vers le point de vente 1. - 80 unités du Raffinerie A vers le point de vente 2. - 20 unités du Raffinerie B vers le point de vente 1. Avec un coût minimum totale Z*= 400. e) Résoudre le (PL) avec l’algorithme de transport : Méthode du coin nord-ouest : 100 ❑ → 60 ❑ → 0 20 ❑ → 0 40 ❑ → 0 80 ❑ → 20 ❑ → 0 Puisque tous les rangés (lignes et colonnes sont éliminés i.e : l`offre est alloués) on uploads/Litterature/ correction-de-devoir-maison-n.pdf