Up: MathématiquesMathématiques
Document disponible au format: PDF, Text, LaTeX, LyX.

Gestion et Recherche Opérationnelle, Notes de cours



Nicolas.Thiery@u-psud.fr

http://Nicolas.Thiery.name/

Chapter 1  Introduction à l'optimisation

1.1  TD: Ordonnancement par la méthode des potentiels



Exercice 1   On veut construire une maison, ce qui consiste en 9 tâches, le plus rapidement possible, avec les contraintes suivantes:








Exemple 1   Organisez un emploi du temps pour un ouvrier, de façon à construire la maison le plus rapidement.
  semaine 1 semaine 2 semaine 3 semaine 4 semaine 5 semaine 6 semaine 7
ouvrier 1              

De même, s'il y a deux ouvriers:
  semaine 1 semaine 2 semaine 3 semaine 4 semaine 5 semaine 6 semaine 7
ouvrier 1              
ouvrier 2              

De même, s'il y a trois ouvriers:
  semaine 1 semaine 2 semaine 3 semaine 4 semaine 5 semaine 6 semaine7
ouvrier 1              
ouvrier 2              
ouvrier 3              

Et s'il y a plus d'ouvriers ?
Généralisation avec des durées.

1.2  Problèmes d'optimisation



Problem 1   Quelles sont les coordonnées du point culminant du massif de la Chartreuse?



Modélisation:
Définition 2   Un problème d'optimisation est décrit par: Il faut de plus préciser s'il s'agit d'un problème de maximisation ou de minimisation.

Une solution faisable p est dite
optimale si z(p)≥ z(q) pour toute autre solution faisable q.

But: déterminer l'ensemble des solutions optimales.
Exemple 3   Modéliser les problèmes suivants, puis les résoudre ou proposer des méthodes de résolution:
  1. Calcul du plus court chemin dans un graphe.
  2. Recherche d'un ordonnancement optimal pour ...
  3. Déterminer le plus petits nombre de cartons nécessaires pour un déménagement.
  4. Chercher un mat en un minimum de coup
  5. Recherche de l'élément maximal d'un tableau de n valeurs aléatoires.
  6. Maximiser z pour z dans [0,1[.
  7. Maximiser z pour z dans R+.
  8. Déterminer la valeur minimale de la fonction x2+2x−4.
    plotfunc2d(x^2 + 2*x - 4)
  9. Déterminer la valeur minimale de la fonction 2x3−5x2x+7.
    plotfunc2d(2*x^3 - 5*x - x + 7)
  10. Déterminer la valeur maximale de la fonction sin(x)sin(π x+2)+0.01x2.
    plotfunc2d(sin(x) * sin(PI*x+2)-0.01*x^2,x=-20..20)
  11. Quelle est la profondeur maximale de l'océan?
Bilan: un problème d'optimisation peut avoir Quelques méthodes d'optimisation:
  1. Méthodes globales:
  2. Méthodes locales, itératives:
    Lorsque le problème a une propriété de «convexité», l'optimisation locale amène à une optimisation globale!
  3. Méthodes mixtes:

Chapter 2  Programmation linéaire

2.1  Rappel d'algèbre linéaire



Problem 1   Considérons le système suivant:
5  = s1       + 2*x1 + 3*x2 +   x3

11 =    s2    + 4*x1 +   x2 + 2*x3

8  =       s3 + 3*x1 + 4*x2 + 2*x3
Que peut-on dire dessus?

C'est un système
linéaire à 6 inconnues et 3 équations.

On peut décrire l'ensemble des solutions en prenant comme paramètres x1
, x2 et x3.

En effet, vu sa forme triangulaire, s1, s2 et s3 s'expriment en fonction de x1
, x2 et x3.

Transformer le système pour prendre comme paramètres s1
, s2, et x1.


2.2  Qu'est-ce que la programmation linéaire

2.2.1  Exemple: le problème du régime de Polly [1, p.3]

Problem 1   Polly peut-elle trouver une solution ?

Comment formaliser le problème ? (modélisation)

Qu'est-ce qui fait la spécificité du problème ?

Savez-vous résoudre des problèmes similaires ?


2.2.2  Forme standard d'un problème de programmation linéaire



Problem 2   [1, p. 5]
Maximiser:            5*x1 + 4*x2 + 3*x3

Sous les contraintes: 2*x1 + 3*x2 +   x3 <=  5 

                      4*x1 +   x2 + 2*x3 <= 11

                      3*x1 + 4*x2 + 2*x3 <=  8

                      x1, x2, x3 >= 0

Minimiser:            3*x1 -   x2

Sous les contraintes: - x1 + 6*x2 -   x3 +   x4 >= -3 

                             7*x2        + 2*x4 =   5

                        x1 +   x2 +   x3        =   1

                                      x3 +   x4 <=  2

                       x2, x3 >= 0
Définition 1   Problème de programmation linéaire sous forme standard:

Maximiser:

z:=
n
Σ
j=1
cjxj


Sous les contraintes:

n
Σ
j=1
aijxj bi, pour i=1,…,m


xj≥0, pour j=1,…,n


Un choix des valeurs des variables (x1,…,xn) est appelé solution du problème.

Une solution est
faisable si elle vérifie les contraintes.

z est appelé
fonction objective. À chaque solution elle associe une valeur.

Une solution est
optimale si elle est faisable et maximize la fonction objective.
Exercice 1   Peut-on mettre sous forme standard les exemples précédents ?


2.2.3  Existence de solutions optimales ?



Problem 3   [1, p. 7] On considère les trois problèmes de programmation linéaire standard suivants, écrits avec la syntaxe du système de calcul formel MuPAD:
Chvatal7a := [ [   x1      <= 3, 

                        x2 <= 7 ],

                3 +x1  +x2, 

               NonNegative]:

Chvatal7b := [ [   x1  +x2 <= 2, 

                -2*x1-2*x2 <= -10 ],

                 3*x1  -x2, 

               NonNegative]: 

Chvatal7c := [ [-2*x1  +x2 <= -1, 

                  -x1-2*x2 <= -2 ],

                   x1  -x2,

               NonNegative]:

extra     := [ [   x1  +x2 <= 1 ],

                   x1  +x2,

               NonNegative]:
Problem 4   Déterminer pour ces trois problèmes s'il y a des solutions optimales.








2.3  Algorithme du simplexe

2.3.1  Premier problème



Problem 1   [1, p. 13]
Chvatal13 := [{2*x1 + 3*x2 +   x3 <= 5, 

               4*x1 +   x2 + 2*x3 <= 11, 

               3*x1 + 4*x2 + 2*x3 <= 8  }, 

               5*x1 + 4*x2 + 3*x3, 

              NonNegative]:
Solution faisable ?

Amélioration de la solution ?









Introduction de variables d'écart:
5  = s1       + 2*x1 + 3*x2 +   x3

11 =    s2    + 4*x1 +   x2 + 2*x3

8  =       s3 + 3*x1 + 4*x2 + 2*x3

----------------------------------

z  =            5*x1 + 4*x2 + 3*x3
En augmentant x1 jusqu'à 5/2, on fait tomber s1 à zéro.

On transforme le système, pour se ramener à une situation similaire à la précédente:
5/2 = x1       + 3/2*x2 + 1/2*x3 + 1/2*s1

1   =    s2    -   5*x2            - 2*s1

1/2 =       s3 - 1/2*x2 + 1/2*x3 - 3/2*s1

-----------------------------------------

z   = 25/2     - 7/2 x2 + 1/2*x3 - 5/2*s1
On augmente x3 jusqu'à 1, ce qui fait tomber s3 à 0:
1 = x3       -   x2 - 3*s1 + 2*s3

2 =    x1    + 2*x2 + 2*s1 -   s3

1 =       s2 - 5*x2 - 2*s1

---------------------------------

z = 13       - 3*x2 -   s1 -   s3
Et maintenant, que fait-on ?

2.3.2  Tableaux



Problem 2   [1, p. 19]
Chvatal19 := [[  x1 + 3*x2   + x3 <= 3, 

                -x1         +3*x3 <= 2,

               2*x1 + 3*x2   - x3 <= 2, 

               2*x1   - x2 + 2*x3 <= 4], 

               5*x1 + 5*x2 + 3*x3, 

              NonNegative]:
Définition 2   Tableau initial:

bi=si+
n
Σ
j=1
aijxj, pour i=1,…,m


z=
n
Σ
j=1
cjxj


Ou sous forme matricielle:
B = S+AX
z = CX
X 0


Exemple 2   Tableau initial du problème précédent:
3 = s1         + x1 + 3 x2   + x3

2 =   s2       - x1        + 3 x3

2 =     s3   + 2 x1 + 3 x2   - x3

4 =       s4 + 2 x1   - x2 + 2 x3

---------------------------------

z = 0        + 5 x1 + 5 x2 + 3 x3
Exemple 3   On peut l'abréger sous forme matricielle:
read("tableaux.mu"):

linopt::Transparent(Chvatal19);

+-                                                   -+

|"linopt","restr",slk[1],slk[2],slk[3],slk[4],x3,x1,x2|

|                                                     |

|  "obj",    0,      0,     0,     0,     0,   3, 5, 5|

|                                                     |

| slk[1],    3,      1,     0,     0,     0,   1, 1, 3|

|                                                     |

| slk[2],    2,      0,     1,     0,     0,   3,-1, 0|

|                                                     |

| slk[3],    2,      0,     0,     1,     0,  -1, 2, 3|

|                                                     |

| slk[4],    4,      0,     0,     0,     1,   2, 2,-1|

+-                                                   -+
Définition 3   De manière générale, un tableau est un ensemble d'équations de la forme:
4 = x1       + 3/2 x2  - 1/2 x3 + 1/2 s4 

2 =   s1     + 3/2 x2  + 3/2 x3 - 1/2 s4 

3 =     s2   + 3/2 x2  + 5/2 x3 + 1/2 s4 

2 =       s3   - 4 x2    + 3 x3     - s4 

---------------------------------------- 

z = 5        - 5/2 x2 + 11/2 x3 - 5/2 s4
x1,s1,s2,s3 sont les variables basiques; { x1,s1,s2,s3} est la base.

x
2,x3,s4 sont les variables non basiques.
Définition 4   Le point de coordonnées (0,…,0) dans les variables non-basiques est appellé solution basique du tableau.

Un tableau est
faisable si la solution basique (0,…,0) est une solution faisable.

De manière équivalente, un tableau est faisable si les constantes dans les équations du haut sont toutes positives ou nulles.
Revenons à l'exemple [1, p. 19]:
read("tableaux.mu"):

t:=linopt::Transparent(Chvatal19);

t:=linopt::Transparent::userstep(t, slk[3], x3);
Exercice 2   [1, 2.1 p. 26]

Utilisez l'algorithme du simplexe pour résoudre les programmes linéaires suivants:
Chvatal26_21a :=

[[  x1  +x2+2*x3 <= 4,

  2*x1     +3*x3 <= 5,

  2*x1  +x2+3*x3 <= 7],

  3*x1+2*x2+4*x3,

 NonNegative]:

Chvatal26_21c :=

[[2*x1+3*x2 <= 3,

    x1+5*x2 <= 1,

  2*x1  +x2 <= 4,

  4*x1  +x2 <= 5],

  2*x1  +x2,

 NonNegative]:


Exercice 3   Essayez d'appliquer l'algorithme du simplexe aux programmes linéaires de l'exercice [1, p. 7] (cf. ci-dessus). Que se passe-t'il ?


2.4  Pièges et comment les éviter

2.4.1  Bilan des épisodes précédents

On a un algorithme qui marche sur quelques exemples.

Il faut vérifier trois points pour savoir s'il marche en général:
  1. Initialisation
  2. Itération
  3. Terminaison

2.4.2  Itération



Proposition 1   Étant donné un tableau faisable, on peut toujours effectuer l'une des opérations suivantes:
  1. Conclure que le système a une solution optimale unique, la calculer et la certifier;
  2. Conclure que le système a une infinité de solutions optimales, les calculer et les certifier;
  3. Conclure que le système est non borné, et le certifier en décrivant une demi-droite de solutions sur laquelle z prend des valeurs aussi grandes que voulu.
  4. Trouver une variable entrante, une variable sortante, et effectuer un pivot. Par construction, le tableau obtenu est équivalent au tableau précédent, et est encore faisable. De plus, z a augmenté au sens large (i.e. la constante z* dans la nouvelle expression de z est supérieure ou égale à l'ancienne).
Proof. Il suffit d'analyser le tableau faisable. Notons S1,…,Sm les variables basiques, X1,…,Xn les variables non-basiques, et C1,…,Cn,z* les coefficients tels que z=z*CiXi.

Par exemple, dans le tableau final du problème1, on a X1=x2, X2=s1, X3=s2, S1=x1, S2=x3, S3=s3, C1=−3, C2=−1, C3=−1 et z*=13.
  1. Si Ci<0, pour tout i, alors la solution basique du tableau, de coordonnées X1*=⋯=Xn*=0 est l'unique solution optimale. Vérifiez le en prouvant qu'une toute solution faisable quelconque de coordonnées X1,…,Xn donnant la même valeur z=z* à la fonction objective est égale à la solution basique du tableau.
  2. Si Ci≤0 pour tout i, la solution basique du tableau est optimale, et l'ensemble des solutions optimales est décrit par les inéquations linéaires du système et l'annulation des variables non-basiques Xi pour lesquelles on a Ci<0. Les détails sont similaires au 1.
  3. Sinon, on peut prendre Xi, variable non-basique avec un coefficient Ci>0. Si les équations du tableau n'imposent pas de limite sur Xi, le système est non borné: la demi-droite décrite par (0,…,0,Xi,0,…,0) pour Xi≥0 est composée de solutions faisables qui donnent des valeurs aussi grandes que voulu à z.
  4. Autrement, une des variables basiques Sj tombe à zéro, et on peut faire un pivot entre la variable entrante Xi et la variable sortante Sj. Par construction, la nouvelle solution basique correspond à une solution faisable (0,…,0,Xi,0,…,0) pour un Xi≥0. En particulier le nouveau tableau est faisable, et comme Ci≥0, la constante z* a augmenté au sens large.

Exemple 3   [1, p. 29] Système où z n'augmente pas strictement lors du pivot:
Chvatal29 :=  [[              2*x3 <= 1, 

                - x1 + 3*x2 + 4*x3 <= 2, 

                2*x1 - 4*x2 + 6*x3 <= 3],

                2*x1   - x2 + 8*x3, 

                NonNegative]:

t0:= linopt::Transparent(Chvatal29);

t1:= linopt::Transparent::userstep(t0, slk[1], x3);

t2:= linopt::Transparent::userstep(t1, slk[3], x1);

t3:= linopt::Transparent::userstep(t2, slk[2], x2);

t4:= linopt::Transparent::userstep(t3, x3, slk[1]);
Remarque 1   Lorsque z n'augmente pas, on est forcément dans une situation de dégénérescence: le pivot change le tableau, mais pas la solution basique décrite par le tableau.


2.4.3  Terminaison



Problem 1   Peut-on garantir que l'algorithme va finir par s'arrêter ?










Théorème 1   Si l'algorithme du simplexe ne cycle pas, il termine en au plus C(n+m,m) itérations.


Proof. (Résumé)

Chaque itération correspond à un tableau faisable.

Un tableau faisable est entièrement caractérisé par le choix des variables basiques.

Il n'y a que C(n+m,m) choix possibles de variables basiques.


Remarque 2   L'algorithme ne peut cycler qu'en présence de dégénérescence.
Avec une stratégie incorrecte, l'algorithme du simplexe peut cycler éternellement:

Exemple 4   [1, p. 31] Système cyclant en 6 itérations avec la stratégie:
Chvatal31 := [[0.5*x1 - 5.5*x2 - 2.5*x3 +  9*x4 <= 0, 

               0.5*x1 - 1.5*x2 - 0.5*x3 +    x4 <= 0,

                   x1                           <= 1],

                10*x1  - 57*x2   - 9*x3 - 24*x4,

              NonNegative]:

t0 := linopt::Transparent(Chvatal31);

t1 := linopt::Transparent::userstep(t0, slk[1], x1);

t2 := linopt::Transparent::userstep(t1, slk[2], x2);

t3 := linopt::Transparent::userstep(t2, x1, x3);

t4 := linopt::Transparent::userstep(t3, x2, x4);

t5 := linopt::Transparent::userstep(t4, x3, slk[1]);

t6 := linopt::Transparent::userstep(t5, x4, slk[2]);
Comment garantir que l'algorithme ne cyclera pas ?

2.4.4  Initialisation

Pour le moment, l'algorithme du simplexe nécessite de partir d'un tableau faisable.

Problème 1   Dans le cas général, comment se ramener à un tableau faisable?

Le système pourrait même ne pas avoir de solution!
Exemple 5   [1, p. 39] Système P1:

Maximiser: x
1x2+x3

Sous les contraintes:

2x
1x2+2x3≤4

2x
1−3x2+x3≤−5

x
1+x2−2x3≤−1

x
1,x2,x3≥0










Exemple 6   Introduction d'un système auxiliaire P0 pour déterminer si P est faisable:

Maximiser: −x
0

Sous les contraintes:

2x
1x2+2x3x0≤4

2x
1−3x2+x3x0≤−5

x
1+x2−2x3x0≤−1

x
0,x1,x2,x3≥0

Remarques: Étudions ce nouveau système:
Chvatal40 := [[ -x1   + x2 - 2*x3 - x0 <= -1,

               2*x1 - 3*x2   + x3 - x0 <= -5, 

               2*x1   - x2 + 2*x3 - x0 <= 4], 

              -x0, 

              NonNegative]:

t0:=linopt::Transparent(Chvatal40);

t1:=linopt::Transparent::userstep(t0, slk[2], x0);

t2:=linopt::Transparent::userstep(t1, slk[1], x2);

t3:=linopt::Transparent::userstep(t2, x0, x3);
Maintenant, nous savons que le système P est faisable.

En fait, en éliminant x
0 on obtient même un tableau faisable pour P!
Algorithme du simplexe en deux phases pour résoudre un problème P sous forme standard:

Phase I:
  1. Si (0,…,0) est solution faisable de P, on passe directement à la phase II.
  2. Définir un problème auxiliaire P0.
  3. Le premier tableau pour P0 est infaisable.
  4. Le rendre faisable par un pivot approprié de x0.
  5. Appliquer le simplexe habituel:
    1. Si à une étape donnée, x0 peut sortir de la base, le faire en priorité:

      En effet, il y a une solution faisable avec x0=0, et on peut passer en phase II.

    2. Si à une étape donnée on atteint une solution optimale:
      1. Si x0 n'est pas basique:

        Il y a une solution faisable avec x0=0. On peut donc passer en phase II.

      2. Si x0 est basique et z0<0:

        P est infaisable, et on s'arrête.

      3. Sinon x0 est basique et z0=0:

        Situation impossible si on fait toujours sortir x0 en priorité de la base.

  6. Tirer de P0 un tableau faisable pour P;
Phase II:
  1. Appliquer le simplexe habituel à partir du tableau donné par P0.
Exercice 2   [1, ex 3.9a p. 44]

Maximiser 3x
1+x2

Sous les contraintes:

x
1x2≤−1

x
1x2≤−3

2x
1+x2≤4

x
1,x2≥0
t0:=linopt::Transparent(Chvatal44_39a0)

t1:=linopt::Transparent::userstep(t0, slk[2], x0)

t2:=linopt::Transparent::userstep(t1, slk[1], x1)

t3:=linopt::Transparent::userstep(t2, x0, x2)

t0:=linopt::Transparent(Chvatal44_39a)

t1:=linopt::Transparent::userstep(t0, slk[1], x1)

t2:=linopt::Transparent::userstep(t1, slk[2], x2)

t3:=linopt::Transparent::userstep(t2, slk[3], slk[2])

2.4.5  Le théorème fondamental de la programmation linéaire



Théorème 3   Tout programme linéaire P sous forme standard a l'une des propriétés suivantes:
  1. Si P n'a pas de solutions optimales, alors P est infaisable ou non borné;
  2. Si P a une solutions faisable, alors P a une solution basique faisable;
  3. Si P a une solution optimale, alors P a une solution basique optimale.

Chapter 3  Problèmes de flot maximum

3.1  Introduction



Définition 4   Problème de flot max:


Objectif:

Maximiser le
volume du flot, c'est-à-dire la quantité transportée entre s et p.
Exemple 7   Un dimanche soir, maximiser le nombre de voitures allant d'Albertville à Lyon, en les répartissant entre les différentes routes possibles.
Exercice 3   Mettre le problème de flot dessiné ci-dessus sous forme de programme linéaire.


Clairement, cela se généralise à tout problème de flot max.

Problème 2   Que peut-on en déduire ?

3.2  Coupes dans un problème de flot



Définition 5   Une coupe C dans un réseau est un ensemble de sommets du réseau contenant la source.

La capacité de la coupe C est la somme des capacités des arrêtes sortantes de C.
Exemple 8   Dans notre réseau, la coupe C={s} est de capacité 5.



Exercice 4   Quelle est la capacité de la coupe C={s,i2,i3}?

Que peut-on en déduire sur la valeur d'un flot ?










Proposition 2   Pour toute coupe C et tout flot F dans un réseau, la capacité |C| de la coupe est supérieure au volume |F| du flot: |C|≥|F|.
Exercice 5   Chercher un flot maximal et une coupe minimal dans notre exemple?

Que peut-on dire?


3.3  Algorithme de Ford-Fulkerson

Nous allons maintenant donner un algorithme qui permet de calculer un flot maximal.

Mieux, comme l'algorithme du simplexe, cet algorithme va donner des résultats théoriques!

Exemple 9   On veut transporter le plus grand nombre possible de voyageurs de San-Francisco à New-York, sachant qu'il ne reste que quelques places dans les avions entre les villes suivantes:



Définition 6   Soit R un réseau, et F un flot donné dans ce réseau.

Un chemin allant de la source s au puits p est
F-augmentant si pour chaque arête ij du chemin on a:
À partir d'un chemin F-augmentant, on peut construire un nouveau flot F' qui sera de volume strictement plus gros.

Le principe de l'algorithme de Ford-Fulkerson est de partir d'un flot F quelconque, et de l'améliorer itérativement en recherchant des chemins F-augmentant.

À chaque étape, la recherche d'un chemin F-augmentant se fait par un parcours en profondeur, de manière similaire à la recherche d'un chemin M-augmentant dans un graphe biparti. Si cette recherche échoue, elle dévoile une coupe de capacité égale au flot, ce qui donne un certificat d'optimalité du flot.

Remarque 1   On peut toujours initialiser l'algorithme avec un flot nul.

Si toutes les capacités sont entières et finies, chaque itération augmente le flot d'au moins 1. Cet algorithme ne peut donc pas cycler, et il termine en un nombre fini d'étapes.

Avec une mauvaise stratégie, et des capacités infinies ou non-entières, l'algorithme peut ne pas terminer.



Avec une stratégie convenable, cet algorithme est en fait polynomial, en O(n
3), même si les capacités sont infinies ou non entières.

Pour les réseaux avec peu d'arcs, il y a des algorithmes plus compliqués qui permettent d'obtenir d'encore meilleurs bornes. Cf. [
1, p. 369] pour les détails.


3.4  Conséquences de l'algorithme de Ford-Fulkerson

3.4.1  Théorème de dualité min-max



Théorème 4   (Coupe min-Flot max) Dans un réseau, le volume maximal d'un flot est égal à la capacité minimale d'une coupe.
Ce théorème est un cas particulier du théorème de dualité de la programmation linéaire.

3.4.2  Théorème d'intégralité

Dans notre exemple, on veut transporter des personnes entières autant que possible!

Qu'aurait-il pu se passer si l'on avait utilisé l'algorithme du simplexe?

Qu'a t-on obtenu avec l'algorithme de Ford-Fulkerson?

Est-ce un accident?

Théorème 5   (dit d'intégralité) Soit P un problème de flot où les contraintes sont entières. Alors:
  1. Si P a une solution, alors il a une solution à coefficients entiers;
  2. Si P a une solution optimale, alors il a une solution optimale à coefficients entiers.


Proof. La solution initiale 0 est à coefficients entiers

À chaque étape, l'amélioration le long du chemin augmentant est entière ou infinie.


Le théorème d'intégralité est assez simple. Alors quel est son intérêt ?

Ce que dit fondamentalement le théorème d'intégralité, c'est que dans certains cas les méthodes de programmation linéaire peuvent être utilisées pour résoudre des problèmes purement combinatoire, ce qui est loin d'être trivial!

C'est le sujet de la combinatoire polyhédrale. On verra quelques exemples la semaine prochaine.

3.4.3  Combinatoire polyhédrale: quelques exemples

Couvertures et couplages dans les graphes bipartis

On va maintenant regarder une application de la programmation linéaire pour étudier des graphes non orientés comme le suivant:



Une couverture C de ce graphe est un ensemble de sommets qui touchent toutes les arêtes, comme par exemple C:={1,3,4,7,8}:



Exemple 1   On a 8 petits villages reliés par des routes. En cas d'accident de la route, on veut que les pompiers puissent intervenir rapidement. Le prefet impose que lorsqu'une route relie deux villages, il y ait une caserne de pompier dans au moins l'un des deux villages. Évidemment le budget est serré, donc on veut construire des casernes de pompier dans un nombre minimal de villages.

Modélisation: Chaque village est représenté par un sommet du graphe précédent, les arêtes représentant les routes. Résoudre notre problème revient à chercher une couverture de taille minimale du graphe.
Un couplage M de ce graphe est un ensemble d'arêtes qui ne se touchent pas, comme par exemple M:={{1,3},{4,5},{7,8}}:



Exemple 2   On veut loger un groupe de 8 personnes dans un hotel, avec des chambres simples et doubles. Pour minimiser les dépenses, on utiliser le maximum de chambres doubles. D'un autre côté on ne veut pas forcer deux personnes qui ne se connaissent pas bien à partager une chambre.

Modélisation: chaque sommet du graphe précédent représente une personne, et chaque arête relie deux personnes qui se connaissent bien. Résoudre notre problème revient alors à rechercher un couplage de taille maximale dans le graphe.
Exercice 4   Montrer que pour un couplage M et une couverture C d'un même graphe, on a toujours |M|≤|C|.










Proof. Comme C est une couverture, chaque arête de M devra être touchée par au moins un sommet dans C. De plus, M étant un couplage, chaque sommet de C touche au plus une arête de M. Donc, on a bien |M|≤|C|.


Problem 3   Peut-on trouver M et C de façon à avoir égalité ?










Dans notre exemple, non. Par contre, on va voir que pour certaines classes de graphe, cela va être vrai: on aura un théorème de dualité min-max. Comme par hasard, c'est une conséquence de la programmation linéaire.

On appelle graphe biparti un graphe dont on peut partitioner les sommets en deux paquets A et B de sorte que toutes les arêtes soient entre A et B:



Exercice 5   On veut rechercher un couplage maximal du graphe précédent. Montrer comment on peut résoudre ce problème en utilisant un problème de flot.

Utiliser l'algorithme de Ford-Fulkerson pour le résoudre.

On appelle cela la Méthode du chemin augmentant . Pourquoi?










Chaque solution entière F du problème de flot correspond à un couplage M du graphe biparti (les arêtes sur lesquelles passent une unité), avec |M|=|F|. Maximiser le flot revient à rechercher un couplage de taille max. Le théorème d'intégralité nous garanti que Ford-Fulkerson donnera bien une solution optimale entière!

Exercice 6   Prendre maintenant la coupe minimale donnée par l'algorithme de Ford-Fulkerson, et définir C l'ensemble des sommets a du graphe biparti tels que:
  1. Que constate-t'on?
Problem 4   Est-ce une coïncidence?
Exercice 7   Soit G un graphe biparti, M un couplage maximal donné par l'algorithme de Ford-Fulkerson, et C l'ensemble de sommets obtenu comme ci-dessus. Montrer que C est une couverture et que |M|=|C|.










Theorem 5   (König-Egerváry) Dans tout graphe biparti, la taille d'un couplage maximal est égale à la taille d'une couverture minimale.
C'est une exemple typique où le théorème de dualité de la programmation linéaire donne un théorème min-max reliant deux problèmes combinatoires qui ne sont pas en lien direct a priori.

Exercice 8   Utiliser la méthode du chemin augmentant pour rechercher un couplage maximal des graphes suivants (on pourra partir du couplage suggéré):







Dualités chaînes/antichaînes dans les ordres partiels; théorème de Dilworth



Problem 6   [1, p. 338] Problème des visites guidées. Une compagnie propose 7 visites guidées dans la journée, notées a,b,c,d,e,f,g, dont les horaires et durées sont fixées. Si une visite (par ex. a) termine suffisament avant une autre (par exemple c), le guide de la première visite peut enchaîner sur la deuxième; on notera alors ac. En l'occurence, voici tous les enchaînements possibles:

ac,
ad, af, ag, bc, bg, dg, ef, eg.










Définition 7   Soit P=(E,<) un ordre partiel.

Une
chaîne C de P est un ensemble de sommets de P deux à-deux comparables:
xC et yC x<y ou y<x.


Une antichaîne A de P est un ensemble de sommets deux-à-deux incomparables.

Une
couverture en chaînes de P est un ensemble C1,…,Ck de chaînes, de sorte que tout sommet de P est dans une unique chaîne Ci.

Une
couverture en antichaînes de P est un ensemble A1,…,Ak d'antichaînes, de sorte que tout sommet de P est dans une unique antichaîne Ai.
Exercice 9   Trouver dans l'ordre partiel P précédent:
  1. Une chaîne de taille maximale
  2. Une antichaîne de taille maximale
  3. Une couverture en chaînes de P de taille minimale
  4. Une couverture en antichaînes de P de taille minimale
Que remarquez vous ?










Y-aurait-il un théorème min-max reliant la taille de la plus grande chaîne et la taille de la plus petite couverture en antichaînes ? Et un autre reliant la taille de la plus grande antichaîne et celle de la plus petite couverture en chaînes ?

Exercice 10   Soit P un ordre partiel quelconque.
  1. Soit C une chaîne de P et A1,…,Ak une couverture de P en antichaînes.

    Montrer que |C|≤ k.


  2. Soit A une antichaîne de P et C1,…,Ck une couverture de P en chaînes.

    Montrer que |A|≤ k.
Proposition 8   Soit P un ordre partiel. La taille de la plus grande chaîne de P est égale à la taille de la plus petite couverture en antichaînes de P.
Exercice 11   Prouvez-le!










Le théorème dans l'autre sens est plus difficile et bien plus profond. Il n'y a pas de construction élémentaire de l'antichaîne et de la couverture en chaîne idoine. On va en fait se ramener au théorème de dualité de la programation linéaire (surprise).

Theorem 9   (Dilworth) Soit P un ordre partiel. La taille de la plus grande antichaîne de P est égale à la taille de la plus petite couverture en chaînes de P.


Proof. On note n le nombre de sommets de P.

Choisir une couverture en chaîne de P est équivalent à sélectionner un certain nombre d'arcs dans P, de sorte que chaque sommet ait au plus un arc sortant de sélectionné, et un arc rentrant de sélectionné.

Remarque: s'il y a k chaînes, il y a nk arcs sélectionnés.

Cela ressemble à un problème de couplage maximal dans un graphe biparti.

On construit un graphe biparti B dans lequel chaque sommet x de P est dupliqué en (x,1) et (x,2).

Chaque fois que x<y dans P, on relie (x,1) et (y,2).

Qu'est-ce qu'un couplage dans B?

Un ensemble d'arcs de P vérifiant exactement les conditions voulues.

Une couverture de P en k chaînes correspond à un couplage de B de taille nk.

Prenons une couverture de P de taille k minimale.

Cela donne un couplage de taille max nk de B.

Le théorème min-max pour les graphes bipartis indique qu'il y a une couverture de B de même taille: nk sommets de B qui touchent tous les arcs.

Dans P cela correspond à au plus nk sommets qui touchent tous les arcs.

Soit A l'ensemble des sommets restants qui est de taille au moins k.

Il ne peut pas y avoir d'arcs entre deux sommets de A.

Conclusion: A est une antichaîne de taille au moins k.


Exercice 12   Suivez le déroulement de la preuve sur l'ordre partiel précédent.


Problème des mines à ciel ouvert



Problème 3   Des études géologiques ont permis de déterminer précisément la nature du sous-sol, et l'emplacement des gisements orifères à l'endroit ou l'on a décidé de creuser une mine à ciel ouvert. Certains gisements sont profonds, et il n'est pas clair qu'il soit rentable d'excaver tout le sol au-dessus pour y accéder.

Modèle: le sous-sol a été délimité en un certain nombre de blocs. Pour chaque bloc i, on connaît le coût C
i d'excavation, et le profit Pi que l'on peut escompter de son traitement.

Au final, on associe à chaque bloc i la quantité w
i=CiPi. Si l'on ne considère pas les autres blocs, il est rentable de creuser i si et seulement si wi<0.

On veut déterminer quels blocs on doit creuser pour maximiser le profit total −Σ
iwi (ou autrement dit minimiser Σiwi).

Maintenant, il y a des contraintes supplémentaires: si un bloc i est sous un bloc j, on ne peux pas creuser i sans creuser j!

On introduit un ordre partiel, de sorte que i<j si pour creuser i on doit creuser j.

Comme on le verra, la forme des blocs, et le type d'ordre partiel n'est pas relevant.
Exemple 10   On considère le sous-sol suivant:
Comment modéliser notre problème sous forme de problème de flot max ?

La modélisation des contraintes de précédences est un peu astucieuse!

On introduit le réseau suivant:

C'est la remarque suivante qui va faire marcher la machine:

Remarque 3   Soit C une coupe.

S'il existe deux blocs i<j, avec iC et jC, alors C est de capacité infinie.

La réciproque est vraie.
Les coupes de capacité finie sont en correspondance avec les coupes respectant les contraintes.

Maintenant, on peut vérifier que la capacité d'une coupe finie vaut exactement

 
Σ
iC, i bloc non rentable
wi
 
Σ
iC, i bloc rentable
wi.


Quitte à rajouter le terme constant Σi, i blocwi, on est en train de calculer le profit lorsque l'on enlève les blocs i avec iC.

Résumé: Soit I un ensemble de blocs, et C la coupe {s}∪ I. Maximiser le profit revient à trouver une coupe min.

Remarque 4   En termes pédants: on peut résoudre par un algorithme de flot le problème de trouver une section finale de poids minimal dans un ordre partiel.


3.5  Synthèse

Plusieurs modèles généraux pour faire de l'optimisation:
  1. Programmation linéaire
    1. Algorithme du simplexe
      Efficace en pratique (quasiment linéaire), non polynomial en théorie
    2. Algorithme de l'élipsoide
      Polynomial, mais non efficace en pratique
    3. Méthode des points intérieurs
      Plus ou moins efficace que le simplexe selon les cas
    4. Théorème de dualité ⇒ Certification, optimisation, coûts marginaux, ...
    5. Mais: solutions dans Q
  2. Problèmes de flots
    1. Algorithme de Ford-Fulkerson
      Polynomial O(n3). Plus efficace que le simplexe.
    2. Théorème de dualité (flots/coupes)
    3. Théorème d'intégralité
      ⇒ Algorithmes et théorèmes min-max sur des problèmes discrets.
  3. Réseaux de transports
    1. Algorithme du simplexe pour les réseaux
    2. Théorème de dualité (coûts marginaux)
    3. Théorème d'intégralité

References

[1]
V. Chvatal. Linear Programming.

[2]
R. Vanderbie. Linear Programming; Foundations and Extensions. http://www.princeton.edu/~rvdb/LPbook/index.html

[3]
Linear Programming FAQ http://rutcor.rutgers.edu/~mnk/lp-faq.html

[4]
http://en.wikipedia.org/wiki/Linear_programming

Valid HTML 4.0! Up: MathématiquesMathématiques
Gestion et Recherche Opérationnelle, Notes de cours / IUT d'Orsay, Cours de Mathématiques / Nicolas M. Thiéry
Dernière modification: Lun 30 Avr 2007 16:05:02