Introduction à la programmation linéaire

La programmation linéaire, également connue sous le nom d'optimisation linéaire, consiste à minimiser ou à maximiser une fonction objectif linéaire soumise à des contraintes de limite, d'égalité linéaire et d'inégalité linéaire. Les exemples traités adressent des problèmes tels que le mélange de produits dans les industries de transformation, la planification de la production dans les unités de fabrication, l'appariement des flux de trésorerie dans la finance et la planification dans le domaine de l'énergie et des transports.

La programmation linéaire est le problème mathématique consistant à trouver un vecteur \(x\) qui minimise la fonction :

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

soumise aux contraintes suivantes :

\[\begin{eqnarray}Ax \leq b & \quad & \text{(contrainte d'inégalité)} \\A_{eq}x = b_{eq} & \quad & \text{(contrainte d'égalité)} \\lb \leq x \leq ub & \quad & \text{(contrainte de limites}\end{eqnarray}\]

La programmation linéaire avec MATLAB

Vous pouvez utiliser MATLAB^® pour implémenter les algorithmes suivants, couramment utilisés pour résoudre les problèmes de programmation linéaire:

• Algorithme de points intérieurs : utilise un algorithme prédicteur-correcteur primal-dual et s'avère particulièrement utile pour les programmes linéaires à grande échelle qui possèdent une structure ou peuvent être définis avec des matrices creuses.
• Algorithme du simplexe : utilise une procédure systématique pour générer et tester des solutions sommets candidates d'un programme linéaire. L'algorithme du simplexe et l'algorithme du simplexe dual associé sont les algorithmes les plus utilisés pour l'optimisation linéaire.

Le solveur linprog dans l'application Optimization Toolbox™ implémente ces techniques d'optimisation linéaire.

Cas particuliers de programmation linéaire

Les algorithmes utilisés pour certains cas particuliers de problèmes d'optimisation linéaire où les contraintes possèdent une structure en réseau, sont généralement plus rapides que les algorithmes généralistes de points intérieurs et du simplexe. Exemples de cas particuliers :

• Le débit maximum d’un réseau : utilise des algorithmes augmenting-path et push-relabel.
• Le plus court chemin : utilise des algorithmes de Dijkstra, Bellman-Ford et de recherche.
• L’affectation linéaire : utilise un algorithme de correspondance bipartite.

Pour plus d'informations sur les algorithmes et l'optimisation linéaire, reportez-vous à Optimization Toolbox.