Généralités
Définition
La programmation linéaire est une méthode permettant d'optimiser (maximiser ou minimiser)
une fonction linéaire
sous certaines contraintes linéaires définies par des inégalités.
La fonction linéaire à optimiser s'appelle la fonction objectif ou
la fonction de coût ou la fonction économique.
Un problème linéaire est un problème pouvant être résolu par de la programmation linéaire.
Remarque
Dans la suite de ce chapitre, on émet une hypothèse de continuité : les solutions d'un
problème linéaire peuvent prendre n'importe quelles valeurs réelles.
Dans le chapitre suivant, on s'intéressera aux problèmes linéaires en nombres entiers.
Les contraintes peuvent être définies par des égalités et
des inégalités large de sens différent (\( \leqslant\) et \( \geqslant\) ).
Définition
Étant donné un problème linéaire, on dira qu'une solution est
admissible ou réalisable si les valeurs numériques associées
aux variables satisfont à l'ensemble des contraintes.
L'ensemble des solutions forme la région admissible également appelé le simplexe.
Une solution admissible sera dite optimale si elle optimise la fonction objectif.
Remarque
Étant donné un problème linéaire, plusieurs situations sont possibles :
- \( \bullet\)
- Il n'existe aucune solution.
\( \left\{
\begin{array}{rcl}
A&\geqslant&0\\
B&\geqslant&0\\
B&\geqslant&1\\
A+B&\leqslant&\dfrac{1}{2}\\
Max(A+2B)&&
\end{array}
\right.\)
- \( \bullet\)
- Il existe une unique solution.
\( \left\{
\begin{array}{rcl}
A&\geqslant&0\\
B&\geqslant&0\\
A+2B&\leqslant&4\\
2A+B&\leqslant&6\\
Max(A+B)&&
\end{array}
\right.
\)
- \( \bullet\)
- Il existe plusieurs solutions.
\( \left\{
\begin{array}{rcl}
A&\geqslant&0\\
B&\geqslant&0\\
A+2B&\leqslant&4\\
2A+B&\leqslant&6\\
Max(2A+B)&&
\end{array}
\right.\)
- \( \bullet\)
- Parmi les solutions, l'optimum n'est pas borné.
\( \left\{
\begin{array}{rcl}
A&\geqslant&0\\
B&\geqslant&0\\
A-B&\geqslant&1\\
A-B&\leqslant&-1\\
Max(A)&&
\end{array}
\right.\)
Le langage le mieux adapté pour la formulation des problèmes linéaires est celui des matrices.
Définition
Soient \( n\) et \( p\) deux entiers strictement positifs,
\( A\in\M_{(p,n)}(\R)\) , \( B\in \M_{(p,1)}(\R)\) , \( C\in\M_{(1,n)}(\R)\) et \( X={}^t(X_i)_{i\in[\![1 ; n]\!]}\)
le vecteur colonne des indéterminées.
Un problème de la forme%1
\( \left\{\begin{array}{c}
A.X\leqslant B\\
X\geqslant 0\\
Max(C.X)
\end{array}
\right.\)
est un problème linéaire sous forme normale.
Proposition
Tout problème linéaire est équivalent à un problème linéaire sous forme normale.
Démonstration
En conservant les notations de la définition précédente, les équivalents sont donnés par les règles suivantes :
- \( \bullet\)
- La recherche du \( \Min(C.X)\) équivaut à la recherche du \( \Max(C'.X)\) où \( C'=-C\) .
- \( \bullet\)
- Si la \( k^{\text{ième}}\) contrainte est de la forme \( \dpl{\sum_{i=1}^{n}A_{k,i}X_i\geqslant B_k}\)
alors cela équivaut à \( \dpl{\sum_{i=1}^{n}A'_{k,i}X_i\leqslant B'_k}\) où pour tout \( i\in[\![1 ; n]\!]\) ,
\( A'_{k,i}=-A_{k,i}\) et \( B'_k=-B_k\) .
- \( \bullet\)
- Si la \( k^{\text{ième}}\) contrainte est de la forme \( \dpl{\sum_{i=1}^{n}A_{k,i}X_i = B_k}\)
alors cela équivaut aux deux contraintes suivantes : \( \dpl{\sum_{i=1}^{n}A_{k,i}x_i \leqslant B_k}\)
et \( \dpl{\sum_{i=1}{n}A_{k,i}x_i \geqslant B_k}\) (et on transforme cette dernière par la technique précédente).
- \( \bullet\)
- Si \( X_k\leqslant 0\) , on pose \( X'_k=-X_k\) .
- \( \bullet\)
- Si \( X_k\) n'est pas distingué, on décompose cette variable en deux nouvelles variables
\( X_k=X_k^+-X_k^-\) où \( X_k^+\) et \( X_k^-\) sont tous deux positifs.
Théorème
Soient \( n\) et \( p\) deux entiers strictement positifs,
\( A\in\M_{(p,n)}(\R)\) , \( B\in \M_{(p,1)}(\R)\) , \( C\in\M_{(1,n)}(\R)\) , \( X={}^t(X_i)_{i\in[\![1 ; n]\!]}\)
le vecteur colonne des indéterminées et
\( \left\{\begin{array}{c}
A.X\leqslant B\\
X\geqslant 0\\
Max(C.X)
\end{array}
\right.\)
un problème linéaire sous forme normal.
Le simplexe forme un polyèdre convexe de \( \R^n\) . La(Les) solution(s) optimale(s), si elle(s) existe(nt),
se trouve(nt) toujours sur la frontière du simplexe, précisément sur un des sommets du simplexe.
1Les inégalités entre matrices se réalisent ligne par ligne.
