Scribd
Importer
43 vues2 pages

CoursPontsRO 55 56

Le chapitre traite de la programmation linéaire, en illustrant un exemple simple avec deux variables, mais souligne que les problèmes réels peuvent impliquer des milliers de variables et de contraintes. Il présente les algorithmes du simplexe et des points intérieurs, ainsi que leur utilisation dans des logiciels pour résoudre des programmes linéaires. Enfin, il aborde les formes standard et canonique des programmes linéaires, en précisant leur équivalence et les méthodes de conversion entre elles.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
43 vues2 pages

CoursPontsRO 55 56

Le chapitre traite de la programmation linéaire, en illustrant un exemple simple avec deux variables, mais souligne que les problèmes réels peuvent impliquer des milliers de variables et de contraintes. Il présente les algorithmes du simplexe et des points intérieurs, ainsi que leur utilisation dans des logiciels pour résoudre des programmes linéaires. Enfin, il aborde les formes standard et canonique des programmes linéaires, en précisant leur équivalence et les méthodes de conversion entre elles.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

49 CHAPITRE 4.

PROGRAMMATION LINÉAIRE

P = {(x, y) : 2x + y ≤ 8, x + 2y ≤ 7, y ≤ 3, x ≥ 0, y ≥ 0}

y=3

x
x + 2y = 7

2x + y = 8

Figure 4.1 – Représentation graphique des contraintes du problème des navets et des courgettes.

Dans l’exemple des navets et des courgettes, nous avons pu résoudre le problème assez
facilement car il n’y avait que 2 variables, et donc une représentation graphique était possible.
Mais la plupart des problèmes réels le nombre de variables et le nombre de contraintes
peuvent dépasser le millier, et ni l’intuition, ni le dessin peuvent alors nous tirer d’affaire.
Heureusement, depuis la fin des années 40, de nombreux chercheurs ont travaillé sur la
programmation linéaire, et c’est maintenant un problème qui est bien résolu tant sur le plan
pratique que sur le plan théorique.
Plan pratique De nombreux logiciels (libres et commerciaux) résolvent des programmes
linéaires de grande taille. Voir la liste en annexe du polycopié. Il y a principalement deux
algorithmes qui sont utilisés dans ces codes : l’algorithme du simplexe et l’algorithme
des points intérieurs. On devrait plutôt parler de familles d’algorithmes car tant l’algo-
rithme du simplexe que l’algorithme des points intérieurs existent sous de nombreuses
variantes.
Plan théorique La programmation linéaire est dans P. Cela signifie qu’il existe des algo-
rithmes polynomiaux qui résolvent la programmation linéaire. L’algorithme des points
CHAPITRE 4. PROGRAMMATION LINÉAIRE 50

intérieurs est un de ceux-là. L’algorithme du simplexe, bien que très rapide en pratique,
ne possède pas pour le moment de version polynomiale : pour chacune de ses versions,
on connaı̂t des instances qui nécessitent un nombre exponentiel d’étapes.
Dans ce chapitre, nous donnons quelques propriétés théoriques de la programmation
linéaire (PL), qui ont un grand intérêt pratique (polyèdres, dualité,...). Les différents algo-
rithmes qui résolvent la programmation linéaire sont également présentés.

4.2 Quelques éléments théoriques

4.2.1 Forme standard


L’algorithme du simplexe et l’algorithme des points intérieurs utilisent une écriture du
programme linéaire différente de celle de l’équation (4.1). Ils utilisent la forme standard qui
consiste à écrire le programme linéaire de la façon suivante :

Min cT x
s.c. Ax = b (4.3)
x ≥ 0.

Comme d’habitude, x est le vecteur des variables, A est une matrice m × n donnée, c ∈ Rn ,
b ∈ Rm sont deux vecteurs donnés et 0 est le vecteur 0, avec n composantes.
En plus de la forme standard et de la forme inéquationnelle, il existe la forme canonique
qui consiste à écrire le programme linéaire de la façon suivante :

Min cT x
s.c. Ax ≤ b (4.4)
x ≥ 0.

Ces trois formes sont équivalentes : à partir d’une solution réalisable d’un programme
sous l’une des formes, on peut aisément construire une solution réalisable pour les deux
autres formes, donnant une même valeur pour la fonction objectif.

Passage de la forme standard à la forme canonique et réciproquement


 
A
Pour passer de la forme standard à la forme canonique, on pose A := 0
, b0 :=
  −A
b
, c0 := c. Le programme
−b
0
Min c T x
s.c. A0 x ≤ b0
x≥0
est alors clairement équivalent au programme (4.3).

Vous aimerez peut-être aussi