Programmation linéaire

La programmation linéaire (LP) est la minimisation ou la maximisation d'une fonction objectif soumise à des contraintes de limites, d'égalité linéaire et d'inégalité. Les exemples proposés adressent les problématiques de mélange de produits dans les industries de transformation, de la planification de la production dans le domaine manufacturier, d'appariement des flux de trésorerie dans le domaine financier et de la planification dans les domaines 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 :

\[\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}\]

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

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

Les algorithmes utilisés pour certains cas particuliers de programmes linéaires, 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. Parmi ces cas particuliers, on trouve :

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

Pour plus d'informations sur les algorithmes et la programmation linéaire, voir Optimization Toolbox™.