next up previous
Next: About this document ...

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: \bgroup\color{blue}$x_1,~x_2,~\cdots ~x_n$\egroup

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

\begin{displaymath}\bgroup\color{blue}{\color {blue}z~=~ \sum_{j=1}^n c_jx_j}\egroup\end{displaymath}

Un ensemble de contraintes linéaires: \bgroup\color{blue}$\color {blue}l_1 \leq l_2$\egroup, \bgroup\color{blue}$\color {blue}l_1 = l_2$\egroup, \bgroup\color{blue}$\color {blue}l_1 \geq l_2$\egroup (chaque \bgroup\color{blue}$\color {blue}l_i$\egroup de la forme de \bgroup\color{blue}$\color {blue}z$\egroup) il suffit de considérer des contraintes du premier type avec \bgroup\color{blue}$\color {blue}l_2$\egroup une constante: \bgroup\color{blue}$\color {blue}\sum A_{i,j}x_j ~\le~ b_i$\egroup

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

Forme canonique

Quelques définitions et cas spéciaux

Exemple de solution sans borne

\begin{displaymath}\bgroup\color{blue}\color {magenta}-4x_1+1x_2~\le~-10\egroup\end{displaymath}


\begin{displaymath}\bgroup\color{blue}\color {magenta}1x_1-2x_2~\le~-30\egroup\end{displaymath}

maximiser \bgroup\color{blue}$\color {blue}z=5x_1-2x_2$\egroup

parmi les solutions sont: \bgroup\color{blue}$\color {blue}(10,20),~(100,200),$\egroup \bgroup\color{blue}$\color {blue}(1000,2000)\cdots$\egroup avec valeurs de \bgroup\color{blue}$\color {blue}z$\egroup: \bgroup\color{blue}$\color {blue}10,~100,~1000$\egroup et ainsi de suite.

Exemple de plusieurs solutions optimales

\begin{displaymath}\bgroup\color{blue}\color {magenta}1x_1+1x_2~\le~10\egroup\end{displaymath}


\begin{displaymath}\bgroup\color{blue}\color {magenta}2x_1+3x_2~\le~24\egroup\end{displaymath}


\begin{displaymath}\bgroup\color{blue}\color {magenta}1x_1+5x_2~\le~18\egroup\end{displaymath}

maximiser \bgroup\color{blue}$\color {blue}z=3x_1+3x_2$\egroup

parmi les solutions sont: \bgroup\color{blue}$\color {blue}(10,0),~(8,2)$\egroup avec valeur de \bgroup\color{blue}$\color {blue}z$\egroup: \bgroup\color{blue}$\color {blue}30$\egroup.

S'il existe \bgroup\color{blue}$2$\egroup solutions optimales, il en existe un nombre infini:
par exemple \bgroup\color{blue}$\color {blue}(9,1),~(9.5,0.5)$\egroup

Exemple sans aucune solution réalisable

\begin{displaymath}\bgroup\color{blue}\color {magenta}1x_1+1x_2~\le~20\egroup\end{displaymath}


\begin{displaymath}\bgroup\color{blue}\color {magenta}-1x_1-3x_2~\le~-50\egroup\end{displaymath}


\begin{displaymath}\bgroup\color{blue}\color {magenta}-1x_1+1x_2~\le~5\egroup\end{displaymath}

(En effet, on voit que la somme des deux dernières contraintes divisée par \bgroup\color{blue}$\color {blue}2$\egroup est \bgroup\color{blue}$\color {blue}-x_1-x_2~\le~-22.5$\egroup en contradiction avec la première.

Interprétation géométrique

Solutions de base

Une solution donnée par la solution de \bgroup\color{blue}$\color {blue}n$\egroup des équations correspondant aux contraintes
(c'est-à-dire les équations obtenues en remplacant \bgroup\color{blue}$\color {blue}\le$\egroup par \bgroup\color{blue}$\color {blue}=$\egroup)
(à noter que si les \bgroup\color{blue}$\color {blue}n$\egroup é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:

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
2001-10-04