Insat – dgei

INSAT – 4^ème année AE 11 mai 2011

Contrôle sur le cours

"PROGRAMMATION LINEAIRE, Graphes

et Problèmes Combinatoires"

Durée : 1h151h30 Documents autorisés

Barème indicatif : exercice 1 : sur 7 6points ; exercice 2 : sur 7 4 points ; exercice 3 : sur 65  points ; exercice 4 : sur 5.
Exercice 1 : Transmission de donnees pour vidéo conférence
On considère une application de vidéoconférence distribuée entre une station émettrice E et 3 stations réceptrices X, Y et Z. Les besoins en qualité de service de cette application imposent que les paquets échangés entre l’émetteur et chacun des récepteurs aient un délai de transit inférieur à 100ms.

Les informations transitent entre la station émettrice E et les stations réceptrices via 4 routeurs intermédiaires R1, R2, R3 et R4. Les liaisons entre les différents éléments de ce réseau et les délais de transit associés figurent dans la table 1. On considère que le temps de traversée des paquets dans les routeurs est négligeable.

	E	R1	R2	R3	R4	X	Y	Z
E		90	30	40
R1					10	30
R2		20					80	70
R3		20	10					20
R4				10		10	40
X
Y
Z

Table 1 : Délais de transit en ms

1. 
   Quelle démarche faut-il avoir pour déterminer si la qualité de service demandée par l’application est atteignable ?
   

2. 
   Mettre en œuvre cette démarche et indiquer si la qualité de service peut être satisfaite. Préciser comment seront acheminés les paquets de la station émettrice vers toutes les stations réceptrices.
   

Exercice 2 : Simplexe
On considère le programme linéaire suivant :

Max Z = 5 x₁ + 3x₂

Sous x₁ + x₂  20

2 x₁ + 5 x₂  24

2 x₁ - x₂  30

x₁ , x₂  0

Ecrire le tableau initial de la méthode du simplexe et donner le tableau obtenu après la 1^ere itération. Quelle est la solution de base associée à ce tableau ?

Exercice 2 : Plan de production

Des produits d’un type donné sont fabriqués dans 4 usines. Ils sont ensuite transportés vers 3 grandes surfaces pour satisfaire la demande des clients dans ces grandes surfaces.

Les capacités de production des usines, capacités de transport entre usines et grandes surfaces et les demandes dans chaque grande surface sont supposées connues. Les demandes doivent être satisfaites.

On note :

• 
  cap_prod_u la capacité de production (en nombre de produits) de l’usine u pour u=1,..,4
  
• 
  cap_transport_u,s la capacité de transport (en nombre de produits) de l’usine u vers la grande surface s pour u= 1,..,4 et s= 1, ..,3
  
• 
  d_s la demande (en nombre de produits) dans la grande surface s pour s= 1,..,3
  

Les coûts de production et de transport sont respectivement proportionnels aux quantités produites et transportées.

On note

• 
  coût_production_u le coût unitaire de production dans l’usine u, pour u=1,..,4
  
• 
  coût_transport_u,s le coût unitaire de transport de l’usine u vers la grande surface s, pour u=1,..,4 et s= 1,..,3
  

Les valeurs de tous ces éléments sont connues.

On cherche le plan de production et de transport optimal qui permet de satisfaire les demandes.
Modéliser ce problème sous la forme d’un programme linéaire. Préciser clairement la signification des variables et des contraintes. Indiquer le nombre de variables et de contraintes de ce modèle.

1. 
   Montrer que ce problème peut se ramener à la recherche d’un flot dans un réseau dont on précisera la construction. Préciser comment les contraintes écrites en 1 sont prises en compte dans la formulation 2. Quelle être la valeur du flot qu’il soit solution du problème modélisé en 1.
   

Exercice 3 : Destruction de ponts

Une ville est traversée par un fleuve sur lequel se trouvent 4 îles A, B, C, et D. Les 2 rives E et F sont reliées entre elles par un ensemble de ponts via les iles (cf. figure 1).

On désire connaître l’ensemble minimum de ponts dont la suppression interdirait la liaison entre les deux rives.

Figure 1 : Schéma des ponts entre les rives et les iles

1. 
   Montrer que ce problème peut se ramener à la recherche d’une coupe de capacité minimale sur un graphe dont on précisera la construction.
   

2. 
   Déduire la constitution de la coupe minimale à partir de la construction d’un flot maximum. Détailler la démarche.
   

3. 
   Préciser l’ensemble minimum de points à détruire pour séparer les rives E et F.
   

Exercice 4 : Plan de production

Des produits d’un type donné sont fabriqués dans 4 usines. Ils sont ensuite transportés vers 3 grandes surfaces pour satisfaire la demande des clients dans ces grandes surfaces.

Les capacités de production des usines, capacités de transport entre usines et grandes surfaces et les demandes dans chaque grande surface sont supposées connues. Les demandes doivent être satisfaites.

On note :

• 
  cap_prod_u la capacité de production (en nombre de produits) de l’usine u pour u=1,..,4
  
• 
  cap_transport_u,s la capacité de transport (en nombre de produits) de l’usine u vers la grande surface s pour u= 1,..,4 et s= 1, ..,3
  
• 
  d_s la demande (en nombre de produits) dans la grande surface s pour s= 1,..,3
  

Les coûts de production et de transport sont respectivement proportionnels aux quantités produites et transportées. On note :

• 
  coût_production_u le coût unitaire de production dans l’usine u, pour u=1,..,4
  
• 
  coût_transport_u,s le coût unitaire de transport de l’usine u vers la grande surface s, pour u=1,..,4 et s= 1,..,3
  

Les valeurs de tous ces éléments sont connues.

On cherche le plan de production et de transport optimal qui permet de satisfaire les demandes.
Modéliser ce problème sous la forme d’un programme linéaire. Préciser clairement la signification des variables et des contraintes. Indiquer le nombre de variables et de contraintes de ce modèle.