Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

PARTIE I Programmation Lin´ eaire EXERCICE I Soit le programme lin´ eaire (P) s

PARTIE I Programmation Lin´ eaire EXERCICE I Soit le programme lin´ eaire (P) suivant : max 3x1 + x2 s.c. 3x1 + 2x2 ≤ 24 4x1 −x2 ≥ 8 x1 −2x2 = 0 x1 ≥0, x2 ≥ 0 Question 1 : R´ esoudre (P) par l’algorithme du simplexe. N.B. : - d´ etailler les diﬀ´ erentes it´ erations de l’algorithme, - ` a la ﬁn du d´ eroulement, Pr´ eciser la valeur de (P) et les valeurs optimales de toutes les variables de la forme standard. Question 2 : On suppose d´ esormais ajouter au mod` ele (P) des contraintes d’int´ egrit´ e aux variables structurelles : x1 et x2 entiers. On obtient un nouveau programme (P’). D´ eduire (en justiﬁant) de la r´ esolution pr´ ec´ edente le valeur et la solution optimale de (P’). EXERCICE II : Soit le programme lin´ eaire (P) suivant : max x1 + x2 s.c. x1 −2x2 + x3 = 1 2x1 + x2 −x4 = 2 −2x1 + x2 + x5 = 2 x1, x2, x3, x4, x5 ≥ 0 1 Apr` es avoir eﬀectu´ e la phase 1 de l’algorithme du simplexe, on obtient le tableau initial de la phase 2 suivant : x1 x2 x3 x4 x5 x3 0 -5/2 1 1/2 0 0 x1 1 1/2 0 -1/2 0 1 x5 0 2 0 -1 1 4 0 1/2 0 1/2 0 -1 Question 1 : Que signiﬁe la valeur 0 dans la derni` ere colonne du tableau ? Question 2 : D´ eduire du tableau la solution du probl` eme (P) trouv´ ee et sa valeur. Cette solution est-elle optimale ? Expliquer. Si cette solution n’est pas optimale, poursuivre le d´ eroulement de l’algorithme du simplexe en d´ etaillant la ou les it´ eration(s) manquante(s) (expliciter le r´ esultat obtenu). PARTIE II Une mod´ elisation du probl` eme du voyageur de commerce Soit G = (S, A) un graphe non orient´ e complet (tous les sommets sont deux ` a deux adjacents) de n sommets. Chaque arˆ ete {i, j} de A est valu´ ee par un entier naturel cij appel´ e coˆ ut de l’arˆ ete {i, j}. Le tableau suivant donne un exemple de coˆ uts pour un graphe de n = 6 sommets. 1 2 3 4 5 6 1 - 10 8 21 5 11 2 - - 3 7 4 6 3 - - - 15 11 3 4 - - - - 14 8 5 - - - - - 13 6 - - - - - - Une tourn´ ee dans G = (S, A) consiste en un cycle empruntant une et une seule fois chacun des n sommets de S. La longueur d’une tourn´ ee est la somme des coˆ uts de ses arˆ etes. Par exemple, la tourn´ ee T = (2, 4, 5, 1, 6, 3) a pour longueur l(T) = 7 + 14 + 5 + 11 + 3 + 3 = 43. Le probl` eme du voyageur de commerce consiste ` a d´ eterminer une tourn´ ee de longueur minimum. Notre objectif est de montrer que le probl` eme du voyageur de commerce peux ˆ etre mod´ elis´ e par le programme lin´ eaire suivant : 2 min X i<j cijxij (1) X i<h xih + X j>h xhj = 2 1 ≤h ≤n (2) X i,j∈V,i<j xij ≤|V | −1 V ⊂S, 3 ≤|V | ≤n 2 (3) xij ∈{0, 1} i, j ∈S, i < j (4) Question 1 Montrer que le probl` eme du voyageur de commerce est d´ eﬁni si et seulement si n ≥3. Question 2 Donner un exemple de probl` eme du voyageur de commerce pour n = 3. Donner une tourn´ ee optimale pour cet exemple. Question 3 Montrer qu’une tourn´ ee (1, 2, . . . , n) est ´ equivalente ` a (n, n−1, . . . , 1). Montrer qu’une tourn´ ee (1, 2, . . . , n) est ´ equivalente ` a (i, i + 1, . . . , n, 1, . . . , i −1). En d´ eduire que le nombre de tourn´ ees diﬀ´ erentes est n! 2n. En d´ eduire le nombre de tourn´ ees diﬀ´ erentes pour un graphe avec n = 3 sommets. Question 4 Montrer que dans toute tourn´ ee chaque sommet a exactement deux voisins. Donner un exemple de graphe ` a n = 6 sommets tel que chaque sommet a deux voisins mais qui ne correspond pas ` a une tourn´ ee. Question 5 Montrer qu’un cycle de q sommets a q arˆ etes. Soit V ⊂S un sous-ensemble de sommets. Nous notons ¯ V le compl´ ementaire de V (l’ensemble des sommets de S qui n’appartiennent pas ` a V ). Question 6 Montrer que si |V | ≤n 2 alors | ¯ V | ≥n 2 . Soit C ⊂A un sous-ensemble d’arˆ etes tel que chaque sommet h de G a exactement deux arˆ etes adjacentes dans C. Soit V ⊂S un sous-ensemble de sommets, nous notons mC(V ) le nombre d’arˆ etes de C qui relient deux sommets de V . Question 7 Montrer que si mC(V ) ≤|V | −1 alors il existe une arˆ ete {i, j} ∈C telle que i ∈V et j ∈¯ V . En d´ eduire que les mC(V ) arˆ etes qui relient deux sommets de V ne forment pas un cycle contenant tous les sommets de V . Question 8 Donner la signiﬁcation de la contrainte (4) du programme lin´ eaire. 3 Question 9 D´ eduire des questions pr´ ec´ edentes que toute solution r´ ealisable du programme lin´ eaire correspond ` a une tourn´ ee. Question 10 Montrer que le programme lin´ eaire mod´ elise le probl` eme du voyageur de commerce. 4 uploads/Voyage/ moca03-no1.pdf