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

Description

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 ...

Informations

• Publié par: shura
• Nombre de lectures: 308
• 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