TD - Programmation lineaire
Optimisation et Recherche Operationnelle
M1 Info - semestre d’automne 2020-2021
Université Claude Bernard Lyon 1
Christophe Crespelle Eric Duchêne Aline Parreau
[email protected] [email protected] [email protected] Le TD est prevu pour 2h. Les exercices importants sont le 1 et le 2.
Exercice 1. Il faut parfois savoir couper les cables en 4.
Une usine produit des cables de cuivre de 5mm et de 10mm de diametre, sur lesquels
le benefice est de respectivement 2 et 7 euros au metre. Le cuivre dont dispose l’usine
permet de produire 20 km de cable de 5 mm de diametre par semaine. La production
de cable de 10 mm demande 4 fois plus de cuivre que celle de cable de 5mm. Pour des
raisons de demande, la production hebdomadaire de cable de 5mm ne doit pas depasser
15 km et pour des raisons de logistique la production de cable de 10 mm ne doit pas
representer plus de 40% de la production totale.
a. Ecrivez un programme lineaire ayant pour objectif de maximiser le benefice heb-
domadaire de l’usine, en supposant que dans les contraintes enoncees, tout se qui est
produit est vendu.
Solution. Il y a deux variables dans le probleme d’optimisation : le nombre de kilo-
metres de cable de 5mm produit, qu’on note x1 , et le nombre de kilometres de cable
de 10mm produit, note x2 .
La fonction objectif a maximiser est le chiffre d’affaire, note z : z = 2x1 + 7x2 . Il y a
une contrainte sur la quantite de cuivre disponible : x1 + 4x2 ≤ 20. Et deux contraintes
4
additionnelles liees a la demande et a la logistique : x1 ≤ 15 et x2 ≤ 10 (x1 + x2 ). Ce
qui donne le programme lineaire suivant :
Maximiser z = 2x1 + 7x2 sous conditions
(a) x1 +4x2 ≤ 20
(b) x1 ≤ 15
4
(c) x2 ≤ 10 (x1 + x2 )
x1 , x2 ≥ 0
b. Mettez le programme lineaire en forme standard.
Solution. Seule la troisieme contrainte n’est pas en forme standard. Il faut faire pas-
ser les deux variables du cote gauche de l’inegalite : −4x1 + 6x2 ≤ 0. Ce qui donne le
programme lineaire en forme standard :
Maximiser z = 2x1 + 7x2 sous conditions
(a) x1 +4x2 ≤ 20
(b) x1 ≤ 15
(c) −4x1 +6x2 ≤ 0
x1 , x2 ≥ 0
c. Resolvez ce programme lineaire a la main, en manipulant les inegalites et la fonction
objectif.
Solution. On peut par exemple proceder ainsi. De la fonction objectif, on tire 7x2 =
z − 2x1 . On s’en sert pour eliminer x2 dans les contraintes (a) et (c) en multipliant au
prealable ces inegalites par 7. Cela donne :
Maximiser z sous conditions
(a) 7x1 +4z − 8x1 ≤ 140
(b) x1 ≤ 15
(c) −28x1 +6z − 12x1 ≤ 0
x1 , x2 ≥ 0
Soit :
Maximiser z sous conditions
(a) z ≤ 35 + 14 x1
(b) x1 ≤ 15
(c) z ≤ 20 x
3 1
x1 , x2 ≥ 0
Arrive a ce stade, on voit que pour maximiser z il faut prendre x1 le plus grand possible,
tout en respectant les contraintes, c’est a dire x1 = 15. (a) donne alors z ≤ 35 + 15 4
et (b) donne z ≤ 100. Pour satisfaire les deux contraintes on doit choisir z = 35 + 15 4
.
On reinjecte dans la fonction objectif pour trouver la valeur de x2 correspondante, on
obtient 35 + 154
= 30 + 7x2 , soit x2 = 35
28
= 54 . Au final, une solution optimale est donc
x1 = 15, x2 = 45 et on realise un objectif de z = 35 + 15 4
= 38 + 34 .
d. Resolvez ce programme lineaire par la methode graphique.
Solution.
La resolution graphique est donnee sur la figure 1. Pour l’obtenir, on procede comme
suit. Pour chaque contrainte du programme lineaire, on trace la droite correspondante,
qui separe le plan en deux : le demi-plan ou la contrainte est satisfaite et le demi-plan
ou elle ne l’est pas. Sur le dessin, le demi-plan ou la contrainte N’EST PAS satisfaite
est materialise par des hachures sur le bord de la droite de separation entre les deux
demi-plans. Par exemple, la contrainte (a) donne la droite D d’equation x1 + 4x2 = 20.
Pour tracer cette droite, le plus simple est de prendre deux points qui appartiennet a
la droite. Par exemple, pour x1 = 0, on a x2 = 5 d’apres l’equation de la droite. Ainsi
(0, 5) est un point de la droite D. Lorsque x2 = 0, toujours d’apres l’equation, on a
x1 = 20, ce qui donne un deuxieme point sur D, le point (20, 0). On trace D entre ces
deux points. Pour savoir de quel cote de la droite se trouve le demi-plan qui satisfait
la contrainte, on remarque que dans la contrainte on a x1 + 4x2 ≤ 20. Ainsi, si on est
sur la droite D et qu’on a l’egalite parfaite entre le membre de gauche et le membre
de droite de la contrainte, si on augmente x1 ou qu’on augmente x2 alors la contrainte
n’est plus satisfaite, car son membre gauche augmente au dela de 20 (cela vient du fait
x2
6
−4x1 + 6x2 = 0 x1 = 15
5
4 x1 + 4x2 = 20
2
z croissant
2x1 + 7x2 = cte
1
0 x1
0 5 10 15 20
Figure 1 – Resolution graphique du programme lineaire en forme standard.
que les coefficients de x1 et x2 dans le membre gauche sont tous deux positifs). Donc,
dans le demi-plan superieur droit (celui ou on se retrouve en augmentant x1 ou x2 ) la
contrainte n’est pas satisfaite. On hachure donc le cote superieur droit de la droite D.
On procede ainsi pour toutes les autres contraintes : on trace la droite dont l’equation
est defini en changeant le ≤ par =, ensuite, on raisonne pour voir si lorsqu’on augmente
une variable a partir de la position d’egalite, la contrainte reste satisfaite ou non, ce
qui determine le cote a hachurer. une fois qu’on fait ca pour les trois contraintes, on
obtient le dessin de la figure 1. remarquez qu’il y a deux contraintes supplememtaires
dans le programme lineaire en forme standard : x1 ≥ 0 et x2 ≥ 0. C’est a dire que
seules les solutions dans le cadrant (quart de plan) superieur droit sont admissibles.
La zone ou les 5 contraintes sont satisfaites est coloree en bleu.
Occupons nous maintenant de la fonction objectif a maximiser z = 2x1 + 7x2 . Sur
le dessin, on a choisit de la materialiser par une droite en pointilles dont l’equation
est 2x1 + 7x2 = cte. Toutes les solutions sur cette droite realise la meme valeur de
la fonction objectif, en l’occurence z = cte. On peut choisir de dessiner la droite qui
nous plait le mieux par sa situation sur le dessin, en choisissant la constante cte. Ici,
on a choisi cte = 2 × 7 = 14 car c’est le produit des coefficients des variables dans la
fonction objectif. Cela permet de facilement trouver des points a coordonnees entieres
sur la droite a tracer en prenant les deux points d’abscisse nulle (x1 = 0) et d’ordonnee
nulle (x2 = 0). Une fois qu’une de ces droites d’equation z = cte, qu’on note O, est
tracee, on cherche la valeur maximum que peut prendre cte dans la zone des solutions
admissibles (ici en bleu). Pour cela on considere toutes les paralleles a la droite O qu’on
a trace. Il faut donc determiner dans quelle direction la cte augmente lorsqu’on deplace
x2
6
−4x1 + 6x2 = 0 x1 = 15
5
4
x1 + 4x2 = 20
3
2
z’ croissant
1 2x1 + 10x2 = cte
0 x1
0 5 10 15 20
Figure 2 – Resolution graphique du programme lineaire en changeant la fonction objectif
pour obtenir une unique solution optimale differente de la precedente.
la droite parallele a O. La encore, cela se voit en regardant l’equation z = 2x1 + 7x2 ,
ou on voit que lorsque x1 ou x2 augmente, z aussi. Il faut donc se deplacer vers le cote
superieur droit pour realiser des valeurs de z plus importantes, ce qui a ete materialise
par une fleche sur la figure 1. Ainsi, on trouve la droite parallele a O, la plus eloignee
dans cette direction et qui intersecte la zone bleue. Elle a ete materialisee en pointilles
rouges sur la figure 1.
On voit que cette droite rouge intersecte la zone bleue en seulement un point, qui est a
l’intersection des droites de contraintes d’equations x1 = 15 et x1 +4x2 = 20. On resoud
donc ce systeme de deux equations a deux inconnues pour trouver les coordonnes de
l’unique solution optimale. Il s’agit du point de coordonnees x1 = 15 et x2 = 54 . On
realise alors une valeur objectif de z = 2 × 15 + 7 × 54 = 30 + 35
4
= 38 + 43 . On retrouve
ainsi bien la solution obtenue par la resolution a la main du systeme.
e. Comment changer les prix de vente pour qu’il y ait toujours une unique solution
optimale mais differente de la precedente ?
Solution.
Pour coller a la realite du probleme, on va se limiter a des benefices au metre qui
soient strictement positifs. Ainsi, la droite z = cte sera toujours une droite strictement
decroissante et non verticale. Ce qui fait que jusqu’a maintenant la solution optimale
est obtenue dans le coin droit de la zone bleue (au croisement des droites d’equation
x1 = 15 et x1 + 4x2 = 20) est que la doite O, d’equation z = cte, est plus pentue
que la droite D d’equation x1 + 4x2 = 20. En effet, le coefficient directeur de la droite
O est − 27 alors que celui de la droite D est − 41 . C’est pour cela que la parallele la
plus eloignee de O qui intersecte la zone bleue l’intersecte en son coin droit. Si on
change les prix pour que le coefficient directeur de O soit moins negatif que celui de
D (c’est a dire pour que O soit moins pentue que D) alors la parallele a O la plus
eloignee de O et qui intersecte la zone bleue l’intersectera cette fois en son coin gauche
(intersection de la droite d’equation −4x1 + 6x2 = 0 et de la droite D). Pour cela
il suffit par exemple d’augmenter le prix du cable de 10mm pour que son benefice
au metre soit de 10 euros, contre 7 actuellement. La droite O0 decrivant la nouvelle
fonction objectif z 0 = 2x1 + 10x2 a alors un coefficient directeur de 15 . Dans ce cas,
la solution optimale est toujours unique mais est obtenue au croisement des droites
d’equations −4x1 + 6x2 = 0 et x1 + 4x2 = 20. On resoud ce systeme de deux equations
a deux inconnues et on trouve x2 = 80 22
= 40
11
et x1 = 60
11
. Cette solution est differente
de l’ancienne solution optimale precedente x1 = 15 et x2 = 45 . On voit que dans cette
nouvelle solution, on produit plus de cable de 10mm que precedemment, en proportion,
ce qui est logique vu qu’on a augmente le benefice sur ces cables. La nouvelle resolution
graphique est donnee sur la figure 2.
Remarque. Si on reste dans le cadre des coefficients strictement positifs pour x1
et x2 dans la fonction objectif, il n’y a que deux solutions optimales qui peuvent
etre l’unique solution optimale au probleme : les deux que nous avons trouvees
precedemment, a savoir x1 = 15, x2 = 54 et x1 = 60 11
, x2 = 40
11
. Les deux autres coins
du quadrilatere des solutions admissibles ne peuvent pas etre solution optimale
sous la contrainte des coefficients strictement positifs pour x1 et x2 dans la fonction
objectif. Ainsi, quelle que soit la fonction objectif a coefficients strictements positifs,
s’il y a une unique solution optimale, c’est necessairement une de ces deux solutions.
Par contre, la valeur de l’objectif realise par ces solutions ne sera pas toujours la
meme et depend des coefficients de la fonction objectif.
f. Comment fixer les prix de vente pour qu’il y ait une infinite de solutions ?
Solution.
En restant dans la limite des benefices au metre strictement positifs, la seule maniere
d’obtenir une infinite de solutions est de prendre la droite z = cte representant la
fonction objectif avec le meme coefficient directeur que la droite D. C’est ce qui se
passe si on fixe le prix du cable de 10mm de sorte que le benefice au metre soit 8
euros. On obtient z 00 = 2x1 + 8x2 et le coefficient directeur de la droite O00 decrivant le
nouvelle fonction objectif est alors − 14 , comme celui de la droite D. Toutes les solutions
se trouvant sur le segment de droite de la droite D entre ses points d’intersections avec
les droites d’equations x1 = 15 et −4x1 + 6x2 = 0 sont alors des solutions optimales
realisant la meme valeur de la fonction objectif z 00 . Il y en a une infinite (autant que
de points sur le segment). On peut calculer la valeur maximale ainsi atteinte pour la
fonction objectif z 00 en prenant un point quelconque du segment solution. Par exemple
si on prend le point d’abscisse x1 = 15 sur ce segment, on sait d’apres les questions c
et d que son ordonnee est x2 = 54 . On realise alors un objectif de z 00 = 30 + 10 = 40.
La resolution graphique dans ce cas est donnee sur la figure 3.
x2
6
−4x1 + 6x2 = 0 x1 = 15
5
4
x1 + 4x2 = 20
3
z’’ croissant
1
2x1 + 8x2 = cte
0 x1
0 5 10 15 20
Figure 3 – Resolution graphique du programme lineaire en changeant la fonction objectif
pour avoir une infinite de solution optimales.
Exercice 2. Beaucoup, a la folie... pas du tout.
On donne les 3 programmes lineaires suivants.
Π1 : maximiser x + 2y sous conditions :
(a) −y ≤ −1
(b) −x +y ≤ 1
(c) 2x +3y ≤ 10
(d) −2x −y ≤ −9
x, y ≥ 0
Π2 : maximiser x + y sous conditions :
(a) −3x +y ≤ −1
(b) x −4y ≤ 1
(c) −2x −3y ≤ −6
(d) −x ≤ −1
x, y ≥ 0
Π3 : maximiser −4x + y sous conditions :
(a) −3x +y ≤ −1
(b) x −4y ≤ 1
(c) −2x −3y ≤ −6
(d) −x ≤ −1
x, y ≥ 0
a. Resolvez graphiquement les 3 problemes proposes.
b. Quelles sont leurs particularites ?
Solution.
y
10
2x + y = 9
−x + y = 1
2x + 3y = 10
y=1
0 x
0 5 10
Figure 4 – Resolution graphique du programme lineaire Π1 .
On repond aux deux questions a la fois. La resolution du premier programme lineaire
est donne sur la figure 4. On y voit que les 4 contraintes donnees ne sont pas satisfiables
simultanement. Le programme lineaire n’a aucune solution admissible et il n’y a donc
rien a optimiser.
La resolution du deuxieme programme lineaire est donne sur la figure 5. Dans ce cas,
la zone des solutions valides, celles qui satisfont toutes les contraintes, n’est pas bornee
(zone bleue sur le dessin), elle est ouverte vers le haut et la droite. Et comme la fonction
objectif, z = x+2y, croit lorsque x croit (vers la droite) ou lorsque y croit (vers le haut),
il n’y a pas de solution maximum : quelle que soit la valeur atteinte pour l’objectif,
on peut toujours faire mieux en choisissant des valeurs plus grandes pour x et pour y.
y
10
x=1
3x − y = 1
5
x + y croissant
x + y = cte
x − 4y = 1
2x + 3y = 6
0 x
0 5 10
Figure 5 – Resolution graphique du programme lineaire Π2 .
Cela ne veut pas dire pour autant qu’on puisse choisir ces valeurs n’importe comment,
meme pour les grandes valeurs, il y a certaines contraintes a respecter, en l’occurence
x − 4y ≤ 1 et −3x + y ≤ −1. En general, lorsqu’on se retrouve dans ce genre de
situation, c’est a dire qu’on peut atteindre une valeur objectif aussi grande qu’on veut,
on peut soupconner qu’il y a eu un probleme de modelisation : soit le probleme a mal
ete modelise par des contraintes lineaires, soit certaines contraintes ont ete oubliees.
En effet, dans les problemes provenant du monde reel, rien n’est illimite. Il n’est donc
en general pas naturel de pouvoir atteindre un objectif aussi grand qu’on veut.
La resolution du troisieme programme lineaire est donne sur la figure 6. remarquez que
la liste des contraintes est exactement la meme que pour le probleme precedant, seule la
fonction objectif change ! Mais cela change completement la situation car dans ce cas,
il y a une solution optimale et elle est unique. Cela peut paraitre etonnant car la zone
des solutions admissibles est encore infinie. Mais la fonction objectif a maximiser ici,
z = −4x + y, decroit lorsque x croit. Ainsi, la maximisation de cette fonction objectif
y
10
x=1
3x − y = 1 −4x + y = cte
−4x + y croissant
x − 4y = 1
2x + 3y = 6
0 x
0 5 10
Figure 6 – Resolution graphique du programme lineaire Π3 .
ne nous "pousse" pas vers la partie non bornee de la zone des solutions admissibles
(en bleu). Au lieu de cela, elle nous "pousse" dans la direction d’un des coins limite
de la zone bleu. La solution admissible correspondant a ce point (croisement entre les
droites d’equations x = 1 et 3x − y = 1) est donc l’unique solution qui maximise la
fonction objectif (−4x + y). Cette solution optimale est x = 1, y = 2 et elle atteint
une valeur de la fonction objectif de −2.
Remarque. Le fait que le coefficient de x dans la fonction objectif soit negatif ne
suffit pas a garantir l’existence d’une solution optimale au probleme. Par exemple,
si la fonction objectif etait z 0 = −2x + y, on se retrouverait encore dans la situation
precedente ou il n’y a pas de solution optimale. En effet, a partir d’une solution
admissible, on pourrait toujours en obtenir une realisant un objectif plus eleve en
augmentant y et en augmentant x de 3 fois moins que y, pour suivre la droite
d’equation 3x − y = 1. Ainsi, on reste dans la zone des solutions admissibles tout
en augmentant la valeur de l’objectif z 0 = −2x + y.
Exercice 3. Le voyageur de commerce
On se propose d’ecrire un programme lineaire en nombre entiers pour resoudre le probleme
du voyageur de commerce. On a donc un ensemble X de villes et on note P2 (X) l’ensemble
des paires de X. A chaque paire uv ∈ P2 (X) est associee une distance duv entre u et v.
Pour ecrire un programme lineaire en nombre entiers, on introduit une variable binaire
buv ∈ {0, 1} pour chaque paire uv ∈ P2 (X) de villes, avec buv = 1 ssi la paire uv est
selectionnee dans le tour, c’est a dire si u et v aparaissent consecutivement dans le tour.
a. Ecrivez la fonction objectif a minimiser.
P
Solution. La fonction objectif a minimiser est la longueur du tour, soit duv buv .
uv∈P2 (X)
Il faut en plus encoder par des contraintes lineaires le fait que l’ensemble des paires
selectionnees forment un cycle passant par tous les sommets.
b. Donnez l’ensemble de contraintes, appelees contraintes de parite, qui garantissent
que chaque ville appartient a exactement 2 paires selectionnees dans le tour.
P
Solution. On introduit une contrainte pour chaque ville u ∈ X, qui s’ecrit v∈X\{u} buv =
2.
A ce stade, on obtient la fomulation suivante pour le programme lineaire en nombres
entiers que l’on est en train de construire, note P :
P
P : minimiser uv∈P2 (X) duv buv sous contraintes :
P
(A) ∀u ∈ X, buv = 2
v∈X\{u}
∀uv ∈ P2 (X), buv ∈ {0, 1}
c. Donnez un exemple dans lequel chaque ville appartient a exactement 2 paires selec-
tionnees dans P (c’est a dire pour lesquelles buv = 1) mais l’ensemble de ces paires ne
forme pas un tour. Caracterisez tous les cas ou cela se produit.
Solution. C’est par exemple le cas si, avec les paires selectionnees, on forme deux
cycles disjoints impliquant chacun une partie (disjointe) des villes. De maniere plus
generale, on peut former autant de cycles disjoints qu’on veut. Et ce sont les seuls cas
dans lesquels toutes les villes appartiennent a exactement 2 paires selectionnees mais
l’ensemble de ces paires ne forme pas un tour (prouvez le !).
Soit maintenant un graphe non oriente G = (V, E), avec |V | = n, et le programme li-
neaire suivant associe a G. On introduit une variable x(u,v) pour chaque couple (u, v) de
sommets adjacents dans G. Attention, couple 6= paire : il y a deux fois plus de couples
que de paires car les paires uv et vu sont identiques alors que les couples (u, v) et (v, u)
sont differents. Le programme lineaire propose, note ΠG , s’ecrit alors, en notant N (u) le
voisinage d’un sommet u dans G :
ΠG : maximiser rien sous contraintes :
(a) ∀uv ∈ E, x(u,v)P+ x(v,u) = 2 2
(b) ∀u ∈ V , x(u,v) ≤ 2 − n
v∈N (u)
∀u, v ∈ V 2 et u 6= v, xuv ∈ R+
d. Montrez que si G contient un cycle, alors le programme lineaire ΠG ci-dessus n’admet
pas de solution faisable.
P P
Solution. Soit C un cycle de G et l sa longueur. x(u,v) ≥ 2l car, d’apres l’
u∈C v∈N (u)
ensemble de contraintes (a), pour toutes les aretes uv de C on a x(u,v) + x(v,u) = 2. Et
y a l sommets sur le cycle, cela implique qu’il existe au moins un d’entre eux
comme il P
tel que x(u,v) ≥ 2, ce qui viole au moins une contrainte de l’ensemble (b).
v∈N (u)
e. Montrez que si G est un chemin, alors le programme lineaire ci-dessus admet au
moins une solution faisable.
Solution. G est un chemin que l’on note x1 , x2 , . . . , xn . On peut voir x(u,v) comme la
charge que l’arete uv donne a u et x(v,u) comme la charge que l’arete uv donne a v.
Au total l’arete uv donne exactement une charge de 2 (ensemble de contraintes (a)),
repartie entre u et v comme on veut. Et on veut que chaque sommet recoive une charge
d’au plus 2 − n2 (ensemble de contraintes (b)). Une facon de construire une solution
est la suivante, en suivant l’idee qu’on veut essayer de donner le maximum de charge
admissible a chaque sommet (pour decharger les autres), car la quantite totale que l’on
donne a l’ensemble des sommets est fixe : exactement 2 par arete de G.
— x1 x2 donne une charge de 2 − n2 a x1 car c’est la seule arete qui le peut, et x1 x2
donne le reste de sa charge a x2 , soit une charge de n2
— x2 x3 donne une charge de 2 − n4 a x2 (c’est le max admissible puisque x2 a deja
recu n2 de x1 x2 ) et le reste, n4 , a x3
— x3 x4 donne une charge de 2 − n6 a x3 et le reste, n6 , a x4
— et ainsi de suite jusqu’a xn−1 xn qui donne 2 − 2(n−1) n
= n2 a xn−1 et 2 − n2 a xn .
A la fin, tous les sommets ont recu exactement 2 − n2 et donc toutes les contraintes de
ΠG sont satisfaites. On peut verifier que le total des charges recues par les n sommets
du chemin n(2 − n2 ) = 2(n − 1) est bien le total des charges distribuees par ses n − 1
aretes.
Soit w une ville quelconque de l’instance donnee du voyageur de commerce.
f. Montrez que si l’ensemble des paires selectionnees dans le programme lineaire P
forme un tour alors le graphe G̃ forme par les paires selectionnees qui ne contiennent
pas w est un chemin, et que sinon G̃ contient un cycle.
Solution. Lorsqu’on retire un sommet dans un cycle, on obtient un chemin. Ainsi, si
l’ensemble des paires selectionnees forment un tour, celles qui ne contiennent pas w
forment un chemin. A l’inverse, si l’ensemble des paires selectionnees ne forment pas un
tour, comme tous les sommets sont incidents a exactement deux paires selectionnees
(voir l’ensemble de contraintes (A) de P ), alors l’ensemble des paires selectionnees
est l’union d’au moins deux cycles disjoints, comme explique dans la reponse a la
question c. Par consequent, lorsqu’on retire le sommet w, qui n’appartient qu’a un
des cycles disjoints, il reste encore au moins un autre cycle intact dans l’ensemble des
paires selectionnees.
g. Completez le programme lineaire en nombre entier P en ajoutant en plus des
contraintes de parite, un ensemble adequat de contraintes pour que les solutions opti-
males de P soient les solutions optimales au probleme de voyageur de commerce.
Solution.
Les contraintes qu’on ajoute servent a forcer que les aretes selectionnees ne contiennent
pas de cycle disjoint de w. Par rapport au programme lineaire ΠG qui precede, w est
retiree de l’ensemble des villes et seules les paires selectionnees dans P (c’est a dire
telles que buv = 1) distribuent de la charge :
∀u, v ∈ X \ {w}, x(u,v) + x(v,u) = 2buv
et on a toujours les contraintes qui garantissent que la charge recue par une ville (autre
que w qui a ete retiree) n’excede pas 2 − 2/n :
X 2
∀u ∈ X \ {w}, x(u,v) ≤ 2 −
n
v∈X\{u,w}
Au final, dans son integralite, le programme lineaire en nombres entiers pour le voya-
geur de commerce, note T SP , s’ecrit comme suit.
P
T SP : minimiser uv∈P2 (X) duv buv sous contraintes :
P
(A) ∀u ∈ X, buv = 2
v∈X\{u}
(B) ∀uv ∈ P2 (X \ {w}), x(u,v)
P + x(v,u) = 2buv
(C) ∀u ∈ X \ {w}, x(u,v) ≤ 2 − n2
v∈X\{u,w}
∀uv ∈ P2 (X), buv ∈ {0, 1}
∀(u, v) ∈ (X \ {w})2 et u 6= v, x(u,v) ∈ R+
Notez que les variables sont les buv et les x(u,v) , que les duv pour uv ∈ P2 (X) sont des
donnees du probleme et que w ∈ X est une ville choisie arbitrairement.
