//img.uscri.be/pth/46efc429cb559ade834c075d4af04455b3850ca3
YouScribe est heureux de vous offrir cette publication
Lire

Optimisation et recherche opérationnelle 2005 Génie Informatique Université de Technologie de Belfort Montbéliard

2 pages
Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Optimisation et recherche opérationnelle 2005. Retrouvez le corrigé Optimisation et recherche opérationnelle 2005 sur Bankexam.fr.
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