Remerciez-le!

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

UNIVERSITE IBN ZOHR Ann´ ee Universitaire 2014-2015 Facult´ e des Sciences Juri

UNIVERSITE IBN ZOHR Ann´ ee Universitaire 2014-2015 Facult´ e des Sciences Juridiques Economiques et Sociales S5 Agadir Recherche Op´ erationnelle Corrig´ e de la s´ erie1: Traduction des probl` emes en language math´ ematique Pr. O.Chadli Exercice 1 Posons x1 le nombre de bureaux du mod` ele M1 et x2 le nombre de bureaux du mod` ele M2. Les temps libres de chaque d´ epartement imposent des contraintes qu’il faut respecter. La contrainte impos´ ee par les temps libres ` a l’atelier de sciage: x1 + 2x2 ≤20. Les autres contraintes sont: 2x1 + x2 ≤22 x1 + x2 ≤12 Il s’ajoute ` a ces contraintes des contraintes de non-n´ egativit´ e puisque le nombre de bureaux ne peut ˆ etre n´ egatif, on a donc: x1 ≥0 et x2 ≥0. Graphiquement les solutions r´ ealisables sont les points du polygone convexe de la ﬁgure suivante: Figure 1: l’ensemble des solutions admissibles c’est le polygone convexe en gris La direction veut maximiser son proﬁt, c’est-` a-dire maximiser la fonction: f(x1, x2) = 300x1 + 200x2. Pour chacune de ces solutions admissibles, c’est-` a-dire pour chacun des points du polygone convexe, la compagnie fera un proﬁt positif. Si la compagnie fabrique trois exemplaires du mod` ele M1 et deux exemplaires du mod` ele M2, le proﬁt sera: f(3, 2) = 300 × 3 + 200 × 2 = 1300 DH. 1 www.coursdefsjes.com Il ne saurait ˆ etre question de calculer le proﬁt r´ ealisable pour chacun des points du polygone convexe. Pour avoir une vision globale du probl` eme, repr´ esentons le proﬁt r´ ealis´ e par le param` etre z. On a: 300x1 + 200x2 = z qui repr´ esente une famille de droites parall` eles. En isolant x2, on obtient: x2 = (−3 2)x1 + 1 200z Il s’agit donc d’une famille de droites de pente −3 2 et qui passent par le point dont l’ordonn´ ee ` a l’origine est z 200 (c’est dire le point dont les coordon´ ees sont x1 = 0 et x2 = z/200) . Parmi les droites de cette famille, seules celles ayant des points communs avec l’ensemble des solutions admissibles (qui est represent´ e ici par le polygone convexe en gris sur le graphique) nous int´ eressent. La fonction f(x1, x2) atteindra sa valeur maximale lorsque l’ordonn´ ee ` a l’origine z 200 de la droite: x2 = (−3 2)x1 + 1 200z atteindra sa valeur maximum tout en passant par au moins un des points de l’ensemble des solutions admissibles (polygone convexe en gris sur le graphique). Figure 2: Les droites hachur´ ees representent les droites parall` eles d’´ equations x2 = (−3 2)x1 + 1 200z pour une valeur donn´ ee de z. Graphiquement on constate que la droite respectant ces conditions semble ˆ etre la droite de la famille passant par le point-sommet du polygone convexe (10, 2). Le proﬁt est alors: f(10, 2) = 300 × 10 + 200 × 2 = 3400 DH. Il reste ` a s’assurer alg´ ebriquement des coordonn´ ees du point-sommet repr´ esentant l’optimum en r´ esolvant le syst` eme: 2x1 + x2 = 22 x1 + x2 = 12 2 ce qui donne x1 = 10 et x2 = 2. Ainsi le programme de la direction est (10,2). Exercice 2 Notons par x1, x2 et x3 respectivement les quantit´ es des produits P1, P2 et P3 fabriqu´ es par l’entreprise. La contrainte impos´ ee par la phase de fabrication li´ ee ` a l’usinage est: x1 + 2x2 + x3 ≤100. Les autres contraintes impos´ ees par les phases d’assemblage et de ﬁnition sont donn´ ees par: 3x1 + 4x2 + 2x3 ≤120 2x1 + 6x2 + 4x3 ≤200 Il s’ajoute ` a ces contraintes des contraintes de non-n´ egativit´ e puisque le nombre des produits fabriqu´ es ne peut ˆ etre n´ egatif, on a donc: x1 ≥0, x2 ≥0 et x3 ≥0. La direction veut maximiser son proﬁt, c’est ` a dire maximiser la fonction: f(x1, x2, x3) = 6x1 + 7x2 + 8x3. Le programme lin´ eaire que doit r´ esoudre l’entreprise est donc: maximiser 6x1 + 7x2 + 8x3 sous contraintes        x1 ≥0, x2 ≥0, x3 ≥0 x1 + 2x2 + x3 ≤100 3x1 + 4x2 + 2x3 ≤120 2x1 + 6x2 + 4x3 ≤200 Exercice 3 Les donn´ ees du probl` eme se r´ esument dans le tableau suivant: Dattes Abricots Pˆ eches boˆ ıte luxe 0.45 kg 0.67 kg 0.34 kg boˆ ıte sp´ eciale 0.56 kg 0.34 kg 0.084 kg boˆ ıte ordinaire 0.45 kg 0.22 kg 0 kg Notons par x1, x2, x3 respectivement le nombre de boˆ ıtes de luxe, sp´ eciales, ordinaires. La con- trainte impos´ ee par la quatit´ e de dattes disponible est: 0.45 x1 + 0.56 x2 + 0.45 x3 ≤33.6 Les autres contraintes impos´ ees par les quatit´ es d’abricots et de pˆ eches disponibles sont donn´ ees par: 0.67 x1 + 0.34 x2 + 0.22 x3 ≤ 25.2 0.34 x1 + 0.084 x2 ≤ 10.08 Il s’ajoute ` a ces contraintes des contraintes de non-n´ egativit´ e puisque le nombre de boˆ ıtes ne peut ˆ etre n´ egatif, on a donc: x1 ≥0, x2 ≥0 et x3 ≥0. 3 La compagnie veut maximiser son proﬁt, c’est ` a dire maximiser la fonction: f(x1, x2, x3) = 3 x1 + 2 x2 + 1.5 x3 Le programme lin´ eaire est donc: maximiser 3 x1 + 2 x2 + 1.5 x3 sous contraintes        x1 ≥0, x2 ≥0, x3 ≥0 0.45 x1 + 0.56 x2 + 0.45 x3 ≤33.6 0.67 x1 + 0.34 x2 + 0.22 x3 ≤25.2 0.34 x1 + 0.084 x2 ≤10.08 Exercice 4 Notons par xij la quantit´ e d’espace lou´ e par la compagnie pour une dur´ ee de j mois ` a compter du mois i (m2). Par exemple x12 signiﬁe que la compagnie a lou´ e l’espace pour une p´ eriode de deux mois ` a partir du premier mois (¸ c.` a.d. le premier mois et le deuxi` eme mois); x32 signiﬁe qu’elle a lou´ e l’espace pour deux mois ` a partir du trois` eme mois (¸ c.` a.d. le troisi` eme mois et le quatri` eme mois) et ainsi de suite. Pour une valeur de i allant de 1 jusqu’` a 5, alors j prend la valeur de 1 jusqu’` a 6 −i. Ainsi les variables xij qui representent la quantit´ e d’espace lou´ e sont comme suite: x11 x12 x13 x14 x15 x21 x22 x23 x24 x31 x32 x33 x41 x42 x51 Les contraintes ´ economiques sont donn´ ees comme suite:            x11 + x12 + x13 + x14 + x15 ≥30000 x12 + x13 + x14 + x15 + x21 + x22 + x23 + x24 ≥20000 x13 + x14 + x15 + x22 + x23 + x24 + x31 + x32 + x33 ≥40000 x14 + x15 + x23 + x24 + x32 + x33 + x41 + x42 ≥10000 x15 + x24 + x33 + x42 + x51 ≥50000 les contraintes de signes sont comme suite: xij ≥0, pour i = 1, · · · , 5 et j = 1, · · · , 6 −i pour chaque valeur de i L’objectif de la compagnie est de minimiser le coˆ ut total de location (en DH): minimiser [65(x11 + x21 + x31 + x41 + x51) + 100(x12 + x22 + x32 + x42) + 135(x13 + x23 + x33)+ 160(x14 + x24) + 190(x15)] Le programme lin´ eaire qui se pose donc pour la compagnie est comme suite: 4 minimiser [65(x11 + x21 + x31 + x41 + x51) + 100(x12 + x22 + x32 + x42) + 135(x13 + x23 + x33)+ 160(x14 + x24) + 190(x15)] sous contraintes                x11 + x12 + x13 + x14 + x15 ≥30000 x12 + x13 + x14 + x15 + x21 + x22 + x23 + x24 ≥20000 x13 + x14 + x15 + x22 + x23 + x24 + x31 + x32 + x33 ≥40000 x14 + x15 + x23 + x24 + x32 + x33 + x41 + x42 ≥10000 x15 + x24 + x33 + x42 + x51 ≥50000 xij ≥0, pour i = 1, · · · , 5 et j = 1, · · · , 6 −i pour chaque valeur de i Exercice 5 Notons par x1, x2, x3, x4 respectivement le nombre de bureaux des mod` eles M1, M2, M3, M4 produits par l’entreprise. La contrainte li´ ee ` a la phase de menuiserie est comme suite: 4 x1 + 9 x2 + 7 x3 + 10 x4 ≤7000. La contrainte li´ ee ` a la phase de ﬁnition est comme suite: x1 + x2 + 3 x3 + uploads/Voyage/ serie-pl-1-corrige.pdf