Chapitre 1 Programmation linéaire ************************************ 1.1 Qu'est-ce que la programmation linéaire *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= 1.1.1 Exemple: le problème du régime de Polly [1, p.3] ======================================================= - Besoins journaliers: Énergie 2000 kcal Protéines 55g Calcium 800 mg - Nourriture disponible --------------------------------------------------------------------- ------------ | |Portion|Énergie (kcal)|Protéines (g)|Calcium (mg)|Prix/portion| --------------------------------------------------------------------- ------------ --------------------------------------------------------------------- ------------ | Céréales | 28g | 110 | 4 | 2 | 3 | --------------------------------------------------------------------- ------------ | Poulet | 100g | 205 | 32 | 12 | 24 | --------------------------------------------------------------------- ------------ | Oeufs |2 gros | 160 | 13 | 54 | 13 | --------------------------------------------------------------------- ------------ | Lait entier | 237cc | 160 | 8 | 285 | 9 | --------------------------------------------------------------------- ------------ | Tarte | 170g | 420 | 4 | 22 | 20 | --------------------------------------------------------------------- ------------ |Porc et haricots| 260g | 260 | 14 | 80 | 19 | --------------------------------------------------------------------- ------------ Quels choix pour Polly ? - Contraintes: Céréales au plus 4 portions par jour Poulet au plus 3 portions par jour Oeufs au plus 2 portions par jour Lait au plus 8 portions par jour Tarte au plus 2 portions par jour Porc et haricots au plus 2 portions par jour Problème 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 ? 1.1.2 Forme standard d'un problème de programmation linéaire ============================================================= Problème 1 [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: n -- \ z:=/ c x -- j j j=1 Sous les contraintes: n -- \ / a x <= b , pour i=1,...,m -- ij j i j=1 x >=0, pour j=1,...,n j Un choix des variables (x_1,...,x_n) 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 2 Peut-on mettre sous forme standard les exemples précédents ? 1.1.3 Existence de solutions optimales ? ========================================= Problème 3 [1, p. 7] On considère les quatre 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]: Problème 4 Déterminer pour ces trois problèmes s'il y a des solutions optimales. - Premier cas: une solution optimale unique - Deuxième cas: pas de solution faisable - Troisième cas: pas de solution optimale, car on peut faire tendre la fonction objective vers l'infini avec des solutions faisables. - Quatrième cas: une infinité de solutions optimales. 1.2 Algorithme du simplexe *=*=*=*=*=*=*=*=*=*=*=*=*=* 1.2.1 Une pointe d'algèbre linéaire ==================================== Problème 5 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. L'ensemble des solutions est un sous espace de dimension 3 de R^3, que l'on peut décrire en prenant comme paramètres x1, x2 et x3. En effet, vu la 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. 1.2.2 Premier problème ======================= Problème 6 [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 ? 1.2.3 Variables d'écart ======================== Problème 7 Est-ce que l'introduction de ces variables change le problème ? 1.2.4 Tableaux =============== Problème 8 [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: n -- \ b =s +/ a x , pour i=1,...,m i i -- ij j j=1 n -- \ z=/ c x -- j j j=1 Ou sous forme matricielle: B =S+ AX z = CX X >= 0 Exemple 1 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 9 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 x_1,s_1,s_2,s_3 sont les variables basiques; {x_1,s_1,s_2,s_3} est la base. x_2,x_3,s_4 sont les variables non basiques. Remarque 10 Terminologie: on utilise dans ce cours les tableaux, plutôt que les dictionnaires utilisés par exemple dans [1]. La différence est minime: on fait juste passer les variables non basiques d'un côté ou de l'autre des équations. D'autre part, on utilise s_1,s_2,s_3,s_4 plutôt que x_4,x_5,x_6,x_7 comme noms pour les variables d'écarts. Voici le dictionnaire correspondant au tableau précédent: x1 = 1 - 3/2 x2 + 1/2 x3 - 1/2 x7 x4 = 2 - 3/2 x2 - 3/2 x3 + 1/2 x7 x5 = 3 - 3/2 x2 - 5/2 x3 - 1/2 x7 x6 = 2 + 4 x2 - 3 x3 + x7 --------------------------------- z = 5 - 5/2 x2 + 11/2 x3 - 5/2 x7 Remarque 11 La caractéristique essentielle d'un tableau est que, connaissant les variables non-basiques, on peut immédiatement calculer les variables basiques et la fonction objective (d'où le terme de dictionnaire). Le calcul devient même immédiat si toutes les variables non-basiques sont nulles. Les équations d'un tableau décrivent un sous-espace affine E de R^n+m. Un point p de cet espace est caractérisé par ses coordonnées dans les variables non-basiques. Exercice 12 Calculer directement le tableau correspondant aux variables non-basiques x_1,s_2,s_3 du programme linéaire Chvatal13. Exercice 13 Soit t_1 et t_2 deux tableaux correspondant au même programme linéaire. Que peut-on dire des deux sous-espaces affine de R^n+m qu'ils définissent ? Chaque choix de variables non-basiques correspond à une base affine de ce sous-espace. Définition 14 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 15 [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 16 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 ? 1.3 Pièges et comment les éviter *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* 1.3.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 1.3.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 S_1,...,S_m les variables basiques, X_1,...,X_n les variables non-basiques, et C_1,...,C_n,z^* les coefficients tels que z=z^*+sumC_iX_i. Par exemple, dans le tableau final du problème6, on a X_1=x_2, X_2=s_1, X_3=s_2, S_1=x_1, S_2=x_3, S_3=s_3, C_1=-3, C_2=-1, C_3=-1 et z^*=13. 1. Si C_i<0, pour tout i, alors la solution basique du tableau, de coordonnées X_1^*=···=X_n^*=0 est l'unique solution optimale. Vérifiez le en prouvant qu'une toute solution faisable quelconque de coordonnées X_1,...,X_n donnant la même valeur z=z^* à la fonction objective est égale à la solution basique du tableau. 2. Si C_i<=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 X_i pour lesquelles on a C_i<0. Les détails sont similaires au 1. 3. Sinon, on peut prendre X_i, variable non-basique avec un coefficient C_i>0. Si les équations du tableau n'imposent pas de limite sur X_i, le système est non borné: la demi-droite décrite par (0,...,0,X_i,0,...,0) pour X_i>=0 est composée de solutions faisables qui donnent des valeurs aussi grandes que voulu à z. 4. Autrement, une des variables basiques S_j tombe à zéro, et on peut faire un pivot entre la variable entrante X_i et la variable sortante S_j. Par construction, la nouvelle solution basique correspond à une solution faisable (0,...,0,X_i,0,...,0) pour un X_i>=0. En particulier le nouveau tableau est faisable, et comme C_i>=0, la constante z^* a augmenté au sens large. Exemple 2 [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. 1.3.3 Terminaison ================== Problème 17 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 3 [1, p. 31] Système cyclant en 6 itérations avec la stratégie: - Choix de la variable entrante avec le coefficient dans l'expression de z le plus fort - Choix de la variable sortante avec le plus petit index 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 ? La méthode des perturbations ---------------------------- L'algorithme du simplexe ne peut cycler qu'en présence de dégénérescence. Problème 18 Comment se débarasser des dégénérescences ? Idée: supprimer les dégénérescences en perturbant légèrement le système! Exemple 4 [1, p. 34,35] On introduit des constantes varepsilon_1>>···>>varepsilon_n. Inconvénient: solution approchée, ou introduction de calcul symbolique La méthode du plus petit index ------------------------------ Théorème 2 L'algorithme du simplexe termine si, lorsqu'il y a ambiguïté sur le choix de la variable entrante ou sortante, on choisit toujours la variable de plus petit index. Cette méthode est simple et élégante. Par contre, elle empêche toute stratégie pour faire converger l'algorithme plus vite. Méthodes intermédiaires ----------------------- Stratégie au choix, mais si z n'augmente pas pendant plus d'un certain nombre d'itérations, on bascule sur la stratégie du plus petit index jusqu'à ce que l'on soit sorti de la dégénérescence. 1.3.4 Initialisation ===================== Pour le moment, l'algorithme du simplexe nécessite de partir d'un tableau faisable. Problème 2 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 P_1: Maximiser: x_1-x_2+x_3 Sous les contraintes: 2x_1-x_2+2x_3<=4 2x_1-3x_2+x_3<=-5 -x_1+x_2-2x_3<=-1 x_1,x_2,x_3>=0 Exemple 6 Introduction d'un système auxiliaire P_0 pour déterminer si P est faisable: Maximiser: -x_0 Sous les contraintes: 2x_1-x_2+2x_3-x_0<=4 2x_1-3x_2+x_3-x_0<=-5 -x_1+x_2-2x_3-x_0<=-1 x_0,x_1,x_2,x_3>=0 Remarques: - P_0 est faisable (prendre x_0 suffisamment grand); - Les solutions faisables de P correspondent aux solutions faisables de P_0 avec x_0=0; - P est faisable si et seulement si P_0 a une solution faisable avec x_0=0. É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 P_0. 3. Le premier tableau pour P_0 est infaisable. 4. Le rendre faisable par un pivot approprié de x_0. 5. Appliquer le simplexe habituel: 1. Si à une étape donnée, x_0 peut sortir de la base, le faire en priorité: En effet, il y a une solution faisable avec x_0=0, et on peut passer en phase II. 2. Si à une étape donnée on atteint une solution optimale: 1. Si x_0 n'est pas basique: Il y a une solution faisable avec x_0=0. On peut donc passer en phase II. 2. Si x_0 est basique et z_0<0: P est infaisable, et on s'arrête. 3. Sinon x_0 est basique et z_0=0: Situation impossible si on fait toujours sortir x_0 en priorité de la base. 6. Tirer de P_0 un tableau faisable pour P; Phase II: 1. Appliquer le simplexe habituel à partir du tableau donné par P_0. Exercice 1 [1, ex 3.9a p. 44] Maximiser 3x_1+x_2 Sous les contraintes: x_1-x_2<=-1 -x_1-x_2<=-3 2x_1+x_2<=4 x_1,x_2>=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]) 1.3.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. 1.4 Efficacité de l'algorithme du simplexe *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* Pour une discussion complète sur ce thème, nous renvoyons au livre de référence [1, 4. How fast is the simplex method], ainsi qu'à l'excellente Foire Aux Questions http://rutcor.rutgers.edu/ mnk/lp-faq.html pour les évolutions récentes. Exercice 2 [1, 4.2 et 4.3, p. 53] 1.5 Le théorème de dualité *=*=*=*=*=*=*=*=*=*=*=*=*=* 1.5.1 Motivation: estimer la valeur optimale de la fonction objective ====================================================================== Exemple 7 Maximiser: z=4x_1+x_2+5x_3+3x_4 Sous les contraintes: x_1-x_2-x_3+3x_4<=1 5x_1+x_2+3x_3+8x_4<=55 -x_1+2x_2+3x_3-5x_4<=3 x_1,x_2,x_3,x_4>=0 Problème 3 Borne inférieure sur la valeur optimale z^*? Borne supérieure sur la valeur optimale z^*? D'après la seconde contrainte: * 25 5 40 275 z <=4x +x +5x +3x <=--x +-x +5x +--x <=--- 1 2 3 4 3 1 3 2 3 3 4 3 En utilisant la somme de la deuxième et troisième contrainte: * z <=4x +3x +6x +3x <=58 1 2 3 4 Problème 4 Comment faire cela de manière systématique ? On recherche des combinaisons linéaires des contraintes: - y_1 fois la première contrainte: x_1-x_2-x_3+3x_4<=1 - y_2 fois la seconde contrainte: 5x_1+x_2+3x_3+8x_4<=55 - y_3 fois la troisième contrainte: -x_1+2x_2+3x_3-5x_4<=3 Ce qui donne: (y +5y -y )x +(-y +y +2y )x +(-y +3y +3y )x +(3y +8y -5y )x 1 2 3 1 1 2 3 2 1 2 3 3 1 2 3 4 <= y +55y +3y 1 2 3 Quelles sont les contraintes pour obtenir une borne sur z^* ? Pour garder le sens des inégalités: y_1,y_2,y_3>=0 Pour obtenir une majoration de z=4x_1+x_2+5x_3+3x_4: y_1+5y_2-y_3>=4 -y_1+y_2+2y_3>=1 -y_1+3y_2+3y_3>=5 3y_1+8y_2-5y_3>=3 Si y_1,y_2,y_3 satisfont ces conditions, on obtient la borne z<= y_1+55y_2+3y_3. On veut donc minimiser y_1+55y_2+3y_3! Par exemple, en prenant y_1=0 et y_2=y_3=1, on retrouve l'inégalité z<=58. 1.5.2 Le problème dual ======================= Définition 4 Soit P un programme linéaire sous forme standard: Maximiser: n -- \ z=/ c x -- j j j=1 Sous les contraintes: n -- \ / a x <= b , pour i=1,...,m -- ij j i j=1 x >=0, pour j=1,...,n j Le dual de P est le problème: Minimiser: m -- \ w=/ b y -- i i i=1 Sous les contraintes: m -- \ / a y >= c , pour j=1,...,n -- ij i j i=1 y >=0, pour i=1,...,m i P est appelé problème primal. Proposition 2 Si x_1,...,x_n est une solution faisable du problème primal et y_1,...,y_m une solution faisable du problème dual, alors z<= w, i.e. n m -- -- \ \ / c x <=/ b y -- j j -- i i j=1 i=1 Proof. Il suffit d'appliquer les inégalités qui définissent les solutions faisables: n n ( m ) m ( n ) m -- -- (-- ) -- (-- ) -- \ \ (\ ) \ (\ ) \ z=/ c x <=/ (/ a y )x =/ (/ a x )y <=/ b y =w -- j j -- (-- ij i) j -- (-- ij j) i -- i i j=1 j=1(i=1 ) i=1(j=1 ) i=1 En particulier: - Si, comme dans l'exemple précédent, on connaît une solution faisable du problème dual, on obtient une borne sur le problème primal et réciproquement! - Si on connaît une solution faisable du problème primal et une solution faisable du problème dual telles que z=w, i.e. n m -- -- \ \ / c x =/ b y , -- j j -- i i j=1 i=1 alors on sait que ces deux solutions sont optimales! Exercice 3 Prouver que les solutions faisables x_1=0 , x_2=14, x_3=0, x_4=5 et y_1=11, y_2=0, y_3=6 du problème original et de son dual sont optimales. La donnée de (y_1,y_2,y_3) donne un certificat de l'optimalité de la solution (x_1,x_2,x_3,x_4): Quelqu'un qui veut faire une vérification peut le faire quasiment sans calcul: il suffit de tester que les solutions sont faisables et que que z=w. Problème 5 Est-il toujours possible de trouver un tel certificat ? La réponse est oui, et c'est le théorème central de la programmation linéaire. 1.5.3 Le théorème de dualité ============================= Théorème 4 Si le problème primal a une solution optimale (x_1^*,...,x_n^*), alors le problème dual a une solution optimale (y_1^*,...,y_m^*) telle que w^*=z^*, i.e. n m -- -- \ * \ * / c x =/ b y . -- j j -- i i j=1 i=1 Ce théorème nous assure de l'existence d'un certificat. Mais y-a-t'il une technique pour le calculer ? Oui, car la preuve va être constructive: son principe va précisément être de construire une solution optimale, en utilisant le tableau final obtenu par l'algorithme du simplexe. Exemple 8 Faisons un peu de magie sur notre exemple. Le tableau initial est: Chvatal54 := [[ x1 - x2 - x3 + 3*x4 <= 1, 5*x1 + x2 + 3*x3 + 8*x4 <= 55, -x1 +2*x2 + 3*x3 - 5*x4 <= 3 ], 4*x1 + x2 + 5*x3 + 3*x4, NonNegative]: t0:=linopt::Transparent(Chvatal54) L'algorithme du simplexe donne comme tableau final: t1:=linopt::Transparent::userstep(t0, slk[1], x4); t2:=linopt::Transparent::userstep(t1, slk[3], x2) Ce calcul donne la solution optimale (x_1^*:=0, x_2^*:=14, x_3^*:=0). Ce calcul donne aussi un certificat, mais pour le vérifier, il faut refaire tout le calcul! Sortons le lapin du chapeau ... La variable y_1 est associée à la première contrainte, qui elle même est associée à la variable d'écart s_1. Hop, on prends pour y_1^* l'opposé du coefficient de s_1 dans l'expression de z dans le tableau final. De même pour y_2^* et y_3^*: * * * y :=11, y :=0, y :=6. 1 2 3 (y_1^*,y_2^*,y_3^*) est une solution faisable du problème dual. Par «miracle», on obtient w^*=z^*. On a donc pu lire le certificat voulu directement sur le tableau final! Voyons maintenant pourquoi cela marche dans le cas général. Proof. Il suffit de construire une solution faisable (y_1^*,...,y_m^*) vérifiant w^*=z^*. On applique l'algorithme du simplexe au problème initial, en introduisant comme d'habitude les variables d'écart s_1,...,s_m. Dans le tableau final, z est de la forme n m -- ---- -- * \ \ z=z +/ c x +/ d s , -- j j -- i i j=1 i=1 où les c_j et d_i sont des coeffs nuls pour les variables basiques, et négatifs pour les autres. On pose comme dans l'exemple: * y :=-d , pour i=1,...,m. i i Il ne reste plus qu'à vérifier que (y_1^*,...,y_m^*) est faisable et donne w^*=z^*. C'est un calcul fastidieux mais direct (surtout sous forme matricielle!) ... Pour une solution quelconque (x_1,...,x_n), on a par définition: n -- \ z=/ c x -- j j j=1 n -- \ s =b -/ a x i i -- ij j j=1 En remplaçant dans l'expression ci-dessus, on obtient n n m n -- -- ---- -- -- \ * \ \ * \ / c x =z +/ c x -/ y (b -/ a x ) -- j j -- j j -- i i -- ij j j=1 j=1 i=1 j=1 n m n m -- -- -- ---- -- \ * \ * \ \ * / c x =z -/ b y +/ ( c +/ a y ) x -- j j -- i i -- j -- ij i j j=1 i=1 j=1 i=1 Cette égalité étant vérifiée quel que soit le choix de (x_1,...,x_n), il doit y avoir égalité des coefficients des x_j de part et d'autre. On en déduit d'une part que n -- * \ * * z =/ b y =w , -- i i j=1 comme voulu, et d'autre part que m -- ---- \ * / a y =c - c >= c , -- ij i j j j i=1 c'est-à-dire que (y_1^*,...,y_m^*) est une solution faisable du problème dual. 1.5.4 Relations entre un problème et son dual ============================================== Proposition 3 Le dual du dual d'un problème P est le problème P lui-même. Exercice 4 Vérifiez-le sur un exemple. Il s'ensuit: Théorème 5 On a les relations suivantes entre un problème P et son dual Q: P admet une solution optimale si et seulement si Q en admet une. Si P est faisable, alors Q est borné; si Q est faisable, alors P est borné. Remarque 3 Un problème et son dual peuvent être simultanément infaisables! Maximiser: 2x_1-x_2 Sous les contraintes: x_1-x_2<=1 -x_1+x_2<=-2 x_1,x_2>=0 Le tableau suivant résume les possibilités (nb: un problème non borné est faisable!) ---------------------------------------------- |primal\dual| optimal |infaisable|non borné | ---------------------------------------------- ---------------------------------------------- | optimal | possible |impossible|impossible| ---------------------------------------------- |infaisable |impossible| possible | possible | ---------------------------------------------- | non borné |impossible| possible |impossible| ---------------------------------------------- 1.5.5 Notations matricielles ============================= Exercice 19 TODO!Introduire les notations matricielles. Vérifier que prendre le dual revient à transposer et à multiplier par -1. En déduire que le dual du dual de P est P. Redémontrer la proposition et le théorème en utilisant les notations matricielles. 1.5.6 Conditions de complémentarité des variables d'écart ========================================================== Problème 6 Supposons que l'on connaisse la solution optimale (x_1^*,...,x_n^*) du problème, mais pas le tableau final dans l'algorithme du simplexe. Peut-on retrouver la solution optimale (y_1^*,...,y_m^*) du problème dual de façon à obtenir un certificat ? Pour voir cela, on va raffiner l'inégalité w>= z sur des solutions x_j et y_i faisables en utilisant les variables d'écart pour mesurer la différence w-z. Exercice 20 On veut introduire des variables d'écart t_i pour le problème dual: Donner une formule raisonable pour t_i. Exprimer w-z en fonction des x_i, y_i, s_i, t_i. Par définition des variables d'écart s_i, on a n -- \ s =b -/ a x , i i -- ij j j=1 et donc n -- \ b =s +/ a x . i i -- ij j j=1 De même, par définition des variables d'écart t_j pour le problème dual, on a m -- \ t =/ a y -c , j -- ij i j i=1 que l'on utilise pour exprimer c_j m -- \ c =/ a y -t . j -- ij i j i=1 En remplaçant dans l'expression de w-z, on obtient m n m m ( n ) n ( m ) n -- -- -- -- (-- ) -- (-- ) -- \ \ \ \ (\ ) \ (\ ) \ w-z=/ b y -/ c x =/ s y +/ (/ a x )y -/ (/ a y )x +/ t x -- i i -- j j -- i i -- (-- ij j) i -- (-- ij i) j -- j j i=1 j=1 i=1 i=1(j=1 ) j=1(i=1 ) j=1 Qui se simplifie en: m n -- -- \ \ w-z=/ s y +/ t x . -- i i -- j j i=1 j=1 Problème 7 Que peut-on déduire de cette égalité ? Théorème 6 (Complémentarité des variables d'écart) Si (x_1^*,...,x_n^*) est solution optimale du problème primal et (y_1^*,...,y_m^*) est solution optimale du problème dual, alors: * * y =0 ou s =0, pour tout i=1,...,m; i i * * x =0 ou t =0, pour tout j=1,...,n. j j Problème 8 Et maintenant ? Comment utiliser ce théorème pour trouver (y_1^*,...,y_m^*)? Exercice 5 [1, p. 64-65] Théorème 7 Si (x_1^*,...,x_n^*) est une solution basique non dégénérée, alors les équations que l'on tire du théorème de complémentarité ont une unique solution. Donc, lorsque la solution optimale du problème est non dégénérée, la technique que l'on a utilisée dans les exercices permet toujours d'obtenir un certificat, pour le prix de la résolution d'un système de m équations linéaires en m variables. 1.5.7 Interprétation géométrique de la dualité =============================================== Exercice 6 Maximiser x_1+x_2 Sous les contraintes 2x_1+x_2<=14 -x_1+x_2<=8 2x_1-x_2<=10 x_1,x_2>=0. Faire une figure dans le plan de la région des solutions faisables. Donner le problème dual. Prendre y_1=y_2=1,y_3=0. Donner l'inégalité sur les x_i correspondante, et représenter la région qu'elle délimite dans le plan. Donner quelques solutions faisables du problème dual. Tracer sur la figure les régions délimitées par les inégalités correspondantes. Calculer la solution optimale du primal et du dual. Les tracer sur la figure. Essayer d'interpréter géométriquement les théorèmes que l'on a rencontrés. 1.5.8 Interprétation économique des variables duales ===================================================== Problème 21 Modèle économique d'une usine dont on veut maximiser le profit. Une papetterie produit et vend différents types de papier: du papier kraft vendu au rouleau, du papier recyclé vendu à la ramette et du papier velin vendu à la feuille. Pour celà, elle dispose en début de mois d'un certain stock de matière première: de l'eau (à l'hectolitre), du chlore (au litre) du bois (à la tonne), du vieux papier (au kilo), des fibres textiles (au ballot). Remplacer les stocks en fin de mois à un certain coût. Chaque type de papier nécessite une certaine proportion de chaque matière première. Par exemple, le chlore sert à blanchir le papier; il n'y en a pas besoin pour le papier kraft; le papier velin est essentiellement produit à partir de bois et de fibres textiles, etc. Le but est de prévoir, pour le mois qui vient, quelle quantité de chaque papier il faut produire pour maximiser le profit de la papetterie. Modéliser ce problème sous forme de programme linéaire sous forme standard. x_j : quantité de produit j fabriquée c_j : prix de vente unitaire du produit j a_ij: quantité de ressource i consommée par unité de produit j fabriquée b_i: limites sur la disponibilité de la ressource i Maximiser: n -- \ z=/ c x -- j j j=1 Sous les contraintes: n -- \ / a x <= b , pour i=1,...,m; -- ij j i j=1 x >=0, pour j=1,...,n. j Quelle dimension (au sens physique) ont les variables x_j , b_i , c_j , a_ij? On voudrait trouver une interprétation pour les variables y_i dans le problème dual. Quelle dimension physique ont-elles ? Qu'est-ce que cela suggère ? Cela suggère que y_i mesure la valeur intrinsèque de la ressource i pour l'usine. Théorème 8 S'il y a au moins une solution optimale (x_1^*,...,x_m^*) non dégénérée, alors il existe varepsilon strictement positif tel que lorsque |t_i|<=varepsilon pour tout i, le programme linéaire relaxé: Maximiser: n -- \ z=/ c x -- j j j=1 Sous les contraintes: n -- \ / a x <= b +t , pour i=1,...,m; -- ij j i i j=1 x >=0, pour j=1,...,n. j a une solution optimale, et la valeur optimale est m -- * \ * z +/ y t -- i i i=1 où z^* est la valeur optimale du problème original et (y_1^*,...,y_m^*) est la solution optimale du dual. Autrement dit, on peut mesurer l'espérance de gain au voisinage d'une solution optimale lorsque l'on relaxe certaines des contraintes: y_i^* décrit le gain que l'usine peut espérer en augmentant la quantité de ressource i disponible. 1.5.9 Problèmes ================ Problème 22 Utiliser le théorème de dualité pour vérifier les solutions des problèmes de programmation linéaire que vous avez résolu jusqu'ici. Problème 23 Un bûcheron a 100 hectares de bois de feuillus. Couper un hectare de bois et laisser la zone se régénérer naturellement coûte 10 kF par hectares, et rapporte 50 kF. Alternativement, couper un hectare de bois, et replanter avec des pins coûte 50 kF par hectares, et rapporte à terme 120 kF. Sachant que le bûcheron n'a que 4000 kF en caisse au début de l'opération, déterminer la meilleure stratégie à adopter et le profit escomptable. Maintenant, le bûcheron a aussi l'option d'emprunter pour augmenter son capital initial, et ce pour un taux d'intérêt total de S% sur la durée de l'opération. Alternativement, il peut décider d'investir son capital dans une autre activité rapportant T% sur la durée de l'opération. Déterminer, selon les valeurs de S et T, la meilleure stratégie à adopter. Problème 24 Pouvez vous interpréter les conditions de complémentarité des variables d'écart en termes économiques ? Problème 25 L'objectif est de démontrer l'un des sens du théorème d'interprétation économique des variables duales. L'autre sens est plus technique, et ne sera pas abordé ici; voir les références pour les détails. Soit z^* la valeur optimale du problème primal et (y_1^*,...,y_m^*) une solution optimale quelconque du problème dual. Montrer que pour toute solution faisable (x_1,...,x_n) du problème primal où l'on a relaxé chaque contrainte i de la quantité t_i, on a n m -- -- \ * \ * / c x <= z +/ y t -- j j -- i i j=1 i=1 Proof. Exprimons le fait que (x_1,...,x_n) est solution faisable du problème avec les contraintes relaxées: n -- \ / a x <= b +t -- ij j i i j=1 Donc: m ( n ) m m m m -- (-- ) -- -- -- -- \ *(\ ) \ * \ * * \ * * \ * / y (/ a x )<=/ y b +/ y t =w +/ y t =z +/ y t -- i(-- ij j) -- i i -- i i -- i i -- i i i=1 (j=1 ) i=1 i=1 i=1 i=1 On a trouvé le terme de droite voulu. Reste à trouver le terme de gauche, ce que l'on fait avec une inversion de somme similaire à celle qui a été utilisée dans les démonstrations précédentes. m ( n ) n ( m ) n -- (-- ) -- (-- ) -- \ *(\ ) \ (\ *) \ / y (/ a x )=/ (/ a y )x >=/ c x -- i(-- ij j) -- (-- ij i) j -- j j i=1 (j=1 ) j=1(i=1 ) j=1 Problème 9 Construire un exemple montrant que la conclusion du théorème est fausse si l'hypothèse de non dégénérescence de la solution optimale est omise. 1.6 Applications *=*=*=*=*=*=*=*=* 1.6.1 Jeux matriciels ====================== Le jeu de Morra --------------- Règles du jeu (pour deux personnes, Louis et Claire). À chaque tour, chaque joueur cache un ou deux pions, et essaye de parier, à voix haute, combien de pions l'autre joueur a caché. Si un seul des joueurs a parié la bonne solution, son score augmente d'autant de point qu'il y a de pions cachés en tout; le score de l'autre joueur diminue du même nombre de points. Sinon, rien ne ce passe. Par exemple, si Claire cache 2 pions et parie 1 tandis que Louis cache 2 pions et parie 2, Louis gagne 4 points et Claire en perds 4. Le but est de trouver une stratégie gagnante. Exercice 26 Jouez! À chaque étape, chaque joueur a le choix entre 4 actions: - [1,1]: Cacher 1 pion, parier 1 pion - [1,2]: Cacher 1 pion, parier 2 pions - [2,1]: Cacher 2 pions, parier 1 pion - [2,2]: Cacher 2 pions, parier 2 pions Chacune de ces options est appelée stratégie pure. Problème 10 Est-ce que suivre une stratégie pure est une stratégie raisonnable ? Quelles autres stratégies ? Exercice 27 Claire et Louis font un long match. Stratégie de Claire: inconnue; elle a joué c_1 fois [1,1], c_2 fois [1,2], c_3 fois [2,1] et c_4 fois [2,2]. Stratégie de Louis: lancer une pièce à chaque tour pour choisir entre [1,2] et [2,1]. Calculer les gains et pertes de Claire et Louis. Résultat: Gain de Louis: (c_1-c_4)/2. Perte moyenne maximale à chaque tour: 1/2. Une stratégie aléatoire de ce type est appellée stratégie mixte. Exercice 28 Généralisation: on suppose que Louis se fixe une stratégie mixte. Caractérisez la meilleure stratégie de contre-attaque de Claire, c'est-à-dire celle qui minimise le gain moyen de Louis. Problème 29 Comment caractériser la meilleure stratégie mixte pour Louis ? Jeux matriciels --------------- Chaque matrice A=(a_ij) définit un jeu. À chaque tour, le joueur par Ligne (Louis) choisit une ligne i parmi les m lignes, et le joueur par Colonnes (Claire) choisit une colonne j parmi les n colonnes. Le gain pour Louis est le coefficient a_ij: - Si a_ij>=0, Louis reçoit a_ij de Claire - Si a_ij<=0, Claire reçoit -a_ij de Louis - Si a_ij=0, il n'y a pas d'échange Exercice 7 Écrire la matrice pour le jeu de Morra. Écrire la matrice pour le jeu papier/ciseaux/caillou/puits. Exercice 30 Dans un long match, Louis adopte une stratégie mixte, en choisissant au hasard la stratégie pure i avec une probabilité fixée x_i. Claire joue selon une stratégie de son choix: à la fin du match, elle a joué c_j fois la stratégie pure j. On note N:=sum_ic_i et y_i:=c_i/N. Calculer le gain moyen par tour pour Louis. Définition 5 Les vecteurs x:=(x_1,...,x_m) et y:=(y_1,...,y_n) sont dit stochastiques: x >=0 et x +···+x =1. i 1 m On considère x:=[x_1,...,x_m] comme un vecteur ligne, et y:=[y_1,...,y_n]^T comme un vecteur colonne, de façon à pouvoir écrire commodément le gain de Louis sous la forme: xAy. Exercice 31 Louis adopte une stratégie mixte donnée. Caractériser le gain au pire pour Louis. Ici, x est constant. Cela peut se mettre sous la forme du programme linéaire en y: min xAy y Si Louis veut une bonne garantie pour maintenir ces gains hauts (ou ses pertes faibles), il peut chercher une stratégie mixte qui maximise la quantité min_y xAy. On appelle une telle stratégie mixte optimale; son gain moyen vaut max min xAy x y Problème 32 Est-ce que la stratégie mixte optimale est la meilleure stratégie ? Comment calculer la stratégie optimale ? Tel quel, le problème ne se met pas sous la forme d'un programme linéaire. On avait vu une astuce pour se débarasser d'un min dans les contraintes; celle ci ne s'applique cependant que lorsque l'on prend le min d'un nombre fini d'expressions, alors qu'ici il y en a a priori autant que de choix de y. Proposition 4 On peut toujours atteindre la quantité min_y xAy avec un y de la forme: (0,...,0,1,0,...,0). Autrement dit: m -- \ min xAy=min/ a x . y j -- ij i i=1 Interprétation ? Proof. Clairement, pour une stratégie pure j donnée: m -- \ min xAy<=/ a x . y -- ij i i=1 Maintenant, supposons que j_0 minimise sum_i=1^ma_ij_0x_i: m m -- -- \ \ / a x >=/ a x pour j=1,...,n. -- ij i -- ij i i=1 i=1 0 Alors, si y:=(y_1,...,y_n) est un vecteur stochastique, on a: n m n ( m ) n ( m ) ( n )( m ) -- -- -- (-- ) -- (-- ) (-- )(-- ) \ \ \ (\ ) \ (\ ) (\ )(\ ) xAy=/ / x a y =/ y (/ a x )>=/ y (/ a x )=(/ y )(/ a x ). -- -- i ij j -- j(-- ij i) -- j(-- ij i) (-- j)(-- ij i) j=1i=1 j=1 (i=1 ) j=1 (i=1 0 ) (j=1 )(i=1 0 ) Donc, comme voulu, m -- \ xAy>=/ a x -- ij i i=1 0 Exercice 33 Formuler le problème de trouver une stratégie mixte optimale pour Louis comme un programme linéaire. Supposons que Claire veuille aussi adopter une stratégie mixte optimale. Formuler de même son problème sous forme de programme linéaire. Théorème 9 (Théorème minimax). Pour toute matrice m× n A, il existe un vecteur stochastique x^* de longueur m, et un vecteur stochastique y^* de longueur n tel que: * * min x Ay=max xAy , y x où le minimum est pris sur tout les vecteurs stochastiques y de longueur n, et le maximum est pris sur tout les vecteurs stochastiques x de longueur m. Interprétation ? Proof. Application immédiate du théorème de dualité. Définition 6 Si A est interprétée comme un jeu, la valeur du jeu est la quantité: * * min x Ay=max xAy . y x Exercice 8 Calculer la valeur du jeu de Morra et du jeu caillou/pierre/ciseaux/puit. D'où vient cette particularité ? Stratégie cachée / stratégie révélée ------------------------------------ Problème 34 Est-ce que révéler sa stratégie à son adversaire, diminue l'espérance de gain? Morra modifié ------------- Il n'est pas très pratique de devoir annoncer simultanément les paris. Problème 35 Est-ce que le jeu est modifié si Claire annonce toujours son pari en premier ? Exercice 9 Faire l'analyse de ce nouveau jeu. Bluff et antibluff ------------------ Jeu de poker avec trois cartes (jeu inventé et analysé par Kuhn en 1950). A et B déposent chacun un pion, puis reçoivent chacun une carte. Ensuite, A peut parier un pion supplémentaire ou passer. De même pour B, puis pour A, jusqu'à ce que: - Un pari est répondu par un passe: celui qui a parié gagne tous les pions; - Un pari est répondu par un pari ou un passe est répondu par un passe: Celui qui a la plus haute carte gagne tous les pions. Exercice 10 Jouez! Étant donné une distribution des cartes, décrire les stratégies pures pour A et B. Décrire toutes les stratégies pures pour A et B. Quelle est la taille de la matrice des gains ? Y-a-t'il des stratégies que l'on peut éliminer d'office ? Au final, on peut obtenir comme matrice de gain: -------------------------- | ||124 |124 |314 |324 | -------------------------- -------------------------- |112|| 0 | 0 |-1/6|-1/6| -------------------------- |113|| 0 |1/6 |1/3 |-1/6| -------------------------- |122||-1/6|-1/6|1/6 |1/6 | -------------------------- |123||-1/6| 0 | 0 |1/6 | -------------------------- |312||1/6 |-1/3| 0 |-1/2| -------------------------- |313||1/6 |-1/6|-1/6|-1/2| -------------------------- |322|| 0 |-1/2|1/3 |-1/6| -------------------------- |323|| 0 |-1/3|1/6 |-1/6| -------------------------- Stratégie mixte pour A: [1/3,0,0,1/2,1/6,0,0,0]; stratégie mixte pour B: [2/3,0,0,1/3]^T. Exercice 11 Prouver que ces stratégies sont optimales. Exercice 12 Lorsque A a la carte 1 en main, calculer en quelles proportions il doit choisir entre les 4 stratégies élémentaires. Résumé de la stratégie de A: - Avec la carte 1: mixer 1 et 3 en proportions 5:1; - Avec la carte 2: mixer 1 et 2 en proportions 1:1; - Avec la carte 3: mixer 2 et 3 en proportions 1:1. Pour A, bluffer ou contre-bluffer est rentable. Résumé de la stratégie de B: - Avec la carte 1: mixer 1 et 3 en proportions 2:1; - Avec la carte 2: mixer 1 et 2 en proportions 2:1; - Avec la carte 3: toujours utiliser 4. Pour B, bluffer est rentable, mais pas contre-bluffer. 1.7 Réseaux de transport *=*=*=*=*=*=*=*=*=*=*=*=* Objectif: étudier une certaine classe de problèmes de programmation linéaire sur laquelle l'algorithme du simplexe prends une forme simple et efficace. 1.7.1 Un exemple d'application =============================== Exemple 9 Considérons le problème de transport d'électricité suivant. Les noeuds sont des villes. Les arcs sont des câbles électriques, à sens unique, reliant les villes. [width=0.75]transport-1 Sources (noeuds avec production): 6: 9 MW; 7: 5 MW Puits (noeuds avec consommation): 3: 6 MW; 4: 6 MW; 5: 2 MW Noeuds intermédiaires (noeuds sans production ni consommation): 1,2 Il y a des pertes en lignes, donc transporter du courant a un coût. On le modélise par un coût par unité de courant transportée sur chaque arc entre la ville i et la ville j. [width=0.75]transport-2 Répartition du flux de courant pour satisfaire la consommation au plus bas coût? Exercice 13 Mettre le problème précédent sous forme de problème de programmation linéaire. Qu'a-t'il de spécifique ? - Consommation et production sont modélisées par des constantes b_i qui représentent la demande. On a pour les puits, b_i>0, pour les sources b_i<0, et pour les noeuds intermédiaires, b_i=0; Attention, sur les graphiques, c'est l'offre qui est représentée! Le signe est inversé! - Le coût de transport unitaire le long d'un arc est modélisé par des constantes c_ij; - On modélise le flux de courant en mesurant par x_ij la quantité de courant transférée directement entre les villes i et j. Remarque 4 Cette modélisation est a priori ambigue: dans le réseau suivant, x_12=1, x_23=1 et x_24=1 peut représenter deux situations différentes: - Transporter une unité de 1 vers 3 via 2, et une unité de 2 vers 4 directement; - Transporter une unité de 1 vers 4 via 2, et une unité de 2 vers 3 directement. [width=0.4]transport-3 Comme le consommateur ne se soucie pas de l'origine du courant (un watt, c'est un watt), et comme le coût dans les deux situations est le même, on peut ignorer cette ambiguïté, et considérer que ces deux situations sont équivalentes. 1.7.2 Problème standard de transport ===================================== Définition 7 Un problème comme le précédent est appelé problème standard de transport. On impose les restrictions suivantes: - La consommation totale est égale à la production totale; - Les arcs sont orientés, avec au plus un arc dans chaque sens; - Le réseau est connexe (cf. ci-dessous). Ces restrictions permettent d'obtenir un algorithme plus simple et élégant. Nous verrons plus tard comment les contourner pour traiter des problèmes plus généraux. Une solution d'un problème de transport peut être modélisé en introduisant pour chaque arc allant du noeud i au noeud j une variable x_ij qui mesure le flux le long de cet arc. Proposition 5 Une solution décrite par les valeurs des x_ij est réalisable (faisable) si et seulement si: - Chaque x_ij est positif (le flux est dans le sens de l'arc); - Pour chaque noeud intermédiaire, le flux entrant est égal au flux sortant; - Pour chaque source, le flux sortant moins le flux entrant est égal à la production; - Pour chaque puit, le flux entrant moins le flux sortant est égal à la consommation; Le seulement si est clair; le si demanderait une vérification pour décider les détails de la réalisation: quel watt venant d'où se retrouve où au final. Les solutions faisables sont donc décrites par un système d'équations de la forme: x +x -x =6. 14 24 45 (ici, il s'agit du sommet 4 dans notre exemple), et d'inégalités du type x_14>=0. Exercice 14 Donner une solution faisable pour notre exemple. Remarque 5 Pour des raisons de conventions, on note n le nombre de noeuds du réseau, et m le nombre d'arcs. C'est l'inverse de ce que l'on avait utilisé pour les problèmes de programmation linéaire généraux ... Définition 8 La matrice d'incidence du réseau est une matrice A de taille n× m. Les lignes sont indexées par les noeuds du réseau, et les colonnes par les arcs. Dans la cellule correspondant à un noeud k et un arc ij, on mets un coefficient valant: - -1 si l'arc part du sommet (i=k), - 1 si l'arc arrive au sommet (j=k), - 0 sinon. Là encore les notations ne sont pas parfaites: une paire ij indexe un arc, et donc une colonne, et non pas une cellule de la matrice... Avec cette notation, et en notant b le vecteur colonne des b_i, x le vecteur colonne des x_ij, et c le vecteur ligne des c_ij on peut mettre le problème sous forme matricielle: Minimiser: cx Sous les contraintes: Ax=b et x>=0. Exercice 15 Écrire sous forme matricielle le problème correspondant à notre réseau: [ ] [ x ] [ 13 ] [ ] [ x ] [ 14 ] [ ] [ x ] [ 15 ] [ ] [ x ] [ 21 ] [ ] [ x ] [ 23 ] [ ] [ x ] [ 24 ] [ ] [ 0 ] [ x ] [ 0 ] [ 25 ] [ 6 ] x:=[ ], b:=[ 6 ] [ x ] [ 2 ] [ 45 ] [ -9 ] [ ] [ -5 ] [ x ] [ 61 ] [ ] [ x ] [ 62 ] [ ] [ x ] [ 63 ] [ ] [ x ] [ 67 ] [ ] [ x ] [ 72 ] [ ] [ x ] [ 75 ] [ -1 -1 -1 1 1 ] [ -1 -1 -1 -1 1 1 ] [ 1 1 1 ] A:=[ 1 1 -1 ] [ 1 1 1 1 ] [ -1 -1 -1 -1 ] [ 1 -1 -1 ] [ ] c:=[ c c c c c c c c c c c c c c ] [ 13 14 15 21 23 24 25 54 61 62 63 67 72 75 ] [ ] c:=[ 48 28 10 7 65 38 7 56 48 108 24 33 19 ] [ ] On peut vérifier que dans l´égalité Ax=b, la quatrième composante donne l'équation x +x -x =6, 14 24 45 correspondant au sommet 4. 1.7.3 Solutions faisables arborescentes ======================================== Définition 9 Quelques classes de graphes classiques: ----------------------------------------- | Chemin | Cycle | ----------------------------------------- | chemin | cycle | ----------------------------------------- ----------------------------------------- | Graphe non connexe |Graphe connexe| ----------------------------------------- | nonconnexe | connexe | ----------------------------------------- ----------------------------------------- |Forêt (graphe acyclique)| Arbre | ----------------------------------------- | foret | arbre | ----------------------------------------- Arbre couvrant du réseau: [width=0.75]transport-arbre-1 Exercice 16 Supposez que seuls les arcs dans l'arbre couvrant précédent peuvent être utilisés. Y-a-t'il une solution ? Est-elle faisable ? Proposition 6 Étant donné un arbre couvrant T, il y a une unique solution de transport pour satisfaire les contraintes de production et consommation en n'utilisant que les arcs de l'arbre couvrant. Formellement, il existe un unique vecteur x:=[x_ij] vérifiant: Ax=b et x =0 pour ij n'appartenant pas à T. ij Définition 10 On appelle une telle solution arborescente. Si de plus le vecteur x vérifie x>=0, c'est une solution arborescente faisable. On dit aussi que l'arbre est faisable. 1.7.4 Algorithme du simplexe pour les réseaux, une motivation ============================================================== économique ========== Exemple 10 Description de l'algorithme sur le réseau précédent. 1.7.5 Démonstration algébrique de l'optimalité =============================================== Soit T un arbre. On note x:=[x_ij] la solution correspondante. Objectif: comparer le coût cx pour la solution x avec le coût cxpour une autre solution faisable x. Soit y:=[y_1,...,y_n] les prix à chaque noeuds pour la solution x. Lors de l'application du simplexe, on a comparé le coût du transport c_ij d'une unité le long de l'arc ij par rapport à la différence de prix y_j-y_i entre les noeuds i et j. On pose c_ij:=c_ij-(y_j-y_i), et c=[c_ij] le vecteur ligne correspondant. Exercice 17 Montrer que c=c-yA. Lemme 1 On a cx=cx+cx. Proof. On va utiliser le résultat de l'exercice pour reformuler le coût de x en fonction de c: --- --- --- ------ --- ------ c x =( c +yA) x = c x +yA x = c x +yb. En particulier, cx=cx+yb. Comme en plus c_ij=0 si ijin T et x_ij=0 si ij¬(in)T, cx=0, on a cx=yb. Conclusion: cx=cx+cx. Théorème 10 Si c_ij>=0 pour tout arc ij, alors la solution x est optimale. Exercice: finissez de le démontrer! Proof. Si x est une autre solution faisable, x_ij>=0. Donc cx=sumc_ijx_ij>=0. 1.7.6 Initialisation ===================== Comment choisir un arbre de départ faisable ? On va, comme pour le simplexe habituel, introduire un problème auxiliaire: 1. Choisir un arbre couvrant T. 2. Calculer la solution x correspondante. 3. Si pour un arc ij de T on a x_ij<0, la solution est infaisable. Ca n'est pas un problème: S'il n'existe pas, on ajoute un arc artificiel ji dans le réseau. On met ji à la place de ij dans T. 4. L'arbre obtenu est faisable dans le réseau modifié. Problème: existe-t'il un arbre faisable dans le réseau modifié n'utilisant pas d'arc artificiel? On prend comme fonction de coût w:=sum_ij artificiel x_ij. De la sorte, si x est une solution faisable du problème original, alors w=0. On applique le simplexe. À la fin, on est dans l'une des situations suivantes: 1. w^*>0: Le problème original est infaisable. 2. w^*=0, et l'arbre final T_1 n'utilise aucun arc artificiel: T_1 est une solution faisable du problème initial, comme voulu. 3. w^*=0, et l'arbre final T_1 utilise au moins un arc artificiel: On a clairement x_ij^*=0 pour tous les arcs artificiels. Comme le réseau est connexe, on peut toujours échanger les arcs artificiels par d'autres arcs non artificiels, sans changer les x_ij^*. 1.7.7 Terminaison et cyclage ============================= Comme dans le cas général, l'algorithme du simplexe pour les réseaux a les propriétés suivantes: - Il peut y avoir des situations dégénérées (pivot ne changeant pas le coût); - L'algorithme peut cycler, mais seulement en présence de dégénérescence; - S'il ne cycle pas, alors il termine; - Il y a des stratégies efficaces pour éviter les cycles. - Même en évitant les cycles, la complexité au pire peut monter jusqu'à 2^n; - Dans la pratique, il ne cycle jamais; la complexité est inférieure à n. Pour les détails, nous renvoyons à [1, Ch. 19]. 1.7.8 Comment contourner les restrictions ? ============================================ Dans les exercices suivants, on cherche à contourner les restrictions sur les problèmes standards de transport. - Arcs orientés - Égalité de la production et de la consommation - Connexité - Au plus un arc dans chaque sens entre deux sommets Exercice 18 Dans les problèmes suivants, on veut répartir au mieux le transport d'oranges via des réseaux ferroviaires, avec les productions et consommations indiquées sur les noeuds, et les coûts de transports indiqués sur les arcs. Pour chacun d'entre eux, indiquer si on peut le modéliser sous forme de problème standard de transport, et si oui, comment. [width=0.75]autoroutes [width=0.75]surproduction [width=0.75]transport-nonconnexe [width=0.75]transport-doublearrete 1.8 Applications du simplexe des problèmes de transports *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* Problème 36 Une usine de barrettes mémoire pour ordinateur doit faire face à une demande fluctuante dans le temps. On suppose que pour l'année à venir, la demande d_j pour chaque mois j est connue à l'avance (cette hypothèse vaut ce qu'elle vaut). Pour adapter la production à la demande, l'usine a le choix entre plusieurs options: - Stocker des barrettes d'un mois sur l'autre, sans limite, mais pour un coût unitaire de a. - Produire, dans la limite de r barrettes par mois, pour un coût unitaire de b. - Surproduire, dans la limite de s barrettes par mois, moyennant un coût unitaire plus élevé c. À la fin de l'année, on veut de plus qu'il n'y ait plus aucun stock, afin de faciliter l'inventaire. Évidemment, l'objectif est d'adapter la production au moindre coût. Modéliser ce problème sous forme de problème de transport standard. 1.8.1 Un problème d'assignement ================================ Exercice 19 Répartition de cours entre plusieurs professeurs. Dans le département de mathématiques d'une université aux USA, l'évaluation des enseignants par les étudiants a donné au cours des derniers semestres les résultats suivants: ------------------------------------------------ | Cours\Professeur |Bill|Yu |Luis|John|Hugh| ------------------------------------------------ ------------------------------------------------ | Calculus 1 | 3 | 4 |2,3 |2,9 |2,8 | ------------------------------------------------ |Differential Equations|2,25|3,2|3,7 |1,9 |4,4 | ------------------------------------------------ | Statistics |2,6 |3,7|4,5 |2.7 |3,1 | ------------------------------------------------ | Calculus 2 |3,9 |4,1|2,6 |3,9 |2,4 | ------------------------------------------------ | Discrete maths |2,8 |2,8|3,5 |3,4 |4,2 | ------------------------------------------------ Dans un semestre, chaque cours est enseigné par un professeur, et chaque professeur enseigne un cours. Le chef du département veut répartir les cours du prochain semestre entre les professeurs de façon à exploiter au mieux leurs talents respectifs (ou minimiser la grogne des étudiants, au choix...). Il décide de prendre comme mesure de la qualité d'une répartition la moyenne sur chaque cours de la note du professeur qui l'enseigne. Modéliser le problème, et indiquer comment on pourrait le résoudre. Problème 11 Est-on sûr d'obtenir une solution entière ? Théorème 11 (dit d'intégralité) Soit P un problème standard de transport où les contraintes sont entières (i.e. les b_i sont entiers). 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. Une solution arborescente pour P a toujours des coefficients entiers! En effet, la matrice d'incidence de l'arbre a des coefficients 1, -1 et 0, et on peut la mettre sous forme triangulaire avec des coefficients 1 et-1 sur la diagonnale. Du coup, lorsque l'on calcule le flux le long des arcs de l'arbre (ce qui revient à inverser la matrice), on obtient uniquement des flux entiers. Le théorème d'intégralité est assez simple. Alors quel est son intérêt ? Le problème précédent est appellé problème d'assignement, et est essentiellement combinatoire (les variables sont discrètes). 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. 1.8.2 Quelques commentaires sur la programmation linéaire en ============================================================= coefficients entiers ==================== Les problèmes de programmation linéaire en entiers (on impose que les solutions soit à coordonnées entières) sont notoirement difficile. Ils sont la plupart du temps NP-complets, et nécessitent la plupart du temps l'utilisation d'algorithme de backtrack (essai-erreur) qui ne sont pas polynomiaux. Par contre, si par chance on peut les mettre sous forme de problèmes standards de transport, le théorème d'intégralité permet de les résoudre par l'algorithme du simplexe. Exemple 11 Un problème de sac-à-dos: On a des objets de différentes tailles l_1,...,l_n et différentes valeurs v_1,...,v_nque l'on veut mettre dans un sac-à-dos de taille l. Évidemment le sac est trop petit, et l'on doit donc faire un choix. Le but est de remplir au maximum le sac-à-dos. Cela peut se mettre sous la forme: Maximiser v=sum_i=1^nx_iv_i, sous les contraintes 0<= x_i<=1, x_i entier. Peut-on le mettre sous forme de problème de transport ? Exemple 12 Le problème d'assignement cours/professeurs. Problème 12 Est-ce que ce ce problème est polynomial ? On note que l'algorithme du simplexe n'est pas polynomial! Par contre, il existe un autre algorithme, dit de l'ellipsoïde, pour résoudre les problème de programmation linéaire qui est polynomial. Il est amusant de constater qu'en pratique il est moins efficace que l'algorithme du simplexe. Nous renvoyons au Chvatal pour une description complète de cet algorithme. Toujours est-il que cela peut permettre de montrer que le problème d'assignement est polynomial. 1.8.3 Combinatoire polyhédrale =============================== Pour des détails sur ce domaine, nous recommandons particulièrement la lecture de l'article sur le sujet dans le handbook of combinatorics. L'idée générale de la combinatoire polyhédrale est la suivante: - On part d'un problème d'optimisation combinatoire du type «maximiser une certaine quantité sur un ensemble discret E» - On le transforme en problème de programmation linéaire, en assignant aux éléments de E des vecteurs, et en considérant le polyhèdre convexe qu'ils engendrent. - Ce convexe peut être décrit par des inégalités (Comment ? c'est l'étape difficile!). - On a alors un problème de programmation linéaire, que l'on peut résoudre. - Si tout ce passe bien, le théorème d'intégralité garantit que la solution trouvée correspond bien à un des vecteurs extrémaux correspondant aux éléments de E. Le théorème de dualité donne alors des relations de type min-max entre des problèmes combinatoires. Théorème de König (lemme des mariages) -------------------------------------- Théorème 12 On a un ensemble de n filles et n garçons que l'on veut marier ensemble. Dans notre grande magnanimité, on veut bien faire attention à ne pas marier deux personnes qui ne se connaissent pas. Si chaque fille connait exactement k>=1 garçons et chaque garçon connaît exactement k filles, alors on peut arranger n mariages de façon à ne pas marier des inconnus. Exercice 20 Prouvez ce théorème en construisant le problème de transport qui va bien. Proof. On associe à chaque fille i une source r_i produisant une unité, et à chaque garçon un puit s_i consommant une unité, et on met un arc entre chaque couple r_i s_i se connaissant. Indépendamment du coût sur les arcs, le problème est faisable: Il suffit de mettre un flux de 1/k sur chaque arc. Le théorème d'intégralité indique alors qu'il y a une solution entière. Cette solution entière donne une façon d'organiser les mariages. Matrices doublement stochastiques --------------------------------- Définition 11 Une matrice X=[x_ij] de taille n× n est doublement stochastique si les coefficients x_ij sont positifs et si la somme des coefficients sur chaque ligne et chaque colonne vaut 1: [ 0,5 0,2 0,3 ] [ 0,01 0,7 0,29 ]. [ 0,49 0,1 0,41 ] X est une matrice de permutation si sur chaque ligne et chaque colonne il y a exactement un 1 et n-1 zéros: [ 0 1 0 ] [ 0 0 1 ]. [ 1 0 0 ] La matrice précédente correspond à la permutation 3,1,2. Clairement une matrice de permutation est une matrice doublement stochastique. Les matrices de permutations sont les matrices doublement stochastiques à coeffs entiers. Exemple 13 Dimension 2: quelles sont les matrices doublement stochastiques ? quelles sont les matrices de permutations ? Théorème 13 (Birkhoff-Von Neumann) Toute matrice doublement stochastique est une combinaison linéaire convexe de matrices de permutations. Exercice 37 Écrire la matrice doublement stochastique ci-dessus comme combinaison linéaire convexe de matrices de permutations. Lemme 2 Pour toute matrice X doublement stochastique, on peut trouver une matrice de permutation Y de façon à ce que si x_ij=0 alors y_ij=0. Exercice 38 Démontrer ce lemme en utilisant un réseau de transport adéquat, et déduisez-en le théorème. 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: graphe 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}: graphe-couverture Exemple 39 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}}: graphe-couplage Exemple 40 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 41 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|. Problème 42 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: biparti Exercice 43 On veut rechercher un couplage maximal du graphe précédent. Montrer comment on peut résoudre ce problème en utilisant un réseau de transport. On peut par exemple introduire le réseau suivant. biparti-reseau Chaque solution entière du réseau correspond à un couplage M du graphe biparti (les arêtes sur lesquelles passent une unité). Le coût de cette solution est 4-|M|. Donc minimiser ce coût revient à rechercher un couplage de taille max. Voilà une solution arborescente optimale du réseau; on a indiqué sur les sommets les prix relatifs, et sur les arêtes les quantités transportées: biparti-reseau-optimal La taille maximale d'un couplage M est donc 3. On remarque que les sommets du graphe biparti de prix 1 à gauche et de prix 0 à droite (en grisé) forment une couverture optimale de taille 3 du graphe biparti. Problème 44 Est-ce une coïncidence? Exercice 45 Soit T une solution arborescente optimale pour le réseau associé à un graphe biparti quelconque. On définit M et C comme ci-dessus. 1. Vérifier que si ij est une arête du graphe biparti, et si i¬(in)C, alors jin C. 2. En déduire que C est une couverture du graphe biparti. 3. Vérifier que si i est dans C, alors i appartient à une des arêtes du couplage M. 4. Vérifier que si ij est une des arêtes du couplage M, alors i et j ne sont pas simultanément dans C. 5. En déduire que |M|=|C|. Théorème 46 (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 clairement reliés a priori. 1.9 Problèmes de transports avec limites de capacités *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*= Exemple 14 Modéliser un réseau routier par un réseau de transport sous forme standard n'est pas très réaliste: sur une autoroute donnée, on ne peut pas faire passer autant de camions que l'on veut ! Dans cette section, nous allons regarder une généralisation des problèmes de transports, dans lesquels on ajoutera des contraintes de capacités maximales. Nous verrons rapidement que l'algorithme du simplexe et les résultats théoriques en découlant peuvent être étendus sans grosses difficultés. Puis nous étudierons quelques applications. Définition 12 Problème de transport avec limites de capacités sous forme standard: Minimiser: cx Sous les contraintes: Ax=b et 0<= x<= u, où A est la matrice d'incidence d'un réseau. (u pour upper bound). Exercice 21 Peut-on mettre le problème suivant sous forme standard ? Minimiser: cx Sous les contraintes: Ax=b et l<= x<= u. Exercice 22 Donner une solution optimale pour le problème suivant: [width=0.75]transport-cycle. Comme on peut le constater dans l'exercice précédent, on ne peut pas toujours espérer trouver une solution optimale, ni même une solution faisable arborescente: c'est-à-dire telle qu'on utilise aucune arête en dehors d'un certain arbre T. On va donc relâcher cette contrainte. Toute arête en dehors de l'arbre T devra être soit non utilisée, soit au contraire utilisée à pleine capacité: Définition 13 Soit T un arbre couvrant du réseau. Une solution x est T-arborescente si tout arc ij¬(in)T on a: x =0 ou x =u . ij ij ij Une solution x est arborescente s'il existe un arbre couvrant T tel que x est T-arborescente. Exercice 23 Donner une solution arborescente au problème précédent. Exercice 24 Étant donné un arbre T, a-t'on unicité de la solution arborescente vis-à-vis de cet arbre ? Exercice 25 Montrer que si les b_i et les u_ij sont entiers, alors toute solution arborescente est entière. Nous allons maintenant voir sur un exemple comment on peut adapter l'algorithme du simplexe pour les réseaux. Dans le cas classique (sans limites de capacités), le principe était de faire rentrer dans l'arbre T une arête ij inutilisée (x_ij=0) rentable (y_i+c_ijy_j), de façon à pouvoir diminuer son utilisation. Exemple 47 Cf. [1, p.356-359]. Théorème 14 Soit x une solution T-arborescente telle que pour toute arête ij en dehors de l'arbre, on ait: - soit x_ij=0 et y_i+c_ij>= y_j, - soit x_ij=u_ij et y_i+c_ij<= y_j. Alors x est une solution optimale. Proof. La démonstration est très similaire à celle du cas sans limites de capacités. On va considérer une autre solution faisable x du problème, et comparer les coûts cx et cx correspondants. On pose c_ij:=c_ij-(y_j-y_i), et c=[c_ij] le vecteur ligne correspondant. c_ij mesure le coût relatif: - c_ij=0 si ij est dans T - c_ij>=0 si x_ij=0 (non rentable d'utiliser l'arc ij). - c_ij<=0 si x_ij=u_ij (rentable d'utiliser l'arc ij à pleine capacité). On note que dans les trois cas, c_ijx_ij>=c_ijx_ij. Donc matriciellement cx>=cx. Comme précédemment on peut écrire c matriciellement sous la forme c=c-yA. De plus, x et x sont solutions faisables et vérifient donc toutes deux Ax=b. On en déduit alors: --- ------ --- ------ --- --- c x = c x +yA x = c x +yb>= c x+yb= c x+yAx=cx. 1.10 Problèmes de flot maximum *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* 1.10.1 Introduction ==================== Définition 14 Problème de flot max: - Réseau avec source et puits - Pas de coûts sur les arcs - Contraintes de capacités sur les arcs - Production et consommation nulle sur chaque noeud intermédiaire [width=0.75]flot Objectif: Maximiser le volume du flot, c'est-à-dire la quantité transportée entre s et p. Exemple 15 Un dimanche soir, maximiser le nombre de voitures allant d'Albertville à Lyon, en les répartissant entre les différentes routes possibles. Exercice 26 Mettre le problème de flot dessiné ci-dessus sous forme de problème de transport standard avec limites de capacités Clairement, cela se généralise à tout problème de flot max. Problème 13 Que peut-on en déduire ? - On a un algorithme de résolution (simplexe) - Le problème de flot est polynomial - On a un théorème d'intégralité: Si les contraintes de capacités sont entières (ou infinies), alors: - Soit le problème est non borné: flot-nonborne - Soit le problème a une solution entière - On doit bien avoir une dualité ! 1.10.2 Dualité: le théorème flot max / coupe min ================================================= Définition 15 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 16 Dans notre réseau, la coupe C={s} est de capacité 5. [width=0.75]flot Exercice 27 Quelle est la capacité de la coupe C={s,i_2,i_3}? Que peut-on en déduire sur la valeur d'un flot ? Proposition 7 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|. Problème 14 Que peut on espérer avoir ? Une dualité et un théorème min-max, bien-sûr! Théorème 15 (Coupe min-Flot max) Dans un réseau, le volume maximal d'un flot est égal à la capacité minimale d'une coupe. Exercice 28 Vérifiez-le dans notre exemple. Proof. On considère une solution F optimale du problème de flot obtenue avec le simplexe pour les réseaux avec limites de capacité. [width=0.75]flot-reseau On calcule les valeurs y_i en chaque sommets. Les coûts sont de 0 partout sauf sur l'arc ps, où le coût est de -1. Donc la valeur de y_i est: - 0 si i est relié à s dans T, - 1 si i est relié à t dans T. On prend comme coupe C l'ensemble des sommets i avec y_i=0. Chaque arc ij sortant de C est «rentable» puisque y_i+c_ij=0<1=y_j. Or, ij n'est pas dans l'arbre, et le flot est optimal. Donc ij doit être utilisé à pleine capacité: x_ij=u_ij. De même, tout arc ij entrant est non rentable, et n'est donc pas utilisé: x_ij=0. Conclusion: Le volume du flot F est égal à la capacité de la coupe C: -- -- -- | | \ \ \ | | |F|= / x - / x = / u =|C|. | | -- ij -- ij -- ij | | ij sortant ij entrant ij sortant Remarque 6 Il y a quelques boulons à serrer. 1. Le simplexe pourrait terminer en indiquant que le problème est non borné: i.e. il existe des flots de volume aussi grand que l'on veut: [width=0.5]flot-reseau-nonborne Dans ce cas, il ne peut pas y avoir de coupe de capacité finie. Donc le théorème reste valide. 2. Le simplexe pourrait indiquer que le problème est non faisable. En fait, non, puisque x_ij=0, forall x_ij est solution. 3. Si le flot max est de volume 0, il se pourrait que l'arbre ne contienne pas l'arc ps. Du coup, l'ensemble des sommets i tels que y_i=0 ne serait pas forcément une coupe. Un tel cas correspond en fait à une solution dégénérée qui est arborescente vis-à-vis de plusieurs arbres. En fait, en faisant un pivot convenable, on peut toujours remettre ps dans l'arbre. 1.10.3 Applications ==================== On a vu que les problèmes de flots était un cas particulier des problèmes de transport avec limites de capacités. Quel est donc l'intérêt de considérer les problèmes de flots ? On a un algorithme (méthode du chemin augmentant) plus rapide que le simplexe. Trouver une solution faisable dans un problème de transport avec limites ------------------------------------------------------------------------ de capacités ------------ Exemple 17 On prend le problème de transport suivant, et on se demande s'il est faisable. [width=0.75]flot-transportfaisable On peut le transformer en problème de flot, en oubliant les coûts, et en rajoutant une source, reliée convenablement aux producteurs, et un puits, relié convenablement aux consommateurs: [width=0.75]flot-transportfaisable2 S'il existe un flot de volume 8, les arcs reliant s aux producteurs seront utilisés à pleine capacité, et de même pour les arcs reliant les consommateurs à t. Cela simule exactement les productions et consommations escomptées, donc le problème de réseau d'origine est faisable. La réciproque est aussi clairement vraie: si le problème est faisable, alors il existe un flot de volume 8. Dans notre cas, on en déduit que le problème n'est pas faisable. En effet, on peut trouver une coupe de capacité 7. De manière générale, on peut toujours transformer un problème de transport avec limite de capacité en un problème de flot, de façon à déterminer s'il est faisable. Cela donne un algorithme plus rapide que le simplexe pour la phase I de la résolution. Couplages dans les graphes bipartis ----------------------------------- Exercice 29 Mettre sous forme de problème de flot le problème de rechercher un couplage max dans le graphe biparti suivant. Problème des mines à ciel ouvert -------------------------------- Problème 15 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 P_i que l'on peut escompter de son traitement. Au final, on associe à chaque bloc i la quantité w_i=C_i-P_i. Si l'on ne considère pas les autres blocs, il est rentable de creuser i si et seulement si w_i<0. On veut déterminer quels blocs on doit creuser pour maximiser le profit total -sum_iw_i (ou autrement dit minimiser sum_iw_i). 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 c. En l'occurence, voici tous les enchaînements possibles: a-> c, a-> d, a-> f, a-> g, b-> c, b-> g, d-> g, e-> f, e-> g. - Combien faut-il de guides au minimum dans cet exemple ? - Comment trouver le nombre minimum de guides nécessaires dans le cas général ? Définition 16 Soit P=(E,<) un ordre partiel. Une chaîne C de P est un ensemble de sommets de P deux à-deux comparables: xin C et yin C => x0 si l'arc ij est dans le sens inverse du réseau. À 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 10 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. flot-mauvais 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. 1.11 Méthodes alternatives au simplexe *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* Pour conclure ce chapitre sur la programmation linéaire, nous présentons rapidement quelques méthodes alternatives qui ont été développées pour résoudre les problèmes de programmation linéaire généraux. Nous nous contentons d'évoquer leur principe, leurs avantages et inconvénients, et donnons des références pour ceux qui voudraient en savoir plus. 1.11.1 Méthode de l'ellipsoïde =============================== Principe On commence par utiliser la dualité pour se ramener à la recherche d'une solution faisable d'un système d'inéquations linéaires. On peut en fait se ramener par une perturbation convenable à la recherche d'une solution faisable d'un système d'inéquations linéaires strictes! Si un tel système est faisable, le volume de l'ensemble des solutions peut alors être minoré par une quantité V qui dépends de la dimension de l'espace, et de la taille des coefficients dans le système linéaire. On part d'un ellipsoïde E suffisamment gros pour contenir toutes les solutions faisables. Si le centre de E est une solution faisable, on a terminé. Sinon, on peut couper l'ellipsoïde en deux, et inclure ce demi-ellispoïde dans un ellipsoïde E' qui contient encore toutes les solutions faisables. On réitère avec E:=E'. À chaque itération, on a V(E')