Module D108 : Programmation mathématique et optimisation
Programmation Linéaire

Programmation linéaire
Exemple
Forme canonique
Cas spéciaux
Exercices


Auteur(s) : Mike Robson - IUP Miage Bordeaux
Date de dernière modification : 30 Janvier 2006

Programmation linéaire

La programmation linéaire est un cas simple mais important du problème général d'optimisation mathématique de trouver la valeur optimale (maximum ou minimum selon le cas) d'une fonction mathématique étant donné un nombre de restrictions (contraintes) sur les valeurs des paramètres. En général, les problèmes de ce type peuvent être très compliqués à résoudre mais dans le cas de la programmation linéaire des algorithmes efficaces sont connus mais un nombre énorme de problèmes réels et importants peuvent être exprimés par des programmes linéaires.

Définition: un programme linéaire sur $ n$ variables (par convention nous écrivons les variables $ x_1,\dots x_n$) est d'optimiser (minimiser ou maximiser) une fonction linéaire dans les variables étant donné des contraintes linéaires dans les variables.

[Une fonction linéaire est une fonction qui peut être exprimée comme $ \sum_{i=1}^n c_ix_i+c_0$; on ignore le $ c_0$ de la fonction à optimiser (la fonction objective ou économique) parce qu'elle ne change en rien la question. Une contrainte linéaire est qu'une fonction linéaire doit être supérieure ou égale à une autre; par une simple manipulation algébrique on peut toujours supposer que la première a le terme constante 0 et la deuxième est une fonction triviale constante On obtient donc une condition de la forme de: $ \sum_{i=1} a_ix_i\le b$.]

Exemple

Une usine de verre peut produire de la verre de qualité basse, moyenne ou supérieure; une tonne de la basse qualité nécessite 3 tonnes de sables, 500gms d'additifs et 1 heure du travail d'un ouvrier; pour les deux autres qualités, les chiffres correspondants sont (moyenne) 3.2 tonnes, 1000gms et 1,5 heures; (supérieure) 3.5 tonnes, 2500 gms et 4 heures. Les bénéfices de la vente d'une tonne sont de 100, 200 et 300 Euros. Chaque semaine 200 tonnes de sable et 120000 gms d'additif sont disponibles et il y a 6 ouvriers chacun travaillant au maximum 35 heures/semaine. Quelles quantités doit-on produire chaque semaine pour maximiser les bénéfices?

On écrit $ x_1,  x_2,  x_3$ pour les quantités produites de chaque qualité.
On veut maximiser $ 100x_1+200x_2+300x_3$ avec les contraintes:

\begin{displaymath}\left\lbrace
\begin{array}{l}
\par
3x_1+3.2x_2+3.5x_3 \le 20...
....5x_2+4x_3 \le 210  (main  d'oeuvre).
\par
\end{array}\right. \end{displaymath}

Forme canonique

Un programme linéaire en forme canonique est à maximiser une fonction $ \sum_{i=1}^n c_ix_i$ avec $ m$ contraintes dont la i-ème est: $ \sum_{j=1} a_{i,j}x_j\le b_i$ et aussi les contraintes implicites que chaque $ x_i\ge 0$.

Il est claire que tout programme linéaire peut être transformé en un programme équivalent en forme canonique; un tel programme est résumé par la matrice $ A$ des $ a_{i,j}$ et les deux vecteurs $ b$ et $ c$.

On appelle solution du programme n'importe quel vecteur de valeurs $ x_i$; les solutions qui respectent toutes les contraintes sont les solutions réalisables; un programme qui admet au moins une solution réalisable est un programme faisable. Pour un programme faisable, on appelle solution optimale une solution réalisable où la fonction objective prend sa valeur maximale parmi toutes les solutions réalisables. (On dit aussi de façon inexacte que cette valeur maximale est la ``solution optimale''.)

Cas Spéciaux

Il y a des cas où la recherche de ``la solution optimale'' ne peut pas réussir; il est important de savoir quels sont ces cas parce qu'un programme doit pouvoir les traiter:

Exemples


 

Exercices

Questions de compréhension directe

3 exercices