Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan Gerard LAIC (Université d’Auvergne) gerard@laic.u-clermont1.fr

  • View
    103

  • Download
    1

Embed Size (px)

Text of Programmation linéaire, polarité et lancer de rayons (la programmation linéaire autrement) Yan...

  • Page 1
  • Programmation linaire, polarit et lancer de rayons (la programmation linaire autrement) Yan Gerard LAIC (Universit dAuvergne) gerard@laic.u-clermont1.fr
  • Page 2
  • Une escroquerie Un imposteur: Une escroquerie : Vous vendre la thorie bien connue de la Programmation Linaire sous une forme diffrente (ni expert en Programmation Linaire ni expert en Gomtrie Algorithmique) Y.G (plus gomtrique)
  • Page 3
  • Escroc sans le savoir ? Reconnaissance de morceaux de plans discrets Donnes: une partie finie S de Z 3 Rponse la question: S appartient-elle un plan discret ? = ?
  • Page 4
  • = ? Escroquerie: vendre la Programmation Linaire sous une forme mconnaissable Escroc sans le savoir ?
  • Page 5
  • A) Programmation Linaire Plan de lexpos 1 Introduction 2 Lemme de Farkas 3 Gomtrie des solutions B) Lancer de Rayon 4 Problmes de Lancer de Rayon 5 Algorithmes de Lancer de Rayon
  • Page 6
  • A) Programmation Linaire 1 Introduction 2 Lemme de Farkas 3 Gomtrie des solutions
  • Page 7
  • 1 Introduction
  • Page 8
  • 1.1 Bref rappel: Quest-ce quun programme linaire ? Lobjectif de la programmation linaire est de rsoudre des systmes dingalits linaires 2 x 1 - 3 x 2 + 4 x 3 6 et de trouver une solution x R d (si il en existe) pour laquelle une forme linaire donne c.x (c R d ) ait une valeur maximale. Exemple : 1 x 1 - 2 x 3 4 4 x 1 + x 3 -5 - x 1 +2 x 2 + x 3 -1 - 3 x 2 0 Exemple :Maximiser x 1 + 4 x 2 1 Introduction
  • Page 9
  • Donnes :- Des ingalits linaires dans R d a 1 x 1 +a 2 x 2 ++ a j x j ++a d x d a d+1 - Une forme linaire de R d c.x o c R d (non nul) Questions : Existe-t-il une solutions aux ingalits? Si oui, trouver une solution telle que c.x soit maximal Si un programme linaire a des solutions, il est dit ralisable. Vocabulaire: Un programme linaire est donc un problme doptimisation de la forme suivante: Algorithmes de rsolution: simplex (Dantzig 1947), lellipsode (Khachiyan 1979) polynomial - points intrieurs (Kamarkar 1984)
  • Page 10
  • 1.2 Une ingalit linaire un point 2 x 1 - 3 x 2 + 4 x 3 6 Exemple : 1 x 1 - 2 x 3 4 4 x 1 + x 3 -5 - x 1 +2 x 2 + x 3 -1 - 3 x 2 0 (2,- 3, 4, 6) (1, 0, -2, 4) (0, 4, 1, -5) (-1, 2, 1,-1) (0,- 3, 0, 0) On formalise lidentification ingalit linaire/point en introduisant la relation binaire # : Soient a R d+1 et b R d, la relation a # b est satisfaite a 1 b 1 +a 2 b 2 ++ a j b j ++a d b d a d+1 Notation: Exemple : Lingalit linaire 2 x 1 - 3 x 2 + 4 x 3 6 est note (2, -3, 4, 6) # x Lingalit linairea 1 x 1 +a 2 x 2 ++ a j x j ++a d x d a d+1 se note donc simplement a # x o a R d+1.
  • Page 11
  • 1.3 Les demi-droites True et False Il y a certains points a R d+1 pour lesquels lingalit linaire a # x a la proprit dtre toujours vraie ou toujours fausse, indpendamment du point x R d considr. Prenons le point (0,0,,0,1) R d+1, lingalit linaire (0,0,,0,1) # x est 0 x 1 +0 x 2 ++ 0 x j ++0 x d 1 soit 0 1 Elle est toujours vraie. Cette proprit stend tous les points a R d+1 dont les d premires coordonnes sont nulles et la dernire a d+1 est positive (a d+1 0). La demi-droite True
  • Page 12
  • Prenons le point (0,0,,0,1) R d+1, lingalit linaire (0,0,,0,1) # x est 0 x 1 +0 x 2 ++ 0 x j ++0 x d 1 soit 0 1 Elle est toujours vraie. Cette proprit stend tous les points a R d+1 dont les d premires coordonnes sont nulles et la dernire a d+1 est positive (a d+1 0). La demi-droite True
  • Page 13
  • Par construction, lingalit a # x est toujours vraie ssi a True. Il sagit de la demi-droite [O,x d+1 [ quon notera dsormais True. Prenons le point (0,0,,0,1) R d+1, lingalit linaire (0,0,,0,1) # x est 0 x 1 +0 x 2 ++ 0 x j ++0 x d 1 soit 0 1 Elle est toujours vraie. Cette proprit stend tous les points a R d+1 dont les d premires coordonnes sont nulles et la dernire a d+1 est positive (a d+1 0). La demi-droite True
  • Page 14
  • On sintresse aux inquations linaires qui sont toujours fausses: Prenons par exemple linquation linaire (0,0,,0,-1) # x. 0 x 1 +0 x 2 ++ 0 x j ++0 x d -1 soit 0 -1 Elle scrit Dune manire gnrale, linquation a # x est toujours fausse ( indpendamment de x ) ssi a est dans la demi droite ]O, - x d+1 [. Cette demi-droite (ouverte) est appele False. La demi-droite False
  • Page 15
  • 1.4 Un systme dingalits linaires un ensemble de points La relation binaire # dfinie sur les paires de points stend facilement aux paires densembles de points soient A C R d+1 et B C R d, la relation A # B est satisfaite si et seulement si pour tout lment a A et b B, on a a # b. Le systme dingalits linaires se note simplement A # x o A est une partie de R d+1. a 1,1 x 1 +a 1,2 x 2 ++ a 1,j x j ++a 1,d x d a 1,d+1 a 2,1 x 1 +a 2,2 x 2 ++ a 2,j x j ++a 2,d x d a 2,d+1 a i,1 x 1 +a i,2 x 2 ++ a i,j x j ++a i,d x d a i,d+1 a n,1 x 1 +a n,2 x 2 ++ a n,j x j ++a n,d x d a n,d+1
  • Page 16
  • Le systme dingalits linaires se note simplement A # x o A est une partie de R d+1. a 1,1 x 1 +a 1,2 x 2 ++ a 1,j x j ++a 1,d x d a 1,d+1 a 2,1 x 1 +a 2,2 x 2 ++ a 2,j x j ++a 2,d x d a 2,d+1 a i,1 x 1 +a i,2 x 2 ++ a i,j x j ++a i,d x d a i,d+1 a n,1 x 1 +a n,2 x 2 ++ a n,j x j ++a n,d x d a n,d+1
  • Page 17
  • Le systme dingalits linaires se note simplement A # x o A est une partie de R d+1. a 1,1 x 1 +a 1,2 x 2 ++ a 1,j x j ++a 1,d x d a 1,d+1 a 2,1 x 1 +a 2,2 x 2 ++ a 2,j x j ++a 2,d x d a 2,d+1 a i,1 x 1 +a i,2 x 2 ++ a i,j x j ++a i,d x d a i,d+1 a n,1 x 1 +a n,2 x 2 ++ a n,j x j ++a n,d x d a n,d+1 2 x 1 - 3 x 2 + 4 x 3 6 Exemple : 1 x 1 - 2 x 3 4 4 x 1 + x 3 -5 - x 1 +2 x 2 + x 3 -1 - 3 x 2 0 Le systme dingalits linaires se note simplement A # x o A = { (2,-3,4,6), (0,-3,0,0), (1,0,-2,4), (0,4,1,-5), (-1,2,1,-1) }.
  • Page 18
  • 2 x 1 - 3 x 2 + 4 x 3 6 Exemple : 1 x 1 - 2 x 3 4 4 x 1 + x 3 -5 - x 1 +2 x 2 + x 3 -1 - 3 x 2 0 Le systme dingalits linaires se note simplement A # x o A = { (2,-3,4,6), (0,-3,0,0), (1,0,-2,4), (0,4,1,-5), (-1,2,1,-1) }.
  • Page 19
  • A est un ensemble de points. Le fait que le systme dingalits linaires A # x soit ou non ralisable a-t-il une interprtation gomtrique sur A ? 2 x 1 - 3 x 2 + 4 x 3 6 Exemple : 1 x 1 - 2 x 3 4 4 x 1 + x 3 -5 - x 1 +2 x 2 + x 3 -1 - 3 x 2 0 Le systme dingalits linaires se note simplement A # x o A = { (2,-3,4,6), (0,-3,0,0), (1,0,-2,4), (0,4,1,-5), (-1,2,1,-1) }. Peut-on caractriser gomtriquement les ensembles A dont le systme dingalits linaires A # x est ralisable ?
  • Page 20
  • Page 21
  • 2 Lemme de Farkas En Programmation Linaire, les lemmes qui caractrisent les systmes dingalits linaires ralisables sont appels lemmes de Farkas. Un systme dingalits linaires est ralisable si et seulement si aucune combinaison linaire coefficients positifs des ingalits nest aberrante ( 0 -1 ). 2.1 Lemme de Farkas standard Peut-on caractriser gomtriquement les ensembles A dont le systme dingalits linaires A # x est ralisable ?
  • Page 22
  • 2.2 Hauteur dans R d+1 On considre que la coordonne verticale est la dernire: x d+1 On prend lintersection de lenveloppe convexe de A et de laxe vertical Ox d+1. - Si lintersection est vide, par convention la hauteur de A est + - Sinon, cest la borne infrieure des coordonnes x d+1 des points de lintersection.
  • Page 23
  • 2.3 Lemme de Farkas gomtrique Le systme A # x (o A est une partie de R d+1 ) est ralisable ssi la hauteur de A est positive ( hauteur(A) 0 ). hauteur(A)