PROGRAMMATION LINEAIRE
(sujet des prochaines 5 semaines)

Maximiser (ou minimiser) une valeur qui dépend de plusieurs variables étant donné des contraintes sur ces variables

Quelques exemples:

Définition générale

Un ensemble de variables: x1, x2, ...  xn

Une fonction objective linéaire à maximiser (ou minimiser):
z =  Sommej=1n cjxj

Un ensemble de contraintes linéaires: l1 < = l2, l1 = l2, l1 > = l2 (chaque li étant une combinaison linéaire des variables comme z) il suffit de considérer des contraintes du premier type avec l2 une constante: Somme Ai,jxj   < =  bi

(Chaque i donne une contrainte; par convention 1  < = i  < = m
on écrit aussi maximiser cx avec Ax  < = b
chaque contrainte correspond à une ligne de la matrice A)

Forme canonique

Quelques définitions et cas spéciaux

Exemple de solution sans borne

-4x1+1x2  < = -10

1x1-2x2  < = -30
maximiser z=5x1-2x2

parmi les solutions sont: (10,20), (100,200), (1000,2000)... avec valeurs de z: 10, 100, 1000 et ainsi de suite.

Exemple de plusieurs solutions optimales

1x1+1x2  < = 10

2x1+3x2  < = 24

1x1+5x2  < = 18
maximiser z=3x1+3x2

parmi les solutions sont: (10,0), (8,2) avec valeur de z: 30.

S'il existe 2 solutions optimales, il en existe un nombre infini:
par exemple (9,1), (9.5,0.5)

Exemple sans aucune solution réalisable

1x1+1x2  < = 20

-1x1-3x2  < = -50

-1x1+1x2  < = 5

(En effet, on voit que la somme des deux dernières contraintes divisée par 2 est -x1-x2  < = -22.5 en contradiction avec la première.

Interprétation géométrique

Solutions de base

Une solution donnée par la solution de n des équations correspondant aux contraintes
(c'est-à-dire les équations obtenues en remplacant < = par =)
(à noter que si les n équations ne sont pas indépendantes la solution n'existe pas et elles ne donnent pas de solution de base)

Un sommet du polytope

théorème : si la fonction objective est bornée, elle prend sa valeur optimale à une solution de base

Donc un algorithme possible:
calculer chaque solution de base;
vérifier qu'elle est réalisable;
si oui calculer la fonction objective;
prendre le maximum des valeurs calculées.

Mais  ca serait très très lent ...

Limitations sur ce qu'on peut exprimer en PL
(forme standard et canonique):

Il existe des types de contraintes réelles qu'on ne peut pas exprimer (directement) par des contraintes linéaires.

Les problèmes qui ne sont pas en forme standard canonique (variables négatives, contraintes > = ou =) sont facilement réformulés.




File translated from TEX by TTH, version 3.05.
On 16 Oct 2006, 10:18.