Optimisation linéaire théorie et algorithme du simplexe

Optimisation linéaire théorie et algorithme du
simplexe

 Le problème à résoudre

Un problème d’optimisation linéaire (OL) est un problème d’optimisation dans lequel le critère et les fonctions définissant les contraintes sont linéaires (on devrait dire affines) ; il s’agit donc de minimiser une fonction linéaire sur un polyèdre convexe. Comme nous le verrons, la formulation suivante du problème est tout à fait générale. Il s’agit de trouver la solution x ∈ R n du problème (PL)    infx c Tx Ax = b x > 0. (17.1) Un problème d’optimisation linéaire écrit de cette manière est dit sous forme standard. On appelle critère du problème, la fonction linéaire x 7→ c Tx. Les données dans (PL) sont deux vecteurs c ∈ R n (appelé coût du problème) et b ∈ R m (en général m 6 n), et une matrice A de dimension m × n. La contrainte d’inégalité x > 0 veut dire que toutes les composantes de x doivent être positives : xi > 0 pour tout i ∈ [1 : n]. On notera x > 0, lorsque toutes les composantes de x seront strictement positives. L’ensemble R n + = {x ∈ R n : x > 0} est appelé l’orthant positif de R n. On rappelle que l’on dit que le problème (PL) est réalisable si son ensemble admissible Fp := {x ∈ R n : Ax = b, x > 0} est non vide. Un point de Fp est dit admissible. On dit que (PL) est borné si la valeur optimale de (PL) est finie. Dans ce chapitre, nous allons étudier le problème (PL) (structure et propriétés) et donner un algorithme pour le résoudre : l’algorithme du simplexe. Les algorithmes de points intérieurs seront décrits et étudiés au chapitre 18. Remarquons déjà que le problème (PL) n’est « intéressant », c’est-à-dire qu’il mérite une étude approfondie, que par la présence des contraintes d’inégalité. En effet, sans ces contraintes le problème se réduit à deux cas complémentaires triviaux. Si c ∈ N (A) ⊥, tout point x vérifiant Ax = b est solution. Si c /∈ N (A) ⊥, il existe une direction d telle que Ad = 0 et c Td < 0 et donc c T(x + td) → −∞ lorsque t → +∞ : si le problème est réalisable (en l’occurrence, il existe un x tel que Ax = b), il n’est pas borné. En ce qui concerne les algorithmes de résolution de (PL), on distingue deux classes principales de méthodes. Les méthodes de points-frontière génèrent des itérés sur la frontière de l’ensemble admissible Fp. La méthode typique de cette classe est l’algorithme du simplexe, introduit par Dantzig en 1947 [153 ; 1951] ; il consiste à faire des déplacements le long des arêtes du polyèdre convexe Fp ; nous le présenterons et l’étudierons à la section 17.4. Cet algorithme n’est pas polynomial dans le pire des cas, bien qu’il soit polynomial en moyenne et en perturbations moyennées (section 17.4.5). Les méthodes de points intérieurs, développées à partir des travaux de Karmarkar [346 ; 1984], génèrent des itérés dans l’intérieur relatif de l’ensemble admissible Fp. Ces méthodes peuvent être polynomiales et sont particulièrement intéressantes lorsqu’il y a beaucoup de contraintes d’inégalité, parce qu’elles ne ressentent pas l’irrégularité du bord de l’ensemble admissible. Nous présenterons et étudierons quelques algorithmes de points intérieurs au chapitre 18. 

Exemples : problèmes d’optimisation dans des réseaux

Un réseau n’est pas autre chose qu’un graphe (orienté ou non), c’est-à-dire une collection de nœuds et d’arcs qui relient ces nœuds. Disons qu’il y a m nœuds, indicés par i = 1, . . . , m, et n arcs, indicés par j = 1, . . . , n. Ces derniers peuvent aussi être spécifiés par des couples (ordonnés ou non, suivant que le graphe est ou n’est pas orienté) formés des nœuds qu’ils relient : l’arc (i1, i2) relie les nœuds i1 et i2. Dans la discussion qui suit, le réseau est supposé être utilisé comme support à l’acheminement d’un produit (eau, gaz, électricité, voitures, trains, avions, télécommunications, messages internet, quantité abstraite, etc). La quantité de produit qui transite par l’arc j est notée xj . Il est normal de supposer que c’est une grandeur positive. L’équilibre du réseau s’exprime en écrivant que la quantité de produit qui sort du nœud i est égale à la quantité qui y entre plus la quantité bi qui y est produite (« loi de Kirchhoff »). Pour tout i, on doit avoir X j : arc sortant du nœud i xj = X j : arc entrant du nœud i xj + bi . (17.2) La quantité bi produite au nœud i peut représenter ce qui y est apporté (auquel cas bi > 0) ou ce qui y est consommé ou demandé (auquel cas bi < 0). Les équations précédentes s’écrivent sous forme matricielle : Ax = b et x > 0,où la matrice A est appelée la matrice d’incidence du réseau. Cette matrice peut avoir des dimensions considérables en pratique, mais elle est très creuse puisqu’elle n’a que deux éléments non nuls par colonne. En effet, au vu de (17.2), la colonne j associée à l’arc j contient Aij = +1 si i est le nœud d’origine de l’arc j, Aij = −1 si i est le nœud de destination de l’arc j et Aij = 0 dans les autres cas. En particulier, la somme des lignes de A est nulle, ce qui implique que A n’est pas surjective. Ceci peut poser des difficultés algorithmiques et requiert au moins une condition de compatibilité sur b, à savoir b ∈ R(A), ce qui conduit à Xm i=1 bi = 0. (17.4) On montre cependant que A est de rang m − 1 lorsque le graphe associé au réseau est connexe, ce qui veut dire que deux nœuds distincts i et i ′ peuvent être reliés par une chemin (une suite d’arcs (i1, i2), (i2, i3), . . . , (ip−1, ip), avec i1 = i et ip = i ′ ) ; voir [57] par exemple. Un exemple de problème d’optimisation linéaire classique dans les réseaux est le problème du transport à coût minimal. On cherche à acheminer des produits identiques depuis certains nœuds d’origine (disons pour i ∈ O) jusqu’à des nœuds de destination (disons pour i ∈ D, avec O ∩ D = ∅). Ceci s’exprime par le positionnement des composantes de b aux valeurs désirées : bO > 0, bD < 0 et bi = 0 si i /∈ O ∪ D, tout en respectant (17.4). D’autre part, en supposant que le coût de transport sur chaque arc est linéaire en xj (coût cj par unité transportée), le coût total du transport sera Xn j=1 cjxj = c Tx. C’est la quantité que l’on cherche à minimiser. On reconnaît dans la minimisation de ce critère sous les contraintes de réseau (17.3), le problème d’optimisation linéaire sous forme standard (PL). Un autre exemple de problème d’optimisation linéaire classique et celui du plus court chemin dans un graphe. C’est un cas particulier du problème précédent : bi0 = +1 au nœud de départ i0, bi1 = −1 au nœud d’arrivée i1 et les autres bi sont nuls, tandis que cj > 0 donne la longueur du chemin représenté par l’arc j. Si x¯ est la solution du problème, x¯j = 0 signifie que l’on ne passe pas par l’arc j et x¯j = 1 signifie que l’on y passe. On peut avoir des valeurs entre 0 et 1 si le problème a plusieurs solutions.