next up previous
Next: About this document ...

INTRODUCTION

Matières: techniques mathématiques de décision;

PROGRAMMATION LINEAIRE
(sujet des prochaines 3-4 semaines)

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

Quelques exemples:

Définition générale

Un ensemble de variables: $x_1,~x_2,~\cdots ~x_n$

Une fonction objective linéaire à maximiser (ou minimiser):

\begin{displaymath}z~=~ \sum_{j=1}^n c_jx_j\end{displaymath}

Un ensemble de contraintes linéaires: $l_1 \leq l_2$, l1 = l2, $l_1 \geq l_2$ (chaque li de la forme de z) il suffit de considérer $\sum A_{i,j}x_j ~\le~ b_i$

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

Forme canonique

Quelques définitions

Interprétation géométrique

Solutions de base

Une solution où n des équations correspondant aux contraintes sont satisfaites
(c'est-à-dire les équations obtenues en remplacant $\le$ par =)

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:

Des contraintes réelles qu'on ne peut pas exprimer (directement) par des contraintes linéaires.




next up previous
Next: About this document ...
Mike ROBSON
2000-10-04