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

Description

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.

Sujets

• 2005

Informations

• Publié par: bankexam
• Publié le: 10 février 2007
• Nombre de lectures: 85
• Langue: Français

Extrait

M´edianAG41-Printemps2005 Dur´ee2heures-Documentsautorise´s

1 Cours 1.Quellessontlesdiffe´rentesm´ethodesexactesetg´ene´ralespermettantdere´soudreunpro- grammelin´eaireennombreentier?D´etailler. 2.Peut-onutiliserl’algorithmedusimplexepourre´soudreunsyste`med’e´quationslin´eairesclas- siquescommeceluiquisuit?De´tailler.  a 11 x 1 +a 12 x 2 +...+a 1n x n =b 1   ... a i1 x 1 +a i2 x 2 +...+a in x n =b i ...   a m1 x 1 +a m2 x 2 +...+a mn x n =b m 3.Montrersurunexemplesimplequeleproble`meduvoyageurdecommercenerentrepasdans lacate´goriedesprobl`emesdeprogrammationdynamique.

2 Exercice1 : Simplexe

Soitleprogrammeline´airesuivant:  maxz= 2x 1 +x 2 +x 3   x 1 +x 3 ≤1 x 2 +x 3 ≤2 x 1 +x 2 +x 3 ≤4   x 1 ≥0;x 2 ≥0;x 3 ≥0

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=x 1 + 2x 2 −2x 1 +x 2 ≤2 −x 1 + 2x 2 ≤5 x 1 −4x 2 ≤4 x 1 ≥0;x 2 ≥0

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´efiniparletableausuivant: 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