UTBM 2005 ag41 optimisation et recherche operationnelle genie informatique semestre 2 partiel

Publié par

Median AG41 - Printemps 2005Duree 2 heures - Documents autorises1 Cours1. Quelles sont les di erentes methodes exactes et generales permettant de resoudre un pro-gramme lineaire en ...

Publié le : jeudi 21 juillet 2011
Lecture(s) : 431
Nombre de pages : 2
Voir plus Voir moins
M´edianAG41-Printemps2005 Dur´ee2heures-Documentsautorise´s
1 Cours 1.Quellessontlesdie´rentesm´ethodesexactesetg´ene´ralespermettantdere´soudreunpro-grammelin´eaireennombreentier?D´etailler. 2.Peut-onutiliserlalgorithmedusimplexepourre´soudreunsyste`mede´quationslin´eairesclas-siquescommeceluiquisuit?De´tailler. a11x1+a12x2+...+a1nxn=b1 ... ai1x1+ai2x2+...+ainxn=bi ... am1x1+am2x2+...+amnxn=bm 3.Montrersurunexemplesimplequeleproble`meduvoyageurdecommercenerentrepasdans lacate´goriedesprobl`emesdeprogrammationdynamique.
2 Exercice1 : Simplexe
Soitleprogrammeline´airesuivant: maxz= 2x1+x2+x3 x1+x31 x2+x32 x1+x2+x34 x10;x20;x30
1.Mettreceprogrammelin´eairesousformestandard. 2. Donnerla base initiale et la solution initiale de ce PL. 3.Re´soudrecePLetdonnerlasolutionoptimaleainsiquelabasecorrespondante.
3 Exercice2 : Dual
Soit le PL suivant : Maxz=x1+ 2x2 2x1+x22 x1+ 2x25 x14x24 x10;x20
1.R´esoudrecePLparlame´thodedevotrechoix. 2. Donnerle dual de ce PL. 3.R´esoudre´egalementledual.
4 Exercice3 : Algorithme de Little
Soitleprobl`emeduvoyageurdecommerce(PVC)suivant:
1
A BC DE A 117 1311 B 58 1515 C 13 1512 11 D 5 135 10 E 37 7 7 1.Donnerunee´valuationdeladistanceminimaledetoutesolutiondecePVC. 2.Calculerlesp´enalit´esdelamatriceinitiale. 3. Utiliserl’algorithme de Little pour donner la solution optimale de PVC.
5Exercice4:Proble`medetransport
Soitleproble`medetransportd´eniparletableausuivant: 1 23 A 12 8 11 1 B 79 17 1 C 96 12 1 1 11
1.Quelleestlasolutiondonne´eparlam´ethodeducoinnord-ouest? 2.Peut-onappliquerlam´ethodedustepping-stone?Pourquoi? 3.Enutilisantleprincipedelame´thodedustepping-stone,essayerdere´soudreceproble`mede transport.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.