Remerciez-le!

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

Programmation Lin´ eaire, FLIN609 Ann´ ee 2008-2009 - Examen du 20 mai 2009. -

Programmation Lin´ eaire, FLIN609 Ann´ ee 2008-2009 - Examen du 20 mai 2009. - - Dur´ ee 2h. Seul document autoris´ e : Une feuille manuscrite recto/verso. Pas de calculatrices. - - Une large part de la notation prendra en compte la clart´ e de la r´ edaction et la rigueur des justiﬁcations. - - Exercice 1 - Extrait de Fiche TD1 Licence Info Paris 6 Une personne soucieuse de sa forme physique souhaite absorber chaque jour 36 unit´ es de Vitamine A, 28 unit´ es de Vitamine C et 32 unit´ es de Vitamine D. Deux marques sont susceptibles de fournir ces apports. La marque 1 coˆ ute 3 euros et procure 2 unit´ es de Vitamine A, 2 unit´ es de Vitamine C et 8 unit´ es de Vitamine D. La marque 2 coˆ ute 4 euros et procure 3 unit´ es de Vitamine A, 2 unit´ es de Vitamine C et 2 unit´ es de Vitamine D. Il s’agit de trouver la combinaison respectant les exigences d’absorption quo- tidienne au moindre coˆ ut. a. Enoncer ce probl` eme sous forme d’un programme lin´ eaire (P). b. Ecrire le dual (D) de (P). c. R´ esoudre (D) par la m´ ethode du simplexe. d. D´ eduire une solution de (P) ` a partir du dictionnaire ﬁnal de (D). e. Certiﬁer l’optimalit´ e de la solution de (P) ` a l’aide de combinaisons de contraintes. f. R´ esoudre (P) graphiquement. - Exercice 2 - R´ esoudre le programme lin´ eaire suivant avec l’algorithme du simplexe en deux phases. Certiﬁer l’optimalit´ e de la solution trouv´ ee. Maximiser 3x1 +x2 Sous x1 −x2 ≤−1 −x1 −x2 ≤−3 2x1 +x2 ≤4 x1, x2 ≥0 1 Programmation Lin´ eaire, FLIN609 Ann´ ee 2008-2009 - Exercice 3 - Montrer que le programme lin´ eaire suivant admet comme solution optimale x1 = 1 5, x2 = 0, x3 = 0, x4 = 7 5. Maximiser x1 +x2 +x3 +x4 Sous 3x1 +6x2 +3x3 +x4 ≤ 2 2x1 +3x2 +3x3 +x4 ≤ 4 x1 +2x2 +5x3 +2x4 ≤ 3 4x1 +3x2 +4x3 +x4 ≤ 5 x1, x2, x3, x4 ≥ 0 - Exercice 4 - On consid` ere deux centrales ´ electriques, chacune de capacit´ e de production 800 megawatt. Ces centrales desservent trois villes dont les besoins en ´ electricit´ e sont respectivement de 700, 400 et 500 megawatt. Chaque centrale peut fournir tout ou partie de sa production ` a chacune des villes. Les coˆ uts d’acheminement (par megawatt) dans le r´ eseau ´ electrique sont donn´ es par le tableau suivant : Centrale 1 Centrale 2 Ville 1 20 25 Ville 2 15 10 Ville 3 10 15 Le probl` eme est de subvenir aux besoins des villes ` a moindre coˆ ut. a. Mod´ eliser sous forme d’un programme lin´ eaire. b. Proposer une solution de ce probl` eme ”` a la main”. c. (Hors barˆ eme) Montrer l’optimalit´ e de votre solution en proposant un certi- ﬁcat dual. 2 uploads/Geographie/ 20-mai-2009.pdf